На станциях Аj сосредоточен однородный груз Аj

Сумма аj = 30+20+10 =60
Сумма bj = 15+14+7+16+8 = 60
Сумма aj = bjЗадача закрытая
i+j – 1 = 3+5-1 ≤7 число занятых клеток
Составим первоначальный опорный план перевозок, стараясь минимизировать расходы на перевозку и проведения плана на оптимальность с помощью потенциалов
bj
15 14 7 16 8 2
aj
30 6^5 4 4 16^10 8^8 0
20 9^5 4^2 7^3 15 9 0
10 -3 10 2 -7 14 -1
ß 5 2 3 10 8
Все затраты распределены
Все потребности удовлетворены
Потенциал первой строки принимаем L1 = 0
Для занятых клеток Сji – (Li-ßj) = 0
Исходя из этого условия находим остальные потенциалы ß1 = 5;ß4 = 10;ß5 = 8; фd2 = 0;ß2 = 2;ß3 = 3 d = -1
Если план оптимальный, то для свободных клеток должно соблюдаться условие Сji – (Li–pi)≥0
Проверяем:
Е12 = 4-(0+2) = 2
Е24 = 15 –(0+10) = 5
Е13 = 4 –(0+2) = 2
Е25 = 9-(8+0) = 1
Е31 = 3-(5-1) = -1
Е33 = 2- (3-1) = 0
Е34 = 7-(10-1) = -2
План F1 = 6*5+16*10+8*8+9*5+1*2+7*3+10*1 = 338у.е
Не оптимальный поскольку Е31, и Е34 <0
Cделаем цикличную передвижку и получим новый план:
5
2
-9 9 9+4
+3
-9+10
9
1
Получаем новый план, который проверен на оптимальность
bj
15 14 7 16 8 2
aj
30 6^5 +4 +4 16^10 8^8 0
20 +5 13^2 7^5 +15 +9 -1
10 9^3 1^1 +2 +7 +14 -2
ß 5 3 4 10 8
30 15^5 +4 -4 7^10 8^8
20 +5 13^2 7^3 +15 +9 -2
10 +3 1 +2 9^7 +14 -3
ß 5 4 5 10 8
F2 = 30+160+64+26+21+27+1 = 329у.е
Неоптимальная передвижка:
6+9 16-9
9-9 0+9
F3 = 75+70+64+26+21+1+63= 320 у.е
Неоптимальная передвижка:
0-11 7-1
13+1
1-1
9+1
1-1 = передвижение
bj
15 14 7 16 8 2
aj
30 15^5 +4 1^4 6^10 8^8 0
20 +5 14^2 6^3 +15 +9 -1
10 +3 +1 +2 10^7 +14 -3
ß 5 3 4 10 8
Условие Сij– (Li–pi)≥0 выполняется для свободных клеток
План оптимальных:
Fmin = 75+4+60+64+28+18+70 = 319 у.е