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

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

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

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

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

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

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

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

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

Мал. 10

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

Нехай:

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

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

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

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

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

Дата добавления: 2014-12-07