Таблица 3. -
Математическая модель: обозначим xij – количество товара, перевозимого из Аi в Bj. Тогда
x
11 x
12 x
13 x
14 x
15x
16x21 x22 x23 x24 x25x26
X = x31 x32 x33 x34 x35x36 - матрица перевозок.
x41 x42 x43 x44 x45x46
min(x11+2x12+3x13+2,5x14+3,5x15+0,4x21+3x22+x23+2x24+3x25+0,7x31+x32+x33+0,8x34+1,5x35++1,2x41+2x42+2x43+1,5x44+2,5x45) (3. )
x11+x12+x13+x14+x15+x16=50
x
21+x
22+x
23+x
24+x
25+x
26=20
x31+x32+x33+x34+x35+x36=75
x41+x42+x43+x44+x45+x46=80
x11+x21+x31+x41=40 x12+x22+x32+x42=50
x13+x23+x33+x43=15
x14+x24+x34+x44=75
x15+x25+x35+x45=40
x16+x26+x36+x46=5
xij≥0 (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3. )
ДвойственнаяЗЛП:
max(50u1+20u2+75u3+80u4+40v1+50v2+15v3+75v4+40v5+5v6) (3. )
| |
u1+v1≤1u1+v2≤2
u1+v3≤3 (3. )
u1+v4≤2,5
u1+v5≤3,5
u1+v6≤0
ui,vj – произвольные (i=1,2,3,4 ; j=1,2,3,4,5,6 )
Будем искать первоначальный план по методу наименьшей стоимости:
1) x21=20и 2-ую строку исключаем;
2) x31=20и 1-ый столбец исключаем;
3) x34=55и 3-ю строку исключаем;
4) x44=20и 4-ый столбец исключаем;
5) x12=50 и 1-ю строку и 2-ой столбец исключаем и x32=0;
6) x43=150 и 3-ий столбец исключаем;
7) x45=40 и 5-ый столбец исключаем и x46=5.
Составим таблицу 3. . Здесь и далее в нижнем правом углу записываем значение перевозки.
Таблица 3. – Проведение итераций
2,0| 3,0 | 2,5 | 3,5 | 0 | | А2(а2=20) |  0,4 |
| 3,0 | 1,0 | 2,0 | 3,0 | 0 | | А3(а3=75) |  0,7 |
| | 1,0| 1,0 | | 0,8| 1,5 | 0 | | |
А4(а4=80)1,2 | 2,0 | 2,0 | | 1,5| | 2,5| 0 | Стоимость 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.Составим таблицу 3. :
Таблица 3. - Проведение итераций
А1 (а1=50)U1=0
  | 1,0   | 2,0| | 3,0| | 2,5| | 3,5| 0 | | |
А2(а2=20)U2=-1,3
| 0,4| | 3,0| | 1,0| | 2,0| | 3,0| 0 | | |
А3(а3=75)U3=-1
| 0,7 
 | 1,0| | 1,0| | 0,8| | 1,5| 0 | | |
А4(а4=80)U4=-0,3
| 1,2| | 2,0| | 2,0| | 1,5| | 2,5| | 0В верхнем левом углу здесь и далее записываем значение 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,
ЦехаСклад
ЦехаСклад