2. Геометричний (графічний) метод рішення злп

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

Постановка задачі. Знайти оптимум лінійної форми

(17)

при наступних обмеженнях

(18)

(19)

Областю припустимих розв’язків задачі (17)-(19) можуть бути замкнуті опуклі багатогранні тіла, розімкнуті опуклі багатогранні тіла або єдина крапка. Система нерівностей (18)-(19) моделює на площині зазначені області.

Функція (17) моделює на площині х₁ох₂ сімейство прямих, які називаються лініями рівня. Кожна з таких ліній відповідає за цілком певні значення функції цілі:

Серед ліній рівня виділяють одну, котра називається лінією нульового рівня, її рівняння має вигляд:

або

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

Розглянемо вектор-градієнт цільової функції

або

Цей вектор указує напрямок найшвидшого зростання цільової функції. Відмітимо, що вектор-градієнт у кожній точці координатної площини х₁ох₂ перпендикулярний лінії рівня функції F, що проходить через цю точку.

2.1. Алгоритм рішення злп графічним методом

Розв’язок ЗЛП графічним методом складається з наступних етапів:

1) У площині х₁ох₂ будуємо область припустимих планів даної ЗЛП – область ;

F=0

Мал. 4

2) Знаходимо вектор-градієнт ;

3) Будуємо лінію нульового рівня ;

4) Лінію нульового рівня переміщаємо уздовж градієнтного напрямку (див. мал. 4) і визначаємо ту вершину опуклого багатогранника, що вперше стикається з лінією рівня. Ця вершина й буде відповідати оптимуму цільової функції типу мінімум

Потім лінію рівня переміщаємо вглиб ОДЗ (див. мал. 4) і відшукуємо ту вершину багатогранника після якої лінія рівня буде залишати зазначену область. Ця вершина й буде відповідати оптимуму цільової функції типу максимум

.

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

Приклад. Деяке підприємство освоїло виробництво продукції двох видів А і В, використовуючи при цьому сировину чотирьох типів S₁, S₂, S₃, S₄. Запаси сировини й норма її витрат на виробництво одиниці продукції зазначені в таблиці. Відомо, що прибуток підприємства від реалізації одиниці продукції виду А становить 7 у.о., а від реалізації одиниці товару типу В - 5 у.о. Визначити такий план випуску продукції, який би дозволив підприємству отримати максимальний прибуток.

Вид продук- Вид ції сировини	А	В	Запаси сировини
S1	2	3	19
S2	2	1	13
S3	1	0	6
S4	0	1	5
Прибуток	7	5

Сформулюємо задачу математично. Через х₁ позначимо кількість виробів виду А, а через х₂ – кількість виробів виду В, які необхідно виготовити за планом. Умова функції – прибуток підприємства від реалізації виробленої продукції.

(1)

(2)

(3)

(4)

Дотримуючись послідовності дій при використанні графічного методу розв’язку, будуємо область припустимих планів  (використовуючи систему обмежень ЗЛП і умови невід’ємності, вектор-градієнт цільової функції , лінію нульового рівня 7х₁ + 5х₂ = 0).

Мал. 5.

Переміщаючи лінію нульового рівня уздовж градієнтного напрямку, знаходимо, що

Визначимо координати вершини Р₄.

Визначник системи

Тому що , те система сумісна по теоремі Крамера і має єдиний розв’язок

Обчислимо допоміжні визначники

Тоді, по формулах Крамера знаходимо

Таким чином, Р₄(5; 3). Знаючи координати точки Р₄, визначимо максимальне значення цільової функції

Виходить, що для одержання максимального прибутку в розмірі 50 у.о. підприємству при заданих обмеженнях на запаси сировини варто робити п'ять виробів типу А и три вироби типу В.