Реферат: Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного программирования)

Лабораторнаяработа № 3

ТелешовойЕлизаветы, гр. 726,

Теория двойственности в задачах линейногопрограммирования.Задача:

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

Сырье

Содержание в процентах Компоненты

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/9002/image002.gif" v:shapes="_x0000_i1025">

Система ограничений будетиметь вид:

<img src="/cache/referats/9002/image004.gif" v:shapes="_x0000_i1026">    (1).

Запишем систему в каноническом виде:

<img src="/cache/referats/9002/image006.gif" v:shapes="_x0000_i1027">    (2).

Решим поставленную задачу методомискусственного  базиса. Для этогосоставим расширенную задачу:

<img src="/cache/referats/9002/image008.gif" v:shapes="_x0000_i1028">

<img src="/cache/referats/9002/image010.gif" v:shapes="_x0000_i1029">    (3).

Составим вспомогательнуюцелевую функцию: <img src="/cache/referats/9002/image012.gif" v:shapes="_x0000_i1030"><img src="/cache/referats/9002/image014.gif" v:shapes="_x0000_i1031"><img src="/cache/referats/9002/image016.gif" v:shapes="_x0000_i1032"> из первогоограничения, а <img src="/cache/referats/9002/image018.gif" v:shapes="_x0000_i1033"> из третьего получаем:

<img src="/cache/referats/9002/image020.gif" v:shapes="_x0000_i1034">;

<img src="/cache/referats/9002/image022.gif" v:shapes="_x0000_i1035">;

Тогда:

<img src="/cache/referats/9002/image024.gif" v:shapes="_x0000_i1036">

Запишем начальную симплекс-таблицу:

4

4,5

5,8

6

7,5

M

M

Св

Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

В

M

X9

1

1

1

1

1

1

1

X6

0,8

0,6

0,1

0,1

0,1

1

0,3

M

X10

0,1

0,3

0,5

0,3

0,2

-1

1

0,1

X8

0,1

0,1

0,4

0,6

0,7

1

0,4

F

-4

-4,5

-5,8

-6

-7,5

FM

1,1

1,3

1,5

1,3

1,2

-1

1,1

Оптимальная симплекс-таблица будет иметь вид:

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

FM

-1

-1

Полученное решение будетоптимальным, поскольку все оценки неположительные. Запишем оптимальное решение:<img src="/cache/referats/9002/image026.gif" v:shapes="_x0000_i1037"> и оптимальное значениецелевой функции: <img src="/cache/referats/9002/image028.gif" v:shapes="_x0000_i1038">

Экономически полученноерешение интерпретируется следующим образом: для получения единицы сплаваминимальной себестоимости необходимо взять 40% сырья №2 и 60% сырья №3. Приэтом сплав содержит ровно 30% олова, более 20% (точнее, 42%) цинка и менее 40%(28%) свинца. Минимальная себестоимость единицы сплава составляет 5,28 у.е.

Математическаямодель и экономический смысл двойственной задачи.

Задача,двойственная к исходной, строитсяследующимобразом:

1) Исходнаязадача – на минимум, следовательно, двойственная задача – на максимум.

2) Матрица коэффициентов системы ограничений будет представлять собойтранспонированную матрицу соответствующих коэффициентов исходной задачи. Приэтом все ограничения должны быть одного типа, например «больше илиравно». Поэтому преобразуем второе и четвертое ограничения к типу«больше или равно», умножив их на –1, затем транспонируем полученнуюматрицу:

<img src="/cache/referats/9002/image030.gif" v:shapes="_x0000_i1039"> => <img src="/cache/referats/9002/image032.gif" v:shapes="_x0000_i1040">

3) Число переменных в двойственной задаче равно числу ограничений висходной, т.е. 4, и наоборот, число ограничений в двойственной задаче равночислу переменных в исходной, т.е. 5. Переменная <img src="/cache/referats/9002/image034.gif" v:shapes="_x0000_i1041"> двойственной задачисоответствует первому ограничению исходной задачи, переменная <img src="/cache/referats/9002/image036.gif" v:shapes="_x0000_i1042"><img src="/cache/referats/9002/image038.gif" v:shapes="_x0000_i1043"><img src="/cache/referats/9002/image040.gif" v:shapes="_x0000_i1044">–четвёртому.

4)Коэффициентами при переменных <img src="/cache/referats/9002/image034.gif" v:shapes="_x0000_i1045"><img src="/cache/referats/9002/image036.gif" v:shapes="_x0000_i1046"><img src="/cache/referats/9002/image038.gif" v:shapes="_x0000_i1047"> и <img src="/cache/referats/9002/image040.gif" v:shapes="_x0000_i1048"> в целевой функциидвойственной задачи являются свободные члены ограничений исходной задачи (всеограничения одного типа), т.е. вектор

<img src="/cache/referats/9002/image042.gif" v:shapes="_x0000_i1049">

а правыми частямиограничений двойственной задачи являются коэффициенты целевой функции исходнойзадачи, т.е. вектор <img src="/cache/referats/9002/image044.gif" v:shapes="_x0000_i1050">

5) Т.к. всепеременные исходной задачи неотрицательны, то все ограничения двойственной задачибудут неравенствами типа «<img src="/cache/referats/9002/image046.gif" v:shapes="_x0000_i1051"><img src="/cache/referats/9002/image034.gif" v:shapes="_x0000_i1052"> может принимать любыезначения, а <img src="/cache/referats/9002/image036.gif" v:shapes="_x0000_i1053"><img src="/cache/referats/9002/image038.gif" v:shapes="_x0000_i1054"><img src="/cache/referats/9002/image040.gif" v:shapes="_x0000_i1055"> – толькоположительные.

Таким образом,математическая модель двойственной задачи следующая:

<img src="/cache/referats/9002/image048.gif" v:shapes="_x0000_i1056">

<img src="/cache/referats/9002/image050.gif" v:shapes="_x0000_i1057">   (4).

Проанализируемтеперь экономический смысл двойственной задачи. Для этого сначала рассмотримэкономический смысл переменных <img src="/cache/referats/9002/image034.gif" v:shapes="_x0000_i1058"><img src="/cache/referats/9002/image036.gif" v:shapes="_x0000_i1059"><img src="/cache/referats/9002/image038.gif" v:shapes="_x0000_i1060"> и <img src="/cache/referats/9002/image040.gif" v:shapes="_x0000_i1061"><img src="/cache/referats/9002/image034.gif" v:shapes="_x0000_i1062"> имеет размерность[у.е./ед. сплава], величина <img src="/cache/referats/9002/image036.gif" v:shapes="_x0000_i1063"><img src="/cache/referats/9002/image038.gif" v:shapes="_x0000_i1064"><img src="/cache/referats/9002/image040.gif" v:shapes="_x0000_i1065"><img src="/cache/referats/9002/image034.gif" v:shapes="_x0000_i1066"> не представляетсявозможным в силу условия задачи. Что касается экономического смысла переменных <img src="/cache/referats/9002/image036.gif" v:shapes="_x0000_i1067"> и <img src="/cache/referats/9002/image040.gif" v:shapes="_x0000_i1068"><img src="/cache/referats/9002/image038.gif" v:shapes="_x0000_i1069">

Такимобразом, экономический смысл ограничений заключается в следующем. Пусть, рассматриваемаяфирма вместо того, чтобы производить сплав из указанных пяти видов сырья, решила,приобретя у некой другой фирмы цинк по цене <img src="/cache/referats/9002/image038.gif" v:shapes="_x0000_i1070"> и взяв у нее некотороеколичество олова с доплатой <img src="/cache/referats/9002/image036.gif" v:shapes="_x0000_i1071"> и свинца сдоплатой <img src="/cache/referats/9002/image040.gif" v:shapes="_x0000_i1072"><img src="/cache/referats/9002/image034.gif" v:shapes="_x0000_i1073">

Целеваяфункция данной двойственной задачи экономически интерпретируется как максимальнаяприбыль фирмы-поставщика ресурсов.

<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">
Решениедвойственной задачи.

1. Решение с помощью IBLP.

Введя задачу в программу,получаем следующее оптимальное решение:

1

-0,3

0,1

-0,4

Св

Б.П.

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

Y9

В

1

Y1

1

0,54

-0,46

-0,2

1,2

6,06

-0,3

Y2

1

0,4

-0,6

-2

2

2,6

Y5

-0,12

-0,12

1

-1,4

0,4

0,02

Y8

-0,2

-0,2

-1

1

0,2

Y9

-0,3

-0,3

-1

1

1,7

T

0,32

0,12

0,4

0,6

5,28

<img src="/cache/referats/9002/image052.gif" v:shapes="_x0000_i1074">8.

2. Решение по второй теореме двойственности.

Согласно второй теореме двойственности,планы <img src="/cache/referats/9002/image054.gif" v:shapes="_x0000_i1075"><img src="/cache/referats/9002/image056.gif" v:shapes="_x0000_i1076">

<img src="/cache/referats/9002/image058.gif" v:shapes="_x0000_i1077">       (5)

<img src="/cache/referats/9002/image060.gif" v:shapes="_x0000_i1078">       (6)

Покомпонентно для нашихзадач эти соотношения записываются следующим образом:

<img src="/cache/referats/9002/image062.gif" v:shapes="_x0000_i1079">              (5).

<img src="/cache/referats/9002/image064.gif" v:shapes="_x0000_i1080">  (6)

Из системы (5) видно, что вовтором и третьем уравнениях в скобках получается ноль, поскольку <img src="/cache/referats/9002/image066.gif" v:shapes="_x0000_i1081"> и <img src="/cache/referats/9002/image068.gif" v:shapes="_x0000_i1082"> положительны, <img src="/cache/referats/9002/image070.gif" v:shapes="_x0000_i1083"><img src="/cache/referats/9002/image072.gif" v:shapes="_x0000_i1084"><img src="/cache/referats/9002/image074.gif" v:shapes="_x0000_i1085"> поскольку в третьем ичетвёртом уравнениях в скобках получаются положительные числа.

Из первого и третьегоуравнений системы (5) имеем:

<img src="/cache/referats/9002/image076.gif" v:shapes="_x0000_i1086">

откуда <img src="/cache/referats/9002/image078.gif" v:shapes="_x0000_i1087"><img src="/cache/referats/9002/image080.gif" v:shapes="_x0000_i1088">

Таким образом, <img src="/cache/referats/9002/image082.gif" v:shapes="_x0000_i1089">

<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">

3. Решение с помощью симплекс-таблицы исходной задачи.

Запишем еще раз оптимальную симплекс-таблицуисходной задачи:

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

FM

-1

-1

Из теории известно, чтосправедливы следующие формулы: <img src="/cache/referats/9002/image084.gif" v:shapes="_x0000_i1090"><img src="/cache/referats/9002/image086.gif" v:shapes="_x0000_i1091">

В системе ограничений (2)исходной задачи переменной <img src="/cache/referats/9002/image034.gif" v:shapes="_x0000_i1092"> соответствует первоеограничение, содержащее базисную переменную <img src="/cache/referats/9002/image016.gif" v:shapes="_x0000_i1093"><img src="/cache/referats/9002/image036.gif" v:shapes="_x0000_i1094"> – второе, содержащее базиснуюпеременную <img src="/cache/referats/9002/image090.gif" v:shapes="_x0000_i1095"><img src="/cache/referats/9002/image038.gif" v:shapes="_x0000_i1096"> – третье, содержащеебазисную переменную <img src="/cache/referats/9002/image018.gif" v:shapes="_x0000_i1097"> и <img src="/cache/referats/9002/image040.gif" v:shapes="_x0000_i1098"> – четвёртоес переменной <img src="/cache/referats/9002/image095.gif" v:shapes="_x0000_i1099"><img src="/cache/referats/9002/image097.gif" v:shapes="_x0000_i1100"><img src="/cache/referats/9002/image099.gif" v:shapes="_x0000_i1101"><img src="/cache/referats/9002/image101.gif" v:shapes="_x0000_i1102"> и <img src="/cache/referats/9002/image103.gif" v:shapes="_x0000_i1103"> приведенной симплекс-таблицы:<img src="/cache/referats/9002/image105.gif" v:shapes="_x0000_i1104">; <img src="/cache/referats/9002/image107.gif" v:shapes="_x0000_i1105">; <img src="/cache/referats/9002/image109.gif" v:shapes="_x0000_i1106">; <img src="/cache/referats/9002/image111.gif" v:shapes="_x0000_i1107">;

Теперь запишем условие (8)для нашего случая:

<img src="/cache/referats/9002/image113.gif" v:shapes="_x0000_i1108">,что покомпонентно записывается как:<img src="/cache/referats/9002/image115.gif" v:shapes="_x0000_i1109">, <img src="/cache/referats/9002/image117.gif" v:shapes="_x0000_i1110">, <img src="/cache/referats/9002/image119.gif" v:shapes="_x0000_i1111">, <img src="/cache/referats/9002/image121.gif" v:shapes="_x0000_i1112">, откуда<img src="/cache/referats/9002/image123.gif" v:shapes="_x0000_i1113"><img src="/cache/referats/9002/image125.gif" v:shapes="_x0000_i1114"><img src="/cache/referats/9002/image127.gif" v:shapes="_x0000_i1115"><img src="/cache/referats/9002/image129.gif" v:shapes="_x0000_i1116">

С учетом того, что мы решали симплекс-методом неисходную задачу (1), а задачу в канонической форме (2), т.е. по оптимальнойсимплекс-таблице мы можем найти решение двойственной задачи к каноническойформе исходной задачи. Очевидно, задача в симметричной и канонической форме –две разные задачи, отличающиеся знаком и количеством ограничений в двойственныхзадачах. Более того, так как все ограничения в канонической задаче – равенства,то в двойственной задаче все <img src="/cache/referats/9002/image131.gif" v:shapes="_x0000_i1117"> могут быть любогознака, поэтому наши <img src="/cache/referats/9002/image133.gif" v:shapes="_x0000_i1118"> не являются ошибкой.Но нам необходимо решить не двойственную к канонической задаче, а двойственнуюк симметричной. Если сделать замену <img src="/cache/referats/9002/image135.gif" v:shapes="_x0000_i1119"><img src="/cache/referats/9002/image137.gif" v:shapes="_x0000_i1120"> или <img src="/cache/referats/9002/image082.gif" v:shapes="_x0000_i1121">

4. Решение через матрицу, обратную к базисной.

Оптимальное решениедвойственной задачи можно найти по формуле <img src="/cache/referats/9002/image086.gif" v:shapes="_x0000_i1122"><img src="/cache/referats/9002/image140.gif" v:shapes="_x0000_i1123"><img src="/cache/referats/9002/image142.gif" v:shapes="_x0000_i1124">

<img src="/cache/referats/9002/image144.gif" v:shapes="_x0000_i1125">.

Получим:

<img src="/cache/referats/9002/image146.gif" v:shapes="_x0000_i1126">

Откуда <img src="/cache/referats/9002/image082.gif" v:shapes="_x0000_i1127">

Такимобразом, мы видим, что всеми четырьмя способами было получено одно и то жерешение: <img src="/cache/referats/9002/image082.gif" v:shapes="_x0000_i1128">;<img src="/cache/referats/9002/image148.gif" v:shapes="_x0000_i1129">.

Экономическаяинтерпретация трех теорем двойственности.

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

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

Как былоуказано выше, вторая теорема двойственности заключается в выполнении соотношенийдополняющей нежесткости в случае оптимальности планов пары задач (соотношения(5) и (6)). Приведем сначала экономическую интерпретацию условия (6). Каждомуиз четырёх «ресурсов» исходной задачи соответствует его двойственнаяоценка, или условная цена (<img src="/cache/referats/9002/image034.gif" v:shapes="_x0000_i1130"><img src="/cache/referats/9002/image036.gif" v:shapes="_x0000_i1131"><img src="/cache/referats/9002/image038.gif" v:shapes="_x0000_i1132"> и <img src="/cache/referats/9002/image040.gif" v:shapes="_x0000_i1133"> соответственно). Вслучае положительности двойственной оценки (в нашем случае <img src="/cache/referats/9002/image034.gif" v:shapes="_x0000_i1134"> и <img src="/cache/referats/9002/image036.gif" v:shapes="_x0000_i1135">

<img src="/cache/referats/9002/image150.gif" v:shapes="_x0000_i1136">

т.е. первый и второй «ресурсы» используютсяполностью и являются дефицитными. Следует оговориться, что первое равенствовыполняется всегда, в противном случае задача не имеет решения. Это логически понятно,поскольку сумма частей всегда равна целому. Что касается третьего и четвёртогоресурсов, то они имеют нулевую двойственную оценку, т.е. эти ресурсы неявляется дефицитным. Рассмотрим теперь условие (5). Поскольку <img src="/cache/referats/9002/image070.gif" v:shapes="_x0000_i1137">

<img src="/cache/referats/9002/image152.gif" v:shapes="_x0000_i1138">

Экономически это значит, что затраты на сырье №1, 4 и 5превосходят возможные затраты в случае закупки отдельных ресурсов, поэтому этивиды сырья использоваться не будут. С другой стороны, <img src="/cache/referats/9002/image154.gif" v:shapes="_x0000_i1139"><img src="/cache/referats/9002/image156.gif" v:shapes="_x0000_i1140">

<img src="/cache/referats/9002/image158.gif" v:shapes="_x0000_i1141">

т.е. затраты на сырье первого и второго вида равны альтернативнымзатратам на производство, значит эти виды сырья будут использоваться.

Третьятеорема двойственности позволяет определить зависимость изменения целевой функцииначальной задачи от изменения запасов «ресурсов»: <img src="/cache/referats/9002/image160.gif" v:shapes="_x0000_i1142"><img src="/cache/referats/9002/image162.gif" v:shapes="_x0000_i1143">

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