最大流與最小費(fèi)用流ppt課件.ppt

1、第3節(jié) 最大流與最小費(fèi)用流,最大流問(wèn)題及其求解方法 最小費(fèi)用流及其求解方法,1,一、最大流問(wèn)題及其求解方法,（一）最大流問(wèn)題,最大流問(wèn)題 設(shè)有向網(wǎng)絡(luò)N（V，A），在發(fā)點(diǎn)Vs 有一批貨，要通過(guò)網(wǎng)絡(luò)上的弧運(yùn)輸?shù)绞拯c(diǎn)Vt 去，受運(yùn)輸條件限制，每條弧aij在單位時(shí)間內(nèi)通過(guò)的車輛數(shù)不能超過(guò)cij 輛，分析：如何組織運(yùn)輸才能使從Vs到Vt 在單位時(shí)間內(nèi)通過(guò)的車輛達(dá)到最多？ 上面描述的這類問(wèn)題，稱為最大流問(wèn)題。,最大流問(wèn)題廣泛地應(yīng)用在交通運(yùn)輸、供水、油管供油、郵電通訊，也可以用在生產(chǎn)安排，管理優(yōu)化等實(shí)際問(wèn)題上。,2,例：如圖10.3.1中，有一批物資需要用汽車盡快從發(fā)點(diǎn)運(yùn)到收點(diǎn)，弧（i，j）上所標(biāo)的數(shù)字表示

2、該條道路在單位時(shí)間內(nèi)最多能通過(guò)的車輛數(shù)（單位：百輛），問(wèn)如何調(diào)運(yùn)，才能使單位時(shí)間里有最多的車輛從調(diào)到。,圖10.3.1,3,線性規(guī)劃方法,點(diǎn)出發(fā)的車輛數(shù)應(yīng)該與點(diǎn)到達(dá)的車輛數(shù)相同，除和以外的各中間點(diǎn)，進(jìn)的車輛數(shù)應(yīng)該與離去的車輛數(shù)應(yīng)該相同。,xij 是通過(guò)弧(i，j)的車輛數(shù)。,（10.3.1）,（10.3.4）,（10.3.5）,（10.3.6）,（10.3.2）,（10.3.3）,4,對(duì)所有弧（i，j），應(yīng)滿足約束 滿足（10.3.1）（10.3.7）的解稱為從到的一個(gè)可行流。 我們的目的：在所有可行流中求出一個(gè)方案，使得這個(gè)可行流得到的 f 最大。 若從收點(diǎn)到發(fā)點(diǎn)連接一條假想弧(7，1)，設(shè)

3、它的容量c71=，那么 對(duì)點(diǎn)： 對(duì)點(diǎn)： 最大流問(wèn)題的目標(biāo)為,線性規(guī)劃方法,（10.3.7）,（10.3.8）,（10.3.9）,（10.3.10）,5,所以，對(duì)于發(fā)點(diǎn)為Vs，收點(diǎn)為Vt的網(wǎng)絡(luò)N（V，U），當(dāng)增加一條約束為cts=的假想?。╰，s）后，最大流問(wèn)題就成為： 容量約束 平衡條件 目標(biāo)函數(shù),線性規(guī)劃方法,（10.3.11）,（10.3.12）,（10.3.13）,6,（二）求最大流的方法：弧標(biāo)號(hào)法,盡管最大流問(wèn)題可以用線性規(guī)劃模型描述，但是我們一般并不用求解線性規(guī)劃的方法求最大流，而是用一種更為簡(jiǎn)便明了的圖上作業(yè)法弧標(biāo)號(hào)法，求解上述最大流問(wèn)題。,7,(1)為了便于弧標(biāo)號(hào)法的計(jì)算，首先需

4、要將最大流問(wèn)題（譬如圖10.3.1）重新改畫成為圖10.3.2的形式。,圖10.3.2,8,在圖10.3.2中，每條弧 上標(biāo)有兩個(gè)數(shù)字，其中，靠近點(diǎn) i 的是 ，靠近點(diǎn) j 的是 。如 表示從到的最大通過(guò)量是5（百輛），從到的最大通過(guò)量是0； 表示從到和從到都可以通過(guò)2（百輛）；等等。,圖10.3.2,9,(2)求最大流的基本步驟：標(biāo)號(hào)法求最大流的過(guò)程，就是對(duì)圖10.3.2反復(fù)地進(jìn)行修改的過(guò)程，其計(jì)算步驟如下： 步驟1. 從發(fā)點(diǎn)s到收點(diǎn)t選定一條路，使這條路通過(guò)的所有弧Vij的前面約束量cij都大于0，如果找不到這樣的路，說(shuō)明已經(jīng)求得最大流，轉(zhuǎn)步驟4。 步驟2. 在選定的路上，找到最小的容許量

5、cij定為P。,10,步驟3. 對(duì)選定的路上每條弧的容量作以下修改，對(duì)于與路同向的弧，將cij修改為cij-P，對(duì)于與路反向的弧，將cij修改為cij+P。修改完畢后再轉(zhuǎn)入步驟1。 步驟4.用原圖中各條弧上起點(diǎn)與終點(diǎn)數(shù)值減去修改后的圖中對(duì)應(yīng)點(diǎn)的數(shù)值，得到正負(fù)號(hào)相反的兩個(gè)數(shù)，并將從正到負(fù)的方向用箭頭表示。這樣，就得到一個(gè)最大流量圖。,11,第1次修改： 從發(fā)點(diǎn)s到收點(diǎn)t找一條路，使得這條路上的所有弧前面的約束量 。從圖10.3.2中可以看出，顯然，就是滿足這樣的條件的一條路。,下面，我們用弧標(biāo)號(hào)法求解圖10.3.2中的最大流。,在路中, , , ， 所以取 。,12,在路中，修改每一條弧的容量,

6、13,通過(guò)第1次修改，得到圖10.3.3。,圖10.3.3,返回步驟，進(jìn)行第2次修改。,14,第2次修改： 選定，在這條路中，由于 ，所以，將 改為2 ， 改為0， 改為5， 、 、 改為3。修改后的圖變?yōu)閳D10.3.4。,圖10.3.4,返回步驟繼續(xù)做第3次修改。,15,第3次修改： 取，在這條路中，由于 所以將 改為0， 改為5， 改為0， 改為4， 改為1， 改為2， 改為3,c75改為5。修改后的圖變?yōu)閳D10.3.5。,圖10.3.5,返回步驟，繼續(xù)做第4次修改。,，,16,第4次修改： 選定，在這條路中，由于 P =c67 =1，所以將c14改為4,c41改為1,c46改為4,c64

7、改為1,c67改為0，c76 改為7。修改后的圖為變?yōu)閳D10.3.6 。,圖10.3.6,返回步驟，繼續(xù)做第5次修改。,17,第5次修改： 選定,在這條路中，由于 P = c65 = 1，所以將c14和c46均改為3，c65改為0，c57改為2，c41、c64、c56均改為2，c75改為6。修改后的圖變?yōu)閳D10.3.7。,圖10.3.7,18,需要注意的是，由圖10.3.7中可以看出，弧 本來(lái)在圖10.3.2中是無(wú)容量可通過(guò)的，但經(jīng)過(guò)幾次修改，由 變成 ，即此時(shí)從到還可通過(guò)1（百輛），而從到，可以通過(guò)6（百輛）的容量，這說(shuō)明，修改過(guò)程實(shí)際上是把計(jì)劃中從到的通過(guò)車輛數(shù)減少了。,19,第6次修改：

8、,取，在這條路中，由于P=c35=1，所以將 c14和 c46均改為2，c63改為5, c35改為0，c57改為1，c41、c64、c53均改為3，c36改為2，c75改為7。修改后的圖變?yōu)閳D10.3.8。,圖10.3.8,20,在圖10.3.8中，從發(fā)點(diǎn)到收點(diǎn)，再也不存在連通的起點(diǎn)容量都大于零的弧了，所以圖10.3.8為最大流圖。,轉(zhuǎn)入步驟，用原圖中各條弧上發(fā)點(diǎn)與收點(diǎn)數(shù)值減去修改后的圖上各點(diǎn)的數(shù)值，將得到正負(fù)號(hào)相反的兩個(gè)數(shù)，將這個(gè)數(shù)標(biāo)在弧上，并將從正到負(fù)的方向用箭頭表示,這樣就得到最大流量圖。例如原來(lái)弧 是 ，現(xiàn)在是 ，相減為5，那邊為正，我們就記作 。這樣，就得到圖10.3.9，即最大流量

9、圖。依這樣的調(diào)度方式，可以從發(fā)點(diǎn)s調(diào)運(yùn)14（百輛）汽車到收點(diǎn)t。,21,圖10.3.9 最大流量圖,22,(3)最大流算法的討論：,從上面的標(biāo)號(hào)計(jì)算過(guò)程可以看出，一個(gè)圖成為最大流圖的條件是從發(fā)點(diǎn)到收點(diǎn)的每一條路上總存在某個(gè)起點(diǎn)容量為零的弧，我們稱這樣的路為飽和路；如果從s到t有一條路，它上面每條路的起點(diǎn)容量都大于零，則稱為非飽和路。 由此可以得到一個(gè)結(jié)論：一個(gè)圖是最大流圖的充分必要條件是不存在從s到t的非飽和路。,23,將網(wǎng)絡(luò)中的點(diǎn)分成兩組，一組包括發(fā)點(diǎn) ，稱為發(fā)集 ，一組包括收點(diǎn)t，稱為收集 ，連接 到 的所有弧稱為截集，截集中各弧在 旁的容量和稱為截集的容量。,例如，在圖10.3.2中，,

10、圖10.3.2,24,我們?nèi)?， ，則截集為 (2,5),(3,5),(1,4),(3,6),(3,4)，它的容量為3+3+5+7+3=21； 若在圖10.3.6中，取 ， ，則截集為(2,5),(3,5),(6,5),(6,7)，其容量為0+1+1+0=2等等。 在將網(wǎng)絡(luò)分成發(fā)集與收集的所有分法中，容量最小的截集稱為最小截集?？梢宰C明：,25,設(shè)f是網(wǎng)絡(luò)N的一個(gè)可行流，那么，網(wǎng)絡(luò)N的最小截集的容量（）等于網(wǎng)絡(luò)最大流 與f 的差，即,（10.3.14）,式中：稱為可行流 f 的余量。,26,顯然，當(dāng)=0時(shí)，就得到了最大流。因此，進(jìn)一步可以得到： 在網(wǎng)絡(luò)N中，設(shè)f是從發(fā)點(diǎn)到收點(diǎn)的一個(gè)可行流，那么

11、，f是最大流的充分必要條件是網(wǎng)絡(luò)N的最小截集的容量為零。 從 到 的最大流的流量等于分離 與 的最小截集的容量。,這表明，從 到 ，最小截集的弧是網(wǎng)絡(luò)中的“卡脖子”線路，要獲得最大流量，必須在最小截集的各弧上達(dá)到滿載。,27,圖10.3.10,最大流fmax的大小是確定的，但最大流的路線可以不唯一。在上例中，如果從不同的路開(kāi)始來(lái)修改圖，也可能得到另外一個(gè)最大流圖（圖10.3.10）。,28,對(duì)于不同的最大流圖（譬如圖10.3.9與圖10.3.10），它們必有以下性質(zhì)： 對(duì)于網(wǎng)絡(luò)的最小截集上的弧，它們的流量是相同的。 對(duì)于由最小截集分開(kāi)的V1和V2內(nèi)，它們的流量可能不同，但都是相差一個(gè)或幾個(gè)不飽

12、和回路上的量，如圖10.3.9與圖10.3.10，相差的是回路上一個(gè)值為2的流量。,29,二、 最小費(fèi)用流及其求解方法,（一）最小費(fèi)用流問(wèn)題,如果在考慮網(wǎng)絡(luò)上流量的同時(shí)，還要使得所安排流量的費(fèi)用或者代價(jià)達(dá)到最小，就是所謂的最小費(fèi)用流問(wèn)題。,在上例中，如果單位車輛數(shù)通過(guò)某一條弧要付出一定的代價(jià)，其代價(jià)如圖10.3.11。,30,現(xiàn)在要從發(fā)點(diǎn)調(diào)動(dòng)若干車輛到收點(diǎn)去，約束條件為圖10.3.1，代價(jià)條件為圖10.3.11，要使所花費(fèi)的代價(jià)達(dá)到最小，用公式表示，就是要在（10.3.1）（10.3.7）式的約束條件下，找到一個(gè)可行流f 的流量,（10.3.15）,使其代價(jià)最小，即,（10.3.16）,式中： 指單位車輛數(shù)通過(guò)弧 的代價(jià)。,31,圖10.3.11 代價(jià)條件,圖10.3.1 約束條件,32,（二）求解最小費(fèi)用流問(wèn)題,求最小費(fèi)用流的步驟和求最大流的步驟幾乎完全一致，只是在步驟（1）中，選一條非飽和路時(shí)，應(yīng)選代價(jià)和最小的路，即最短路。 例如，在圖10.3.11中，從到的最短路是，代價(jià)為7，在這條最短非飽和路上取 后，變成容量為零，在下一次選擇最短路時(shí)應(yīng)將視為斷路來(lái)選取最短非飽和路。另外，選取路后，的弧成為容量大于零的弧，可分別標(biāo)上它們的代價(jià)值為-3，-3，-1，是，的相反數(shù)。,33,在求最小費(fèi)用流過(guò)程中，可以依上述方法不斷重復(fù)求最大流的步驟來(lái)進(jìn)行，當(dāng)流量達(dá)到 時(shí)就可以停止，這時(shí)