運(yùn)籌學(xué)基礎(chǔ) 課件 第 4章

第4章網(wǎng)絡(luò)最優(yōu)化4.1最小支撐樹(shù)問(wèn)題4.2最短路問(wèn)題4.3最大流問(wèn)題4.4

最小費(fèi)用流問(wèn)題4.5二分匹配問(wèn)題

4.1最小支撐樹(shù)問(wèn)題

定義4-3連通圖G=(V,E)的最小支撐樹(shù)T(G)就是圖的權(quán)重之和最小的支撐樹(shù)。

其中,cij是邊(i,j)的權(quán)重。

例4-1某公司中標(biāo)為“一帶一路”上某國(guó)家的六個(gè)居民點(diǎn)提供寬帶建設(shè)服務(wù),圖4-1給出了鋪設(shè)通信線路的可能情況及相應(yīng)距離。請(qǐng)確定最經(jīng)濟(jì)的通信線路鋪設(shè)方案,使六個(gè)居民點(diǎn)可以連接起來(lái)。

圖4-1寬帶網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)問(wèn)題的輸入

記六個(gè)居民點(diǎn)及相應(yīng)的可能連接方式組成的圖為G=(V,E),設(shè)xij為決策變量,xij=1代表點(diǎn)i與點(diǎn)j之間鋪設(shè)的通信線路,否則不鋪設(shè)。此問(wèn)題可以表示為以下線性規(guī)劃模型

本問(wèn)題可以使用線性規(guī)劃求解,但是對(duì)于點(diǎn)的數(shù)量較多的問(wèn)題,使用線性規(guī)劃求解的話就不可行了。例如,對(duì)于有60個(gè)點(diǎn)的圖,要用線性規(guī)劃模型求解最小支撐樹(shù),需要的約束條件數(shù)量比地球上的原子數(shù)量還多。

支撐樹(shù)使用了最少數(shù)量的邊連通了圖的所有點(diǎn),從數(shù)量方面是網(wǎng)絡(luò)連通優(yōu)化設(shè)計(jì)問(wèn)題的最優(yōu)方案,而最小支撐樹(shù)是邊的總長(zhǎng)度之和最小的支撐樹(shù),因此,從數(shù)量和質(zhì)量方面都是最優(yōu)的網(wǎng)絡(luò)連通設(shè)計(jì)方案。

4.1.2兩個(gè)屬性

1.Cut屬性

在最小支撐樹(shù)的線性規(guī)劃模型中,式(4-2)代表連通性約束,不等式左側(cè)的表達(dá)式表示圖的截集中至少有一條邊要保留。

定義4-4-圖G=(V,E)中,對(duì)于?S?V,所有的一端在S中、一端不在S中的邊構(gòu)成的集合稱為圖的截集。

例4-2圖4-1的截集數(shù)量為6!/2,其中兩個(gè)如圖4-2所示。圖4-2圖的截集示例

最小支撐樹(shù)的Cut屬性:連通圖G任意截集的最小邊必屬于最小支撐樹(shù)。

2.Cycle屬性

最小支撐樹(shù)的另外一個(gè)屬性是無(wú)圈的,因此,任意圈上肯定有一條邊不屬于最小支撐樹(shù),依據(jù)“貪婪法”的啟發(fā)式規(guī)則,我們猜測(cè)圈上的最大邊不屬于最小支撐樹(shù)。

最小支撐樹(shù)的Cycle屬性:圖中圈上若只有單一最大邊,則此最大邊一定不屬于最小支撐樹(shù);若有多條最大邊,則去掉任意一條最大邊,不影響得到最小支撐樹(shù)?？傊?去掉圈上一條最大邊,仍然可以得到最小支撐樹(shù)。

算法的步驟如下:

例4-3利用Prim算法求解圖4-1的最小支撐樹(shù)。

步驟1:首先令S={6},則Cut(S)={(6,3),(6,4)},E(T)=?,得到最小邊為emin=(6,4),如圖4-3所示。

步驟2:(6,4)是最小支撐樹(shù)上的邊,令E(T)=E(T)∪emin={(6,4)},S=S∪V(emin)={6,4},則

Cut(S)={(6,3),(4,1),(4,2),(4,3),(4,5)}

得到最小邊emin=(4,2),如圖4-4所示。

圖4-3例4-3求解步驟1的結(jié)果

圖4-4-例4-3求解步驟2的結(jié)果

步驟3:(4,2)是最小支撐樹(shù)上的邊,令E(T)=E(T)∪emin={(6,4),(4,2)},S=S∪V(emin)={6,4,2},則

Cut(S)={(6,3),(4,1),(4,3),(4,5),(2,1),(2,3),(2,5)}

得到最小邊emin=(1,2),如圖4-5所示。

圖4-5例4-3求解步驟3的結(jié)果

步驟4:(1,2)是最小支撐樹(shù)上的邊,令E(T)=E(T)∪emin={(6,4),(4,2),(1,2)},S=S∪V(emin)={6,4,2,1},則

Cut(S)={(6,3),(4,3),(4,5),(2,3),(2,5),(1,3),(1,5)}

得到最小邊有三條,emin=(2,3)、(2,5)、(4,3),如圖4-6所示。

圖4-6例4-3求解步驟4的結(jié)果

步驟5:可以任選一條最小邊加入E(T),如(2,3)。令E(T)=E(T)∪emin

={(6,4),(4,2),(1,2),(2,3)},S=S∪V(emin

)={6,4,2,1,3},則

Cut(S)={(4,5),(2,5),(1,5)}

得到最小邊emin

=(2,5),如圖4-7所示。

圖4-7例4-3求解步驟5的結(jié)果

步驟6:(2,5)是最小支撐樹(shù)上的邊。令E(T)=E(T)∪emin

={(6,4),(4,2),(1,2),(2,3),(2,5)},S=S∪V(emin

)={6,4,2,1,3,5},算法結(jié)束,如圖4-8所示。圖4-8例4-3求解步驟6的結(jié)果

2.Kruskal算法

從構(gòu)造的角度考慮,在選擇一部分邊時(shí),只要避免將圈上的最大邊選上就可以了。

Kruskal從構(gòu)造的角度提出了尋找最小支撐樹(shù)的方法。

Kruskal法將所有的邊從圖中取出來(lái),從小到大依次考慮重新加回到圖中,如果不產(chǎn)生圈則留下,否則拋棄掉,這也是一種“貪婪算法”。

例4-4-利用Kruskal算法求解圖4-1的最小支撐樹(shù)。

步驟1:令E(T)=?,當(dāng)前圖中的最小邊為

如圖4-9所示。圖4-9例4-4求解步驟1的結(jié)果

步驟2:(1,2)選作最小支撐樹(shù)上的邊,令E(T)=E(T)∪emin={(1,2)},E=E-{(1,2)},剩下圖中的最小邊為圖4-10例4-4求解步驟2的結(jié)果

步驟3:(6,4)選作最小支撐樹(shù)上的邊,令E(T)=E(T)∪emin

={(1,2),(6,4)},E=E-{(6,4)},剩下圖中的最小邊為

如圖4-11所示。圖4-11例4-4求解步驟3的結(jié)果

步驟4:(2,4)選作最小支撐樹(shù)上的邊,令E(T)=E(T)∪emin

={(1,2),(6,4),(2,4)},E=E-{(2,4)},剩下圖中的最小邊有三條,emin

=(2,3)、(2,5)、(4,3),如圖4-12所示。圖4-12例4-4求解步驟4的結(jié)果

步驟5:可以任選一條最小邊加入E(T),如(2,3)。令E(T)=E(T)∪emin={(1,2),(6,4),(2,4),(2,3)},E=E-{(2,3)},剩下圖中的最小邊有兩條,emin=(2,5)、(4,3),如圖4-13所示。圖4-13例4-4求解步驟5的結(jié)果

步驟6:可以任選一條最小邊加入E(T),如(2,5)。令E(T)=E(T)∪emin

={(1,2),(6,4),(2,4),(2,3),(2,5)},E=E-{(2,5)},剩下圖中的最小邊為emin

=(4,3),如圖4-14所示。圖4-14-例4-4求解步驟6的結(jié)果

步驟7:此時(shí),E(T)中已經(jīng)有5條邊滿足支撐樹(shù)點(diǎn)數(shù)和邊數(shù)的關(guān)系,算法停止。可以看到,此時(shí),若再加入任意邊,都會(huì)產(chǎn)生圈。

算法的步驟可以總結(jié)為口訣:“一邊一邊地連,先連最小邊,不能產(chǎn)生圈”。

3.破圈法

破圈法是指利用Cycle屬性,逐步去掉圈上的最大邊,最終得到最小支撐樹(shù)。其步驟總結(jié)為口訣:“一圈一圈地破,破掉圈上最大邊”。

對(duì)于連通圖G=(V,E),破圈法的步驟總結(jié)如下:

4.1.4-拓展應(yīng)用:k－聚類分析

聚類就是一種尋找數(shù)據(jù)之間一種內(nèi)在結(jié)構(gòu)的技術(shù)。聚類把全體數(shù)據(jù)實(shí)例組織成不同的組,處于相同分組中的數(shù)據(jù)實(shí)例彼此相近,處于不同分組中的實(shí)例彼此相遠(yuǎn)。對(duì)一個(gè)集合

V={v1,v2,…,vn}中的對(duì)象,在已知對(duì)象之間差異性度量的情況下,將其分為由類似的對(duì)象組成的多個(gè)類Vi的過(guò)程,稱為聚類分析,其中

使用最小支撐樹(shù)進(jìn)行k－聚類分析的步驟如下:

步驟1:將聚類的對(duì)象集合V看作圖G=(V,E)的點(diǎn)集,將對(duì)象之間的差異性dij作為點(diǎn)之間邊(i,j)∈E的權(quán)重。

步驟2:求解G的最小支撐樹(shù)T=(V,E')。

步驟3:去掉T上的k-1條最大邊,得到k個(gè)相互不連通的連通子圖Gi=(Vi,Ei

')i=1,…,k,則Vi是第i類的點(diǎn)集合。

例4-5某電子企業(yè)需要在10臺(tái)機(jī)器上生產(chǎn)15種電子零件。企業(yè)準(zhǔn)備將機(jī)器分成若干組,使零件在不同機(jī)器上生產(chǎn)的“差異”最小。零件i在機(jī)器j上生產(chǎn)的“差異”定義為

其中,nij表示機(jī)器i和機(jī)器j上都可以生產(chǎn)的零件數(shù)量;mij表示只能在機(jī)器i和機(jī)器j其中之一生產(chǎn)的零件數(shù)量。根據(jù)表4-1給出的數(shù)據(jù),求將機(jī)器分成兩組和三組的解。

步驟1:將不同機(jī)器生產(chǎn)的零件按照表4-1所示的對(duì)應(yīng)關(guān)系輸入Matlab的cell結(jié)構(gòu)變量中,可以得到:

步驟2:按照差異的定義,計(jì)算dij:

步驟3:將d作為鄰接矩陣,求解圖的最小支撐樹(shù):

結(jié)果如圖4-15所示。

圖4-15機(jī)器差異性最小支撐樹(shù)

步驟4:若要將機(jī)器分成2組,則去掉最小支撐樹(shù)上的一條最大邊就可以達(dá)到目的(見(jiàn)圖4-16(a)),若要將機(jī)器分成3組,再去掉一條最大邊即可(見(jiàn)圖4-16(b)),以此類推。圖4-16利用最小支撐樹(shù)對(duì)圖上的點(diǎn)進(jìn)行2－聚類和3－聚類

4.1.5拓展應(yīng)用:戰(zhàn)備通信節(jié)點(diǎn)的建設(shè)問(wèn)題

1.問(wèn)題描述

構(gòu)建將N個(gè)城市作為節(jié)點(diǎn)的有線通信網(wǎng)絡(luò),在每個(gè)城市內(nèi)設(shè)置一架專用網(wǎng)絡(luò)連接設(shè)備,請(qǐng)?jiān)O(shè)計(jì)通信網(wǎng)絡(luò)的最經(jīng)濟(jì)連接方案。同時(shí),為了增加抗毀性,可以在N個(gè)城市之外的地方構(gòu)建一定數(shù)量的戰(zhàn)備節(jié)點(diǎn),戰(zhàn)備節(jié)點(diǎn)平時(shí)不工作,當(dāng)出現(xiàn)應(yīng)急突發(fā)情況、通信網(wǎng)絡(luò)中斷時(shí),可以啟用戰(zhàn)備節(jié)點(diǎn),迅速地恢復(fù)通信網(wǎng)絡(luò)的連通性,請(qǐng)?jiān)O(shè)計(jì)戰(zhàn)備節(jié)點(diǎn)的建設(shè)方案。設(shè)計(jì)時(shí)應(yīng)充分考慮經(jīng)濟(jì)性和抗毀性。經(jīng)濟(jì)性是指要考慮節(jié)省網(wǎng)絡(luò)連接的總費(fèi)用,而抗毀性是指要提高網(wǎng)絡(luò)在節(jié)點(diǎn)故障的情況下仍然保持連通的能力。

現(xiàn)已知138個(gè)城市(見(jiàn)圖4-17)建設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)的選址的經(jīng)緯度坐標(biāo),請(qǐng)為通信網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)提供優(yōu)化方法。圖4-17需要建立通信網(wǎng)絡(luò)連接的138個(gè)節(jié)點(diǎn)分布

2.問(wèn)題分析

若只考慮經(jīng)濟(jì)性指標(biāo),這是一個(gè)網(wǎng)絡(luò)最優(yōu)化決策中的最小支撐樹(shù)問(wèn)題(參見(jiàn)4.1節(jié)),輸入是點(diǎn)以及點(diǎn)之間的連接費(fèi)用。給定的N個(gè)城市作為網(wǎng)絡(luò)上的點(diǎn),點(diǎn)之間的通信連接費(fèi)用可以用點(diǎn)之間的通信連接長(zhǎng)度來(lái)代替。

3.最經(jīng)濟(jì)的連通方案

根據(jù)已知通信網(wǎng)絡(luò)節(jié)點(diǎn)的選址經(jīng)緯度坐標(biāo),可以計(jì)算相互之間的距離,這是一種簡(jiǎn)要的代替節(jié)點(diǎn)之間通信連接建設(shè)費(fèi)用的方法。然后利用網(wǎng)絡(luò)最優(yōu)化中的最小支撐樹(shù)求解算

法,求解通信線路總長(zhǎng)度最短的建設(shè)方案。假設(shè)將N個(gè)城市的經(jīng)緯度坐標(biāo)(度)存儲(chǔ)到N×2維變量Cord中,其第一列存儲(chǔ)的是點(diǎn)的緯度信息,第二列存儲(chǔ)的是經(jīng)度信息,共有N行,每行對(duì)應(yīng)一個(gè)城市選址點(diǎn),可得到:

求得的以距離度量的最經(jīng)濟(jì)的通信線路建設(shè)方案如圖4-18所示。

圖4-18以距離度量的最經(jīng)濟(jì)的通信線路建設(shè)方案

4.最經(jīng)濟(jì)的恢復(fù)方案

預(yù)備建設(shè)戰(zhàn)備節(jié)點(diǎn)的集合為Nb,使通信節(jié)點(diǎn)Nd?V被破壞的情景下,網(wǎng)絡(luò)G'=(V-Nd

,E-E(Nd

)),可以對(duì)網(wǎng)絡(luò)進(jìn)行連通性分析

例如,去掉第53、56和105個(gè)城市之后,網(wǎng)絡(luò)分成相互不連通的4個(gè)部分,如圖4-19所示。Matlab代碼如下:

圖4-19破壞掉3個(gè)節(jié)點(diǎn)后,通信網(wǎng)絡(luò)分成4個(gè)獨(dú)立的部分

4.2最短路問(wèn)題4.2.1線性規(guī)劃模型在網(wǎng)絡(luò)G=(V,E)中,邊(i,j)∈E的權(quán)值(長(zhǎng)度、時(shí)間、費(fèi)用等的抽象)為cij,尋找從起點(diǎn)s∈V到終點(diǎn)t∈V的最短路P,就稱為最短路問(wèn)題。目標(biāo)函數(shù)是位于最短路上的邊的總長(zhǎng)度最短,即其中,xij∈{0,1}是決策變量,xij=1代表邊(i,j

)是最短路上的邊,否則不是。

約束條件是,對(duì)于起點(diǎn)s來(lái)講

對(duì)于終點(diǎn)t來(lái)講

對(duì)于網(wǎng)絡(luò)中的其他點(diǎn)k∈V-s-t來(lái)講

4.2.2最優(yōu)性條件

在圖G=(V,E)上,為每個(gè)點(diǎn)vj引入一個(gè)標(biāo)號(hào){dj,vj},dj代表從s出發(fā)到達(dá)vj的某條已知道路的長(zhǎng)度,vi是這條道路上與vj鄰接的上一個(gè)點(diǎn)。

最優(yōu)性條件:如果圖上的所有的點(diǎn)的標(biāo)號(hào)滿足以下條件:

則圖上任意點(diǎn)vi的標(biāo)號(hào)dj都代表從s點(diǎn)到當(dāng)前點(diǎn)vi的最短路長(zhǎng)度。

4.2.3標(biāo)號(hào)法

1.標(biāo)號(hào)更新操作

假設(shè)對(duì)于圖上的某個(gè)邊(vi,vj

),其長(zhǎng)度為cij,兩個(gè)端點(diǎn)的標(biāo)號(hào)分別為{di,vi1},{dj,vj1},如圖4-20所示。曲線邊代表從s到箭頭端點(diǎn)的某條路,值代表這條路的長(zhǎng)度;直線邊代表圖上的邊,值代表這條邊的長(zhǎng)度。

若

可以執(zhí)行標(biāo)號(hào)更新操作

代表的含義是從s出發(fā)到點(diǎn)vj,找到了一條更短的路。

圖4-20標(biāo)號(hào)示意圖

2.標(biāo)號(hào)固定操作

假設(shè)圖上的邊的長(zhǎng)度均非負(fù),那么在任意時(shí)刻,圖上的最小標(biāo)號(hào)對(duì)應(yīng)的點(diǎn)為

此時(shí),可以將vmin的標(biāo)號(hào)固定下來(lái),不再考慮更新,也可稱其為永久標(biāo)號(hào)。因?yàn)楦鶕?jù)標(biāo)號(hào)更新操作的條件,永久標(biāo)號(hào)不可能再更新。對(duì)于任意其他點(diǎn)的標(biāo)號(hào),有

不可能存在標(biāo)號(hào)更新條件:

直觀理解就是,從s出發(fā)到任意其他與vj鄰接的點(diǎn)vi,再經(jīng)過(guò)邊(vi,vj)到永久標(biāo)號(hào)點(diǎn)vj,都不可能更短了。但是確定永久標(biāo)號(hào)的前提是cij≥0,當(dāng)圖中有負(fù)邊的時(shí)候,不能確定永久標(biāo)號(hào)。

3.標(biāo)號(hào)設(shè)定法

所謂標(biāo)號(hào)設(shè)定法(Dijkstra算法),就是針對(duì)圖上不存在負(fù)值邊的G,在求解最短路的時(shí)候,每次更新標(biāo)號(hào)后,都確定一個(gè)最小的標(biāo)號(hào)點(diǎn)作為永久標(biāo)號(hào)點(diǎn),不再考慮標(biāo)號(hào)的更新,直到所有的標(biāo)號(hào)都固定下來(lái)后,算法結(jié)束。標(biāo)號(hào)設(shè)定法的步驟如下:

例4-6在圖4-21中,求解從S=1到t=5的最短路。圖4-21例4-6圖

步驟1:設(shè)起點(diǎn)的標(biāo)號(hào)為(0,?),其他點(diǎn)的標(biāo)號(hào)為(∞,?),

S={v1},如圖4-22所示。圖4-22例4-6求解步驟1的結(jié)果

步驟2:更新{vj|(vi,vj)∈E,vi∈S}的標(biāo)號(hào),找到最小標(biāo)號(hào)vmin=v2,將其標(biāo)號(hào)固定下來(lái),令S=S∪{vmin}={v1,v2},如圖4-23所示。圖4-23例4-6求解步驟2的結(jié)果

步驟3:更新{vj|(vi,vj)∈E,vi∈S}的標(biāo)號(hào),找到最小標(biāo)號(hào)vmin=v3,將其標(biāo)號(hào)固定下來(lái),S=S∪{vmin}={v1,v2,v3},如圖4-24所示。圖4-24-例4-6求解步驟3的結(jié)果

步驟4:更新{vj|(vi,vj)∈E,vi∈S}的標(biāo)號(hào),找到最小標(biāo)號(hào)vmin=v4,將其標(biāo)號(hào)固定下來(lái),令S=S∪{vmin}={v1,v2,v3,v4},如圖4-25所示。圖4-25例4-6求解步驟4的結(jié)果

步驟5:更新{vj|(vi,vj)

∈E,vi∈S}的標(biāo)號(hào),找到最小標(biāo)號(hào)vmin=v5,將其標(biāo)號(hào)固定下來(lái),令S=S∪{vmin}={v1,v2,v3,v4,v5}。S=V,算法停止,如圖4-26所示。圖4-26例4-6求解步驟5的結(jié)果

4.標(biāo)號(hào)更新法

所謂標(biāo)號(hào)更新法,是指在求解最短路的時(shí)候,迭代地應(yīng)用標(biāo)號(hào)更新操作,直到所有的點(diǎn)的標(biāo)號(hào)都無(wú)法更新為止,也就是滿足dj≤di+cij。標(biāo)號(hào)更新法的步驟如下:

步驟1:設(shè)起點(diǎn)的標(biāo)號(hào)為{0,?},其他點(diǎn)的標(biāo)號(hào)為{∞,?}。

步驟2:更新{vj|(vi,vj)∈E}的標(biāo)號(hào)。

步驟3:如果沒(méi)有標(biāo)號(hào)可以更新,則算法停止,否則轉(zhuǎn)步驟2。

例4-7在圖4-27中,求解從S=1到t=5的最短路。圖4-27例4-7圖

步驟1:設(shè)起點(diǎn)的標(biāo)號(hào)為{0,?},其他點(diǎn)的標(biāo)號(hào)為{∞,?},如圖4-28所示。圖4-28例4-7求解步驟1的結(jié)果

步驟2:更新{vj|(vi,vj)∈E}的標(biāo)號(hào),如圖4-29所示。圖4-29例4-7求解步驟2的結(jié)果

步驟3:更新{vj|(vi,vj)∈E}的標(biāo)號(hào),沒(méi)有標(biāo)號(hào)可更新,算法停止,如圖4-30所示。圖4-30例4-7求解步驟3的結(jié)果

4.2.4-拓展應(yīng)用:數(shù)據(jù)約減

1.問(wèn)題描述

數(shù)據(jù)包含信息,但是并不代表數(shù)據(jù)越多信息量越多。因此,對(duì)數(shù)據(jù)進(jìn)行約減,可方便信息的存儲(chǔ)、讀取、分析等,同時(shí),數(shù)據(jù)所包含的信息量沒(méi)有損失或者損失最小化,這個(gè)問(wèn)題稱為數(shù)據(jù)約簡(jiǎn)問(wèn)題。

假設(shè)vi和vj(i<j)之間的點(diǎn)都被約減掉,那么,節(jié)省的存儲(chǔ)空間可以度量為

2.模型建立

如果要完全地羅列出圖G的所有弧,由于點(diǎn)的總數(shù)N很大,因此為了存儲(chǔ)所有的弧所需的空間仍然很大。為了降低計(jì)算對(duì)存儲(chǔ)空間的需求,可以采用降度的思路,迭代完成數(shù)據(jù)的約減,每步迭代只構(gòu)造圖G的部分弧。

3.計(jì)算實(shí)例分析

假設(shè)有一組按時(shí)間序列記錄的數(shù)據(jù),三個(gè)參數(shù)分別為A、B和C,數(shù)據(jù)如表4-2所示。

首先對(duì)數(shù)據(jù)進(jìn)行無(wú)量綱化處理,得到的結(jié)果如圖4-31所示。圖4-31對(duì)飛參數(shù)據(jù)進(jìn)行無(wú)量綱化處理后的數(shù)據(jù)

按照間隔為2的跨度建立最短路問(wèn)題模型,則對(duì)于這個(gè)樣本數(shù)據(jù)來(lái)講,無(wú)損數(shù)據(jù)約減后(令α=1,β=1000000)剩余33個(gè)點(diǎn),也就是有5個(gè)點(diǎn)是完全信息量意義下的冗余點(diǎn)(見(jiàn)圖4-32),這5個(gè)點(diǎn)的序號(hào)分別是17,18,19,20,21。

圖4-32無(wú)損數(shù)據(jù)約減后得到的數(shù)據(jù)序列,使用*標(biāo)識(shí)

如果信息可以有損失,則可以有更多的點(diǎn)被約減掉,令α=1,則隨著β值的變化,被約減的點(diǎn)的數(shù)量統(tǒng)計(jì)如圖4-33所示。

圖4-33α=1情況下,隨著β值的增加,可以約減飛參數(shù)據(jù)的個(gè)數(shù)

4.3最大流問(wèn)題

4.3.1線性規(guī)劃模型在圖G=(V,E)中,邊(i,j)∈E帶有容量uij和流量xij兩個(gè)參數(shù),最大流問(wèn)題就是求解從起點(diǎn)s到終點(diǎn)t可以通過(guò)的最大流量。

目標(biāo)函數(shù)是網(wǎng)絡(luò)流量的最大化,也就是從s發(fā)出的流量最大,或者流入t的流量最大,即

對(duì)于圖上的點(diǎn)k∈V-{s,t},滿足以下流量守恒約束

任意邊上的流量還要滿足容量約束

4.3.2剩余容量圖

為了更加直觀地在圖上使用標(biāo)號(hào)法求解圖的最大流,將容量流量標(biāo)號(hào)變換為剩余容量標(biāo)號(hào)。從容量流量標(biāo)號(hào)到剩余容量標(biāo)號(hào)的方法如圖4-34所示。圖4-33α=1情況下,隨著β值的增加,可以約減飛參數(shù)據(jù)的個(gè)數(shù)

4.3.3增廣鏈法

利用剩余容量圖法,計(jì)算圖上從s到t的最大流的步驟如下:

步驟1:將圖G=(V,E)的邊都轉(zhuǎn)化為剩余容量標(biāo)號(hào)。

步驟2:在剩余容量圖上找到一條從s到t的任意路p,若找不到,則轉(zhuǎn)步驟4;否則計(jì)算

例4-8在圖4-35所示的容量圖中,求從S到t的最大流。圖4-35例4-8圖

步驟1:將圖G=(V,E)的邊都轉(zhuǎn)化為剩余容量標(biāo)號(hào),在剩余容量圖上找到一條從s到t的任意路p,并計(jì)算最大可擴(kuò)充流量rmin=5,如圖4-36所示。圖4-36例4-8求解步驟1的結(jié)果

步驟2:在p上擴(kuò)充流量,即執(zhí)行以下運(yùn)算:

結(jié)果如圖4-37所示。

圖4-37例4-8求解步驟2的結(jié)果

步驟3:在剩余容量圖上找到一條從s到t的任意路p,并計(jì)算最大可擴(kuò)充流量,如圖4-38所示。圖4-38例4-8求解步驟3的結(jié)果

步驟4:在p上擴(kuò)充流量,即執(zhí)行以下運(yùn)算:

結(jié)果如圖4-39所示。圖4-39例4-8求解步驟4的結(jié)果

步驟5:在剩余容量圖上找不到一條從s到t的路p,算法停止,將剩余容量圖上所有的邊,轉(zhuǎn)換為容量流量標(biāo)號(hào)。也就是對(duì)于邊(i,j),其容量為uij,流量xij=rji=uij-rij,得到網(wǎng)絡(luò)最大流為6,結(jié)果如圖4-40所示。圖4-40例4-8求解步驟5的結(jié)果

4.3.4-拓展應(yīng)用:彈藥目標(biāo)最大化匹配問(wèn)題

不同類型的彈藥適合轟炸不同類型的目標(biāo),如果匹配不得當(dāng),轟炸效果會(huì)大打折扣。在某次空中進(jìn)攻作戰(zhàn)任務(wù)規(guī)劃中,有A、B、C、D、E五類彈藥各一個(gè)單位,計(jì)劃打擊6個(gè)

目標(biāo)。6個(gè)目標(biāo)最適合使用的彈藥如表4-3所示。

請(qǐng)問(wèn)最多能打擊幾個(gè)目標(biāo)?

將待打擊目標(biāo)和彈藥都看作圖上的點(diǎn),彈藥和目標(biāo)之間有一條邊,容量為1,代表彈藥目標(biāo)的匹配關(guān)系,增加一個(gè)虛擬的起始點(diǎn)s和一個(gè)虛擬的終點(diǎn)t,建立最大流模型如圖4-41所示,則圖上的從s到t的任意一個(gè)單位流,都代表一個(gè)彈藥目標(biāo)匹配,最大流是由單位流組成的,代表最大的匹配關(guān)系。

圖4-41彈藥目標(biāo)匹配問(wèn)題的最大流

步驟1:根據(jù)表4-3建立圖模型:

步驟2:求解圖上的最大流,得到最優(yōu)匹配方案:

4.3.5拓展應(yīng)用:最大投送能力評(píng)估問(wèn)題

最大投送能力是機(jī)動(dòng)能力的重要度量?，F(xiàn)假定需要從三個(gè)倉(cāng)庫(kù)6、7、8將后勤物資運(yùn)送到目的地1。道路上的容量取決于這條路上可用運(yùn)輸工具的數(shù)量、容量以及往返次數(shù)。表

4-4給出了相應(yīng)路線上的每天的最大運(yùn)輸能力,也就是容量。請(qǐng)?jiān)u估三個(gè)倉(cāng)庫(kù)到目的地的最大投送能力。

若將倉(cāng)庫(kù)和目的地都看作圖上的點(diǎn),倉(cāng)庫(kù)到目的地之間的道路投送容量設(shè)為邊上的容量值,為圖4-42增加一個(gè)虛擬的起點(diǎn)s連接到所有的倉(cāng)庫(kù),增加一個(gè)虛擬的終點(diǎn)t連接到所有的營(yíng)地,則可以使用最大流模型進(jìn)行求解。

步驟1:建立容量網(wǎng)絡(luò),將表4-4的數(shù)據(jù)存儲(chǔ)到CapacityA矩陣中,在Matlab中建立有向圖模型:

結(jié)果如圖4-42所示。圖4-42投送能力評(píng)估的容量圖模型

步驟2:求解從9到1的最大流:

求得結(jié)果如圖4-43所示。

圖4-43最大投送能力的解

4.4-最小費(fèi)用流問(wèn)題4.4.1線性規(guī)劃模型在圖G=(V,E)中,邊(i,j)∈E上的參數(shù)包括容量uij、單位流量費(fèi)用cij和實(shí)際流量xij,一些稱為源點(diǎn)或者匯點(diǎn)的點(diǎn)上具有參數(shù)bi,代表點(diǎn)上純供應(yīng)流量或者純消耗流量,供應(yīng)點(diǎn)的供應(yīng)流量要流經(jīng)網(wǎng)絡(luò)到達(dá)需求點(diǎn)滿足其需求,最小費(fèi)用流問(wèn)題就是求解從源點(diǎn)s到匯點(diǎn)t的最小費(fèi)用流方案?？梢员硎緸橐韵戮€性規(guī)劃模型

4.4.2三個(gè)最優(yōu)性條件

1.負(fù)圈最優(yōu)性條件

定理4-1一個(gè)網(wǎng)絡(luò)流方案是最小費(fèi)用流的充分必要條件是,剩余容量圖中不存在單位流量費(fèi)用為負(fù)的增廣圈。

證明:首先證明必要性。若剩余容量圖中存在增廣圈,且其擴(kuò)充流量的費(fèi)用為負(fù),則可以在這個(gè)圈上擴(kuò)充流量,總的費(fèi)用下降,因此,必要性得證。

2.勢(shì)差最優(yōu)性條件

定理4-2對(duì)每個(gè)點(diǎn)增加一個(gè)勢(shì)值π(i),i∈V,如果存在一組勢(shì)值使以下不等式成立

則網(wǎng)絡(luò)上的可行流為最小費(fèi)用流,且可稱

的勢(shì)差。

證明:對(duì)于網(wǎng)絡(luò)上的可行流x*,若存在勢(shì)值使勢(shì)差c

成立,則網(wǎng)絡(luò)上任意增廣圈W上的勢(shì)差之和,即

不存在負(fù)值增廣圈。因此,根據(jù)負(fù)圈最優(yōu)性條件,充分性得證。

3.互補(bǔ)松弛最優(yōu)性條件

定理4-3一個(gè)網(wǎng)絡(luò)流方案x*是最小費(fèi)用流的充分必要條件是,存在這么一組勢(shì)值使以下條件成立:

4.4.3兩個(gè)算法

1.負(fù)圈消除算法

根據(jù)負(fù)圈最優(yōu)性條件,不含負(fù)圈的可行流即為最小費(fèi)用流,因此,可以通過(guò)消除負(fù)圈的辦法,找到最小費(fèi)用流。算法的步驟如下:

2.連續(xù)最短路算法

記網(wǎng)絡(luò)上的一個(gè)非飽和可行流x={xij|0≤xij≤uij},假設(shè)存在一組勢(shì)π,使其滿足勢(shì)差最優(yōu)性條件。令d代表從某個(gè)點(diǎn)s在剩余容量圖上到其他點(diǎn)的最短路(邊(i,j)的長(zhǎng)度用cπij表示),則以下性質(zhì)成立:

(1)如果把點(diǎn)的勢(shì)更新為π'(i)=π(i)-d(i),?i∈V,則非飽和可行流仍然滿足勢(shì)差最優(yōu)性條件。

定理4-4-假設(shè)存在一組勢(shì)π,使非飽和可行流x滿足勢(shì)差最優(yōu)性條件。在x的基礎(chǔ)上通過(guò)沿著某條從s到k的最短路擴(kuò)充流量得到x',x'也滿足勢(shì)差最優(yōu)性條件。

證明:令d代表從某個(gè)點(diǎn)s在剩余容量圖上到其他點(diǎn)的最短路(邊(i,j)的長(zhǎng)度用cπij表示),則在新的勢(shì)值π'(i)=π(i)-d(i)下,x仍然滿足勢(shì)差最優(yōu)性條件。

4.4.4-拓展應(yīng)用:網(wǎng)絡(luò)上的最小費(fèi)用最大流問(wèn)題

某網(wǎng)絡(luò)上的邊的容量數(shù)值及單位流量費(fèi)用如圖4-44所示,求從起點(diǎn)N1到終點(diǎn)N8的最小費(fèi)用最大流。

圖4-44-網(wǎng)絡(luò)上的容量及單位流量費(fèi)用參數(shù)

步驟1:利用4.3節(jié)的算法求解網(wǎng)絡(luò)上的最大流,得到結(jié)果如圖4-45所示。圖4-45網(wǎng)絡(luò)最大流

步驟2:利用4.3.2節(jié)所述的方法將圖4-45轉(zhuǎn)換成剩余容量圖,如圖4-46(a)所示,其對(duì)應(yīng)的單位流量費(fèi)用圖如圖4-46(b)所示。在圖4-46(a)中,若邊上的單位流量費(fèi)用為負(fù),則邊使用虛線表示,邊上的流量使用小號(hào)的數(shù)字標(biāo)識(shí)。在圖4-46(b)中,單位流量費(fèi)用為負(fù)的邊也是使用虛線表示。

圖4-46網(wǎng)絡(luò)最大流的剩余容量圖

步驟3:在剩余容量圖的單位流量費(fèi)用圖(見(jiàn)圖4-47(a))上尋找到一個(gè)負(fù)圈(見(jiàn)圖4-47(b))(加粗邊構(gòu)成的圈),單位流量費(fèi)用為圈上邊的單位流量費(fèi)用之和

可擴(kuò)充流量為圈上邊的剩余容量的最小值

圖4-47在剩余容量圖的單位流量費(fèi)用圖上找到負(fù)圈

步驟4:并沿著負(fù)圈在剩余容量圖上擴(kuò)充流量結(jié)果如圖4-48所示,其中單位流量費(fèi)用為負(fù)的邊使用虛線標(biāo)識(shí)。圖4-48負(fù)圈在剩余容量費(fèi)用圖及剩余容量圖中的顯示

步驟5:在剩余容量圖的單位流量圖上找到負(fù)圈,如圖4-49中加粗的實(shí)邊和虛線邊所組成的圈。負(fù)圈上的單位流量費(fèi)用之和為

可擴(kuò)充流量為

然后在負(fù)圈上擴(kuò)充流量,直到?jīng)]有負(fù)圈為止,如圖4-50所示,其中單位流量費(fèi)用為負(fù)的邊使用虛線來(lái)表示,單位流量費(fèi)用為負(fù)的邊上的流量使用小號(hào)字體來(lái)表示。

圖4-