16. Знаходженння розв’язку задачі лінійного програмування. Алгоритм симплексного методу.

Для розв”язування двовимірних задач лінійного програмування, використовують графічний та симплексний методи. Графічний метод грунтується на геометричній інтерпретації та аналітичних властивостях задач лінійного програмування. Розв”зяати ЗЛП графічно означає знайти таку вершину многокутника розв”язків, у результаті підставляння кооридант якої в цільову функцію, вона набуває найбільшого (найменшого значення).

Алгоритм графічного методу

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

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

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

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

5. Будуємо пряму перепендикулярну градієнту

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

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

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

Алгоритм симплекс

1. визначення початкового опорного плану злп

2. побудова симплексної таблиці

3. перевірка опорного плану на оптимальність за доп. оцінок Zj-Cj. Якщо всі оцінки задовольняють умову опитимальності, то план є оптимальним. Якщо не задовольняє – переходять до іншого опорного плану

4. перехід до нового опорного плану задачі виконується визначенням розв”язувального елемента та розрахунком нової симплексної таблиці

5. повторення дії починаючи з п.3