|
Решение:
Составим таблицу транспортной задачи. Заполним таблицу методом северо-западного угла:
|
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
A1 |
25 200 |
21 |
20 |
50 |
18 |
200 |
A2 |
15 |
30 200 |
32 |
25 |
40 |
200 |
A3 |
23 |
40 100 |
10 200 |
12 100 |
21 200 |
600 |
bj |
200 |
300 |
200 |
100 |
200 |
1000 |
Количество заполненных ячеек r=m+n-1=6.
Проверим сумму по столбцам, сумму по строкам и количество базисных (заполненных) клеток:
r =6, å ai=å bj=1000, всё выполняется, значит, найденный план является опорным.
L=25*200+30*200+40*100+10*200+12*100+21*200=22400
Постараемся улучшить план перевозок.
1) Рассмотрим цикл (1;1)-(1;2)-(2;2)-(2;1)
Подсчитаем цену цикла: j=15-30+21-25=-19<0
|
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
A1 |
25 |
21 200 |
20 |
50 |
18 |
200 |
A2 |
15 200 |
30 |
32 |
25 |
40 |
200 |
A3 |
23 |
40 100 |
10 200 |
12 100 |
21 200 |
600 |
bj |
200 |
300 |
200 |
100 |
200 |
1000 |
L=21*200+15*200+40*100+10*200+12*100+21*200=18600
2) Рассмотрим цикл (2;1)-(2;2)-(3;2)-(3;1)
j=-15+30+23-40=-2<0
|
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
A1 |
25 |
21 200 |
20 |
50 |
18 |
200 |
A2 |
15 100 |
30 100 |
32 |
25 |
40 |
200 |
A3 |
23 100 |
40 |
10 200 |
12 100 |
21 200 |
600 |
bj |
200 |
300 |
200 |
100 |
200 |
1000 |
L=21*200+15*100+30*100+23*100+10*200+12*100+21*200=18400
Проверим методом потенциалов:
Примем α1=0, тогда βj = cij – αi (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0
Очевидно, что Δij =0 для заполненных клеток.
В результате получим следующую таблицу:
|
B1=6 |
B2=21 |
B3=-7 |
B4=-5 |
B5=4 |
ai |
A1=0 |
25-6>0 |
21-21=0 200 |
20+7>0 |
50+5>0 |
18-4>0 |
200 |
A2=9 |
15-9-6=0 100 |
30-21-9=0 100 |
32-9+7>0 |
25+5-9>0 |
40-4-9>0 |
200 |
A3=17 |
23-17-6=0 100 |
40-21-17>0 |
10+7-17=0 200 |
12+5-17=0 100 |
21-4-17=0 200 |
600 |
bj |
200 |
300 |
200 |
100 |
200 |
1000 |
Таким образом, решение верное, т.к. Δij > 0 для всех пустых клеток и Δij =0 для всех заполненных.
Тогда сумма всех перевозок:
L=18400
Ответ:
|
B1 |
B2 |
B3 |
B4 |
B5 |
ai |
A1 |
25 |
21 200 |
20 |
50 |
18 |
200 |
A2 |
15 100 |
30 100 |
32 |
25 |
40 |
200 |
A3 |
23 100 |
40 |
10 200 |
12 100 |
21 200 |
600 |
bj |
200 |
300 |
200 |
100 |
200 |
1000 |
При использовании материалов активная ссылка на источник обязательна.