Двойственная задача линейного программирования
Задача линейного оптимального планирования - исходная в своей паре симметричных двойственных задач. Вообще же другая задача в двойственной паре строится так:
1)меняется тип экстремума целевой функции (mах на min и наоборот);
2)коэффициенты целевой функции одной задачи становятся свободными членами другой задачи;
3)свободные члены одной задачи становятся коэффициентами целевой функции двойственной задачи;
4)тип неравенств меняется (≤ на ≥ и наоборот);
5) каждый столбец одной задачи порождает строку ограничений другой задачи и наоборот. В матрично-векторном виде обе задачи выглядят так:
исходная задача двойственная задача
L=(c,x)-max Z=(b,y)-min
Ax≤b, x≥0 Ya≥c, y≥0,
L(x1,x2,x3,x4)=48xl+30x2+29x3+10x4 -max Z(y1,y2,y3,y4)=198yl+96y2+228y3 - min
3х1+2х2+4х3+3х4≤198 3y1+2y2+6y3≥48
2х1+3х2+1х3+2х4≤96 2y1+3y2+5y3≥30
6х1+5х2+1х3+0х4≤228 4y1+ y2 + y3≥29
xj≥0, jєN4 3y1+2y2≥10
yj≥0, jєN3
Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений X(x1, x2, x3, x4) и Y(y1, y2, y3) пары двойственных задач необходимо и достаточно выполнение условий:
x1(3y1+2y2+6y3-48)=0 y1 (3х1+2х2+4х3+3х4)-198=0
x2(2y1+3y2+5y3-30)=0 y2 (2х1+3х2+1х3+2х4)-96=0
x3(4y1+1y2+1y3-29)=0 y3 (6х1+5х2+1х3+0х4)-228=0
x4(3y1+2y2+0y3-10)=0
В решении исходной задачи х1>0, х3>0, поэтому
3y1+2y2+6y3-48=0
4y1+1y2+1y3-29=0
Учитывая, что второй ресурс был избыточным и, согласно теореме двойственности его оценка равна нулю – y2=0, то приходим к системе:
3y1+6y3-48=0
4y1+1y3-29=0
из которой следует, что y1=6; y3=5.
Таким образом получили двойственные оценки ресурсов: y1=6; y2=0; y3=5; общая оценка всех ресурсов Z=198y1+228y3=2328.
Заметим, что полученное решение содержалось в последней строке последней симплексной таблицы исходной задачи
Таблица N 3
| C | B | H | 48 | 30 | 29 | 10 | 0 | 0 | 0 |
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | |||
| 29 | х3 | 24 | 0 | -1/7 | 1 | 6/7 | 2/7 | 0 | -1/7 |
| 0 | x6 | 4 | 0 | 13/7 | 0 | 13/7 | -4/21 | 1 | -5/21 |
| 48 | х1 | 34 | 1 | 6/7 | 0 | -1/7 | -1/21 | 0 | 4/21 |
| 2328 | 0 | 7 | 0 | 8 | 6 | 0 | 5 |
Решение одной из пары двойственных задач можно найти, зная только ответ к другой задаче и пользуясь 2-й теоремой двойственности: если i-e ограничение одной из пары двойственных задач на компонентах оптимального решения есть строгое неравенство, то оптимальное значение i-й переменной другой задачи равно 0, или, что то же самое - если оптимальное значение j-й переменной одной задачи строго положительно, то j-e ограничение другой из пары двойственных задач на компонентах оптимального решения есть равенство.
Важен экономический смысл двойственных оценок. Двойственная оценка, например, третьего ресурса у3=5 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли на 5 единиц.
Расшивка "узких мест" производства
Таблица N 3
| C | B | H | 48 | 30 | 29 | 10 | 0 | 0 | 0 |
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | |||
| 29 | х3 | 24 | 0 | -1/7 | 1 | 6/7 | 2/7 | 0 | -1/7 |
| 0 | x6 | 4 | 0 | 13/7 | 0 | 13/7 | -4/21 | 1 | -5/21 |
| 48 | х1 | 34 | 1 | 6/7 | 0 | -1/7 | -1/21 | 0 | 4/21 |
| 2328 | 0 | 7 | 0 | 8 | 6 | 0 | 5 |
При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, тем самым они образуют "узкие места" производства. Будем их заказывать дополнительно. Пусть Т=( t1,t2,t3) - вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие H+Q-lТ≥0, где Н - значения базисных переменных в последней симплексной таблице, а Q-1 - обращенный базис, который образуют столбцы при балансовых переменных в этой таблице. Задача состоит в том, чтобы найти вектор Т, максимизирующий суммарный прирост прибыли W=6t1+5 t3 при условии сохранения двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой продукции), предполагая, что можно получить дополнительно не более 1/3 первоначального объема ресурсов каждого вида.
24 2/7 0 -1/7 t1 0
4 + -4/21 1 -5/21 0 ≥ 0
34 -1/21 0 4/21 t3 0
t1 198
0 ≤ 1/3 96
t3 228
t1≥0, t3≥0.
W=6t1+5t3 -max
-2/7 t1 + 1/7 t3 ≤ 24
4/21 t1 + 5/21 t3 ≤ 4
1/21 t1 - 4/21 t3 ≤ 34
t1≤198/3, t3≤228/3.
t1≥0, t3≥0.
Как видно, после графического решения (График 2) программа расшивки приобретает вид:
t1=21, t2=0, t3=0
С новым количеством ресурсов: 198+21 219
b' = 96+0 = 96
228+0 228
у предприятия будет новая производственная программа.
Найдем h'=Q-1 b'
5/28 0 -1/7 219 30 -x3
-4/7 1 -1/7 96 = 0 -x6
-3/28 0 2/7 228 33 -x1
Теперь новая производственная программа имеет вид: X'оpt=(33;0;30;0). При этом второй ресурс был использован полностью.
219
При наличии ресурсов b' = 96 производство наиболее выгодно, так как
228
достигается max прибыль с использованием всех ресурсов. Также обратим внимание на то, что производство продукции 1–го вида при заказе дополнительных ресурсов необходимо будет уменьшить на 15 единиц, а производство продукции 3–го вида – увеличить на единицу.
ΔLmax=(Y,t)=6·21=126, где Y=(6;0;5); t(21;0;0)
L'max= ΔLmax+ Lmax=126+2328=2454.
Этот результат можно проверить, подставив значения х1 и х3 в первоначальную целевую функцию: L'max=48xl+30x2+29x3+10x4=31·37+41·21=1147+861=2454.