Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

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

Розглянемо на площині Х10x2 сумісну систему лінійних нерівностей:

(2.9)

Кожна нерівність цієї системи геометрично визначає півплощину з граничною прямою ai1x1 + ai2x2 = bi(i = 1, 2, ...,т). Умови невід’ємності змінних визначають півплощини з граничними прямими х1 = 0 та х2 = 0. Система сумісна, тому півплощини як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожної з яких є розв’язком даної системи (рис. 2.1).

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

Якщо в системі обмежень (2.9) буде три змінних, то кожна нерівність геометрично визначатиме півпростір тривимірного простору, граничними площинами котрого будуть ai1x1 + ai2x2 + ai3x3 = bi (i = 1, 2, ...,т), а умови невід’ємності — півпростори з граничними площинами хj = 0 (j = 1, 2, 3), де і — номер обмеження, а j — номер змінної. Якщо система обмежень сумісна, то ці півпростори як опуклі множини, перетинаючись, утворять у тривимірному просторі спільну частину, що називається багатогранником розв’язків. Він може бути точкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю.

Нехай у системі обмежень (2.9) кількість змінних більша, ніж три: х1, х2,… хn; тоді кожна нерівність визначає півпростір n-вимірного простору з граничною гіперплощиною аi1x1 + ai2x2 + ai3x3 + … +ainxn = bi (i = 1, 2, ...,т). Кожному обмеженню виду (2.9) відповідають гіперплощина та напівпростір, який лежить з одного боку цієї гіперплощини, а умови невід’ємності — півпростори з граничними гіперплощинами хj = 0 (j = 1, 2, 3, ..., n).

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

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

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

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

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

Таблиця 2.3

ПОКАЗНИКИ ВИРОЩУВАННЯ СІЛЬСЬКОГОСПОДАРСЬКИХ КУЛЬТУР

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

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

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

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

Задача лінійного програмування має такий вигляд:

max Z = 0,7x1 + x2 (2.10)

за умов:

x1 + x2 ≤ 20; (2.11)

5x1 + 25x2 ≤ 270; (2.12)

2x1 + 8x2 ≤ 80; (2.13)

x2 ≥ 5; (2.14)

x1 ≥ 0, x2 ≥ 0. (2.15)

Геометричну інтерпретацію задачі зображено на рис. 2.2.

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

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