Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного програм...
Реферат - Компьютеры, программирование
Другие рефераты по предмету Компьютеры, программирование
Лабораторная работа № 3
Телешовой Елизаветы, гр. 726,
Теория двойственности в задачах линейного программирования.
Задача:
Для изготовления определенного сплава из свинца, цинка и олова используется сырье из тех же металлов, отличающееся составом и стоимостью.
СырьеСодержание в процентахКомпоненты12345Свинец1010406070Цинк1030503020Олово8060101010Стоимость, у. е.44,55,867,5
Определить, сколько нужно взять сырья каждого вида, чтобы изготовить с минимальной себестоимостью сплав, содержащий олова не более 30%, цинка не менее 10%, свинца не более 40%.
Решение задачи:
Пусть хi доля сырья i-го вида в единице полученного сплава. Тогда функция цели (себестоимость единицы сплава в у.е.) запишется следующим образом:
.
Система ограничений будет иметь вид:
(1).
Запишем систему в каноническом виде:
(2).
Решим поставленную задачу методом искусственного базиса. Для этого составим расширенную задачу:
(3).
Составим вспомогательную целевую функцию: . Выразим ее через переменные, не входящие в начальный базис . Выражая из первого ограничения, а из третьего получаем:
;
;
Тогда:
.
Запишем начальную симплекс-таблицу:
44,55,867,5000MMСвБ.П.X1X2X3X4X5X6X7X8X9X10ВMX9111110001010X60,80,60,10,10,1100000,3MX100,10,30,50,30,20-10010,10X80,10,10,40,60,7001000,4F-4-4,5-5,8-6-7,5000000FM1,11,31,51,31,20-10001,1Оптимальная симплекс-таблица будет иметь вид:
44,55,867,5000MMСвБ.П.X1X2X3X4X5X6X7X8X9X10В4,5X21,41000200-0,200,40X80,12000,20,30,601-0,4600,125,8X3-0,40111-2001,200,60X70,12000,20,3-0,4100,54-10,32F-0,0200-0,2-1,7-2,600-6,0605,28FM00000000-1-10Полученное решение будет оптимальным, поскольку все оценки неположительные. Запишем оптимальное решение: и оптимальное значение целевой функции: .
Экономически полученное решение интерпретируется следующим образом: для получения единицы сплава минимальной себестоимости необходимо взять 40% сырья №2 и 60% сырья №3. При этом сплав содержит ровно 30% олова, более 20% (точнее, 42%) цинка и менее 40% (28%) свинца. Минимальная себестоимость единицы сплава составляет 5,28 у.е.
Математическая модель и экономический смысл двойственной задачи.
Задача, двойственная к исходной, строится следующим образом:
1) Исходная задача на минимум, следовательно, двойственная задача на максимум.
2) Матрица коэффициентов системы ограничений будет представлять собой транспонированную матрицу соответствующих коэффициентов исходной задачи. При этом все ограничения должны быть одного типа, например "больше или равно". Поэтому преобразуем второе и четвертое ограничения к типу "больше или равно", умножив их на 1, затем транспонируем полученную матрицу:
=> .
3) Число переменных в двойственной задаче равно числу ограничений в исходной, т.е. 4, и наоборот, число ограничений в двойственной задаче равно числу переменных в исходной, т.е. 5. Переменная двойственной задачи соответствует первому ограничению исходной задачи, переменная второму, третьему, а четвёртому.
4) Коэффициентами при переменных ,, и в целевой функции двойственной задачи являются свободные члены ограничений исходной задачи (все ограничения одного типа), т.е. вектор
,
а правыми частями ограничений двойственной задачи являются коэффициенты целевой функции исходной задачи, т.е. вектор .
5) Т.к. все переменные исходной задачи неотрицательны, то все ограничения двойственной задачи будут неравенствами типа (поскольку двойственная задача на максимум). Поскольку первое условие исходной задачи представляет собой равенство, а остальные три неравенства, то может принимать любые значения, а ,и только положительные.
Таким образом, математическая модель двойственной задачи следующая:
.
(4).
Проанализируем теперь экономический смысл двойственной задачи. Для этого сначала рассмотрим экономический смысл переменных ,, и . Из ограничений видно, что величина имеет размерность [у.е./ед. сплава], величина [у.е./ед. олова], [у.е./ед. цинка ], а [у.е./ед. свинца]. Указать экономический смысл переменной не представляется возможным в силу условия задачи. Что касается экономического смысла переменных и , то в системе (1) они соответствует второму и четвёртому ограничениям, отражающим относительную избыточность ресурсов "олово" и "свинец", т.е. они могут быть рассмотрены как условный убыток для держателя этого ресурса, или цену, выплачиваемую его приобретателю. Таким образом, олово и свинец выступают в данной задаче в качестве антиблага, что экономически также достаточно абсурдно. Экономический смысл переменной , отражающей ограниченность ресурса "цинк", виден явно: она представляет собой двойственную оценку, или условную цену этого ресурса.
Таким образом, экономический смысл ограничений заключается в следующем. Пусть, рассматриваемая фирма вместо того, чтобы производить сплав из указанных пяти видов сырья, решила, приобретя у некой другой фирмы цинк по цене и взяв у нее некоторое количество олова с доплатой и свинца с доплатой , производить свой сплав из этих компонентов с учетом некоего параметра . Стоимость получаемых компонент по каждому виду сырья в этом случае не должна превосходить стоимость единицы сырья.
Целевая функция данной двойственной задачи экономически интерпретируется как максимальная прибыль фирмы-поставщика ресурсов.
Решение двойственной задачи.
1. Решение с помощью IBLP.
Введя задачу в программу, получаем следующее оптимальное решение:
1-0,30,1-0,400000СвБ.П.Y1Y2Y3Y4Y5Y6Y7Y8Y9В1Y1100,54-0,460-0,21,2006,06-0,3Y2010,4-0,60-22002,60Y500-0,12-0,121-1,40,4000,020Y800-0,2-0,200-1100,20Y900-0