АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Их решение.
  2. Решение.
  3. Решение.
  4. Решение.
  5. Решение.
  6. Решение.
  7. Решение.
  8. Решение.
  9. Решение.
  10. Решение.

 

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

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

 

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

 

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

 

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

xj → max при A 0 x = b 0, x0.

 

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

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

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

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

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

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

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

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

 

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

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

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

 

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

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

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

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

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

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


1 | 2 | 3 | 4 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)