Вырожденное решение

Рассматривается задача P в канонической форме:

f ₀(x) = c ⁰ · x → max при A ⁰ x = b ⁰, x ≥ 0.

Пусть x ^* – некоторое вырожденное базисное оптимальное решение с базисом β и базисной матрицей B.

Определение: Переменную назовем существенной для задачи P, если существует допустимое решение задачи, в котором эта переменная имеет положительное значение.

Для определения существенности решается задача ЛП:

x_j → max при A ⁰ x = b ⁰, x ≥ 0.

Утверждение: Если x ^* –вырожденное оптимальное решение задачи P и хотя бы одна базисная переменная, имеющая в x ^* нулевое значение, существенна, то x ^* имеет альтернативный оптимальный базис.

Доказательство:

Рассмотрим симплекс-таблицу, полученную приведением задачи P к базису β. Все элементы в z -строке неотрицательны (так как базис оптимален) и для .

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

Уравнение с номером :

Вектор x ^* удовлетворяет этому уравнению, так как допустим. Так как и небазисные компоненты равны нулю, то .

Если для всех j, то в левой части значение неотрицательно и равно нулю при . Это противоречит существенности переменной . Поэтому существуют j для которых . Эти столбцы не входят в базис.

Необходимо жорданово исключение с разрешающим элементом .

Этот элемент выбирается из отрицательных элементов строки r так, чтобы базис остался оптимален (элементы z -строки неотрицательны):

после преобразования симплекс-таблицы элементы z -строки вычислим по формуле

Условие эквивалентно неравенству

Если (правая часть неположительна (), левая часть неотрицательна ()), то неравенство выполняется.

Если , то разделив обе части неравенства на этот элемент, получим

То есть, выбираем так, чтобы достигался максимум отношений

Новый базис – оптимален.

Решения для обоих базисов совпадают:

Получили альтернативный оптимальный базис для x ^*.

Поиск по сайту: