|
|
90 |
50 |
30 |
15 |
45 |
45 |
50 |
15 |
45 |
60 |
40 |
|
|
с14 |
с15 |
с21 |
с22 |
с23 |
с24 |
с25 |
с31 |
с32 |
с33 |
с34 |
с35 |
|
|
60 |
95 |
35 |
30 |
55 |
30 |
40 |
50 |
40 |
35 |
30 |
100 |
Решение:
Составим таблицу транспортной задачи и заполним ее методом северо-западного угла:
B1
B2
B3
B4
B5
a
A1
45
60
40
60
95
90
15
45
30
A2
35
30
55
30
40
50
15
35
A3
50
40
35
30
100
30
15
15
b
15
45
45
50
15
170
Это будет опорный план.
Количество заполненных ячеек r=m+n-1=6.
1) Рассмотрим цикл (1,2)-(1,3)-(2,3)-(3,2):
с1,2+с2,3>c1.3+c3.2 (60+55>30+40)
Количество единиц товара, перемещаемых по циклу: min (с1,2 ; с2,3)=15
2) Рассмотрим цикл (2,4)-(2,5)-(3,5)-(3,4):
c2,4+с3,5>c2.5+c3.4 (30+40>30+100)
Количество единиц товара, перемещаемых по циклу: min (с2,4 ; с3,5)=15
В результате получится следующий план:
B1
B2
B3
B4
B5
a
A1
45
60
40
60
95
90
15
30
45
A2
35
30
55
30
40
50
15
20
15
A3
50
40
35
30
100
30
30
b
15
45
45
50
15
170
Больше циклов с «отрицательной ценой» нет, значит, это оптимальное решение.
Проверим методом потенциалов:
Примем α1=0, тогда βj = cij – αi (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0
Очевидно, что Δij =0 для заполненных клеток.
В результате получим следующую таблицу:
β1=45
β2=60
β3=40
β4=60
Страницы: 1, 2, 3, 4, 5, 6, 7, 8
При использовании материалов активная ссылка на источник обязательна.