Геометричний метод розв’язання задач ЛП

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

Схема розв’язання задачі ЛП геометричним методом:

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

2. Серед точок ОДР знаходимо таку, в якій функція мети набуває оптимального значення. Для цього:

а) Зображуємо градієнт функції мети – вектор з початком у точці О (0;0) і кінцем – у точці з координатами, що дорівнюють коефіцієнтам при відповідних змінних цієї функції. Зображуємо лінію рівня функції мети f – пряму, уздовж якої ця функція набуває одного й того ж фіксованого значення a, тобто (лінія рівня завжди перпендикулярна градієнту). Важливою властивістю лінії рівня є те, що при її паралельному зміщенні в напрямку градієнта значення функції мети зростає, а при зміщенні в протилежному напрямку – спадає.

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

Зауваження 2.1. Задача має єдиний оптимальний розв’язок, коли лінія рівня у своєму крайньому положенні проходить тільки через одну кутову точку многокутника розв’язків системи обмежень. Якщо лінія рівня у своєму крайньому положенні збігається з гранню многокутника (наприклад, з відрізком АВ), задача має нескінченно багато оптимальних розв’язків (їх задають координати точок відрізка АВ: ).

Задача 2.1. Розв'язати задачу лінійного програмування геометричним методом.

Дата добавления: 2014-11-06