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

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

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

Мал. 4.1.

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

Якщо в даній системі обмежень буде три змінних, то кожна нерівність геометрично визначатиме півпростір тривимірного простору, граничними площинами якого будуть:

, ,

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

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

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

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

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

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

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

 

Таблиця 4.1.

Показник (із розрахунку на 1 га)	Озима пшениця	Цукрові буряки	Наявний ресурс
Затрати праці, людино-днів
Затрати праці механізаторів, людино-днів
Урожайність, тонн	3,5		—
Прибуток, тис. грн.	0,7		—

 

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

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

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

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

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

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

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

Область допустимих розв’язків цієї задачі дістаємо так. Кожне обмеження, наприклад , задає півплощину з граничною прямою . Будуємо її і визначаємо півплощину, яка описується нерівністю . З цією метою в нерівність підставляємо координати характерної точки, скажімо, і . Переконуємося, що ця точка належить півплощині . Цей факт на мал.4.2 ілюструємо відповідною напрямленою стрілкою. Аналогічно будуємо півплощини, які відповідають й іншим нерівностям. У результаті перетину цих півплощин утворюється область допустимих розв'язків задачі (на мал.4.2 — чотирикутник АВСD). Цільова функція являє собою сім’ю паралельних прямих, кожна з яких відповідає певному значенню Z. Зокрема, якщо Z = 0, то маємо . Ця пряма проходить через початок системи координат. Коли Z = 3,5, то маємо пряму .

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

Теорема 4.1. Множина всіх планів задачі лінійного програмування опукла.

Доведення. Необхідно довести, що коли та - плани задачі лінійного програмування (3.1)-(3.3), то їх опукла комбінація також є планом задачі.

Так як та - плани задачі, то виконуються такі співвідношення:

Якщо підставити в систему обмежень значення Х, то отримаємо: .

Отримали, що Х задовольняє систему обмежень задачі лінійного програмування (3.2), і оскільки то й , тобто задовольняють і умову (3.3). У такий спосіб доведено, що Х – план задачі лінійного програмування.

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

Теорема 4.3. Якщо відомо, що система векторів у розкладі лінійно незалежна і така, що

де всі , то точка є кутовою точкою багатогранника розв’язків.

Доведення. Припустимо, що точка Х не є кутовою. Тоді вона може бути виражена опуклою лінійною комбінацією двох інших точок та багатогранника розв’язків, тобто:

.

Компоненти векторів та , значення та невід’ємні і останні n-k компонентів вектора Х дорівнюють нулю, тому відповідні n-k компонент векторів та також мають дорівнювати нулю, тобто

,

.

Оскільки та - плани, то

,

.

Віднімаючи від першого рівняння друге, отримаємо:

За припущенням вектори лінійно незалежні, тому останнє співвідношення виконується, якщо

Звідки: .

Отже, Х неможливо подати як опуклу лінійну комбінацію двох інших точок багатокутника розв’язків. Значить, Х – кутова точка.

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

Наслідки:

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

2) Кожній кутовій точці багатокутника розв’язків відповідає лінійно незалежних векторів системи .

З наведених властивостей можна зробити наступні висновки: якщо функціонал задачі лінійного програмування обмежений на багатограннику розв’язків, то:

1) існує така кутова точка багатогранника розв’язків, в якій лінійний функціонал досягає свого оптимального значення;

2) кожний опорний план відповідає кутовій точці багатогранника розв’язків.

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