Двойственные задачи линейного программирования
Пусть решается задача нахождения максимума при ограничениях
Ей можно сформулировать двойственную задачу. Вводятся переменные: показывающие ценность ресурса для данного производства. За единицу стоимости примем единицу выпускаемой продукции. Стоимость всех затраченных ресурсов, идущих на изготовление единицы продукции,
Считается, что она не может быть меньше стоимости окончательного продукта (дохода)
Стоимость всех имеющихся ресурсов
Необходимо минимизировать целевую функцию и найти все
Например, если прямая задача имеет вид: целевая функция необходимо найти максиму
Ограничения по ресурсам:
Решение прямой задачи: оптимальный план
Тогда двойственная задача имеет вид: целевая функция необходимо найти минимум
Ограничения:
Решим двойственную задачу.
Вводим дополнительные переменные и превращая неравенства в уравнения. Для представления уравнений в каноническом виде вводим искусственные переменные и
Решать задачу будем с помощью двухэтапного симплекс-метода. Делая базисными переменными и на первом этапе находим минимум в результате получаем начальное допустимое базисное решение а базисными переменными становятся и
На втором этапе находим минимум целевой функции, получаем остальные переменные свободные и равны нулю (в частности . Ценность второго ресурса равна нулю, так как он используется не полностью. Первый и третий ресурс расходуется полностью.
Решение задачи приведено в контрольном примере № 3.
Контрольный пример №3 |
|
|
|
|
|
|||||
|
|
|
|
|
Двойственный симплекс метод |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
Целевая функция: F=24*y1+6000*y2+200*y3 |
|
|
|
min |
|||||
|
|
|
|
|
|
|
|
|
|
|
Ограничения: |
4*y1+1200*y2+20*y3≥5000 |
|
|
|
|
|
||||
|
|
1.5*y1+150*y2+20*y3≥2500 |
|
|
|
|
|
|||
|
|
y1,y2, y3≥0 |
|
|
|
|
|
|
|
|
Этап 1. |
|
|
|
|
|
|
|
|
|
|
Добавляем переменные y4,y5 превращая неравенства в уравнения. |
|
|
||||||||
Вводим искусственно y6,y7, целевую функцию F1=y6+y7, решаем задачу min(F1) |
|
|||||||||
Получим следующие коэффициенты в ограничениях и целевой функции: |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
Y6 |
Y7 |
B |
|
|
|
4 |
1200 |
20 |
-1 |
0 |
1 |
0 |
5000 |
|
|
|
1,5 |
150 |
20 |
0 |
-1 |
0 |
1 |
2500 |
|
|
F |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
min |
|
|
|
|
|
|
|
|
|
|
|
|
|
Исходная таблица (столбец с минимальным значением C и строка |
|
|
||||||||
с минимальным значением B/A выделены серым цветом)
|
||||||||||
|
W |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
Cb |
Yb |
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
Y6 |
Y7 |
B |
B/A |
1 |
y6 |
4 |
1200 |
20 |
-1 |
0 |
1 |
0 |
5000 |
4,1667 |
1 |
y7 |
1,5 |
150 |
20 |
0 |
-1 |
0 |
1 |
2500 |
16,667 |
C-строка |
|
-5,5 |
-1350 |
-40 |
1 |
1 |
0 |
0 |
F1= |
7500 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Результат 1 шага |
||||||||||
|
|
0 |
0 |
0 |
0 |
0 1 |
1 |
|
|
|
Cb |
Yb |
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
Y6 |
Y7 |
B |
B/A |
0 |
y2 |
0,003 |
1 |
0,0167 |
-0,000833 |
0 |
0,0008 |
0 |
4,1667 |
250 |
1 |
y7 |
1 |
0 |
17,5 |
0,125 |
-1 |
-0,125 |
1 |
1875 |
107,14 |
C-строка |
|
-1 |
0 |
-17,5 |
-0,125 |
1 |
1,125 |
0 |
F1= |
1875 |
|
|
|
|
|
|
|
|
|
|
|
Результат 2 шага |
|
|
|
|
|
|
|
|
||
|
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
Cb |
Yb |
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
Y6 |
Y7 |
B |
B/A |
0 |
y2 |
0,002 |
1 |
0 |
-0,000952 |
0,001 |
0,001 |
-1E-03 |
2,381 |
-2500 |
0 |
y3 |
0,057 |
0 |
1 |
0,007143 |
-0,057 |
-0,007 |
0,0571 |
107,14 |
15000 |
C-строка |
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
F1= |
0 |
|
|
|
|
|
|
|
|
|
|
|
Вся C-строка содержит неотрицательные числа. Минимум F1 найден: F1=y6+y7=0 |
||||||||||
Этап 2. |
|
Нахождение минимума функции F=24*y1+6000*y2+200*y3 |
|
|
||||||
Искусственные переменные y6, y7 и соответствующие столбцы |
|
|
|
|||||||
(выделены черным цветом) в преобразованиях не участвуют |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
Исходная таблица (столбец с минимальным значением C и строка |
|
|
||||||||
с минимальным значением B/A выделены серым цветом)
|
||||||||||
|
|
24 |
6000 |
200 |
0 |
0 |
0 |
0 |
|
|
Cb |
Yb |
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
Y6 |
Y7 |
B |
B/A |
6000 |
y2 |
0,002 |
1 |
0 |
-0,000952 |
0,001 |
0,001 |
-1E-03 |
2,381 |
1000 |
200 |
y3 |
0,057 |
0 |
1 |
0,007143 |
-0,057 |
-0,007 |
0,0571 |
107,14 |
1875 |
C-строка |
|
-1,714 |
0 |
0 |
4,285714 |
5,7143 |
-4,286 |
-5,714 |
F= |
35714 |
|
|
|
|
|
|
|
|
|
|
|
Результат 1 шага |
|
|
|
|
|
|
|
|
||
|
|
24 |
6000 |
200 |
0 |
0 |
0 |
0 |
|
|
Cb |
Yb |
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
Y6 |
Y7 |
B |
|
24 |
y1 |
1 |
420 |
0 |
-0,4 |
0,4 |
0,4 |
-0,4 |
1000 |
|
200 |
y3 |
0 |
-24 |
1 |
0,03 |
-0,08 |
-0,03 |
0,08 |
50 |
|
C-строка |
|
0 |
720 |
0 |
3,6 |
6,4 |
-3,6 |
-6,4 |
F= |
34000 |
|
|
|
|
|
|
|
|
|
|
|
Вся C-строка содержит неотрицательные числа. |
|
|
|
|
||||||
Минимум W найден. Задача решена |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
y1=1000 y2=0 y3=50 y4=y5=y6=y7=0 F=34000 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
Сравним последнюю таблицу симплекс-метода двойственной задачи
24 |
1 |
420 |
0 |
- 0.4 |
0.4 |
1000 |
|
200 |
0 |
- 24 |
1 |
0.03 |
- 0.08 |
50 |
|
С-строка |
0 |
720 |
0 |
3.6 |
6.4 |
F=34000 |
с последней таблицей симплекс-метода прямой задачи, которая (без учета ограничения ) имеет вид
5000 |
1 |
0 |
0.4 |
0 |
- 0.03 |
3.6 |
|
250 |
0 |
1 |
- 0.4 |
0 |
0.08 |
6.4 |
|
0 |
0 |
0 |
- 420 |
1 |
24 |
720 |
|
С-строка |
0 |
0 |
- 1000 |
0 |
- 50 |
W=34000 |
Из сравнения таблиц можно сделать вывод, что обратную задачу мы могли бы не решать, так как при решении прямой задачи содержится решение обратной задачи (и наоборот): (то есть решение уже было получено с точностью до знака). Прямая и обратная содержит одинаковые (с точностью до знака) коэффициенты вместо , с-строка с точностью до знака совпадает со свободными членами обратной задачи,
Можно вместо прямой задачи решать обратную задачу и наоборот. Такой подход иногда позволяет сократить число переменных, заменить условия типа на , избавится от двух этапов и т.д.
В заключении сформулируем основные типы прямых и обратных задач.