Концепцията за дегенерация
Основният план на LLP, написан в предпочитаната форма, е неизроден, когато свободните членове на всички уравнения са положителни, и изроден, ако сред тях има нули.
Дефиниция: Канонично LLP се нарича неизродено, ако всички негови планове за поддръжка са неизродени. Ако сред поддържащите планове има поне един изроден, тогава проблемът се нарича изроден.
Нека ЗЛП се реши максимално. При две последователни итерации стойностите на целевата функция са свързани с отношението:
Ако проблемът не е изроден, тогава за всяка стъпка . Следователно, т.е. стойността на целевата функция няма да бъде по-лоша от предишната (монотонно нараства). По същия начин, ако проблемът е решен до минимум, тогава, тъй като , на всяка стъпка, стойностите на целевата функция при две последователни итерации ще бъдат свързани с неравенството , т.е. целевата функция монотонно намалява. Това е монотонността на симплексния метод.
Крайността на алгоритъма следва от крайния брой планове за поддръжка на LLP (вече няма такива).
Ако LLP е изроден, тогава има случаи, когато . В този случай стойността на целевата функция няма да се подобри. Нека приемем, че процесът продължава без спиране, генерирайки безкрайна последователност от базови планове. Поради ограничеността на набора от референтни планове в тази последователност, някои планове трябва да бъдат повторени. По силата на равенството на целевата функция за тях те трябва да лежат в една и съща хиперравнина и да са върхове на изпъкнал многостен. Следователно трябва да има верига (цикъл), в която началният и крайният план съвпадат и поради монотонността на метода
Процесът ще продължи безкрайно дълго, ако няколко последователни дегенерации доведат до образуването на цикъл. Това явление се нарича зацикляне.Зациклянето е възможно само за изродени проблеми. Теорията и практиката показват, че зациклянето възниква при много малко вероятна комбинация от условия. Известни са само няколко специално проектирани (много сложни) примера, в процеса на решаването на които възниква цикъл. Точният алгоритъм за излизане от цикъл е доста сложен. В най-простия случай, когато се появи цикъл, последователността от изчисления трябва да се промени чрез промяна на избора на колоната за разрешаване. Друго правило препоръчва промяна на избора на разрешителния низ. Ако в процеса на симплексни трансформации се появят няколко минимални симплексни съотношения, тогава се избира разрешаващият ред, за който съотношението на елементите на първата колона към разрешаващото ще бъде най-малкото. Ако това отново се окаже, че са няколко минимални съотношения, тогава се компилират съотношенията на елементите от втората колона към разрешаващата и така нататък, докато не се определи еднозначно разрешаващата редица.