Випадок виродження та зациклювання

Для визначення будь-якого допустимого розв’язку складають сукупність т базисних змінних, які мають залежності через (п-т)вільних змінних.

Розв’язок, в якому кількість нульових змінних перевищує(п-т),називають виродженим, тобто є випадок, коли .

У цьому разі при подальшій спробі поліпшити розв’язок значення цільової функції залишається незмінним. Це можливо, якщо в головному рядку в колонці вільних членів . Унаслідок перетворень змінюється тільки сукупність базисних змінних з однією і тією ж самою величиною цільовою функцією . Після деякої кількості переходів від однієї симплекс-таблиці до іншої можна повернутись до раніше побудованої сукупності базисних змінних. Такий випадок у процесі розрахунку називають зациклюванням.

Слід зазначити, що в практиці розв’язування задач зациклювання трапляються дуже рідко, але такі випадки треба завжди враховувати та усу­вати, особливо коли задачу розв’язують за допомогою ЕОМ.

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

Щоб усунути зациклювання, треба змінити правила вибору генерального (розв’язувального) елемента: якщо є кілька однакових значень то беруть співвідношення відповідних елементів наступної колонки за колонкою вільних членів до величин . Коли знову є невизначеність у виборі головного рядка, то переходять до наступної колонки таблиці. Такий процес продовжують до однозначного вибору головного рядка.

Наприклад, маємо таку симплекс-таблицю:

				-4
	-2		-6

Якщо , то згідно з аналізом умов оптимальності за елементами індексного рядка ( = -6) спочатку знаходять головну колонку (), а потім головний рядок: оскільки є два однакових співвідношення (6/2 та 3/1), то перевіряють співвідношення (4/2 та 2/І) для цих самих рядків – вони знову однакові, тоді знаходять співвідношення (2/2 та 3/1), де перше найменше; таким чином, головним елементом перетворенняє .