Лабораторная работ №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-го вида в единице полученного сплава. Тогда функция цели (себестоимость единицы сплава в у.е.) запишется следующим образом:
align="left">Математическая модель и экономический смысл двойственной задачи.
Задача, двойственная к исходной, строится следующим образом:
1) Исходная задача - на минимум, следовательно, двойственная задача - на максимум.
2) Матрица коэффициентов системы ограничений будет представлять собой транспонированную матрицу соответствующих коэффициентов исходной задачи. При этом все ограничения должны быть одного типа, например "больше или равно". Поэтому преобразуем второе и четвертое ограничения к типу "больше или равно", множив их на Ц1, затем транспонируем полученную матрицу:
Решение двойственной задачи.
1. Решение с помощью IBLP.
Введя задачу в программу, получаем следующее оптимальное решение:
|
1 |
-0,3 |
0,1 |
-0,4 |
0 |
0 |
0 |
0 |
0 |
|||
|
Св |
Б.П. |
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
Y6 |
Y7 |
Y8 |
Y9 |
В |
|
1 |
Y1 |
1 |
0 |
0,54 |
-0,46 |
0 |
-0,2 |
1,2 |
0 |
0 |
6,06 |
|
-0,3 |
Y2 |
0 |
1 |
0,4 |
-0,6 |
0 |
-2 |
2 |
0 |
0 |
2,6 |
|
0 |
Y5 |
0 |
0 |
-0,12 |
-0,12 |
1 |
-1,4 |
0,4 |
0 |
0 |
0,02 |
|
0 |
Y8 |
0 |
0 |
-0,2 |
-0,2 |
0 |
0 |
-1 |
1 |
0 |
0,2 |
|
0 |
Y9 |
0 |
0 |
-0,3 |
-0,3 |
0 |
0 |
-1 |
0 |
1 |
1,7 |
|
T |
0 |
0 |
0,32 |
0,12 |
0 |
0,4 |
0,6 |
0 |
0 |
5,28 |
Экономическая интерпретация трех теорем двойственности.
Согласно первой теореме двойственности, если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план, причем значения функций цели при оптимальных планах равны между собой; если же целевая функция одной из задач неограниченна, то другая совсем не имеет планов, и наоборот.
В нашем случае пара задач имеет оптимальные планы, значения целевых функций при которых равны 5,28. Экономический смысл этого состоит в том, что в оптимальном плане минимальные затраты фирмы на производство тонны сплава равны максимальной прибыли некой другой фирмы от продажи первой фирме необходимых для производства ресурсов по условным ценам, равным двойственным оценкам этих ресурсов.
Как было указано выше, вторая теорема двойственности заключается в выполнении соотношений дополняющей нежесткости в случае оптимальности планов пары задач (соотношения (5) и (6)). Приведем сначала экономическую интерпретацию словия (6). Каждому из четырёх "ресурсов" исходной задачи соответствует его двойственная оценка, или словная цена (img src="images/image-image034-239.gif">img src="images/image-image036-223.gif">img src="images/image-image038-216.gif">аи img src="images/image-image040-213.gif">асоответственно). В случае положительности двойственной оценки (в нашем случае img src="images/image-image034-239.gif">аи img src="images/image-image036-223.gif">
т.е. первый и второй "ресурсы" используются полностью и являются дефицитными. Следует оговориться, что первое равенство выполняется всегда, в противном случае задача не имеет решения. Это логически понятно, поскольку сумма частей всегда равна целому. Что касается третьего и четвёртого ресурсов, то они имеют нулевую двойственную оценку, т.е. эти ресурсы не является дефицитным. Рассмотрим теперь словие (5). Поскольку img src="images/image-image070-130.gif">
Экономически это значит, что затраты на сырье №1, 4 и 5 превосходят возможные затраты в случае закупки отдельных ресурсов, поэтому эти виды сырья использоваться не будут. С другой стороны, img src="images/image-image154-56.gif">img src="images/image-image156-57.gif">
т.е. затраты на сырье первого и второго вида равны альтернативным затратам на производство, значит эти виды сырья будут использоваться.
Третья теорема двойственности позволяет определить зависимость изменения целевой функции начальной задачи от изменения запасов "ресурсов": img src="images/image-image160-58.gif">img src="images/image-image162-54.gif">