Рассмотрим влияние изменения Bi = Bi + q для некоторого 1 <= i <= m Обычно принято рассматривать случай, когда компонента Bi является правой частью ограничения-неравенства в которое введена дополнительная переменная. Мы хотим определить такой диапазон изменения Bi в котором текущее решение остается оптимальным. В случае ограничения-равенства мы могли бы рассматривать соответствующую искусственную переменную как неотрицательную дополнительную (которая должна быть небазисной в допустимом решении)
а) Базисная дополнительная переменная
Если дополнительная переменная i-го ограничения базисная то это ограничение не является активным в точке оптимума. Анализ прост: значение дополнительной базисой переменной дает диапазон изменения, в котором соответствующая компонента Bi уменьшается (увеличивается в случае ограничения типа =>).
Решение остается допустимым и оптимальным в диапазоне Bi + q, где
-Xs <= q <= +oo для ограничений типа <=
-oo <= q <= Xs для ограничений типа =>
Здесь Xs - значение соответствующей дополнительной переменной. Например рассмотрим ограничение-неравенство:
3X1 + 4X2 + 7X3 <= 100
Приведем его к равенству введя дополнительную переменную
3X1 + 4X2 + 7X3 + X4 = 100
Если в оптимальном решении X4 = 26 то оставшиеся переменные удовлетворяют неравенству:
3X1 + 4X2 + 7X3 <= 74
а также любому неравенству того же вида со значением правой части большим 74.
б) Небазисная дополнительная переменная
Если дополнительная переменная небахзисная и равна нулю, то исходное ограничение-неравенство является активным в точке оптимума. На первый взгляд может показаться что так как это ограничение активное то отсутствует возможность изменения значения правой части такого ограничения, в частности возможность уменьшения значения Bi (для ограничений типа <=). Оказывается что изменяя вектор В мы меняем также вектор Xb и так как существует диапазон изменений в котором Xb неотрицателен, то решение остается еще и оптимальным в том смысле, что базис не меняется. (Заметим что при этом изменяется значение как Xb так и Р).
|
|
Рассмотрим ограничение:Ak1X1+Ak2X2 +... +Xs = Bk где Xs - дополнительная переменная. Пусть теперь правая часть станет равной Bk + q, тогда уравнение можно переписать так: 1. 1) Ak1X1+Ak2X2 +... +(Xs-q) = Bk
Так что (Xs - q) заменяет Xs Следовательно, если в оптимальном решении переменная Xs небазисная и равна нулю то мы имеем Xb = B - As*(-q) где As - столбец конечной таблицы соответствующий Xs. Так как Xs должен оставаться неотрицательным то мы получаем соотношение: B - As*(-q) => 0 которое определяет диапазон изменения q:
MAX {Bi/-Ais} <= q <= MIN {Bi/-Ais}
i/Ais>0 i/Ais<0
Если нет ни одного Ais > 0 то q > -oo,
а если нет ни одного Ais < 0 то q < +oo
Для ограничений типа => q меняет знак, так как вместо неравенства E AijXj => Bi мы можем рассматривать
-E AijXj <= -Bi
Поэтому в уравнении 1. 1) вместо +(Xs-q) мы должны писать -(Xs+q).
Снова рассмотрим пример:
Максимизировать Р= 31. 5 -3. 5X4 -0. 1X3 -0. 25X
При условиях X1 = 3. 2 -1. 0X4 -0. 5X3 -0. 60X5
X2 = 1. 5 +0. 5X4 +1. 0X3 -1. 00X5
X6 = 5. 6 -2. 0X4 -0. 5X3 -1. 00X5
Пусть X4 - дополнительная переменная некоторого ограничения i (типа <=). Если компонену Bi изменить на величину q, мы получим:
X1 = 3. 2 - 1. 0*(-q)
X2 = 1. 5 + 0. 5*(-q)
X6 = 5. 6 - 2. 0*(-q)
3. 2 1. 0
то есть B = 1. 5 As = -0. 5
5. 6 2. 0
Тогда,
X1 => 0 при 3. 2 - 1. 0*(-q) => 0, то есть q => 3. 2/-1. 0,
X2 => 0 при 1. 5 + 0. 5*(-q) => 0, то еасть q <= 1. 5/0. 5,
|
|
X6 => 0 при 5. 6 - 2. 0*(-q) => 0, то есть q => 5. 6/-2. 0
Значит q может меняться в диапазоне:
MAX {3. 2/-1. 0; 5. 6/-2. 0} <= q <= 1. 5/0. 5, то есть -2. 8 <= q <= 3. 0
ВЫРОЖДЕННОСТЬ
1. Вырожденность прямой задачи
Вырожденное решение прямой задачи характеризуется тем, что его базисная компонента равна нулю. Вырожденность прямой задачи может часто проявляться через промежуточные (неоптимальные) вырожденые базисные решения. Так например не произойдет улучшения целевой функции от введения в базис переменной, для которой положительна соответствующая компонента вектор а Aq.
Возможен случай, когда прямая задача ЛП имеет вырожденое промежуточное но невырожденное оптимальое решение. Если оптимально решение прямой задачи вырождено, то двойственная задача имеет бесконечно много оптимальных решеий.
2. Вырожденность двойственой задачи
С вырожденностью двойственной задачи мы сталкиваемся, когда относительная оценка, отвечающая небазисной переменной, равна нулю.
Это означает, что небазисная переменная может увеличиваться, не меняя при этом значения целевой функции. Если такая нулевая относительная оценка соответствует оптимальному решению, то имеется множество оптимальных решений так как Р не меняется). Заметим, что мы получили вырожденное решение двойственной задачи, отвечающее границе диапазоа устойчивости коэффициента целевой функции, а также вырожденное решение прямой задачи соответствующее границе диапазона устойчивости компоненты вектора ограничений.
Как пример источника ценной информации, получаемой при постоптимальном анализе, рассмотрим следующую производственную задачу. Предприятие по переработке руды производит два сорта очищенной продукции, которая продается предприятиям металлургической промышленности. Схема работы предприятия выглядит следующим образом.
|
|
Перерабатываются два вида руды: А и В. Заводу может быть поставлено до 100 тыс. т в день руды вида А по цене 3. 25 долл/т и д 30 тыс. т в день руды вида В более высокого качества по цене 3. 40 долл/т. Общая мощность основного процесса переработки равна 100 тыс. т руды в день при затратах на переработку 0. 35 долл. /т.
Основной процесс переработки позволяет получить из каждой тонны руды вида А 0. 15 т продукта 1 и 0. 85 т продукта 2, а из каждой тонны руды вида В 0. 25 т продукта 1 и 0. 75 т продукта 2.
Продукт 1 более ценный, и агрегат, называемый конвертером, способен из каждой тонны продукта 2 получить 0. 5 т продукта 1 и 0. 5 т продукта, который может быть продан как продукт 2, но который нельзя повторно перерабатывать конвертером. Мощность конвертера 50 тыс. т сырья в день при затратах на конвертерную обработку 0. 25 долл/т сырья. Условия реализации следующие. Продукт 2 может быть продан в неограниченном количестве по цене 3. 8 долл/т, продукт 1 продается по цене 5. 5 долл/т и его можно продать по этой цене до 45 тыс. т/день. Существующий контракт требует, чтобы менее 40 тыс. т/день продукта 1. Запасы продукта 1 могут увеличиваться со скоростью 4 тыс. т/день и эти запасы оцениваются из расчета 5. 20 долл/т. Излишек продукта 1 может быть продан в неограниченном количестве по пониженной цене равной 5. 0 долл/т. Оба продукта можно при необходимости докупить: закупочная цена продукта 1 равна 5. 75 долл/т; закупочная цена продукта 2 равна 4. 0 долл/т.
Для построения модели введем следующие обозначения переменных:
X1 - количество переработанной руды вида А
X2 - количество переработанной руды вида В
X3 - количество докупленного продукта 1
X4 - количество докупленного продукта 2
X5 - количество продукта 2 переработанного в конвертере
X6 - количество продукта 1 на складе
X7 - количество продукта 1 проданного по пониженной цене
X8 - дополнительная переменная ограничения на используемые ресурсы руды вида В (<=30)
X9 - дополнительная переменная условия, ограничивающего сверху количество продукта 1 которое можно продать по обычной цене (<=45)
X10 - дополнительная переменная условия, ограничивающего снизу количество продукта 1 которое можно продать по обычной цене (<=40)
X11 - дополнительная переменная условия, ограничивающего сверху объем складируемого запаса продукта 1 (<=4)
X12 - дополнительная переменная условия, ограничивающего сверху мощность основного процесса обработки (<=100)
X13 - дополнительная переменная условия, ограничивающего сверху мощность конвертера (<=50)
X14 - излишек продукта 2, который идет непосредственно на продажу не проходя конвертерной обработки
Ограничения
0. 15X1 + 0. 25X2 + X3 + 0. 5X5 - X6 - X7 + X9 = 45 [ 1 ]
0. 15X1 + 0. 25X2 + X3 + 0. 5X5 + X6 - X7 - X10 = 40 [ 2 ]
X2 + X8 = 30 [ 3 ]
X6 + X11 = 4 [ 4 ]
X1 + X2 + X12 = 100 [ 5 ]
X5 + X13 = 50 [ 6 ]
- 0. 85X1 - 0. 75X2 - X4 + X5 + X4 = 0 [ 7 ]
Целевая функция
5. 50*(0. 15X1 + 0. 25X2 + 0. 5X5) + 3. 80*(0. 85X1 + 0. 75X2 - 0. 5X5)
- 0. 35*(X1 + X2) - 3. 25X1 - 3. 40X2 - 0. 25X5 - 0. 1*(0. 15X1 +
0. 25X2) - 0. 25X3 - 0. 20X4 - 0. 30X6 - 0. 5X7 - MAX
0. 825X1 + 1. 375X2 + 2. 750X5 + 3. 230X1 + 2. 85X2 - 1. 9X5 - 0. 35X1
- 0. 35X2 - 3. 25X1 - 3. 40X2 - 0. 25X5 - 0. 015X1 - 0. 025X2 - 0. 25X3
- 0. 20X4 - 0. 30X6 - 0. 5X7 -> MAX
0. 44X1 + 0. 45X2 + 0. 6X5 - 0. 25X3 - 0. 2X4 - 0. 3X6 - 0. 5X7 -> MAX
Оценки ресурсов
Оценка ограничения на мощность основного процесса переработки равна 0. 44 долл/т (относительная оценка, соответствующая переменной X12 равна 0. 44). Эта оценка справедлива в диапазоне изменения мощности основного процесса определяемом выражением 100 + q, где MAX { 3/-0. 15; 70/-1; 32/-0. 85 } <= q <= MIN { 2/0. 15 } отсюда -20 <= q <= 13. 33
Таким образом, текущий доход можно увеличить на 0. 44 долл. за каждую тонну увеличения мощности основого процесса обработки, если будем увеличивать эту мощность лишь до 113, 33 тыс. т/день.
Оценка ограничения на мощность конвертера равна 0. 6 долл/т (относительная оценка, соответствующая переменной X13 равна 0. 6) Эта оценка справедлива в диапазоне изменения 50 + q, где MAX { 3/-0. 5; 50/-1 } <= q <= MIN { 2/0. 5 } отсюда -6 <= q <= 4
Таким образом, текущий доход можно увеличит на 0. 6 долл. за каждую тонну увеличения мощности конвертера, если будем увеличивать эту мощность лишь до 54 тыс. т/день.
Маргинальная оценка
Маргинальная оценка руды В равна 0. 01 долл/т и справедлива в диапазоне 30 + q, где MAX { 3/-0. 1; 30/-1 } <= q <= MIN { 2/0. 1; 70/1; 32/0. 1 } отсюда -30 <= q <= 20
Если лq = -30, то X2=0, то есть руда вида В закупаться не будет. Если q = 20, то X2=50, то есть можно покупать до 50 тыс. т руды В в день.
Можно сделать вывод, что мы получим чистый доход по 0. 01 долл. за каждую тонну руды вида В, купленную сверх 30 тыс. т/день, при условии, что общее количество покупаемой руды этого вида не превысит преела 50 тыс. т/день, при котором меняется маргинальная оценка из-за изменения базиса. Точно так же мы потеряем по 0. 01 долл. за каждую недостающую тонну руды вида В, если мы будем покупать меньше 30 тыс. т/день. Мы можем рассуждать иначе, а именно, что мы могли бы вести переговоры о дополнительной закупке руды вида В сверх 30 т/день (но не более чем на 20 тыс. т/день) по цене до
3. 40 + 0. 01 = 3. 41 долл/т.