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

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

Зробимо кілька попередніх зауважень. В якій би формі не розглядалась задача лінійного програмування, кожне обмеження-рівняння визначає в n-вимірному просторі основних змінних (х₁, х₂, ..., х_п) деяку гіперплощину, яка є (п-1) -вимірною множиною у згаданому просторі. Кожне обмеження-нерівність, включаючи і об­меження по знаку, визначає теж деяку площину і півпростір n-вимірного простору, що лежить по один бік від цієї площини. Перетин усіх цих опуклих множин, які визначаються обмеженнями задачі, дає опуклий многогранник допустимих розв'язків системи основних об­межень задачі . Лінійну форму можна також інтерпретувати в n-ви­мірному просторі основних змінних як сімейство деяких паралельних гіперплощин, положення кожної з яких визначається значенням пара­метра Z. Отже, кожну таку окрему гіперплощину можна інтерпрету­вати як площину рівня цільової функції Z.

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

Графічний метод вирізняється серед методів лінійного програмування простотою та наглядністю, але недоліком його є те, що використовується цей метод лише для задач незначної розмірності ( лише для 2-3 змінних).

Нерівність а_і1х₁+а_і2х₂  b_і визначає граничну пряму а_і1х₁+а_і2х₂ =b_і, яка поділяє площину на дві півплощини: додатну а_і1х₁+а_і2х₂ >b_і та від’ємну а_і1х₁+а_і2х₂ <b_і. Для того, щоб побудувати обмеження-нерівність, необхідно побудувати граничну пряму а_і1х₁+а_і2х₂ =b_і за двома точками, а потім визначити півплощину, що задовольняє дану нерівність.

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

Цільовій функції Z можна надати будь-якого значення і побудувати пряму, що відповідає отриманому виразу. Пряма, одержана таким чином, називається лінією рівня. Оскільки цільовій функції можна надати безліч значень (дійсних), то можна отримати й безліч ліній рівня. Усі лінії рівня паралельні між собою. Напрямок максимізації цільової функції показує вектор-градієнт. Введемо поняття градієнта функції Z.

Якщо наша цільова функція має вигляд Z = С₁x₁+ С₂x_2, то Z=(dZ/dx₁; dZ/dx₂) = (С₁; С₂). Таким чином, вектор-градієнт N – це вектор, котрий завжди виходить з початку координат, проходить через точку (С₁; С₂), координати якої є частинними похідними цільової функції і вказує напрямок її зростання. Вектор-градієнт та лінії рівня перпендикулярні між собою.

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

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

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

• будуємо прямі лінії, рівняння яких дістаємо заміною знаків нерівностей задачі (2.1-2.7), на знаки рівності;

• визначаємо півплощини, які відповідають кожному обмеженню задачі;

• знаходимо многокутник розв‘язків задачі лінійного програмування (симплекс);

• б удуємо вектор =(c_{1 ;} c₂) (вектор-градієнт), що задає напрям зростання цільової функції задачі;

• б удуємо пряму c₁х_{1 +} c₂х₂ = const, перпендикулярну до вектора-градієнта ;

• переміщуючи пряму c₁х_{1 +} c₂х₂ = const у напрямі вектора-градієнта (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину многокутника розв‘язків, де цільова функція досягає екстремального значення;

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

У разі застосування графічного методу для розв‘язування задач лінійного програмування можливі такі випадки.

Цільова функція набуває максимального значення в єдиній вершині А многокутника розв‘язків (рис.2.1).

Максимального значення цільова функція досягає у будь-якій точці відрізку АВ (рис.2.2). Тоді задача лінійного програмування має альтернативні оптимальні плани (вся множина точок, що належить відрізку АВ).

Задача лінійного програмування не має оптимального плану (рис.2.3 – цільова функція не обмежена згори (зверху); рис.2.4 – система обмежень задачі не сумісна).Задача лінійного програмування має оптимальний план за необмеженої області допустимих розв‘язків (рис.2.5 і 2.6). На рис.2.5 у точці В маємо максимум, на рис.2.6 у точці В – мінімум, на рис.2.7 показано, що у разі необмеженої області допустимих планів цільова функція набуває максимального і мінімального значення.

А х2 Zmax N х1 Рис. 2.1		A х2 B Zmax N х1 Рис. 2.2
х2 Zmax→∞ N х1 Рис. 2.3		х2 х1 Рис.2.4
х2 Zmax B N х1 Рис. 2.5		х2 Zmin N B х1 Рис.2.6
	х2 N х1 Рис. 2.7