3. Поняття виродженності задач лп.

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

При використанні симплекс-методу вважалося, що всі вільні члени >0, ( ) додатні як у вихідній системі обмежень, так і в системах обмежень, які одержуємо після чергових ітерацій. Якщо в деяких рівняннях вільні члени дорівнюють нулю, то у відповідному цій системі опорному плані базисні змінні приймають нульові значення. Опрний план, у якому хочаб одна з базисних змінних дорівнює нулю, називається виродженим. Задача ЛП, яка має хоча б один вироджений опорний план, називається виродженою задачею ЛП.

Вироджений опорний план може бути або початковим або виникнути у процесі розв’язання задачі.

Приклад 1.

За початковий базис можна вибрати Р₁, Р₄, Р₅ або Р₂, Р₄, Р₅, тоді початковий опорний план Х=(0,0,0,1,1) є виродженим, так як базисна змінна х₁=0 або х₂=0. Для обох початкових планів z=0, тобто у випадку виродженності значення цільової функції може повторюватись навідь при зміні базису.

Поточний базисний розв’язок може стати виродженим, якщо виникає невизначеність у виборі ключового рядка, тобто одержуємо однакове мінімальне значення симплексного відношення

для декількох значень k, де s – номер вектора, який вводять до базису. У цьому випадку також при зміні складу базисних змінних значення цільової функції буде залишатись незмінним.

Оскільки число наборів векторів скінченне, то після деякого числа ітерацій дійдемо до одного з висновків:

1. розв’язок оптимальний;

2. задача не розв’язувана;

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