《运筹学》课后习题答案 E13-第13次作业解答-最小费用最大流

第十三次作业解答：P179：13）；

13）求图7.23中从匕到匕的最小费用最大流，边上的数字为（4,今）。

解：（1）求该网络的最大流，用Ford-Fukerson标号法寻找增广链并调整流量。

容易找到图中“黑色（调整量2）、绿色（调整量1）和橙色（调整量2）”三条增广链.

（2）第一次迭代：

①原图全部是零流弧，保持原边不变，单位费用为权；

②因为所有的权（单位费用）均大于零，可以用狄氏标号法求出最短路:

求至V6短路线0：9)，sf匕V7%f匕(X，小费用:V8-链。

③调整流量£=min(l-0,4-0,2-0)=l。总流量/=1<5

④最小费用增广链上单位流量的费用：ZG=10+5+7=22。总费用=1X22=22

调整后的网络如下：

、/_(3,9,0)v,

(3)第二七Y竺代：画［削费用网络V7

①零流弧保持不变，非饱和、非零流弧增加反向弧，饱和弧去掉原边，添加反向弧。

②用列表法求出最短路：匕T•匕-匕，即最小费用增广链。

VsVVVVVVVVV

Wdfd?

12345678t号4"

Vs0oooo6oooo7oooooo00000

V-105co5oo8ooco8oo12121111

10

Voo-50cooo4oooooo7oooo161616

2

Voo6oo03oo41oooo66666

3

Voooo7oo0ooooco8oooo9999

4

Voooooocooo08oo59ooooco2020

5

Vcooooocooooo09oooo77777

6

Vcooooooo5oooo()7oooo7777

7

Vooooooooooooooco01oooo141414

82

Vtoooo-7oooooooooooooooooo2323

③调整流量£=min(3-0,3-0,2-0,2-l)=l。总流量_/；=1+1=2<5

④最小费用增广链上单位流量的费用：ZG=6+3+7+7=23。

总费用=元费用+新增费用=22+1X23=45

调整后的网络如下：

(4)第三次迭代：画增广费用网络

(1,-5)

①零流弧保持不变，非饱和、非零流弧增加反向弧，饱和弧去掉原边，添加反向弧。

②用列表法求出最短路：匕一>%->%—%-»匕，即最小费用增广链。

VsVVVVVVVVVdp(44)d?d,

12345678t学

Vs0oooo6oooo7oooooo00000

V-105oo5oooooooo8oo12121111

10

V8-50oo-74oooooooooooo161616

2

V-66oo03oo41oooo66666

3

Voooo7-30oooooo8oooo9999

4

Vcooooooooo08859oooooo2020

5

Voooocooooooo09oooo77777

6

Voooooooo5oooo07oooo7777

7

Voooo8oooocooooo01ooco141414

82

Vtoooo-7oooooooooooo0oooooo2626

③调整流量e=min(3—l,4-0,2—0,2-1)=2。总流量/=2+2=4<5

④最小费用增广链上单位流量的费用：=6+1+7+12=26。

总费用=元费用+新增费用=45+2X26=45+52=97

调整后的网络如下：

(5)第四次迭代：画增广费用网络

(1,-5)

①零流弧保持不变，非饱和、非零流弧增加反向弧，饱和弧去掉原边，添加反向弧。

②用列表法求出最短路：匕­匕一匕—匕—匕—匕一匕一/即最小费用增广链。

VsVIV2V3V4V5V6V7V8Vt

J<4)j;8)

学4”Jd7d?

Vs0oooooooooo7oooooo00000000

VI-1005oo5oooooooooooooooo2121202020

V2co-50oo-74oooooooooooooo2825252525

V3-66oo03oo41oooooooo151515151515

V4oooo7-30oooooo8oooooo211818181818

V5oooooooooo08oo59oocooooo32292929

V6oooooooooooo09oooo77777777

V7oooooo-15oooo0oooooo16161616161616

V8oooooooooooo8-70oooooooo2926262626

Vtoooo-7oooooooooo-120oooooooooo413838

③