Поняття про виродження
Базисний план ЗЛП, записаної у кращому вигляді невироджений, коли вільні члени всіх рівнянь позитивні, і вироджений, якщо серед них є нулі.
Визначення: Канонічну ЗЛП називають невиродженою, якщо всі її опорні плани невироджені. Якщо серед опорних планів є хоча б один вироджений, завдання називають виродженим.
Нехай ЗЛП вирішується максимум. На двох послідовних ітераціях значення цільової функції пов'язані співвідношенням:
Якщо завдання невироджене, то для будь-якого кроку. Звідси , т. е. значення цільової функції буде гірше колишнього (монотонно зростає). Аналогічно, якщо завдання вирішується на мінімум, то, оскільки на будь-якому кроці значення цільової функції на двох послідовних ітераціях будуть пов'язані нерівністю, тобто цільова функція монотонно зменшується. У цьому полягає монотонність симплексного методу.
Кінцевість алгоритму випливає з кінцевого числа опорних планів ЗЛП (їх не більше).
Якщо ЗЛП вироджена, то можливі випадки, коли . У цьому випадку значення цільової функції не покращиться. Припустимо, процес триває без зупинки, породжуючи нескінченну послідовність опорних планів. Внаслідок кінцівки безлічі опорних планів у цій послідовності деякі плани мають повторюватися. У силу рівності для них цільової функції вони повинні лежати в одній гіперплощині та бути вершинами опуклого багатогранника. Тому має зустрітися ланцюжок (цикл), в якому початковий і кінцевий плани збігаються, причому в силу монотонності методу
Процес продовжиться необмежено, якщо кілька послідовних вироджень призведуть до утворення циклу. Таке явище називається зациклюванням.Зациклювання можливе лише для вироджених завдань. Теорія та практика показують, що зациклювання виникає за досить малоймовірного поєднання умов. Відомо лише кілька спеціально розроблених (дуже складних) прикладів, у процесі вирішення яких виникає зациклювання. Точний алгоритм виведення із циклу досить складний. У найпростішому випадку при появі циклу слід змінити послідовність обчислень шляхом зміни вибору стовпця, що дозволяє. Інше правило рекомендує змінити вибір роздільної здатності. Якщо в процесі симплексних перетворень з'являється кілька мінімальних симплексних відносин, то як вирішальна вибирають той рядок, для якого буде найменшим відношення елементів першого стовпця до вирішального. Якщо при цьому знову виявляється кілька мінімальних відносин, то складаються відношення елементів другого стовпця до вирішального, і так до тих пір, поки рядок, що дозволяє, не визначиться однозначно.