Реферат: Лабораторная работа №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

еще рефераты
Еще работы по теории систем управления