Задачи по математическому моделированию

    Стоимость 1-ого плана:

    D1=2•50+0,4•20+0,7•20+0,8•55+2•15+1,5•20+2,5•40=326.

    Будем улучшать этот план методом потенциалов: ui- потенциал Аi ,vj- потенциал Bj.

    Тогда u1+v2=2,u2+v1=0,4, u3+v1=0,7, u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5 ,u4+v6=0.

    Положим u1=0, тогда v2=2,u3=-1,v1=1,7,v4=1,8, u2=-1,3,u4=-0,3, v3=2,3,v5=2,8,v6=0,3. 
 

    Составим  таблицу: 

 

    В верхнем левом углу здесь и далее записываем значение ui+vj-cij. Имеем: u1+v1--c11 =0,7>0,

    u1+v6-c16 =0,3>0,

    u3+v3-c33 =0,3>0,

    u3+v5-c35 =0,3>0,

    u4+v1-c41 =0,2>0. => По критерию оптимальности, первый план не оптимален. Далее max(0,7;0,3;0,3;0,3;0,2)=0,7. => Поместим перевозку в клетку А1В1, сместив 20=min(20,50) по циклу, указанному в таблице штрихом.

    Получим новую таблицу.

    Найдем  потенциалы: u1+v1=1,

    u1+v2=2,

    u2+v1=0,4,

    u3+v2=1,

    u3+v4=0,8,

    u4+v3=2,

    u4+v4=1,5,

    u4+v5=2,5 ,

    u4+v6=0.

    Положим u1=0,тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=2,3,v5=2,8,v6=0,3. Составим таблицу: 

 

    Стоимость 2-ого плана:

    D2=1•20+2•30+0,4•20+1•20+0,8•55+2•15+1,5•20+2,5•40=312.

    Имеем:

    u1+v6-c16=0,3>0,

    u2+v3-c23 =0,7>0,

    u3+v3-c33 =0,3>0,

    u3+v5-c35=0,3>0. => По критерию оптимальности, второй план не оптимален.

    Далее max(0,3;0,7;0,3;0,3)=0,7 => Поместим перевозку  в клетку А2В3, сместив 15=min(20,30,55,15) по циклу, указанному в таблице штрихом. Получим новую таблицу.

    Найдем  потенциалы: u1+v1=1,

    u1+v2=2,

    u2+v1=0,4,

    u3+v2=1,

    u3+v4=0,8,

    u2+v3=1,

    u4+v4=1,5,

    u4+v5=2,5 ,

    u4+v6=0.

    Положим u1=0,тогда v1=1, u2= -0,6, v2=2, v4=1,8, u3= -1, u4= -0,3, v3=1,6, v5=2,8, v6=0,3.

    Составим  таблицу: 

 

    Стоимость 3-его плана:

    D3=1•35+2•15+0,4•5+1•15+0,8•40+1•35+1,5•35+2,5•40=301,5.

    Имеем: u1+v6-c16=0,3>0,

    u3+v5-c35=0,3>0. => По критерию оптимальности, третий план не оптимален.

    Далее max(0,3;0,3)=0,3. => Поместим перевозку в клетку А3В5, сместив 40=min(40,40) по циклу, указанному в таблице штрихом. Получим новую таблицу.

    Чтобы 4-ый план был невырожденным, оставим  в клетке А4В5 нулевую перевозку.

    Найдем  потенциалы: u1+v1=1,

    u1+v2=2,

    u2+v1=0,4,

    u3+v2=1,

    u4+v5=2,5,

    u2+v3=1,

    u4+v4=1,5,

    u3+v5=1,5 ,

    u4+v6=0.

    Положим u1=0, тогда v1=1, u2= -0,6, v2=2, v4=1,5, u3= -1, u4=0, v3=1,6, v5=2,5, v6=0.

    Составим  таблицу: 

 

    Стоимость 4-ого плана: 

    D4=1•35+2•15+0,4•5+1•15+1•35+1,5•40+1,5•75=289,5.

    Для всех клеток последней таблицы выполнены  условия оптимальности:

    1) ui+vj-сij=0 для клеток, занятых перевозками;

    2) ui+vj-сij ≤0 для свободных клеток.

    Несодержательные  ответы:

    Прямой  ЗЛП:

                         35 15 0 0 0 0

                         5 0 15 0 0 0

    X =               0 35 0 0 40 0 

                         0 0 0 75 0 5

    min=289,5.

    Двойственной  ЗЛП:

    U1=0 ; U2=-0,6 ; U3= -1 ; U4=0 ; V1=1 ; V2=2 ; V3=1,6 ; V4=1,5 ; V5=2,5 ; V6=0.

    max=289,5.

    Так как min=max, то по критерию оптимальности найдены оптимальные решения прямой и двойственной ЗЛП.

    Ответ: Оптимально перевозить так:

    Из  А1 в B1 – 35 единиц груза;

    Из  А1 в B2 – 15 единиц груза;

    Из  А2 в B1 – 5 единиц груза;

    Из  А2 в B3 – 15 единиц груза;

    Из  А3 в B2 – 35 единиц груза;

    Из  А3 в B5 – 40 единиц груза;

    Из  А4 в B4 – 75 единиц груза.

    При этом стоимость минимальна и составит D min=289,5.

    5 единиц груза необходимо оставить  на складе А4 для их последующей  перевозки другим потребителям.