|
|
|
|
Учебный материал
РОССИЙСКОЙ КОЛЛЕКЦИИ РЕФЕРАТОВ (с) 1996
http://referat.students.ru; http://www.referats.net; http://www.referats.com
Лабораторная работа ? 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) они соответствует второму и четвёртому ограничениям, отражающим относительную избыточность ресурсов "олово" и "свинец", т.е. они могут быть рассмотрены как условный убыток для держателя этого ресурса, или цену, выплачиваемую его приобретателю. Таким образом, олово и свинец выступают в данной задаче в качестве антиблага, что экономически также достаточно абсурдно. Экономический смысл переменной , отражающей ограниченность ресурса "цинк", виден явно: она представляет собой двойственную оценку, или условную цену этого ресурса.
Таким образом, экономический смысл ограничений заключается в следующем. Пусть, рассматриваемая фирма вместо того, чтобы производить сплав из указанных пяти видов сырья, решила, приобретя у некой другой фирмы цинк по цене и взяв у нее некоторое количество олова с доплатой и свинца с доплатой , производить свой сплав из этих компонентов с учетом некоего параметра . Стоимость получаемых компонент по каждому виду сырья в этом случае не должна превосходить стоимость единицы сырья.
Целевая функция данной двойственной задачи экономически интерпретируется как максимальная прибыль фирмы-поставщика ресурсов.
Решение двойственной задачи.
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.
2. Решение по второй теореме двойственности.
Согласно второй теореме двойственности, планы и начальной и двойственной задачи соответственно являются оптимальными тогда и только тогда, когда выполняются соотношения:
(5)
(6)
Покомпонентно для наших задач эти соотношения записываются следующим образом:
(5).
(6)
Из системы (5) видно, что во втором и третьем уравнениях в скобках получается ноль, поскольку и положительны, . Из системы (6) получаем, что , поскольку в третьем и четвёртом уравнениях в скобках получаются положительные числа.
Из первого и третьего уравнений системы (5) имеем:
откуда
Таким образом, .
3. Решение с помощью симплекс-таблицы исходной задачи.
Запишем еще раз оптимальную симплекс-таблицу исходной задачи:
4
4,5
5,8