Лабораторнаяработа № 4
ТелешовойЕлизаветы, гр. 726,Послеоптимизационный анализ задачлинейного программирования.1.Анализчувствительности оптимального решения задачи к изменению свободных членов ограничений.
Для изготовленияопределенного сплава из свинца, цинка и олова используется сырье из тех же металлов,отличающееся составом и стоимостью.
Сырье Содержание в процентах Компоненты
1
2
3
4
5
Свинец
10
10
40
60
70
Цинк
10
30
50
30
20
Олово
80
60
10
10
10
Стоимость, у. Е.
4
4,5
5,8
6
7,5
Определить, сколько нужновзять сырья каждого вида, чтобы изготовить с минимальной себестоимостью сплав,содержащий олова не более 30%, цинка не менее 10%,свинца не более 40%.
Математическая модель:
Пусть хi – доля сырья i-го вида в единице полученного сплава. Тогда функция цели (себестоимостьединицы сплава в у.е.) запишется следующим образом:
Система ограничений будетиметь вид:
Запишем систему в каноническом виде:
Оптимальная симплекс-таблица:
4
4,5
5,8
6
7,5
M
M
Св
Б.П.
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
В
4,5
X2
1,4
1
2
-0,2
0,4
X8
0,12
0,2
0,3
0,6
1
-0,46
0,12
5,8
X3
-0,4
1
1
1
-2
1,2
0,6
X7
0,12
0,2
0,3
-0,4
1
0,54
-1
0,32
F
-0,02
-0,2
-1,7
-2,6
-6,06
5,28
Оптимальное решение: и оптимальное значениецелевой функции:
Экономическиполученное решение интерпретируется следующим образом: для получения единицысплава минимальной себестоимости необходимо взять 40% сырья №2 и 60% сырья №3.При этом сплав содержит ровно 30% олова, более 20% (точнее, 42%) цинка и менее40% (28%) свинца. Минимальная себестоимость единицы сплава составляет 5,28 у.е.Оптимальные двойственные оценки
Теперь найдём областьустойчивости двойственных оценок к изменению свободных членов ограничений. Какизвестно, область устойчивости двойственных оценок – это область изменениясвободных членов ограничений, при которой двойственные оценки не меняются.Неизменность двойственных оценок говорит о том, что не меняют своих номеровбазисные и свободные переменные в решении.
В связи с вычислениеминтервалов устойчивости необходимо сделать замечание о знаках неравенств. Мыпомним, что изначально их изменение мы учитывали (), но знаки самихнеравенств не меняли. Сейчас мы также не будем менять знаки второго ичетвёртого неравенств, но примем во внимание обратный знак при расчёте конкретныхзначений. (Это делается для более наглядной экономической интерпретацииинтервалов устойчивости.)
Пусть свободные членыизменились на и соответственно. Тогдаоптимальное решение новой задачи (базисныекомпоненты) можно найти как:
Базисное решениевычисляется через матрицу, обратную к базисной, и свободные члены ограничений.Из оптимальной симплекс-таблицы получим матрицу, обратную к базисной, и оптимальноерешение (базисные компоненты):
>
Все элементы решениядолжны быть неотрицательны, иначе решение будет недопустимым, т.е. базисноерешение остаётся оптимальным до тех пор, пока оно допустимое. Область устойчивостиследующая:
Теперь найдём интервалыустойчивости (интервал устойчивости двойственных оценок к изменению правойчасти ограниченияили i-го ресурса – такое множество i–горесурса, при котором двойственные оценки не меняются):
1),:
=>
2),
=>
3),
=>
4),
=>
Полученные результатыэкономически означают, что свободный член в первом ограничении может менятьсяот 0,5 до 1,26, но экономического смысла это ни какого не имеет,т.к. сумма составляющих долей сплава всегда 100%. Содержание олова в новомсплаве варьируется от 10% до 60%,цинка – от нуля ( не имеет экономическойинтерпретации) до 42%и свинца – от 28% до 100% (аналогично случаюс цинком не может бытьобъяснена экономически). Возможны также различные комбинации изменений, которыеописывает область устойчивости (интервалы устойчивости являются своеобразнымичастными случаями области устойчивости). При данных изменениях ресурсовдвойственные оценки не изменятся, а значити номера базисных переменныхтакже не изменятся.
(4)
(1)
(2)
(3)
Изобразим область устойчивости двойственных оценок к изменению свободных членовограничений графически. Для этого, исходя из экономических соображений инаглядности графика, построим его в координатах и
Пример практического применения интервалов устойчивости.
Изменим условие задачи следующим образом:
а)содержание олова в новом сплаве не должно превосходить 15%;
Интервал устойчивости для олова – это 15% или 0,15 входят в этот интервал, следовательнодвойственные оценки не изменятся и оптимальное решение будет (при .
По третьей теореме двойственностинайдём значение критерия при этом решении:
=>
б)содержание цинка должно быть не менее 45%;
Интервал устойчивости дляцинка — .Т.к. содержание цинка в сплаве должно быть не более 42%, а т.к. 0,45 не входитв интервал устойчивости двойственных оценок, то двойственные оценки и номерабазисных переменных сменятся (
Решение недопустимое. Но если бы оно былодопустимым, то оно было бы и оптимальным, а значит, оценки бы удовлетворяликритерию оптимальности. Полученное решение является псевдопланом и можно использовать двойственныйсимплекс-метод.
4
4,5
5,8
6
7,5
Св
Б.П.
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
В
4,5
X2
1,4
1
2
-0,2
0,4
X8
0,12
0,2
0,3
0,6
1
-0,46
0,12
5,8
X3
-0,4
1
1
1
-2
1,2
0,6
X7
0,12
0,2
0,3
-0,4
1
0,54
-1
-0,03
F
-0,02
-0,2
-1,7
-2,6
-6,06
5,28
Определим, какую из переменных выведем из базиса. Вданном случае это будет единственная отрицательная переменная стандартныхпреобразований однократного замещения получим новую симплекс-таблицу:
4
4,5
5,8
6
7,5
Св
Б.П.
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
В
4,5
X2
2
1
1
1,5
5
2,5
-5
0,25
X8
0,3
0,5
0,75
1,5
1
0,35
-1,5
0,075
5,8
X3
-1
1
-0,5
-5
-1,5
5
0,75
X6
-0,3
-0,5
-0,75
1
-2,5
-1,35
2,5
0,075
F
-0,8
-1,5
-3,65
-6,5
2,55
6,5
5,475
Как видим, оценки по-прежнему удовлетворяюткритерию оптимальности и все базисные переменные неотрицательны, значит,решение допустимое и оптимальное. Новое решение задачи
в) вновом сплаве должно быть менее 40% олова и более 30% цинка;
Запишем область устойчивости двойственных оценок,учитывая новые изменения (; ):
Решение является допустимым, а значит, иоптимальным. Значение критерия найдём по третьей теореме двойственности:
=>
г)менее 60% олова и более40% цинка;
В данном случае изменения составляют: увеличениесодержания олова на 30% и цинка на 30%, т.е и
Решение недопустимое, но является псевдопланом,поэтому, руководствуясь рассуждениями, аналогичными пункту б), решим задачудвойственным симплекс-методом.
4
4,5
5,8
6
7,5
Св
Б.П.
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
В
4,5
X2
1,4
1
2
-0,2
0,4
X8
0,12
0,2
0,3
0,6
1
-0,46
0,12
5,8
X3
-0,4
1
1
1
-2
1,2
0,6
X7
0,12
0,2
0,3
-0,4
1
0,54
-1
-0,1
F
-0,02
-0,2
-1,7
-2,6
-6,06
5,28
Оптимальная симплекс-таблица:
4
4,5
5,8
6
7,5
Св
Б.П.
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
В
4,5
X2
2
1
1
1,5
5
2,5
-5
0.5
X8
0,3
0,5
0,75
1,5
1
0,35
-1,5
0,15
5,8
X3
-1
1
-0,5
-5
-1,5
5
0,5
X6
-0,3
-0,5
-0.75
1
-2.5
-1.35
2,5
0,25
F
-0,8
-1,5
-3,65
-6,5
2,55
6,5
5,15
Получим следующее решение: 50% сырья №2 и 50% сырья №3.
Задача анализа дополнительно закупаемых объёмов ресурсов с цельюобеспечения наибольшей эффективности планирования.
Предположим, что появилась возможность покупатьсырьё у других поставщиков по более низкой цене: цинк по 2 у.е., а за олово исвинец, т.к. согласно экономическому смыслу задачи они являются «антиблагами»,мы получаем большую доплату от их поставщика: 1,5 у.е. и 0,5 у.е. соответственно.Руководитель предприятия выделил на закупку ресурсов 3 у.е.
Решение:
По ранее полученным результатам мы знаем, чтопредприятие тратит минимум средств (5,28 у.е.) когда в полученном сплаве ровно30% олова, 42% цинка и 28% свинца (будем считать для удобства, что дляпроизводства 10 тонн сплава необходимо 3 тонны олова, 4,2 тонны цинка и 2,8тонн свинца). Т.к. олово и свинец мы получаем с доплатой, то возьмём их вполном объёме, необходимом для производства сплава. От «покупки»олова мы получим
Будем вести анализ закупок цинка. На первойитерации мы не закупаем цинк, т.к. в этом случае он бы приносил больше убытка(двойственная оценка равна нулю по сравнению с предлагаемой ценой в 2 у.е.).Решив новую задачу без производства олова и свинца, мы безусловно выйдем заграницы области устойчивости двойственных оценок. Кроме того, сменится решение:двойственная оценка цинка увеличится до 3 и новое значение целевой функциипонизится до 4 у.е. Вычтем из этих затрат на производство сплава доход отполучения олова и цинка:
С увеличением двойственной оценки цинка становитсявыгодно покупать его. Но мы располагаем суммой денег только 3 у.е. и можем закупитьна них 1,5 тонн вместо 2 необходимых. Теперь нам нужно производить только 0,5тонны цинка. На второй итерации мы получаем такое же решение: критерий равен 4у.е. и двойственная оценка цинка, которого мы производим 3 тонны, равна 4.
Таким образом, мы получили оптимальное решениерасходования выделенных 3 у.е.: «закупать» с доплатой 4 тонны олова и5 тонн свинца и покупать по цене 2 у.е. 1,5 тонны цинка. При таком плане предприятиеполучит прибыль от производства сплава в размере 1,9 у.е.2.Анализ чувствительностиоптимального решения задачи к изменению коэффициентов целевой функции.
Определим интервал устойчивости решения к изменениюстоимости сырья, то есть, в каких пределах могут меняться цены на сырьё, чтобыплан выпуска сплава не изменился. Для этого рассмотрим два случая: изменениецен (коэффициентов целевой функции) происходит на сырьё, использующееся припроизводстве сплава (базисные переменные) и не использующееся (свободныепеременные).
1.Пусть, сначала, меняется цена второго и третьего ресурсов (базисныепеременные).
а)
Тогда оптимальнаясимплекс-таблица будет иметь вид:
4
4,5
5,8
6
7,5
Св
Б.П.
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
В
4,5
X2
1,4
1
2
-0,2
0,4
X8
0,12
0,2
0,3
0,6
1
-0,46
0,12
5,8
X3
-0,4
1
1
1
-2
1,2
0,6
X7
0,12
0,2
0,3
-0,4
1
0,54
-1
0,32
F
Для того, чтобы решениеоставалось оптимальным, необходимо, чтобы все оценки были неположительными (длязадачи на минимум):
=>
Это значит, что ценапервого ресурса может меняться от нуля (бесплатный, недефицитный ресурс) до 4,514 у.е. (отрицательный коэффициент вцелевой функции в данном случае не имеет экономического смысла, т.к.свидетельствует о получении ресурса с доплатой. В этом случае ресурс выступаетв роли антиблага). Критерий изменится на
б)
4
4,5
5,8
6
7,5
Св
Б.П.
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
В
4,5
X2
1,4
1
2
-0,2
0,4
X8
0,12
0,2
0,3
0,6
1
-0,46
0,12
5,8