2.3. Альтернативный оптимум

Если среди оценок свободных переменных в последней симплексной таблице есть, хотя бы одна оценка равная нулю, то задача имеет альтернативное решение, т.е. хотя бы два оптимальных решения .Для этих решений экстремальное значение функции будет одинаковое. Чем больше будет нулевых оценок, тем больше - оптимальных решений .

Пример3

Представим последнюю симплексную таблицу:

Таблица 2.5.

Последняя симплексная таблица

Св.П	Cj	0	1	5
Б.П.	Ci	ai0	X1	X2
X3	1	6	3	(5)
X4	0	8	2	4
Z		6	2	0 

Xопт(0, 0, 6,8) Z max=6

Разрешающий столбец выбираем по нулевой оценке.

Таблица 2.6.

Альтернативная симплексная таблица

Св.П	Cj	0	1	1
Б.П.	Ci	ai0	X1	X3
X2	5	6/5	3/5	1/5
X4	0	26/5	-2/5	-4/5
Z		6	2	0

Xопт(0, 6/5, 0, 26/5) Zmax=6

2.4. Вырождение основной задачи линейного программирования

Если в опорном решении задачи, хотя бы одна базисная переменная принимает нулевое значение, то это решение называется вырожденным, а задача линейного программирования, имеющая хотя бы одно вырожденное решение - вырожденной задачей.

Вырождение наступает в тех случаях, когда при выборе разрешающего элемента, получается несколько одинаковых минимальных симплексных отношений. В этом случае в следующей симплексной таблице в столбце свободных членов появится хотя бы один нуль. Вырождение в больших задачах может привести к зацикливанию, т.е. через некоторое число шагов мы можем придти к опорному решению, которое было уже получено раньше. Чтобы избежать зацикливания, разрешающий элемент нужно выбирать по определенному правилу, а именно - для тех строк разрешающего столбца, где получились одинаковые минимальные симплексные отношения. нужно составить отношения элементов, стоящих в столбце за разрешающим столбцом к элементам разрешающего столбца. Наименьшее отношение с учетом знака даст разрешающую строку.

Пример4

Х₁+2Х₂4

2Х₁+Х₂4

Х₁ 2

Х₂2

Хj0, j=1,2

Zmax =X₁+X₂

Приводим к канонической форме

X₁+2X₂+X₃=4

2X₁+X₂+X₄=4

X₁+ +X₅=2

X₂+X₆=2

Xj0, j=1,...,6

Zmax=X₁+X₂+0X₃+0 X₄+0 X₅+0 X₆

Заполняем первую симплексную таблицу по алгоритму симплексного метода (табл.2.7.).

В оценочной строке две одинаковые отрицательные оценки, поэтому разрешающий столбец выбираем тот, который ближе к столбцу свободных членов. Минимальных симплексных отношений два, поэтому находим отношение элементов столбца Х₂ к элементам столбца Х₁. После пересчета минимальное отношение находится в третьей строке и равно 0, следовательно, разрешающий элемент равен 1. Далее идет обычный пересчет.

Таблица 2.7.

Первая симплексная таблица

Св.П	Cj	0	1	1	ai0/ aip
Б.П.	Ci	ai0	X1	X2
X3	0	4	1	2	4 (2)
X4	0	4	2	1	2 (1/2)
X5	0	2	(1)	0	2 (0) 
X6	0	2	0	1	-
Z		0	-1	-1