4. Вырожденное решение.
Рассматривается задача P в канонической форме:
f0(x) = c0 · x → max при A0x = b0, x ≥ 0.
Пусть x* – некоторое вырожденное базисное оптимальное решение с базисом β и базисной матрицей B.
Определение: Переменную назовем существенной для задачи P, если существует допустимое решение задачи, в котором эта переменная имеет положительное значение.
Для определения существенности решается задача ЛП:
xj → max при A0x = b0, x ≥ 0.
Утверждение: Если x* –вырожденное оптимальное решение задачи P и хотя бы одна базисная переменная, имеющая в x* нулевое значение, существенна, то x* имеет альтернативный оптимальный базис.
Доказательство:
Рассмотрим
симплекс-таблицу, полученную приведением
задачи P
к базису β.
Все элементы в z-строке
неотрицательны (так как базис оптимален)
и
для
.
По
определению вырожденного решения
для некоторого
.
По условию среди таких k
есть номер существенной переменной. Из
следует, что
для некоторого r.
Уравнение
с номером
:
Вектор
x*
удовлетворяет этому уравнению, так как
допустим. Так как
и небазисные компоненты равны нулю, то
.
Если
для всех j,
то в левой части значение неотрицательно
и равно нулю при
.
Это противоречит существенности
переменной
.
Поэтому существуют j
для которых
.
Эти столбцы не входят в базис.
Необходимо
жорданово исключение с разрешающим
элементом
.
Этот элемент выбирается из отрицательных элементов строки r так, чтобы базис остался оптимален (элементы z-строки неотрицательны):
после преобразования симплекс-таблицы элементы z-строки вычислим по формуле
Условие
эквивалентно неравенству
Если
(правая часть неположительна (
),
левая часть неотрицательна (
)),
то неравенство выполняется.
Если , то разделив обе части неравенства на этот элемент, получим
То есть, выбираем так, чтобы достигался максимум отношений
Новый
базис
– оптимален.
Решения для обоих базисов совпадают:
Получили альтернативный оптимальный базис для x*.