На рис. 1 приведена транспортная сеть. В табл. 1 приведены стоимости транспортировки щебня

100584076206
4
3
2
5
1
5/150
4/120
3/150
4/180
2/90
(+150)
(+80)
60
10
(-100)
80
10
15
19
50
17
2/90
4/160
3/80
50
20
17
3/140
(-130)
90
6
4
3
2
5
1
5/150
4/120
3/150
4/180
2/90
(+150)
(+80)
60
10
(-100)
80
10
15
19
50
17
2/90
4/160
3/80
50
20
17
3/140
(-130)
90
Рис. 2. Условия решения и начальный план транспортной задачи
Начальный план показан на рис. 2 стрелками.
Для построения системы потенциалов присвоим вершине 6 потенциал 10 (U6=10).
Тогда потенциалы остальных составят
U1=U6+С61=10+5=15,
U5=U1+С15=15+4=19,
U2=U1+С12=15+2=17,
U3=U2+С23=17+3=20,
U4=U3-С43=20-3=17.
Потенциалы присвоены всем вершинам сети. При этом звено 65 не применялось для построения системы потенциалов, так как на нем полностью использованы пропускные способности. Потенциалы показаны на рис. 2 рядом с вершинами в квадратах.
Проверяем выполнение условия оптимальности на звеньях 64, 25 и 53 (без перевозок) и звене 65 (с «заполненной» пропускной способностью), которые не использовались при построении системы потенциалов.
На звеньях 64, 25 и 53 проверяем выполнение первого условия оптимальности, а на звене 65 – третьего условия.
δ64=U4-U6-С46=17-10-4=3>0,
δ25=U5-U2-С25=19-17-4=-2<0,
δ53=U3-U5-С53=20-19-3=-2<0,
δ65=U5-U6-С56=19-10-2=7>0.
Так как прокатная оценка звена 64 (без перевозок) δ64>0, то нарушено первое условие оптимальности и план необходимо улучшить.
Для улучшения плана составляем замкнутый контур из звена 64 и звеньев с перевозками 43, 32, 21, 61 . При этом на звеньях 64, 43, попутные перевозки, а на звеньях 23, 12, 61 – встречные. Минимальный объем встречной перевозки 50, а минимальная разность между пропускной способностью и объемом перевозки составляет 150 – 80 = 70 единиц. Следовательно, объем улучшения плана составляет 50 единиц (выбрали минимальное из этих значений). Прибавляя этот объем к попутным перевозкам, и вычитая из встречных перевозок, получим улучшенный план (рис. 3).
292036584455(+150)
(+150)
341566516065510
10
1491615609606
4
3
2
5
1
6
4
3
2
5
1
220599014668510
10
342519018478550
50
22155151993905/150
5/150
32727901612904/180
4/180
22345655651529013152184402/90
2/90
4130040123190(+80)
(+80)
117729012319015
15
2853690218440259651516129090
90
3520440113665
204406512827010
10
424434016637014
14
19964401244604/120
4/120
21107407683529108401968519
19
2834640210185(-100)
(-100)
3425190181610130
130
3768090635003/150
3/150
36918902540015868652159002/90
2/90
2367915501654/160
4/160
2844165501653/80
3/80
382524015113017
17
2615565330203/140
3/140
3329940185420(-130)
(-130)
Рис