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

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

Припустимо, що система(1.1) за умов (1.2) сумісна і багатокутник її розв’язків обмежений.

Згідно з геометричною інтерпретацією задачі лінійного програмування (п.3.3) кожне і -те обмеження-нерівність у (1.2) визначає півплощину з граничною прямою

(і = 1, 2, …, т). Системою обмежень (1.2) графічно можна зобразити спільну частину, або переріз усіх зазначених півплощин, тобто множину точок, координати яких задовольняють всі обмеження задачі – багатокутник розв’язків.

Умова (1.3) невід’ємності змінних означає, що область допустимих розв’язків задачі належить першому квадранту системи координат двовимірного простору. Цільова функція задачі лінійного програмування геометрично інтерпретується як сім’я паралельних прямих с ₁ х ₁+ с ₂ х ₂ = const.

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

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

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

1.Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі (1.2) знаків нерівностей на знаки рівностей.

2.Визначаємо півплощини, що відповідають кожному обмеженню задачі.

3.Знаходимо багатокутник розв’язків задачі лінійного програмування.

4.Будуємо вектор

, що задає напрям зростання значення цільової функції задачі.

5.Будуємо пряму с ₁ х ₁+ с ₂ х ₂=const, перпендикулярну до вектора

6.Рухаючи пряму с ₁ х ₁+ с ₂ х ₂=const в напрямку вектора

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

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

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

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

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

3. Задача лінійного програмування не має оптимальних планів: якщо цільова функція необмежена згори (рис.3.5) або система обмежень задачі несумісна (рисунок 3.6).

4. Задача лінійного програмування має оптимальний план за необмеженої області допустимих розв’язків (рис.3.7 і 3.8). На рис.3.7 у точці В маємо максимум, на рис.3.8 у точці А – мінімум, на рис.3.9 зображено, як у разі необмеженої області допустимих планів цільова функція може набирати максимального чи мінімального значення у будь-якій точці променя.

Розв’язувати графічним методом можна також задачі лінійного програмування n -вимірного простору, де

, якщо при зведенні системи нерівностей задачі до системи рівнянь шляхом введення додаткових змінних кількість змінних n на дві більша, ніж число обмежень m, тобто

Тоді, як відомо з курсу вищої математики, можна дві з n змінних, наприклад х ₁ та х ₂, вибрати як вільні, а інші m зробити базисними і виразити через вільні. Припустимо, що це зроблено. Отримаємо

рівнянь вигляду:

Оскільки всі значення

, то мають виконуватись умови:

Розглянемо, як можна зобразити ці умови геометрично. Візьмемо, наприклад, першу з них:

Узявши величину х ₃ рівною своєму крайньому значенню — нулю, отримаємо рівняння:

Це рівняння прямої. Для такої прямої

, по одну сторону від неї

, а по другу –

. Відмітимо ту сторону прямої

, де

В аналогічний спосіб побудуємо і всі інші обмежуючі прямі:

;

;...;

і відмітимо для кожної з них півплощину, де відповідна змінна більше нуля.

У такий спосіб отримують n– 2 прямі та дві осі координат(

). Кожна з них визначає півплощину, де виконується умова

. Частина площини в

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

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

Підставивши вирази для

,...;

з (3.18) у цей функціонал, зведемо подібні доданки і отримаємо вираз лінійної функції F всіх n змінних лише через дві вільні змінні

та

де

— вільний член, якого в початковому вигляді функціонала не було.

Очевидно, що лінійна функція

досягає свого максимального значення за тих самих значень

та

, що й

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

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: