Алгоритм графічного методу розв’язання злп

1. Побудувати прямі лінії, рівняння яких отримуємо заміною в системі обмежень (1.1.2) знаків нерівностей на знаки рівностей.

2. Визначити півплощини, що відповідають кожному обмеженню задачі.

3. Знайти багатокутник розв’язків ЗЛП, враховуючи, що .

4. Побудувати вектор напрямів = (с₁,с₂), який вказує напрям зростання цільової функції ЗЛП (1.1.1).

5. Побудувати пряму, яка проходить через область допустимих розв’язків, перпендикулярно до вектора : . Це лінія рівня.

6. Перемістити пряму у напрямі вектора у разі максимізації цільової функції; або в протилежному напрямі у разі мінімізації цільової функції, знайти вершину багатокутника розв’язків ЗЛП, в якій цільова функція досягає екстремального значення.

7. Визначити координати точки, в якій цільова функція досягає оптимальне значення, і обчислити екстремальне значення цільової функції в цій точці.

Реалізацію графічного методу розв’язання ЗЛП розглянемо на прикладах.

Приклад 1.2.1. Розв’язати ЗЛП графічним методом:

(1.2.1)

max z = x₁ + 4x₂ (1.2.2)

Розв’язання.

Для побудови області допустимих розв’язків, яка складається з перетину півплощин, що відповідають кожній нерівності системи обмежень (1.2.1), запишемо рівняння граничних прямих:

l₁: x₁ + 5x₂ = 5; l₂: x₁ + x₂ = 6; l₃: 7x₁ + x₂ = 7.

Зауваження. Для зручності побудови прямої лінії, її рівняння можна привести до вигляду у відрізках на осях

, (1.2.3)

де параметри а, b – довжини відрізків, що відсікає пряма на відповідних осях Ох₁, Ох₂.

Зауваження. Якщо рівняння прямої лінії має вигляд: Аx₁ + Вx₂ = 0, то вона проходить через точку з координатами (0;0). Для її побудови слід виразити x₂ через x₁, і знайти ще одну точку.

Для приведення рівняння прямої l₁ до вигляду (1.2.3.) розділимо обидві його частини на 5: . Таким чином, пряма l₁ відсікає на осі Ох₁ 5 одиниць, на осі Ох₂ – 1 одиницю. Аналогічно маємо для l₂: і l₃: .

Для визначення півплощин, які відповідають обмеженням системи (1.2.1), в обмеження потрібно підставити координати якої-небудь точки, що не лежить на граничній прямій. Якщо отримаємо вірну нерівність, то всі точки з півплощини, в якій розташована вибрана точка, є розв’язками даної нерівності. Інакше вибирають іншу півплощину.

Зауваження. В якості точки порівняння доцільно вибирати, якщо це можливо, точку О(0,0).

Таким чином, перша і друга шукані півплощини розташовані в протилежний бік від початку координат (0 – 5·0 – 5; 7·0 + 0 7), а друга – у бік початку координат (0 + 0 6). Область допустимих розв’язків на рисунку 1.1 заштриховано.

Зауваження. Через обмеження х₁ 0, х₂ 0, область допустимих розв’язків ЗЛП завжди лежить в першій чверті координатної площини.

Рисунок 1.1 – Область допустимих розв’язків

Для знаходження оптимального плану, який знаходитиметься у вершині багатокутника розв’язків, потрібно побудувати вектор напрямів = (с₁,с₂), який вказує напрям зростання цільовій функції z = с₁х₁ + с₂х₂.

У даній задачі вектор напрямів = (1, 4): він починається в точці О(0,0) і закінчується в точці N(1, 4).

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

Таким чином, точкою максимуму цільової функції z є точка А перетини прямих l₂ і l₃.

Для обчислення оптимального значення цільової функції z знайдемо координати точки А – це точка перетину прямих l₂ і l₃, вирішимо систему рівнянь:

Таким чином, точка А має координати x₁ =1/6, x₂ = 35/6.

Для обчислення оптимального значення цільової функції потрібно підставити в неї координати точки А.

Підставивши координати точки А в цільову функцію (1.2.2), отримаємо

max z = 1/6 + 4·(35/6)= 47/2.

Приклад 1.2.2. Побудувати на площині область допустимих розв’язків системи лінійних нерівностей (1.2.4) і знайти найбільше і найменше значення цільової функції (1.2.5):

(1.2.4)

z = –2x₁ – x₂ (1.2.5)

Розв’язання.

Для побудови області допустимих розв’язків, яка складається з перетину півплощин, що відповідають кожній нерівності системи обмежень (1.2.4), запишемо рівняння граничних прямих:

l₁: 4x₁ – x₂ = 0; l₂: x₁ + 3x₂ = 6; l₃: x₁ – 3x₂ = 6; l₄: x₂ = 1.

Пряма l₁ проходить через точку з координатами (0;0). Для її побудови виразимо x₂ через x₁: x₂ = 4x₁. Знайдемо ще одну точку, через яку проходить пряма l₁, наприклад (1;4). Через точку з координатами (0;0) і точку з координатами (1;4) проведемо пряму l₁ .

Для приведення рівняння прямої l₂ до вигляду у відрізках на осях (1.2.3.) розділимо обидві його частини на 6: . Таким чином, пряма l₂ відсікає на осі Ох₁ 6 одиниць, на осі Ох₂ 2 одиниці. Аналогічно маємо для l₃: . Пряма l₄ паралельна осі Ох₁ і проходить через точку з координатами (0;1) .

Для визначення півплощин, які відповідають обмеженням системи (1.2.4) в обмеження потрібно підставити координати якої-небудь точки, що не лежить на граничній прямій. Через обмеження х₁  0, х₂  0 область допустимих розв’язків ЗЛП лежить в першій чверті координатної площини.

Область допустимых розв’язків на рисунку 1.2 заштриховано.

Рисунок 1.2 – Область допустимих розв’язків

Побудуємо вектор напрямів = (–2,–1). Далі будуємо лінію рівня, перпендикулярно до вектора .

Для знаходження найбільшого значення цільової функції пересуваємо лінію рівня у напрямі вектора до останнього перетину з областю допустимих розв’язків. Таким чином, точкою максимуму цільової функції z є точка А перетину прямих l₁ і l_2.

Для обчислення оптимального значення цільової функції z знайдемо координати точки А. Оскільки точка А – це точка перетину прямих l₁ і l₂, то її координати задовольняють системі рівнянь, що складена з рівнянь відповідних граничних прямих, які перетинаються в оптимальній вершині:

Таким чином, точка А має координати x₁ =6/13, x₂ = 24/13.

Підставивши координати точки А в цільову функцію (1.2.4), отримаємо оптимальне значення цільової функції

max z = – 2·(6/13) – (24/13) = – 36/13.

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

В результаті розв’язання ЗЛП можливі наступні випадки:

Цільова функція досягає оптимального значення в єдиній вершині багатокутника розв’язків;

Цільова функція досягає оптимального значення в будь-якій точці ребра багатокутника розв’язків (ЗЛП має альтернативні опорні плани);

ЗЛП не має оптимальних планів;

ЗЛП має оптимальний план у разі необмеженої багатокутника розв’язків.