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

Спочатку розв’яжемо графічним методом (тобто геометрично) математичну модель задачі, яка була наведена першою. А саме задачі, де f = 200 х₁ + 300 х₂ (max) – цільова функція, а система обмежень

.

Коефіцієнти нерівностей системи обмежень можна скоротити, звідки

.

Перший крок: знайдемо множину допустимих розв’язків оптимізаційної задачі Ω на координатній площині (х₁, х₂). Множина розв’язків кожної нерівності системи обмежень визначає на координатній площині деяку півплощину. Так розв’язки нерівності х₁ + 2х₂ ≤ 10 – це півплощина, обмежена прямою х₁ + 2х₂ = 10, яку можна побудувати по двом точкам її перетину з осями системи координат: (10;0) і (0;5). Оскільки 0 + 2∙0 ≤ 10, то це та півплощина, обмежена прямою х₁ + 2х₂ = 10, яка містить початок координат О(0;0). Умови невід’ємності х₁ ≥ 0, х₂ ≥ 0 визначають півплощини з граничними прямими х₁ = 0 та х₂ = 0 відповідно, тобто сукупно визначають першу чверть координатної площини. Перетин всіх п’яти півплощин і утворює множину допустимих розв’язків Ω. З рисунку 1 видно, що це п’ятикутник ОАВСД.

Другий крок: у множині допустимих розв’язків Ω, тобто у п’ятикутнику ОАВСД треба знайти точку, у якій цільова функція f = 200 х₁ + 300 х₂ набуває найбільшого можливого значення. Спочатку побудуємо пряму L₀: 200 х₁ + 300 х₂ = 0 – це сукупність точок, у яких f = 0, нульовий рівень цільової функції. Пряма L₀ містить точку О(0;0) (оскільки 200∙0 + 300∙0 = 0) і перпендикулярна вектору нормалі N (2;3) = .(200;300).

Будь – яка пряма 200 х₁ + 300 х₂ = f при деякому фіксованому значенні f має той самий вектор нормалі N (2;3) і отже паралельна прямій L₀ (наприклад, пряма L₁ на рисунку 1). Кожна з них визначає лінію рівня цільової функції f. Із зростанням f пряма паралельно L₀ пересувається у напрямку вектора N, із спаданням f у протилежному напрямку. Тож для пошуку максимуму треба рухатись у напрямку вектора N, а мінімуму – у напрямку протилежному.

х₂

 

 

 

L₂ 5 А

 

4 В

N

L₁ 3

.

2 Ω С

 

L₀ 1

Д х₁

О 1 2 3 4 5 6 7 8 9 10

 

 

Рисунок 1

 

(Насправді, значення f по модулю пропорційно відстанню відповідної прямої від початку координат). Отже, шукані оптимальні розв’язки – це точки перетину області Ω з прямою, паралельною L₀, у такому її положенні, що подальше пересування у напрямку вектора N дає пустий перетин з Ω. На рисунку 1 це пряма L₂ і вона має єдину точку перетину з Ω – точку В. Залишилося знайти координати точки В. Оскільки це точка перетину прямих х₁ + 2х₂ = 10 та х₁ + х₂ = 6, то отримуємо х₁ = 2, х₂ = 4. Отже, щоденний план виробництва, що забезпечує найбільший прибуток, складає 2 одиниці виробу А і 4 одиниці виробу Б.

 

х₂ х₂

L₁ L₂ L₂

А А

В

L₁

 

Ω

Ω С В

L₀ N Д

N

L₀ С

х₁ х₁

О Д О

 

Рисунок 2 Рисунок 3

 

Графічний метод можна застосувати до будь – якої задачі лінійного програмування, яка містить лише дві змінні. Як було показано, спочатку треба знайти область розв’язків Ω, як перетин півплощин. В результаті отримуємо опуклу множину, обмежену прямими, тобто многокутник. Потім треба для цільової функції f = а₁х₁ + а₂х₂ побудувати лінію нульового рівня L₀: а₁х₁ + а₂х₂ = 0 і далі пересувати пряму паралельно L₀ до виходу із області Ω у напрямку вектора нормалі N (а₁;а₂) для пошуку максимуму і у протилежному

напрямку для пошуку мінімуму. Відповідь залежить від області Ω. У розглянутому вище прикладі пряма у кінцевому положенні – це пряма L₂ і вона має єдину точку перетину з

Ω – точку В (рисунок 1). На рисунку 2 лінія нульового рівня L₀ паралельна прямій ВС, що обмежує множину розв’язків Ω, і тому кінцеве положення прямої L₂ перетинає Ω по відрізку ВС. Отже, у цьому прикладі існує нескінченна множина оптимальних розв’язків

– всі точки відрізка ВС. На рисунку 3 множина розв’язків Ω – це необмежений зверху

многокутник АВСД. Оскільки при пересуванні у напрямку вектора N пряма весь час

буде перетинати область Ω, то цільова функція f не обмежена зверху на допустимих

розв’язках і тому не існує точки, у якій f набуває найбільшого можливого значення,

тобто не існує оптимального розв’язка. Можливі також приклади, у яких система обмежень несумісна, тобто множина допустимих розв’язків Ω пуста. Звичайно, у таких прикладах теж не існує оптимальних розв’язків.

Якщо задача лінійного програмування містить три змінні, то аналогічно множина Ω допустимих розв’язків (якщо вона не пуста) є перетином півпросторів трьохвимірного простору, обмежених площинами. Це опуклий многогранник із скінченим числом вершин. Нульовий рівень цільової функції f = а₁х₁ + а₂х₂ + а₃х₃ визначає площина а₁х₁ + а₂х₂ + а₃х₃ = 0, яка містить початок координат і перпендикулярна до вектора нормалі N (а₁;а₂;а₃). Далі треба пересувати площину нульового рівня паралельно до виходу із області Ω у напрямку вектора нормалі N (а₁;а₂;а₃) для пошуку максимуму, а для пошуку мінімуму у протилежному напрямку. Оптимальний розв’язок визначає точка найбільш (або найменш) віддалена від початку координат. Відповідь залежить від області Ω, можливі ті ж випадки, що у двовимірному просторі. А саме найчастіше це єдиний розв’язок, який визначає деяка вершина многогранника. Якщо площина нульового рівня паралельна площині Р, що обмежує Ω, то існує нескінченна множина оптимальних розв’язків, які утворюють многокутник на Р. Якщо Ω не обмежена у напрямку N, то не існує максимуму цільової функції; якщо у протилежному напрямку, то мінімуму.

Задача лінійного програмування загального виду містить n змінних, а її система обмежень за означенням 2 включає рівняння і нерівності. Аналогічно випадкам n = 2 і 3 множина Ω допустимих розв’язків (якщо вона не пуста) є перетином півпросторів n – вимірного простору, обмежених гіперплощинами с₁х₁ + с₂х₂ + с₃х₃ + … + с_nх_n = b, яким у системі обмежень відповідає нерівність с₁х₁ + с₂х₂ + с₃х₃ + … + с_nх_n ≤ b або с₁х₁ + с₂х₂ + с₃х₃ + … + с_nх_n ≥ b, і гіперплощин, яким у системі обмежень відповідає рівняння. (При n = 2 гіперплощина – це пряма, при n = 3 площина і саме так можна уявляти її). Тому Ω – це n – вимірний опуклий многогранник із скінченим числом вершин. Формально вони визначаються так.

Означення 3. Крайньою точкою опуклої множини V називається така точка х є V, що будь – яка опукла комбінація х = λ∙y + μ∙z, де у,z є V, λ, μ ≥ 0, λ + μ = 1 можлива лише за умови, що у = z = х.

Очевидно, що у опуклому многограннику Ω крайні точки – це його вершини, всі інші точки Ω є опуклими комбінаціями його вершин. Нульовий рівень цільової функції f = а₁х₁ + а₂х₂ + а₃х₃ + … + а_nх_n визначає гіперплощина а₁х₁ + а₂х₂ + а₃х₃ + … + а_nх_n = 0, яка перпендикулярна вектору нормалі N (а₁;а₂;а₃;…;а_n) і містить початок координат. Далі треба пересувати гіперплощину нульового рівня паралельно напрямку вектора нормалі N для пошуку максимуму, а для пошуку мінімуму у протилежному напрямку до виходу із області Ω. Відповідь залежить від виду Ω, можливі ті ж випадки, що у двовимірному або у трьохвимірному просторах.

Висновки. 1. Множина Ω допустимих розв’язків задачі лінійного програмування (якщо вона не пуста) є опуклим многогранником у Rⁿ із скінченим числом вершин.

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

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

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