3.4. Примеры построения двойственных задач
Задача 3.1.Построить двойственную задачу к заданной модели линейного программирования.
Исходная задача:
max Z = 3 x1 + x2 + 2 x3
x1
+ 3
x2
+ 5
x3
9
2
x1
+ 2 x2
+ x3
5
x1, x2, x3 0.
Двойственная задача имеет вид:
min f = 9 y1 + 5 y2
y1 + 2 y2 3
3 y1 + 2 y2 1
5 y1 + y2 2
y1 0, y2 0.
Задача 3.2.Построить двойственную задачу к модели линейного программирования:
max Z = 2 x1 + x2 + 3 x3
-x1 + 3 x2 - 5 x3 = 12
2 x1 - 2 x2 + 4 x3 = 4
3 x1 + x2 + x3 = 18
x1, x2, x3 0.
Двойственная задача:
min f= 12y1 + 24 y2 + 18y3
-y1 + 2 y2 + 3 y3 2
3 y1 - y2 + y3 1
-5 y1 + 4 y2 + y3 3.
Задача 3.3.Построить двойственную модель к задаче 2.2. Выписать ее решение из оптимальной симплекс-таблицы задачи 2.2.
Исходная задача имеет вид:
max Z = 25 x1 + 50 x2 + 40 x3
25 x1+ 50 x2 21000
40 x3 12000
x1
+
x2
+
x3
1000
10
x1
+
x2
+25
x3
15760
x1, x2, x3 0.
В результате решения данной задачи была получена следующая симплекс-таблица:
Таблица 3.2 – Оптимальная симплекс-таблица исходной задачи
|
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
|
X2 |
700 |
1 |
1 |
0 |
0 |
0.02 |
1 |
0 |
|
X3 |
300 |
0 |
0 |
1 |
0 |
-0.03 |
0 |
0 |
|
X4 |
14000 |
25 |
0 |
0 |
1 |
1.25 |
50 |
0 |
|
X7 |
7560 |
9 |
0 |
0 |
0 |
0.60 |
-1 |
1 |
|
M+1 |
47000 |
25 |
0 |
0 |
0 |
0.25 |
50 |
0 |
Оптимальный план исходной задачи:
, 
,
,
,
, 
,
.
Перейдем
к построению двойственной задачи.
Предварительно приведем два первых
ограничения к неравенствам со знаком
«
». Для
этого умножим левые и правые их части
на «-1».
max Z = 25 x1 + 50 x2 + 40 x3
-25
x1
– 50
x2
-21000
-40
x3
-12000
x1
+
x2
+
x3
1000
10
x1
+
x2
+25
x3
15760.
x1, x2, x3 0.
Двойственная задача будет иметь вид:
min f = -21000 y1 - 12000 y2 + 1000 y3 + 15760 y4
-25 y1 + 0 y2 + y3 + 10 y4 25
-50 y1 + 0 y2 + y3 + y4 50
0 y1 - 40 y2 + y3 + 25 y4 40
y1, y2, y3, y4 0.
Согласно первой теореме двойственности если прямая задача имеет оптимальное решение, то и двойственная задача также будет иметь решение. Оптимальный план двойственной задачи расположен в строке «M+1» таблицы 3.2:
, 
,
,
, 
,
,
,
.
3.5 Контрольные вопросы к разделу 3
1. Как определить число основных ограничений в двойственной задаче?
2. Как определить количество неизвестных в двойственной задаче?
3.Каков экономический смысл целевой функции и ограничений двойственной задачи, если исходная задача является задачей производственного планирования?
4.Какой знак будут иметь основные ограничения в двойственной задаче, если исходная задача имеет ограничения равенства?
5.Что можно сказать о решении двойственной задачи, если прямая задача не имеет допустимых решений?
6. Что можно сказать о решении двойственной задачи, если целевая функция исходной задачи не ограничена?
7.Существует ли связь между экстремальными значениями целевых функций двойственных задач?
8.
Прямая задача имеет неизвестные x1,x2,x3.
Ресурсы заданы в количествеb1,
b2 соответственно. Целевую
функцию с коэффициентамис1,
с2, с3 следует
максимизировать. Матрица коэффициентов
основных ограничений
.
Записать модель задачи производственного
планирования и двойственную к ней.
9. Для моделей линейного программирования, составленных по условию предыдущей задачи, записать условия дополняющей нежесткости.
10. Если одна из пары двойственных задач имеет четыре неизвестные и пять ограничений, какое количество дополняющей нежесткости будет иметь эта пара задач?
11. Решена задача оптимизации производственного планирования с неизвестными x1,x2,x3, х4, ресурсами в количестве 100, 150, 230 единиц. Получено максимальное значение целевой функцииmaxZ = 200 ден.ед. Также известно решение двойственной задачи:
у1 = 5, y2 = 0, y3=6.
Какие ресурсы в оптимальном решении будут дефицитными?
12. В задаче 11 определить максимальное значение целевой функции, если ресурсы будут заданы в количестве 110, 150, 250 ед.
13. Как в экономическом анализе решения задачи оптимизации производственного планирования используются оптимальные значения двойственных переменных?