Лекция: Анализ устойчивости оптимального решения.

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

Возможность анализа влияния изменения ресурсов, т.е. bi, на устойчивость оптимального решения определяется свойством равенства целевых функций оптимальных планов исходной и двойственной задач:

max F = min Fд (2.27)

Заменяя правую часть в равенстве 2.27 на ее выражение в 2.26 получим:

Если последнюю формулу записать для наглядности в виде:

то видно, что двойственная переменная zi является коэффициентом при bi и, следовательно, показывает, как изменится целевая функция при изменении ресурса bi на единицу. Исходя из этого, в литературе по оптимизации двойственные переменные часто называют двойственными оценками.

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

Определить значение двойственных оценок можно следующим образом. Если некоторый i-ый ресурс используется не полностью, т.е. имеется его остаток, то дополнительная переменная yi в ограничении для данного ресурса будет больше нуля. В нашем примере таким ресурсом являются вспомогательные материалы, для которых b2=110 и остаток y2 = 26. совершенно очевидно, что если бы сырья было бы не 110 единиц, а 111, то остаток стал бы равен не 26, а 27. при этом не произошло бы увеличения целевой функции. Следовательно, для второго ограничения двойственная переменная z2 = 0. таким образом, если по ресурсу есть остаток, то дополнительная переменная будет больше нуля, а двойственная оценка этого ограничения равна нулю.

В рассматриваемом примере трудозатраты и комплектующие использовались полностью, поэтому их дополнительные переменные равны нулю. В таблице 2.9 переменные у1 и у3 являются свободными, значит у1=у3=0. если ресурс используется полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции и, следовательно, на величину целевой функции. В этом случае двойственные оценки будут больше нуля.

Значение двойственной оценки находится в симплексной таблице, соответствующей оптимальному варианту решения (табл 2.9), на пересечении строки целевой функции со столбцом данной дополнительной переменной. Для трудозатрат при у1=0 двойственная оценка z1=20, а для комплектующих при у3=0 двойственная оценка z3=10.

Из этого следует, что при трудозатрат на единицу, целевая функция увеличивается (уменьшается) на 20 единиц и будет равна:

при увеличении F = 1320+20*1 = 1340,

при уменьшении F = 1320-20*1 = 1300.

Аналогично обстоит дело и с комплектующими. При увеличении (уменьшении) затрат на них на единицу целевая функция будет равна:

при увеличении F = 1320+10*1 = 1330,

при уменьшении F = 1320-10*1 = 1310.

Рассмотрение подхода, обеспечивающего определение при помощи двойственных переменных возможных пределов изменения ресурсов, при условии сохранения анализируемого оптимального плана, будет рассмотрено на примере позднее.

Для оценки диапазона устойчивости оптимального варианта решения в зависимости от изменения величины сj (прибыль или иной выигрыш) используются дополнительные двойственные переменные. Для рассмотрения этой характеристики составим для задачи (2.) двойственную задачу:

Fд = 16z1+110z2+100z3 → min

z1+6z2+4z3 ≥ 60

z1+5z2+6z3 ≥ 70 (2.28)

z1+4z2+10z3 ≥ 120

z1+3z2+13z3 ≥ 130

zi ≥ 0; i = 1,2,3

Представим полученную модель в канонической форме записи, введя в ограничение (2.28), по аналогии с вводом дополнительных переменных yi дополнительные двойственные переменные vj:

Fд = 16z1+110z2+100z3 → min

z1+6z2+4z3-v1 = 60

z1+5z2+6z3-v2 = 70

z1+4z2+10z3-v3 = 120

z1+3z2+13z3-v4 =130

zi ≥ 0; vj ≥ 0; j = 1,2,3,4 i = 1,2,3

Значения дополнительных двойственных переменных также специально вычислять не надо. Их значения уже определены в симплексной таблице, приведенной применительно к рассматриваемой задаче в таблице 2.9. Фрагмент этой таблицы с обозначениями основных и дополнительных двойственных переменных показан в таблице 2.15, а их значения – в таблице 2.16.

Таблица 2.15 Таблица 2.16

Определим отсюда смысл дополнительных двойственных переменных. Если основные переменные (в нашем примере х1=10, х3=6) вошли в оптимальное решение, то их дополнительные двойственные переменные равны нулю (v1=0, v3=0). Если основные переменные не вошли в оптимальное решение, т.е. равны нулю (в примере х2=х4=0), то соответствующие им дополнительные двойственные переменные имеют положительное значение (v2=10, v4=20). Эти величины показывают, насколько уменьшится целевая функция при принудительном выпуске единицы данной продукции. Следовательно, если мы захотим принудительно выпустить единицу продукции Прод 2, то целевая функция F уменьшится на 10 единиц и будет равна 1320-10*1=1310.

В литературе по оптимизации дополнительная двойственная переменная часто называется редуцированной стоимостью.

а) Анализ влияния изменения ресурсов bi на устойчивость оптимального плана.

Рассмотрим влияние изменения ресурсов на примере оптимального плана (табл 2.9). Пусть произошло изменение ресурсов по трудозатратам на ∆b1. В этом случае ограничения относительно трудозатрат будет иметь вид:

х1+х2+х3+х4 ≤ 16+∆b1,

или, переходя к неравенству:

у1 = (16+∆b1)-(х1+х2+х3+х4).

При этом столбец свободных членов в исходной симплексной таблице будет иметь вид, показанный в таблице 2.17, а фрагмент таблицы с оптимальным решением – в таблице 2.18, из которой видно правило формирования значений плана:

Таблица 2.17 Таблица 2.18

В соответствии с признаком допустимости решение будет допустимым в том случае, если все элементы в плане будут неотрицательными. Значит, из таблицы 2.18 следует:

10+1,67∆b1 ≥ 0

26-7,73∆b1 ≥ 0

6-0,67∆b1 ≥ 0

Откуда можно получить:

Подставляя поочередно значения ∆b1 в столбец план и производя вычисления можно определить, что для сохранения структуры оптимального плана изменение трудовых ресурсов должно быть в пределах

-6 ≤ ∆b1 ≤ 3,55

Аналогично можно получить значения для ∆b3:

-36 ≤ ∆b3 ≤ 60

Переход от ∆bi к пределам bi производится по зависимостям

min bi = bi + min ∆bi

min bi = bi + max ∆bi

min bi ≤ bi ≤ max bi

Для b1 диапазон изменений составит:

min bi = 16-6=10

mах bi = 16+3,55=19,55

Обобщенно можно записать:

10 ≤ b1 ≤ 19,55

64 ≤ b3 ≤ 160

Найденные пределы показывают границы, в которых могут изменяться ресурсы, чтобы структура оптимального решения, т.е. номенклатура выпускаемой продукции, остались без изменений. А это означает, что при изменении трудозатрат в найденных пределах оптимальным, т.е. обеспечивающим наибольшую прибыль, является выпуск той же продукции х1 и х3, но в других количествах. При этом необходимо будет выпускать:

х1 = 10+1,67∆b1

х3 = 6-0,67∆b1

При этом целевая функция будет:

F = 1320+20∆b1

Аналогично для комплектующих полученные зависимости будут иметь вид:

х1 = 10-0,17∆b3

х3 = 6+0,17∆b3

F = 1320+10∆b3

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

∆b3 = 10

При этом получим:

х1 = 10-0,17*10 = 8,3

х3 = 6+0,17*10 = 7,7

В данном случае целевая функция будет:

F = 1320+10*10 = 1420

Видимо, было трудно представить, что увеличении средств на приобретение комплектующих для обеспечения максимизации прибыли выпуск продукции х1 целесообразно уменьшить, а выпуск продукции х3 – увеличить. Такое решение объясняется следующим. Как видно из условий задачи, прибыль от единицы продукции с3 = 120, т.е. единица продукции Прод3 в 120/60 = 2 раза дает большую прибыль по сравнению с единицей продукции Прод1. В связи с этим оказалось целесообразным такое перераспределение выпуска продукции.

б) Анализ влияния изменения прибыли cj на устойчивость оптимального плана.

В математической модели рассматриваемой задачи целевая функция равна:

F = 60х1+70х2+120х3+130х4 → max

Допустим, прибыль от продажи Прод1 с1 = 60 изменится на величину ∆с1 и станет:

с1 = 60

Таблица 2.19

При этом строка целевой функции в исходной симплексной таблице примет вид, как в таблице 2.19.

В результате поиска оптимального решения фрагмент последней симплексной таблицы будет иметь вид:

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

Применительно к рассматриваемой задаче решение будет оптимальным при условии:

20+1,67∆с1 ≥ 0

10+0,67∆с1 ≥ 0

10-0,17∆с1 ≥ 0

20-0,5∆с1 ≥ 0

Вычисляя построчно значения ∆с1 получим:

∆с1 ≥ -20/1,67 ≈ -11,97

∆с1 ≥ -10/0,67 ≈ -14,92

∆с1 ≤ -10/0,17 ≈ 59,8

∆с1 ≤ -20/0,5 = 40

Подставляя поочередно вычисленные значения в строку целевой функции определим диапазон изменения ∆с1:

-12 ≤ ∆с1 ≤ 40

Найденный диапазон определяет пределы изменения ∆с1 при которых сохраняется структура оптимального плана, т.е. будет выгодно по-прежнему выпускать продукция х1.

Нижний предел (в примере равный -11,97) называется допустимое уменьшение; верхний предел, равный 40 – допустимое увеличение.

Если от пределов приращенный ∆с1 перейти к пределам значения величины с1, то можно записать:

min c1 = c1 + max ∆с1 ≈ 60-12 = 48

max c1 = c1+ max ∆с1 = 60+40 = 100

Таким образом, при изменении с1 в пределах:

48 ≤ с1 ≤ 100

будет по-прежнему выгодно выпускать продукцию х1. При этом значение целевой функции будет:

F = 1320+10∆с1

Если выполнить аналогичное преобразование с с3, то получим:

-13,33 ≤ ∆с3 ≤ 30

И далее, аналогично рассмотренному выше, не трудно перейти к пределах изменение значений с3.

Рассмотрение приведенных примеров позволило увидеть на какие важные вопросы можно получить ответы с помощью двойственных и дополнительных двойственных переменных. Следует подчеркнуть, что все эти ответы могут быть получены без дополнительного решения двойственной задачи, а только используя оптимальный план исходной. Говоря о двойственных и дополнительных двойственных переменных, следует сказать о пределах, в которых справедливы полученные значения этих переменных. Пределы изменения ∆bi – есть пределы справедливости двойственных оценок zi, а пределы изменения ∆сj – это пределы справедливости дополнительных двойственных оценок vj.