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

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

має оптимальний план та кожний з опорних планів не є надмірним).Під опорним планом розуміють невід’ємний базисний розв’язок задачілінійного програмування. Нагадаємо: базисний план (розв’язок) – рішення системи обмежень, у якому всі вільні змінні дорівнюють нулю,тобто геометрично базисний план відповідає одній з вершин або граней багатокутника розв’язків.

Стереометрично ідея методу полягає у тому, що:

 знаходять будь-яку вершину багатогранника розв’язків;

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

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

Нагадаємо ще раз:

 вектор розв’язків, що задовольняє всім обмеженням, називається планом;

 план, що відповідає вершині багатогранника розв’язків (всівільні змінні дорівнюють нулю), називається опорним планом;

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