Умови збіжності симплексного процесу

Визначення. ЗЛП називається невиродженою, якщо в жодному з її опорних планів серед базисних змінних немає нульових значень.

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

Мал. 10

Теорема (про збіжність симплексного процесу)

Нехай:

1. ЗЛП невироджена.

2. Система обмежень ЗЛП має, принаймні, одне опорне рішення.

3. Лінійна форма F обмежена знизу при визначенні opt min і зверху при визначенні opt max.

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

Як правило, при рішенні ЗЛП симплексним методом кількість ітерацій R < 2 r (r – ранг системи обмежень ЗЛП).