Геометрична інтерпретація задачі лінійного програмування

Розгляне& 737f54h #1084;о на площині х₁Оx₂ сумісну систему лінійних нерівностей:

(2.9)

a_i x a_i x b_i (i = 1, 2, ,т). Умови невід’ємності

a_i x a_i x a_i x b_i (i  _j j j

_n; тоді кожна нерівність визначає півпростір n-вимірного простору з граничною гіперплощиною а_i x a_i x a_i x a_inx_n b_i (i = 1, 2, ,т). Кожному обмеженню виду (2.9) відповідають гіперплощина та напівпростір, який лежить з одного боку цієї гіперплощини, а умови невід’ємності — півпрос­тори з граничними гіперплощинами х_j j = 1, 2, 3, , n).

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

кож ної з яких визначається значенням параметра Z.

Розгляне& 737f54h #1084;о геометричну інтерпретацію задачі лінійного програмування на прикладі. Нехай фермер прийняв рішення вирощувати озиму пшеницю і цукрові буряки на площі 20 га, відвівши під цукрові буряки не менше як 5 га. Техніко-економічні показники вирощування цих культур маємо у табл. 2.3:

max Z x x (2.10)

x x (2.11)

x x (2.12)

x x (2.13)

x (2.14)

x x (2.15)

Область допустимих розв’язків цієї задачі дістаємо так. Кожне обмеження, наприклад х₁ + х₂ 20, задає півплощину з граничною прямою х₁ + х₂ = 20. Будуємо її і визначаємо півплощину, яка описується нерівністю х₁ + х₂ 20. З цією метою в нерівність х₁ + х₂  20 підставляємо координати характерної точки, скажімо, х₁ = 0 і х₂ = 0. Переконуємося, що ця точка належить півплощині х₁ + х₂  20. Цей факт на рис. 2.2 ілюструємо відповідною напрямленою стрілкою. Аналогічно будуємо півплощини, які відповідають нерівностям (2.11)—(2.15). У результаті перетину цих півплощин утворюється область допустимих розв’язків задачі (на рис. 2.2 — чотирикутник ABCD). Цільова функція Z x x являє собою сім’ю паралельних прямих, кожна з яких відповідає певному значенню Z. Зокрема, якщо Z = 0, то маємо 0,7х₁ + х₂ = 0. Ця пряма проходить через початок системи координат. Коли Z = 3,5, то маємо пряму 0,7х₁ + х₂ = 3,5.