Читайте данную работу прямо на сайте или скачайте

Лабораторная работа №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-го вида в единице полученного сплава. Тогда функция цели (себестоимость единицы сплава в у.е.) запишется следующим образом:

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

(1).

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

(2).

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

(3).

Составим вспомогательную целевую функцию: аиз первого ограничения, аиз третьего получаем:

;

;

Тогда:

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

	4	4,5	5,8	6	7,5	0	0	0	M	M
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
M	X9	1	1	1	1	1	0	0	0	1	0	1
0	X6	0,8	0,6	0,1	0,1	0,1	1	0	0	0	0	0,3
M	X10	0,1	0,3	0,5	0,3	0,2	0	-1	0	0	1	0,1
0	X8	0,1	0,1	0,4	0,6	0,7	0	0	1	0	0	0,4
	F	-4	-4,5	-5,8	-6	-7,5	0	0	0	0	0	0
	FM	1,1	1,3	1,5	1,3	1,2	0	-1	0	0	0	1,1

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

	4	4,5	5,8	6	7,5	0	0	0	M	M
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	0,32
	F	-0,02	0	0	-0,2	-1,7	-2,6	0	0	-6,06	0	5,28
	FM	0	0	0	0	0	0	0	0	-1	-1	0

Полученное решение будет оптимальным, поскольку все оценки неположительные. Запишем оптимальное решение: аи оптимальное значение целевой функции:

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

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

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

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

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

а=>

3) Число переменных в двойственной задаче равно числу ограничений в исходной, т.е. 4, и наоборот, число ограничений в двойственной задаче равно числу переменных в исходной, т.е. 5. Переменная адвойственной задачи соответствует первому ограничению исходной задачи, переменная Ц четвёртому.

4) Коэффициентами при переменных _аи ав целевой функции двойственной задачи являются свободные члены ограничений исходной задачи (все ограничения одного типа), т.е. вектор

правыми частями ограничений двойственной задачи являются коэффициенты целевой функции исходной задачи, т.е. вектор

5) Т.к. все переменные исходной задачи неотрицательны, то все ограничения двойственной задачи будут неравенствами типа ламожет принимать любые значения, Ц только положительные.

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

(4).

Пронализируем теперь экономический смысл двойственной задачи. Для этого сначала рассмотрим экономический смысл переменных _аи аимеет размерность [у.е./ед. сплава], величина ане представляется возможным в силу словия задачи. Что касается экономического смысла переменных _аи

Таким образом, экономический смысл ограничений заключается в следующем. Пусть, рассматриваемая фирма вместо того, чтобы производить сплав из казанных пяти видов сырья, решила, приобретя у некой другой фирмы цинк по цене аи взяв у нее некоторое количество олова с доплатой _аи свинца с доплатой

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

Решение двойственной задачи.

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

8.

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

Согласно второй теореме двойственности, планы

(5)

(6)

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

а (5).

а (6)

Из системы (5) видно, что во втором и третьем равнениях в скобках получается ноль, поскольку аи аположительны, апоскольку в третьем и четвёртом равнениях в скобках получаются положительные числа.

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

откуда

Таким образом,

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

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

	4	4,5	5,8	6	7,5	0	0	0	M	M
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	0,32
	F	-0,02	0	0	-0,2	-1,7	-2,6	0	0	-6,06	0	5,28
	FM	0	0	0	0	0	0	0	0	-1	-1	0

Из теории известно, что справедливы следующие формулы:

В системе ограничений (2) исходной задачи переменной асоответствует первое ограничение, содержащее базисную переменную Ц второе, содержащее базисную переменную Ц третье, содержащее базисную переменную аи _аЦ четвёртое с переменной _аи априведенной симплекс-таблицы: ; ; ; ;

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

, что покомпонентно записывается как: , , , , откуда

С четом того, что мы решали симплекс-методом не исходную задачу (1), задачу в канонической форме (2), т.е. по оптимальной симплекс-таблице мы можем найти решение двойственной задачи к канонической форме исходной задачи. Очевидно, задача в симметричной и канонической форме - две разные задачи, отличающиеся знаком и количеством ограничений в двойственных задачах. Более того, так как все ограничения в канонической задаче - равенства, то в двойственной задаче все амогут быть любого знака, поэтому наши ане являются ошибкой. Но нам необходимо решить не двойственную к канонической задаче, двойственную к симметричной. Если сделать замену аили

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

Оптимальное решение двойственной задачи можно найти по формуле

.

Получим:

Откуда

Таким образом, мы видим, что всеми четырьмя способами было получено одно и то же решение: ;.

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

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

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

Как было указано выше, вторая теорема двойственности заключается в выполнении соотношений дополняющей нежесткости в случае оптимальности планов пары задач (соотношения (5) и (6)). Приведем сначала экономическую интерпретацию словия (6). Каждому из четырёх "ресурсов" исходной задачи соответствует его двойственная оценка, или словная цена (_аи асоответственно). В случае положительности двойственной оценки (в нашем случае аи

т.е. первый и второй "ресурсы" используются полностью и являются дефицитными. Следует оговориться, что первое равенство выполняется всегда, в противном случае задача не имеет решения. Это логически понятно, поскольку сумма частей всегда равна целому. Что касается третьего и четвёртого ресурсов, то они имеют нулевую двойственную оценку, т.е. эти ресурсы не является дефицитным. Рассмотрим теперь словие (5). Поскольку

Экономически это значит, что затраты на сырье №1, 4 и 5 превосходят возможные затраты в случае закупки отдельных ресурсов, поэтому эти виды сырья использоваться не будут. С другой стороны,

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

Третья теорема двойственности позволяет определить зависимость изменения целевой функции начальной задачи от изменения запасов "ресурсов":