《運(yùn)籌學(xué)》課后習(xí)題答案 E13-第13次作業(yè)解答-最小費(fèi)用最大流

第十三次作業(yè)解答：P179：13）；

13）求圖7.23中從匕到匕的最小費(fèi)用最大流，邊上的數(shù)字為（4,今）。

解：（1）求該網(wǎng)絡(luò)的最大流，用Ford-Fukerson標(biāo)號(hào)法尋找增廣鏈并調(diào)整流量。

容易找到圖中“黑色（調(diào)整量2）、綠色（調(diào)整量1）和橙色（調(diào)整量2）”三條增廣鏈.

（2）第一次迭代：

①原圖全部是零流弧，保持原邊不變，單位費(fèi)用為權(quán)；

②因?yàn)樗械臋?quán)（單位費(fèi)用）均大于零，可以用狄氏標(biāo)號(hào)法求出最短路:

求至V6短路線0：9)，sf匕V7%f匕(X，小費(fèi)用:V8-鏈。

③調(diào)整流量￡=min(l-0,4-0,2-0)=l。總流量/=1<5

④最小費(fèi)用增廣鏈上單位流量的費(fèi)用：ZG=10+5+7=22?？傎M(fèi)用=1X22=22

調(diào)整后的網(wǎng)絡(luò)如下：

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

(3)第二七Y竺代：畫［削費(fèi)用網(wǎng)絡(luò)V7

①零流弧保持不變，非飽和、非零流弧增加反向弧，飽和弧去掉原邊，添加反向弧。

②用列表法求出最短路：匕T?匕-匕，即最小費(fèi)用增廣鏈。

VsVVVVVVVVV

Wdfd?

12345678t號(hào)4"

Vs0oooo6oooo7oooooo00000

V-105co5oo8ooco8oo12121111

10

Voo-50cooo4oooooo7oooo161616

2

Voo6oo03oo41oooo66666

3

Voooo7oo0ooooco8oooo9999

4

Voooooocooo08oo59ooooco2020

5

Vcooooocooooo09oooo77777

6

Vcooooooo5oooo()7oooo7777

7

Vooooooooooooooco01oooo141414

82

Vtoooo-7oooooooooooooooooo2323

③調(diào)整流量￡=min(3-0,3-0,2-0,2-l)=l。總流量_/；=1+1=2<5

④最小費(fèi)用增廣鏈上單位流量的費(fèi)用：ZG=6+3+7+7=23。

總費(fèi)用=元費(fèi)用+新增費(fèi)用=22+1X23=45

調(diào)整后的網(wǎng)絡(luò)如下：

(4)第三次迭代：畫增廣費(fèi)用網(wǎng)絡(luò)

(1,-5)

①零流弧保持不變，非飽和、非零流弧增加反向弧，飽和弧去掉原邊，添加反向弧。

②用列表法求出最短路：匕一>%->%—%-?匕，即最小費(fèi)用增廣鏈。

VsVVVVVVVVVdp(44)d?d,

12345678t學(xué)

Vs0oooo6oooo7oooooo00000

V-105oo5oooooooo8oo12121111

10

V8-50oo-74oooooooooooo161616

2

V-66oo03oo41oooo66666

3

Voooo7-30oooooo8oooo9999

4

Vcooooooooo08859oooooo2020

5

Voooocooooooo09oooo77777

6

Voooooooo5oooo07oooo7777

7

Voooo8oooocooooo01ooco141414

82

Vtoooo-7oooooooooooo0oooooo2626

③調(diào)整流量e=min(3—l,4-0,2—0,2-1)=2。總流量/=2+2=4<5

④最小費(fèi)用增廣鏈上單位流量的費(fèi)用：=6+1+7+12=26。

總費(fèi)用=元費(fèi)用+新增費(fèi)用=45+2X26=45+52=97

調(diào)整后的網(wǎng)絡(luò)如下：

(5)第四次迭代：畫增廣費(fèi)用網(wǎng)絡(luò)

(1,-5)

①零流弧保持不變，非飽和、非零流弧增加反向弧，飽和弧去掉原邊，添加反向弧。

②用列表法求出最短路：匕-匕一匕—匕—匕—匕一匕一/即最小費(fèi)用增廣鏈。

VsVIV2V3V4V5V6V7V8Vt

J<4)j;8)

學(xué)4”Jd7d?

Vs0oooooooooo7oooooo00000000

VI-1005oo5oooooooooooooooo2121202020

V2co-50oo-74oooooooooooooo2825252525

V3-66oo03oo41oooooooo151515151515

V4oooo7-30oooooo8oooooo211818181818

V5oooooooooo08oo59oocooooo32292929

V6oooooooooooo09oooo77777777

V7oooooo-15oooo0oooooo16161616161616

V8oooooooooooo8-70oooooooo2926262626

Vtoooo-7oooooooooo-120oooooooooo413838

③