Задача 5. Фірма спеціалізується на виробництві офісних меблів, зокрема вона випускає дві моделі збірних книжкових полиць А та В

Теоретичні питання:

6. Основні етапи геометричного методу розв’язування ЗЛП.

7. Геометрична інтерпретація ЗЛП.

Деякі задачі лінійного програмування (ЗЛП) можна розв'язу­вати графічно. Використовують графічний метод розв'язування ЗЛП для обмеженого типу задач, а саме - з двома (трьома) змін­ними.

Визначити найменше або найбільше значення функції
г = с₀+с ₁ x₁₊ с₂х₂ -» max (min) (1)

при таких обмеженнях:

(2)

Розв'язок знаходять у такій послідовності:

1) будують многокутник розв'язків, системи нерівностей
(2), який є перетином півплощин, що описуються окремо кож­
ною нерівністю цієї системи;

2) знаходять оптимальну точку, яка за основною властивістю
задач ЛП, розміщена у вершині многокутника розв'язків нерівнос­тей (2). Для знаходження оптимальної точки використовують вектор нормалі

, побудований за цільовою функцією. Він перпендикулярний до лінії рівня, яка задана рівнянням c₀+ c ₁x₁ +c₂x₂=const. Нагадаємо, що лінією рівня функції z=z{x_1.x₂) називають пряму z=z(x_{ х₂) = c = const. Якщо z = z(x₁, x₂) - лінійна функція х_1,х₂, то лінія рівня є пряма і для різних значень сталої с такі лінії є паралельні. Якщо z(x_1, x₂) = 0 - лінія на площині, то вектор - перпендикулярний до цієї лінії в кожній її точці.

При паралельному перенесенні лінії рівня у напрямку векто­ра нормалі N значення цільової форми зростає. Знаходимо верши­ну многокутника, в якій досягається найбільше значення функції z. Для знаходження точки мінімуму лінії рівня потрібно переміщува­ти у напрямку, протилежному до N.

Лінії рівня, що проходять через оптимальні вершини много­кутників розв'язків, називають опорними (оптимальними).

За допомогою нормалі N на одному рисунку можна одноча­сно знайти точки тіп і тах, тобто розв'язати одночасно дві задачі;

3.Обчислюють оптимальні значення. Для цього знаходять координати вершин тіп і тах як спільний розв'язок рівнянь відпо­відних граничних прямих, що перетинаються в оптимальних вер­шинах. Знайдені координати підставляють у формулу (1) й об­числюють Z_тіп і Z_тах.

Приклад.

Знайти найбільше і найменше значення функції z = -10+ Зх₁+2х₂ при обмеженнях

Розв'язування.

І.Будуємо многокутник розв'язків, який складається з пере­тину чотирьох півплощин розв'язків. Проводимо на рис. 1 граничні прямі усіх чотирьох півплощин розв'язків. Граничні прямі півплощини розв'язків пройдуть через точки:

I. 2х₁+3х₂=18, -А₁( 0;6), А₂(9;0)

II. 2х₁+х₂=10, - В₂( 0;10), В₂(5;0)

III. x₁=0,- пряма паралельна осі Ох₁;

IV. х₂=0,- пряма паралельна осі Ох₂.

Щоб визначити, з якого боку від граничної прямої лежить півплощина розв'язків, достатньо узяти будь-яку точку поза пря­мою І і підставити її координати у нерівність Якщо нерівність за­довольняється, то півплощина розв'язків розміщена з боку обраної точки, якщо ні - то з протилежного. За точку порівняння доцільно, якщо це можливо, брати початок системи координат. Так, розв'яз­ки першої і другої півплощин розміщені з того ж боку, що й поча­ток координат, а розв'язок третьої - з протилежного. Многокутник розв'язків на рис. 1. заштриховано.

2 Знаходимо оптимальну точку. Будуємо вектор нормалі, початок якого лежить у точці (0; 0), кінець - у точці (3;2). Пересу­ваючи лінію рівня (-10+ Зхі+2х₂=0) у напрямку N, знаходимо, що z _тіп досягається в точці 0, z _тах - у точці В₂.

3 Обчислюємо оптимальні значення. Точка С - точка перети­ну граничних прямих І і II:

Із рис. 1 видно, що Хі=4, х₂=3, С(4;3);

Z _тах=2(С)=- 10+3-4+2-3=8. Точка 0 є точкою перетину граничних прямих III і IV

х₁= 0, х₂ - 0, С(0;0);

Z_тіп=z(0) = -10+3-0+2-0 = -10.

Відповідь: Z _тах =8, Z_тіп = -10.

Розв’язати графічно ЗЛП:

1. 2.

Відповідь: Відповідь:

3. 4.

Відповідь: Відповідь

Тема: «Симплекс – метод. Побудова подвійних (спряжених) задач»

Теоретичні питання:

1. Симплексний метод розв’язування ЗЛП.

2. Вихідна математична модель ЗЛП для симплекс – методу.

3. Опорний план ЗЛП для її розв’язування симплекс-методом.

4. Обґрунтування (основні теореми) симплекс-метода для невироджених задач.

5. Визначення оптимального плану ЗЛП в алгоритмі симплекс-методу.

6. Визначення необмеженості функції мети в алгоритмі симплекс-методу.

7. Метод штучної бази. М – задача.