Реферат: Лабораторная работа №4 по "Основам теории систем" (Послеоптимизационный анализ задач линейного программирования)
Лабораторнаяработа № 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-го вида в единице полученного сплава. Тогда функция цели (себестоимостьединицы сплава в у.е.) запишется следующим образом:
<img src="/cache/referats/9001/image002.gif" v:shapes="_x0000_i1025">
Система ограничений будетиметь вид:
<img src="/cache/referats/9001/image004.gif" v:shapes="_x0000_i1026">
Запишем систему в каноническом виде:
<img src="/cache/referats/9001/image006.gif" v:shapes="_x0000_i1027">
Оптимальная симплекс-таблица:
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
Оптимальное решение: <img src="/cache/referats/9001/image008.gif" v:shapes="_x0000_i1028"> и оптимальное значениецелевой функции: <img src="/cache/referats/9001/image010.gif" v:shapes="_x0000_i1029">
Экономическиполученное решение интерпретируется следующим образом: для получения единицысплава минимальной себестоимости необходимо взять 40% сырья №2 и 60% сырья №3.При этом сплав содержит ровно 30% олова, более 20% (точнее, 42%) цинка и менее40% (28%) свинца. Минимальная себестоимость единицы сплава составляет 5,28 у.е.Оптимальные двойственные оценки <img src="/cache/referats/9001/image012.gif" v:shapes="_x0000_i1030">
Теперь найдём областьустойчивости двойственных оценок к изменению свободных членов ограничений. Какизвестно, область устойчивости двойственных оценок – это область изменениясвободных членов ограничений, при которой двойственные оценки не меняются.Неизменность двойственных оценок говорит о том, что не меняют своих номеровбазисные и свободные переменные в решении.
В связи с вычислениеминтервалов устойчивости необходимо сделать замечание о знаках неравенств. Мыпомним, что изначально их изменение мы учитывали (< на >), но знаки самихнеравенств не меняли. Сейчас мы также не будем менять знаки второго ичетвёртого неравенств, но примем во внимание обратный знак <img src="/cache/referats/9001/image014.gif" v:shapes="_x0000_i1031"> при расчёте конкретныхзначений. (Это делается для более наглядной экономической интерпретацииинтервалов устойчивости.)
Пусть свободные членыизменились на <img src="/cache/referats/9001/image016.gif" v:shapes="_x0000_i1032"><img src="/cache/referats/9001/image018.gif" v:shapes="_x0000_i1033"><img src="/cache/referats/9001/image020.gif" v:shapes="_x0000_i1034"> и <img src="/cache/referats/9001/image022.gif" v:shapes="_x0000_i1035"> соответственно. Тогдаоптимальное решение новой задачи (базисныекомпоненты) можно найти как:
<img src="/cache/referats/9001/image024.gif" v:shapes="_x0000_i1036">
Базисное решениевычисляется через матрицу, обратную к базисной, и свободные члены ограничений.Из оптимальной симплекс-таблицы получим матрицу, обратную к базисной, и оптимальноерешение (базисные компоненты):
<img src="/cache/referats/9001/image026.gif" v:shapes="_x0000_i1037">><img src="/cache/referats/9001/image028.gif" v:shapes="_x0000_i1038">
Все элементы решениядолжны быть неотрицательны, иначе решение будет недопустимым, т.е. базисноерешение остаётся оптимальным до тех пор, пока оно допустимое. Область устойчивостиследующая:
<img src="/cache/referats/9001/image030.gif" v:shapes="_x0000_i1039">
Теперь найдём интервалыустойчивости (интервал устойчивости двойственных оценок к изменению правойчасти ограниченияили i-го ресурса – такое множество i–горесурса, при котором двойственные оценки не меняются):
1)<img src="/cache/referats/9001/image032.gif" v:shapes="_x0000_i1040">,<img src="/cache/referats/9001/image034.gif" v:shapes="_x0000_i1041">:
<img src="/cache/referats/9001/image036.gif" v:shapes="_x0000_i1042"> => <img src="/cache/referats/9001/image038.gif" v:shapes="_x0000_i1043"><img src="/cache/referats/9001/image040.gif" v:shapes="_x0000_i1044">
2)<img src="/cache/referats/9001/image042.gif" v:shapes="_x0000_i1045">,<img src="/cache/referats/9001/image044.gif" v:shapes="_x0000_i1046">
<img src="/cache/referats/9001/image046.gif" v:shapes="_x0000_i1047"> => <img src="/cache/referats/9001/image048.gif" v:shapes="_x0000_i1048"><img src="/cache/referats/9001/image050.gif" v:shapes="_x0000_i1049">
3)<img src="/cache/referats/9001/image052.gif" v:shapes="_x0000_i1050">,<img src="/cache/referats/9001/image054.gif" v:shapes="_x0000_i1051">
<img src="/cache/referats/9001/image056.gif" v:shapes="_x0000_i1052"> => <img src="/cache/referats/9001/image058.gif" v:shapes="_x0000_i1053"><img src="/cache/referats/9001/image060.gif" v:shapes="_x0000_i1054">
4)<img src="/cache/referats/9001/image062.gif" v:shapes="_x0000_i1055">,<img src="/cache/referats/9001/image064.gif" v:shapes="_x0000_i1056">
<img src="/cache/referats/9001/image066.gif" v:shapes="_x0000_i1057"> => <img src="/cache/referats/9001/image068.gif" v:shapes="_x0000_i1058"><img src="/cache/referats/9001/image070.gif" v:shapes="_x0000_i1059">
Полученные результатыэкономически означают, что свободный член в первом ограничении может менятьсяот 0,5 до 1,26, но экономического смысла это ни какого не имеет,т.к. сумма составляющих долей сплава всегда 100%. Содержание олова в новомсплаве варьируется от 10% до 60%,цинка – от нуля (<img src="/cache/referats/9001/image072.gif" v:shapes="_x0000_i1060"> не имеет экономическойинтерпретации) до 42%и свинца – от 28% до 100% (аналогично случаюс цинком <img src="/cache/referats/9001/image074.gif" v:shapes="_x0000_i1061"> не может бытьобъяснена экономически). Возможны также различные комбинации изменений, которыеописывает область устойчивости (интервалы устойчивости являются своеобразнымичастными случаями области устойчивости). При данных изменениях ресурсовдвойственные оценки не изменятся, а значити номера базисных переменныхтакже не изменятся.
(4)
(1)
(2)
(3)
<img src="/cache/referats/9001/image078.gif" v:shapes="_x0000_s1063 _x0000_s1027 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043 _x0000_s1044 _x0000_s1045 _x0000_s1046 _x0000_s1047 _x0000_s1048 _x0000_s1049 _x0000_s1050 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1056 _x0000_s1057 _x0000_s1058 _x0000_s1059 _x0000_s1060 _x0000_s1061 _x0000_s1062">Изобразим область устойчивости двойственных оценок к изменению свободных членовограничений графически. Для этого, исходя из экономических соображений инаглядности графика, построим его в координатах <img src="/cache/referats/9001/image080.gif" v:shapes="_x0000_i1062"> и <img src="/cache/referats/9001/image082.gif" v:shapes="_x0000_i1063"><img src="/cache/referats/9001/image084.gif" v:shapes="_x0000_i1064">
<img src="/cache/referats/9001/image086.gif" v:shapes="_x0000_i1065"> <img src="/cache/referats/9001/image088.gif" v:shapes="_x0000_i1066">
Пример практического применения интервалов устойчивости.
Изменим условие задачи следующим образом:
а)содержание олова в новом сплаве не должно превосходить 15%;
Интервал устойчивости для олова – это <img src="/cache/referats/9001/image090.gif" v:shapes="_x0000_i1067"> 15% или 0,15 входят в этот интервал, следовательнодвойственные оценки не изменятся и оптимальное решение будет (при <img src="/cache/referats/9001/image092.gif" v:shapes="_x0000_i1068">.
<img src="/cache/referats/9001/image094.gif" v:shapes="_x0000_i1069">
По третьей теореме двойственностинайдём значение критерия при этом решении:
<img src="/cache/referats/9001/image096.gif" v:shapes="_x0000_i1070"> => <img src="/cache/referats/9001/image098.gif" v:shapes="_x0000_i1071">
б)содержание цинка должно быть не менее 45%;
Интервал устойчивости дляцинка — <img src="/cache/referats/9001/image100.gif" v:shapes="_x0000_i1072">.Т.к. содержание цинка в сплаве должно быть не более 42%, а т.к. 0,45 не входитв интервал устойчивости двойственных оценок, то двойственные оценки и номерабазисных переменных сменятся (<img src="/cache/referats/9001/image102.gif" v:shapes="_x0000_i1073">
<img src="/cache/referats/9001/image104.gif" v:shapes="_x0000_i1074">
Решение недопустимое. Но если бы оно былодопустимым, то оно было бы и оптимальным, а значит, оценки бы удовлетворяликритерию оптимальности. Полученное решение является псевдопланом и можно использовать двойственныйсимплекс-метод.
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
Определим, какую из переменных выведем из базиса. Вданном случае это будет единственная отрицательная переменная <img src="/cache/referats/9001/image106.gif" v:shapes="_x0000_i1077"><img src="/cache/referats/9001/image108.gif" v:shapes="_x0000_i1078"> стандартныхпреобразований однократного замещения получим новую симплекс-таблицу:
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
Как видим, оценки по-прежнему удовлетворяюткритерию оптимальности и все базисные переменные неотрицательны, значит,решение допустимое и оптимальное. Новое решение задачи <img src="/cache/referats/9001/image110.gif" v:shapes="_x0000_i1079"><img src="/cache/referats/9001/image112.gif" v:shapes="_x0000_i1080">
в) вновом сплаве должно быть менее 40% олова и более 30% цинка;
Запишем область устойчивости двойственных оценок,учитывая новые изменения (<img src="/cache/referats/9001/image114.gif" v:shapes="_x0000_i1081">; <img src="/cache/referats/9001/image116.gif" v:shapes="_x0000_i1082">):
<img src="/cache/referats/9001/image118.gif" v:shapes="_x0000_i1083">
Решение является допустимым, а значит, иоптимальным. Значение критерия найдём по третьей теореме двойственности:
<img src="/cache/referats/9001/image120.gif" v:shapes="_x0000_i1084"> => <img src="/cache/referats/9001/image122.gif" v:shapes="_x0000_i1085">
г)менее 60% олова и более40% цинка;
В данном случае изменения составляют: увеличениесодержания олова на 30% и цинка на 30%, т.е <img src="/cache/referats/9001/image124.gif" v:shapes="_x0000_i1086"> и <img src="/cache/referats/9001/image126.gif" v:shapes="_x0000_i1087">
<img src="/cache/referats/9001/image128.gif" v:shapes="_x0000_i1088">
Решение недопустимое, но является псевдопланом,поэтому, руководствуясь рассуждениями, аналогичными пункту б), решим задачудвойственным симплекс-методом.
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
Получим следующее решение: <img src="/cache/referats/9001/image130.gif" v:shapes="_x0000_i1089"><img src="/cache/referats/9001/image132.gif" v:shapes="_x0000_i1090">50% сырья №2 и 50% сырья №3.
Задача анализа дополнительно закупаемых объёмов ресурсов с цельюобеспечения наибольшей эффективности планирования.
Предположим, что появилась возможность покупатьсырьё у других поставщиков по более низкой цене: цинк по 2 у.е., а за олово исвинец, т.к. согласно экономическому смыслу задачи они являются «антиблагами»,мы получаем большую доплату от их поставщика: 1,5 у.е. и 0,5 у.е. соответственно.Руководитель предприятия выделил на закупку ресурсов 3 у.е.
Решение:
По ранее полученным результатам мы знаем, чтопредприятие тратит минимум средств (5,28 у.е.) когда в полученном сплаве ровно30% олова, 42% цинка и 28% свинца (будем считать для удобства, что дляпроизводства 10 тонн сплава необходимо 3 тонны олова, 4,2 тонны цинка и 2,8тонн свинца). Т.к. олово и свинец мы получаем с доплатой, то возьмём их вполном объёме, необходимом для производства сплава. От «покупки»олова мы получим <img src="/cache/referats/9001/image134.gif" v:shapes="_x0000_i1091"><img src="/cache/referats/9001/image136.gif" v:shapes="_x0000_i1092">
Будем вести анализ закупок цинка. На первойитерации мы не закупаем цинк, т.к. в этом случае он бы приносил больше убытка(двойственная оценка равна нулю по сравнению с предлагаемой ценой в 2 у.е.).Решив новую задачу без производства олова и свинца, мы безусловно выйдем заграницы области устойчивости двойственных оценок. Кроме того, сменится решение:двойственная оценка цинка увеличится до 3 и новое значение целевой функциипонизится до 4 у.е. Вычтем из этих затрат на производство сплава доход отполучения олова и цинка: <img src="/cache/referats/9001/image138.gif" v:shapes="_x0000_i1093">
С увеличением двойственной оценки цинка становитсявыгодно покупать его. Но мы располагаем суммой денег только 3 у.е. и можем закупитьна них 1,5 тонн вместо 2 необходимых. Теперь нам нужно производить только 0,5тонны цинка. На второй итерации мы получаем такое же решение: критерий равен 4у.е. и двойственная оценка цинка, которого мы производим 3 тонны, равна 4.
Таким образом, мы получили оптимальное решениерасходования выделенных 3 у.е.: «закупать» с доплатой 4 тонны олова и5 тонн свинца и покупать по цене 2 у.е. 1,5 тонны цинка. При таком плане предприятиеполучит прибыль от производства сплава в размере 1,9 у.е.
2.Анализ чувствительностиоптимального решения задачи к изменению коэффициентов целевой функции.Определим интервал устойчивости решения к изменениюстоимости сырья, то есть, в каких пределах могут меняться цены на сырьё, чтобыплан выпуска сплава не изменился. Для этого рассмотрим два случая: изменениецен (коэффициентов целевой функции) происходит на сырьё, использующееся припроизводстве сплава (базисные переменные) и не использующееся (свободныепеременные).
1.Пусть, сначала, меняется цена второго и третьего ресурсов (базисныепеременные).
а)<img src="/cache/referats/9001/image140.gif" v:shapes="_x0000_i1094">
Тогда оптимальнаясимплекс-таблица будет иметь вид:
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
<img src="/cache/referats/9001/image142.gif" v:shapes="_x0000_i1095">
<img src="/cache/referats/9001/image144.gif" v:shapes="_x0000_i1096">
<img src="/cache/referats/9001/image146.gif" v:shapes="_x0000_i1097">
<img src="/cache/referats/9001/image148.gif" v:shapes="_x0000_i1098">
<img src="/cache/referats/9001/image150.gif" v:shapes="_x0000_i1099">
<img src="/cache/referats/9001/image152.gif" v:shapes="_x0000_i1100">
Для того, чтобы решениеоставалось оптимальным, необходимо, чтобы все оценки были неположительными (длязадачи на минимум):
<img src="/cache/referats/9001/image154.gif" v:shapes="_x0000_i1101"> => <img src="/cache/referats/9001/image156.gif" v:shapes="_x0000_i1102"><img src="/cache/referats/9001/image158.gif" v:shapes="_x0000_i1103">
Это значит, что ценапервого ресурса может меняться от нуля (бесплатный, недефицитный ресурс) до 4,514 у.е. (отрицательный коэффициент вцелевой функции в данном случае не имеет экономического смысла, т.к.свидетельствует о получении ресурса с доплатой. В этом случае ресурс выступаетв роли антиблага). Критерий изменится на <img src="/cache/referats/9001/image160.gif" v:shapes="_x0000_i1104">
<span Times New Roman",«serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">б) <img src="/cache/referats/9001/image162.gif" v:shapes="_x0000_i1105">
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