СИМПЛЕКСНИЙ МЕТОД РОЗВ’язування ЗЛП

Розглянутий вище графічний метод розв’язку ЗЛП застосовують до задач досить вузького класу. Універсальним методом розв’язування ЗЛП є симплексний метод (або метод послідовного поліпшення плану).

Симплексний метод дозволяє розв’язувати задачі в тому випадку, коли постановка виконана в одній з канонічних форм.

Нехай ЗЛП представлена в наступному виді

Припустимо, що система обмежень (24) сумісна в області невід’ємних значень змінних (25) і ранг системи дорівнює r (причому r<n).

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

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

1. Визначається який-небудь первісний опорний план .

2. За спеціальними правилами здійснюється перехід

, поки не буде знайдене оптимальне значення (opt) лінійної форми. Opt лінійної форми буде доставляти опорний план .