Теоретичні відомості

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

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

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

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

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

3. Перевірка опорного плану на оптимальність за допомогою оцінок . Якщо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок не задовольняє умову оптимальності, то переходять до нового опорного плану або встановлюють, що оптимального плану задачі не існує.

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