6.2.2. Выбор разрешающей строки в симплексных преобразованиях

Переход от одного опорного плана к другому называется симплексным преобразованием.

Пусть при решении ЗЛП получена таблица:

БП	x1	x2	…	xm	xm+1	…	xs	…	xn	Свобод- ный член	,
x1	1	0	…	0	a′1,m+1	…	a′1,s	…	a′1,n	b′1
x2	0	1	…	0	a′2,m+1	…	a′2,s	…	a′2,n	b′2
…	…	…	…	…	…	…	…	…	…	…
xm	0	0	…	1	a′m,m+1	…	a′m,s	…	a′m,n	b′m
Z	0	0	…	0	r1	…	rs	…	rn–m	q

в которой все , , т.е. найден опорный план:

.

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

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

Как было указано, за разрешающую строку принимают k-ю строку, для которой выполняется условие

.

Покажем, что при таком выборе разрешающей строки неотрицательные свободные члены симплекс-таблицы после преобразования Жордана–Гаусса перейдут в неотрицательные.

Действительно, согласно правилам преобразований Жордана–Гаусса имеем:

a) для разрешающей строки ( ) очевидно:

, так как

б) для остальных строк ( ) имеем

.

В самом деле,

и , так как .

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

Пусть в последней симплекс-таблице получен оптимальный план Х^*. Если среди неотрицательных компонент вектора при этом имеется хотя бы одна нулевая компонента , то введение переменной в базис не изменит величины функции цели Z Действительно, выполнив шаг преобразований Жордана–Гаусса с разрешающим элементом получим новое опорное решение, для которого

БП				Свободный член
		a kp

Следовательно, новое опорное решение является новым оптимальным решением. Обозначим эти оптимальные планы соответственно Х^*1 и Х^*2. Тогда согласно свойствам допустимых планов задача имеет бесконечно много решений и оптимальный план является выпуклой линейной комбинацией оптимальных планов Х^*1 и Х^*2, т. е.

Итак, признаком существования альтернативного оптимума при решении ЗЛП в симплексных таблицах является наличие хотя бы одной нулевой компоненты вектора r, соответствующего оптимальному плану.

Если нулевых компонент окажется несколько, то введением в базис каждой из соответствующих переменных можно найти несколько оптимальных планов и т.д. Согласно теореме 5.3 общее оптимальное решение при наличии k оптимальных опорных решений имеет вид:

где

Очевидно, при наличии только двух свободных переменных могут быть лишь два альтернативных оптимальных опорных решения (две вершины). Однако уже при наличии трех свободных переменных этих оптимумов может оказаться сколько угодно. Геометрически это соответствует случаю, когда плоскость уровня параллельна грани многогранника и в крайнем положении будет проходить через все вершины этой грани.