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

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

Нехай необхідно знати

(1)

при умовах

(2)

(3)

Допустимо, що система (2) при умовах (3) сумісна та її многокутник розв’язків обмежений.

Із геометричної інтерпретації задачі лінійного програмування (1)-(3) мамо що кожне і -те обмеження-нерівність (2) геометрично визначає півплощину з граничною прямою
(і = 1, 2, …, т). Система обмежень (2) у цілому — це спільна частина, перетин усіх зазначених півплощин, тобто множина точок, координати яких задовольняють всі обмеження задачі. Таку сукупність точок називають многокутником розв’язків, або областю допустимих планів задачі лінійного програмування.

Умова невід’ємності невідомих (3) визначає, що область допустимих розв’язків задачі міститься в першому квадранті системи координат двовимірного простору. Цільова функція задачі лінійного програмування геометрично інтерпретується як сім’я паралельних прямих с ₁ х ₁ + с ₂ х ₂ = const.

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

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

Підсумуємо викладене. Розв’язати задачу лінійного програмування графічно означає, що необхідно знайти таку вершину многокутника розв’язків, при підстановці координат якої в (1) лінійна цільова функція набуває найбільшого (найменшого) значення.

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

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

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

3. Визначення многокутника розв’язків задачі лінійного програмування.

4. Побудова вектора , що показує напрям збільшення значень цільової функції задачі.

5. Побудова прямої с ₁ х ₁ + с ₂ х ₂ = const, перпендикулярної до вектора .

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

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

Геометричну інтерпретацію ЗЛП розглянемо на такому прикладі. Нехай фермер прийняв рішення вирощувати озиму пшеницю і цукровий буряк. Під ці дві культури він виділив 20 гектарів ріллі, причому під цукровий буряк можна заняти не менше 5 га ріллі. У наступній таблиці маємо техніко-економічні показники вирощування цих культур:

№ п/п	Техніко-економічний показник	Вид діяльності	Наявний ресурс
Озима пшениця	Цукровий буряк
1.	Жива праця, людино-днів/га
2.	Механізована праця, людино-днів/га
3.	Вихід товарної продукції, тон/га	3,5
4.	Прибуток, тис. грн./га	0,7

Критерієм оптимальності є максимізація прибутку.

Запишемо економіко-математичну модель структури виробництва озимої пшениці та цукрового буряку. Нехай:

х ₁ — шукана площа посіву озимої пшениці;

х ₂— шукана площа посіву цукрового буряку.

Маємо:

(1^*)

при умовах

(2^*)

, (3^*)

Ця задача у геометричному вигляді представлена на рис. 1.

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

Область допустимих розв’язків отримали таким чином. Кожне обмеження, наприклад, х ₁ + х ₂ ≤ 20, представляє собою півплощину з граничною прямою х ₁ + х ₂ = 20. Будуємо цю пряму і визначаємо півплощину яка описується цією нерівністю х ₁ + х ₂ ≤ 20. З цією метою у нерівність х ₁ + х ₂ ≤ 20 підставляємо координати якоїсь характерної точки, наприклад, х ₁ = 0 і х ₂ = 0. Переконуємося, що ця точка належить півплощині х ₁ + х ₂ ≤ 20. Цей факт на рис. 1. показуємо стрілкою. Відповідно будуємо півплощини, які відповідають нерівностям (2^*). Півплощини пересікаємо та отримуємо область допустимих розв’язків задачі (на рис.1 многокутник ABCD). Цільова функція є сімейством паралельних прямих Z = 0, то маємо 0,7 х ₁ + х ₂ = 0. Ця пряма проходить через початок системи координат. Якщо Z = 35, то отримуємо пряму 0,7 х ₁ + х ₂ = 3,5.

Загальна задача лінійного програмування (1)-(3) геометрично інтерпретується таким чином: кожне і -те обмеження — рівняння

у п -мірному просторі основних змінних х ₁, х ₂, …, х_п є гіперплощиною. Кожне обмеження — нерівність (2) і (3) є гіперплощиною і напівпростором, який належить по одну сторону цієї гіперплощини. Пересічення всіх цих напівпросторів, які визначаються обмеженнями задачі (2) і (3), дають випуклий многогранник допустимих розв’язків цієї задачі.

Цільову функцію

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

Задача 1.

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

1.1. ; 1.2. ;