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

Алгебра симплексного процесу при визначенні оптимального розв’язку типу max

1. Розв'язувальний стовпець вибирається по від’ємному елементу в рядку лінійної форми F (за винятком вільного члена).

2. Розв'язувальний рядок вибирається по мінімальному симплексному відношенню.

3. Розв'язувальний елемент завжди позитивний.

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

5. Процес триває доти, поки в рядку лінійної форми F всі коефіцієнти стануть від’ємними (за винятком, бути може, значення лінійної форми).

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

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

Мал. 10

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

Нехай:

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

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

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

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

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