下表给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用最大流问题,画出网络图并求数值解。
产量
销地
1 2 3 产量
A
B
２0
30
24
22
5
20
8
7
销量 4 5 6
网络图如下,弧旁数字为
(,)
ij ij
b c
. 设ij
f为边(i,j ) 上的数量，ij c为边(i, j )上的单位运费, 则最小费用最大流的数学ij
u为边(ｉ, j)上的额定容量，规划表达(,)
min;
ij ij
i j E
c f
∈
∑
(,)(,),,0,,f ij ij f j V j V i j E
j i E
v i s f f v i t
i s t ∈∈∈∈=??
-
=-=??
≠?∑
∑
0,(,)ij ij f u i j E ≤≤∈
s ｅts ：
points ／s,v1,v2,v ３,v4，v5,ｔ/; ｅd ｇe(po ｉnts,po ｉnts)
/s,v1 s,v2 v1,v3 ｖ1,v4 ｖ1,v ５ Ｖ２，v3 v2,v4 v ２,v ５ v3,ｔ ｖ4,t Ｖ5,t ／：c ，u,ｆ; ｅnds ｅt ｓ ｄata :
ｃ=0 0 2０ 2４ ５ ３0 2２ ２０ 0 ０ 0; u=8 ７ ８ 8 8 7 7 7 4 5 6; v ｆ=15; e ｎddat ａ
m ｉn =＠sum (edge(i,j ）:ｃ(ｉ,j)*f （ｉ,ｊ));
@for (ｐｏint ｓ（i ）|i ＃ne#＠i ｎde ｘ(s) #an ｄ# i#n ｅ#@in ｄex (t ）： @sum (edge(i,ｊ):ｆ(ｉ,j))-@ｓum (edge(j ， i):f （j,i)）=０; )； ＠s ｕm (ed ｇe(i,j ）|i#e ｑ#@ｉndex (s ）:ｆ（i,ｊ)） =ｖf; @s ｕm (edg ｅ(j,i)|i ＃eq ＃＠index (t):ｆ(j,i)） =vf; @ｆor （ｅdge(ｉ,j)：@bnd (0,ｆ(i,ｊ),u(i,ｊ))） ; end
Ｇl ｏb ａl optim ａl ｓolu ｔion f ｏun ｄ.
Ｏbje ｃt ｉve va ｌu ｅ： 240．0000 Total solver ｉterations: １
Va ｒiab ｌe Va ｌue Redu ｃed Co ｓt
VF 15.00000 0．000000 Ｃ（ Ｓ, Ｖ１) 0.00000０ 0.000０00
C （ S, Ｖ2) 0.0０000０ 0.000０００
C( V １, Ｖ3) 20.０000０ 0.０0
Ｃ( V１,V4) ２４.0000００.00００0０
Ｃ( V１,V５)5．000００0
0.０00000
Ｃ（ V2, V３) ３0.000０0 0.0００000
Ｃ( Ｖ2, V４) ２２.00００0
０.0０0000
C( V２,V5)2０.00000 0.00０000
Ｃ(V3，Ｔ)０.0０0０0０
0．0000００
Ｃ( V4, T) ０.00０000 0．００00００
C(V5, T) 0．0000０0 0.000００0
U( S， V1） 8.000000 0.０00000
Ｕ( S, V２）7.000０00 ０．000000
Ｕ(V１， V3） 8.00０000 0.000０0０
U(Ｖ1，V4） 8.000000 0.000000 U( V１, V5) 8.000００0 0．000000
Ｕ（ V2,Ｖ3) 7.000000 0．0０000０
U(V2，V4） 7.０0０000 0．0００００0
Ｕ（ V2, Ｖ５) ７.０0００00 0.0０000０
U( V3, T) 4.000000 ０.00000０
U( V４, T) 5.０000０0 0.00０000
U( Ｖ５, T) 6.00００00 0.０000０0
F（Ｓ, V１） 8.000000
-10.00000
F( S, V2) 7.00０000 0.00０000
F( V1, V3） 2.０000０0 ０．00０000
F( V１， V4) ０.000000 12.00000
F( V１，Ｖ5) 6.0０0000 ０.0０0000
F( Ｖ2, Ｖ3) 2.000000 ０.00000
０
Ｆ（Ｖ2, V4) 5．0０0０0０ 0．０
F( Ｖ2,V5) 0.０００00０
5.0０000０
Ｆ( Ｖ3,T) 4.000000 ０.000０00
F( Ｖ4,T) 5.000000
-8.000000
Ｆ( V5,T) ６.0０0000－1５.00０00
Row Slack orＳuｒｐｌuｓ Duaｌ P ｒiｃｅ
1 24０.000０ -1．０00０00
2 0．0000０0 0.0００000
30．０00０00 -１
0.00000
4 0.000000
20.0000０
50.０00000 12．000０0
6 0.000000
5.000000
7 0.00000０ -１0.０0000
8０.0０0000
-20.00000
结果其最小总费用为240。