2. Графічний метод

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

Розглянемо клас задач лінійного програмування, які можна розв’язати на площині графічно. Нехай треба знайти мінімум або максимум лінійної функції F=c₁x₁+c₂x₂ (1.4) за умов

a ₁₁x₁+a₁₂x₂b₁

a₂₁x₁+a₂₂x₂b₂ (1.5)

. . . . . . . .

a_m1x₁+a_m2x₂b_m

x₁0,x₂0 (1.6)

Щоб знайти розв’язок задачі (1.4)-(1.6), треба спочатку знайти множину точок, які задовольняють умови (1.5)-(1.6) . Для цього в площині х₁Ох₂ проведемо прямі (див. рис. 1)

a₁₁x₁+a₁₂x₂=b₁

a₂₁x₁+a₂₂x₂=b₂

. . . . . . . .

a_m1x₁+a_m2x₂=b_m

x₁0,x₂0

Кожна пряма a_i1x₁+a_i2x₂=b_i поділяє площину на дві півплощини. Точки однієї з цих півплощин задовольняють нерівність a_i1x₁+a_i2x₂b_i, іншої – ні. Щоб дізнатися, точки якої півплощини задовольняють нерівність, треба в цю нерівність підставити координати точки О (початку координат), тобто х₁=0, х₂=0. Якщо координати цієї точки задовольняють нерівність, то нерівність будуть задовольняти всі точки півплощини, яка містить початок координат. Якщо координати цієї точки не задовольняють нерівність, то нерівність будуть задовольняти всі точки півплощини, яка не містить початку координат.

Перетином (спільною частиною) півплощин є деяка опукла многокутна область К, множиною точок якої є множина розв’язків системи (1.5). Нехай К не є порожньою множиною.

Рис. 1.

Множина точок, які задовольняють умову (1.6), утворює першу чверть площини х₁0х₂. Тому множиною точок, які задовольняють умови (1.5),(1.6.), є та частина області К, яка лежить у першій чверті площини. Позначимо цю множину через М. Очевидно, М може бути порожньою множиною, опуклим многокутником або необмеженою опуклою многокутною областю. В першому випадку умови задачі є суперечливі, задача не має розв’язку; в другому - завжди існують точки, в яких функція набуває мінімального і максимального значень; у третьому - лінійна функція на множині М є необмеженою або зверху, або знизу, або зверху і знизу, тому відповідно ця функція може не досягати або максимуму, або мінімуму, або максимуму й мінімуму.

Геометричне місце точок, в яких лінійна функція (1.4) набуває фіксованого значення с, є прямою лінією, перпендикулярною до вектора N=(c₁,c₂), і визначається рівнянням c₁x₁+c₂x₂=c. Надавши параметру с всіх можливих значень від - до + , одержимо сімейство паралельних прямих, які займуть всю площину. Перехід від однієї прямої сімейства до іншої у напрямку вектора N веде до збільшення значення лінійної функції, у протилежному напрямку - до його зменшення.

Якщо М - опуклий многокутник, то оптимальне значення лінійної функції завжди досягається у його вершині. Якщо оптимальне значення досягається в двох вершинах, то F набуває його в будь-якій точці, що лежить на відрізку, який з’єднує їх. Координати потрібної вершини - це координати точки перетину відповідних прямих.

Якщо область М необмежена, то мінімум чи максимум лінійної функції може не досягатись, тобто при зміщенні прямої у тому чи іншому напрямку весь час будуть траплятися точки області М.

П ри знаходженні розв'язку задачі за допомогою графіч­ного методу можливі випадки:

В

С

В

А

N N

0 0 А

Рис.2 Рис.3

F_max=+∞

N N

0 0

Рис.4 Рис.5

Рисунок 1 xарактеризує випадок, коли цільова функція приймає максимальне значення у єдиній точці В.

Рисунок 2 - максимальне значення функція приймає в кожній точці відрізку ВС.

Рисунок 3 - цільова функція не обмежена зверху на множині допустимих розв'язків.

Рисунок 4 - система обмежень несумісна.

Етапи розв'язування ЗЛП на основі її геометричної інтерпретації:

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

2. Знаходять півплощини, що визначаються кожним обме­женням задачі.

3. Знаходять многокутник розв'язків.

4. Будують вектор

5. Будують пряму C₁X₁+C₂X₂=h, що проходить через много­кутник розв'язків.

6. Пересуваючи пряму C₁X₁+C₂X₂=h у напрямку вектора або знаходять точку /точки/, в якій цільова функція приймає максимальне /мінімальне/ значення, або встановлюють необмеженість зверху /знизу/ функції на множині планів.

7. Визначають координати точки максимуму /мінімуму/ функ­ції та обчислюють значення цільової функції в цій точці.

Наприклад Графічним способом знайти максимум і мінімум лінійної функції: F=-3x₁+4x₂ , за умов

-3x₁+4x₂ 12,

-2x₁+ x₂ 2,

4x₁+3x₂ 24;

x₁,x₂0

l₃

l₂ l₁

C

B

N A

0 D

Рис. 6

На площині (Рис. 6) побудуємо прямі лінії -3х₁+4х₂=12, -2х₁+х₂=2, 4х₁+3х₂=24, відкладемо вектор N=(-3,4) і знайдемо область М . Областю М буде п’ятикутник ОАВСD. Перетнемо область М прямою f, перпендикулярною до вектора N . Якщо пряму f зміщувати паралельно самій собі в напрямку вектора N доти, поки вона не стане опорною до М , то бачимо, що F досягає максимуму на відрізку ВС. Якщо пряму f зміщувати в протилежному напрямку доти, поки вона не стане опорною до М, то бачимо, що F досягає мінімуму в точці D. Для знаходження максимального значення функції достатньо знайти координати однієї з вершин В чи C. Для знаходження координат точки В необхідно розв’язати систему лінійних рівнянь: В=l₁∩l₂,

-3x₁+4x₂=12 -3x₁+4x₂=12 -3x₁+4x₂=12 x₂=18/5

-2x₁+x₂=2  8x₁ -4x₂= -8  5x₁=4  x₁=4/5

Отже F_max=-3 4/5 +4 18/5=12. Координати точки D: х₁=6, х₂=0.Підставивши ці значення в лінійну функцію, отримаємо, F_min=-18.