Вырожденность.
Если нет однозначной идентификации переменной (в случае одинаковых отношений), которая подлежит исключению из базиса, то выбор такой переменной можно сделать произвольно. Однако на следующей итерации по крайней мере, одна из базисных переменных должна быть равна нулю. В этом случае говорят, что новое решение является вырожденным. Появление вырожденного решения объясняется присутствием в модели, по крайней мере, одного избыточного ограничения.
Пример 2. 9. 1:
f0 = 3х1 + 9х2® maх
при ограничениях: х1 + 4х2 + х3 = 8 (1)
х1 + 2х2 + х4 = 4 (2)
хi 
0, i = 1,..,4
Таблица20
| № итер. | Базис | х1 | х2 | х3 | х4 | Знач | Отнош. | Формула |
| N=0 х2 ввод. х3 искл. | fур | -3 | -9 | 0 | 0 | 0 | ||
| х3 | 1 | 4 | 1 | 0 | 8 | 8:4=2 | ||
| х4 | 1 | 2 | 0 | 1 | 4 | 4:2=2 | ||
| N=1 х1 ввод., х4 искл. | fур | -3/4 | 0 | 9/4 | 0 | 18 | fур=fyp+9x2 | |
| х2 | 1/4 | 1 | 1/4 | 0 | 2 | 2:1/4=8 | x2=x3/4 | |
| х4 | 1/2 | 0 | -1/2 | 1 | 0 | 0:1/2=0 | x4=x4-2x2 | |
| (вырожденное | решение) | |||||||
| N=2 оптимум | fур | 0 | 0 | 3/2 | 3/2 | 18 | fур=fyp+3/4x1 | |
| х2 | 0 | 1 | 1/2 | -1/2 | 2 | x2=x2-1/4x1 | ||
| х1 | 1 | 0 | -1 | 2 | 0 | x1=x4:1/2=х4. 2 |
max f =18 при плане Х* = (0;2;0;0).
Решим задачу графически. Через точку оптимума А проходят три прямые. Задача содержит только две переменные х1 и х2, поэтому для идентификации точки А достаточно 2-х прямых. Отсюда вывод: одно из ограничений является избыточным.
Рис. 20.
Информация, что некоторые ресурсы не нужны для достижения поставленной цели, оказывается полезной при практической реализации результатов исследования.
Однако не существует надежных способов обнаружения избыточных ограничений непосредственно из симплекс - таблицы.
Теоретически, вырожденность может привести к зацикливанию.
Зацикливание.
Посмотрите на симплекс – таблицу (см. табл. 20) значение целевой функции не улучшилось после 2-ой итерации по сравнению с 1 итерацией. Поэтому, можно предположить, что в общем случае может возникнуть зацикливание (циклическое повторение одинаковых операций, не улучшающих значение целевой функции, и не приводящих к завершению вычислительного процесса). Имеются специальные приемы, которые предотвращают зацикливание. Однако их использование чрезмерно замедляет процесс численных расчетов. Поэтому разработанные программы не содержат таких блоков, тем более, что вероятность зацикливания ничтожно мала.
Пример 2. 9. 1. Появление промежуточного вырожденного решения.
Рассмотрим пример.
| В стандартной форме | В канонической форме |
| f0 = 3х1 + 2х2® maх | fур - 3х1 - 2х2=0 |
| при ограничениях |
при ограничениях
|
 4х1 + 3х2£ 12 (1)
| 4х1 + 3х2+х3=12 |
| 4х1 + х2£ 8 (2) | 4х1 + х2+х4 =8 |
| 4х1 – х2£ 8 (3) | 4х1–х2+х5= 8 |
| х1, х2 ³0 | хi³0 i=1,2,...,5 |
n = 5; m = 3; (n - m)= 2 число небазисных переменных
Таблица21
| № итер. | Базис | х1 | х2 | х3 | х4 | x5 | Знач | Отнош | Формула |
| N=0 х1 ввод., х4 искл. | fур | -3 | -2 | 0 | 0 | 0 | 0 | ||
| х3 | 4 | 3 | 1 | 0 | 0 | 12 | 12:3=4 | ||
| х4 | 4 | 1 | 0 | 1 | 0 | 8 | 8:4=2 | ||
| x5 | 4 | -1 | 0 | 0 | 1 | 8 | 8:4=2 | ||
| N=1 х2 ввод., х3 искл. | fур. | 0 | -5/4 | 0 | ¾ | 0 | 6 | fyp = fyp + 3x1 | |
| х3 | 0 | 2 | 1 | -1 | 0 | 4 | 4:2=2 | x3=x3-4x1 | |
| х1 | 1 | 1/4 | 0 | ¼ | 0 | 2 | 2:1/4=8 | x1=x4:4 | |
| х5 | 0 | -2 | 0 | -1 | 0 | 0 | x5=x5-4x1 | ||
| N=2 оптимум | fур | 0 | 0 | 5/8 | 1/8 | 0 | 17/2 | fyp = fyp+5/4x2 | |
| х2 | 0 | 1 | 1/2 | -1/2 | 0 | 2 | x2=x3:2 | ||
| х1 | 1 | 0 | -1/8 | 3/8 | 0 | 3/2 | x1=x1-1/4x2 | ||
| х5 | 0 | 0 | 1 | -2 | 1 | 4 | X5=x5+2x2 |
В рассмотренном примере на второй итерации вырожденности нет, причем значение целевой функции возросло с 6 до 
. Из примера можно сделать следующий вывод: итерации симплекс - метода должны выполняться до тех пор, пока не будет выполнено условие оптимальности! Точка С переопределена (через нее проходят 3 прямые).
Рис. 21.