Экономика и менеджмент \ Экономико-математические методы и модели

Математическое моделирование экономических процессов на железнодорожном транспорте, страница 29

Прямая задача

Подстановка значений

Двойственная задача

Подстановка значений

4x1+2x2+0x3+1x4 <=760

2 x1+0x2+2x3+1x4 <=770

2x1+2x2+2x3+0x4 <=740

2x1+2x2+1x3+1x4 <=700

0x1+2x2+2x3+2x4 <=800

x1 >=0

x2>=0

x3>=0

x4>=0

12x1+6x2+8x3+16x4 =max F

4*90+2*0+0*0+1*400=760; 760=760

2*90+0*0+2*0+1*400<770; 580<770

2*90+2*0+2*0+0*400<740; 180<740

2*90+2*0+1*0+1*400<700; 580<700

0*90+2*0+2*0+2*400=800; 800=800

X1 =90

X2 =0

X3 =0

X4=400

12*90+6*0+8*0+16*400 =7480

Y1>=0

Y2>=0

Y3>=0

Y4>=0

Y5>=0

4Y1+2Y2+2Y3+2Y4+0Y5>=12

2Y1+0Y2+2Y3+2Y4+2Y5>=6

0Y1+2Y2+2Y3+1Y4+0Y5>=8

1Y1+1Y2+0Y3+1Y4+2Y5>=16

760Y1+770Y2+740Y3+700Y4+

800Y5 =min F1

Y1=3

Y2=0

Y3=0

Y4=0

Y5=13/2

4*3+2*0+2*0+2*0+0*13/2=12;

12-12=0;

2*3+0*0+2*0+2*0+2*13/2=19;

19-6=13;

0*3+2*0+2*0+1*0+2*13/2=13;

13-8=5;

1*3+1*0+0*0+1*0+2*13/2=16;

16-16=0;

760*3+770*0+740*0+700*0+

800*13/2 = 7480

Далее рассматривается двойственная задача. В прямой задаче ограничений по ресурсам пять. Поэтому в двойственной вначале запишем ограничения >=0, для каждой двойственной переменной Y. Далее под ними записываются неравенства относительно коэффициентов целевой функции, представленных ограничениями справа. Для этого в каждом столбце левой части ограничений прямой задачи выбираются коэффициенты при неизвестных и записываются, как левые части ограничений для двойственных переменных в транспонированном виде.

Произведем подстановку значений двойственных переменных, полученных в оптимальном плане при решении прямой задачи. Вернемся к нашему решению.*Y1=3, *Y2=0, *Y3=0, *Y4=0, *Y5=13/2  в оптимальном плане. Занесем это в подстановку  двойственной задачи. Сравним типы неравенств в подстановке прямой и двойственных задач. Если в прямой для ресурсов первого вида реализуется равенство (760=760), то переменная оказывается больше 0: (Y1=3). Для ресурсов второго вида реализуется уже неравенство вида <: (580<770), то здесь двойственная переменная уже оказывается равной 0: (Y2=0). Аналогично для третьего и четвертого витда ресурсов. Для ресурсов пятого вида реализуется равенство (800=800), то переменная оказывается больше 0: (Y5=13/2).

Продолжим подстановку дальше для ограничений вида ">=" в постановке двойственной задачи.

Первое ограничение  реализуется как  равенство: (12=12), что соответствует неравенству X1>0 переменной прямой задачи (Х1=90).

Второй из них реализуется как жесткое неравенство вида >: (19>6), что соответствует равенству 0 переменной прямой задачи (Х2=0). Заметим, что разность левой и правой части составит в точности величину потерь в целевой функции если бы производилась продукция второго вида : 19-6=13.

Третье ограничение реализуется как жесткое неравенство вида >: (13>8), что соответствует равенству 0 переменной прямой задачи (Х3=0). Заметим, что разность левой и правой части составит в точности величину потерь в целевой функции если бы производилась продукция второго вида : 13-8=5.

Четвертое ограничение  реализуется как  равенство: (16=16), что соответствует неравенству X4>0 переменной прямой задачи (Х4=400).

Мы видим что, все наоборот в прямой и двойственной задачах. Если в прямой задаче реализуется ограничение как равенство, то двойственной задаче, соответствующее ограничение вводится как жесткое неравенство, и, наоборот, если в прямой имеется жесткое неравенство, то в двойственной соответствующее ограничение выглядит равенством.

И последнее. При решении симплекс-методом задач на максимум в оптимальном плане величина целевой функции в прямой задаче равна стоимости используемых ресурсов в целевой функции двойственной задачи. Это и достигается при нашей подстановке.

Скачать файл