資源描述：
《最大網(wǎng)絡(luò)流-最小費(fèi)用流模型》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、最大網(wǎng)絡(luò)流1基本概念和術(shù)語(yǔ)（1）網(wǎng)絡(luò)G是一個(gè)簡(jiǎn)單有向圖，G=(V,E)，V={1，2，…，n}。在V中指定一個(gè)頂點(diǎn)s，稱為源,另一個(gè)頂點(diǎn)t，稱為匯。有向圖G的每一條邊(v,w)∈E，對(duì)應(yīng)有一個(gè)值cap(v,w)≥0，稱為邊的容量。這樣的有向圖G稱作一個(gè)網(wǎng)絡(luò)。（2）網(wǎng)絡(luò)流網(wǎng)絡(luò)上的流是定義在網(wǎng)絡(luò)的邊集合E上的一個(gè)非負(fù)函數(shù)flow={flow(v,w)}，并稱flow(v,w)為邊(v,w)上的流量。1（3）可行流滿足下述條件的流flow稱為可行流：(3.1)容量約束：對(duì)每一條邊(v,w)∈E，0≤flow(v,w)≤cap(v,w)。(3.2)平衡約束：對(duì)于中間頂點(diǎn)：流出量=流入量。即對(duì)每個(gè)v∈V
2、(v≠s,t)有：頂點(diǎn)v的流出量－頂點(diǎn)v的流入量=0，即對(duì)于源s：s的流出量－s的流入量=源的凈輸出量f，即對(duì)于匯t：t的流入量－t的流出量的=匯的凈輸入量f，即式中f稱為這個(gè)可行流的流量，即源的凈輸出量(或匯的凈輸入量)?？尚辛骺偸谴嬖诘?。例如，讓所有邊的流量flow(v,w)=0，就得到一個(gè)其流量f=0的可行流(稱為0流)。2（4）邊流對(duì)于網(wǎng)絡(luò)G的一個(gè)給定的可行流flow，將網(wǎng)絡(luò)中滿足flow(v,w)=cap(v,w)的邊稱為飽和邊；flow(v,w)0的邊稱為非零流邊。當(dāng)邊(v,w)既不是一條
3、零流邊也不是一條飽和邊時(shí)，稱為弱流邊。（5）最大流最大流問(wèn)題即求網(wǎng)絡(luò)G的一個(gè)可行流flow，使其流量f達(dá)到最大。即flow滿足：0≤flow(v,w)≤cap(v,w)，(v,w)∈E；且（6）流的費(fèi)用在實(shí)際應(yīng)用中，與網(wǎng)絡(luò)流有關(guān)的問(wèn)題，不僅涉及流量，而且還有費(fèi)用的因素。此時(shí)網(wǎng)絡(luò)的每一條邊(v,w)除了給定容量cap(v,w)外，還定義了一個(gè)單位流量費(fèi)用cost(v,w)。對(duì)于網(wǎng)絡(luò)中一個(gè)給定的流flow，其費(fèi)用定義為：3（7）殘流網(wǎng)絡(luò)對(duì)于給定的一個(gè)流網(wǎng)絡(luò)G及其上的一個(gè)流flow，網(wǎng)絡(luò)G關(guān)于流flow的殘流網(wǎng)絡(luò)G*與G有相同的頂點(diǎn)集V，而網(wǎng)絡(luò)G中的每一條邊對(duì)應(yīng)于G*中的1條邊或2條邊。設(shè)(v,w)
4、是G的一條邊。當(dāng)flow(v,w)>0時(shí)，（w,v）是G*中的一條邊，該邊的容量為cap*(w,v)=flow(v,w)；當(dāng)flow(v,w)5、和(w,v)與之對(duì)應(yīng)，這2條邊的容量分別為cap(v,w)-flow(v,w)和flow(v,w)。殘流網(wǎng)絡(luò)是設(shè)計(jì)與網(wǎng)絡(luò)流有關(guān)算法的重要工具。4增廣路算法1算法基本思想設(shè)P是網(wǎng)絡(luò)G中聯(lián)結(jié)源s和匯t的一條路。定義路的方向是從s到t。將路P上的邊分成2類：一類邊的方向與路的方向一致，稱為向前邊。向前邊的全體記為P+。另一類邊的方向與路的方向相反，稱為向后邊。向后邊的全體記為P-。設(shè)flow是一個(gè)可行流，P是從s到t的一條路，若P滿足下列條件：（1）在P的所有向前邊(v,w)上，flow(v,w)6、)>0，即P-中的每一條邊都是非零流邊。則稱P為關(guān)于可行流flow的一條可增廣路?？稍鰪V路是殘流網(wǎng)絡(luò)中一條容量大于0的路。將具有上述特征的路P稱為可增廣路是因?yàn)榭梢酝ㄟ^(guò)修正路P上所有邊流量flow(v,w)將當(dāng)前可行流改進(jìn)成一個(gè)流值更大的可行流。5增流的具體做法是：（1）不屬于可增廣路P的邊(v,w)上的流量保持不變；（2）可增廣路P上的所有邊(v,w)上的流量按下述規(guī)則變化：在向前邊(v,w)上，flow(v,w)+d；在向后邊(v,w)上，flow(v,w)-d。按下面的公式修改當(dāng)前的流。其中d稱為可增廣量，可按下述原則確定：d取得盡量大，又要使變化后的流仍為可行流。按照這個(gè)原則，d既不能
7、超過(guò)每條向前邊(v,w)的cap(v,w)-flow(v,w)，也不能超過(guò)每條向后邊(v,w)的flow(v,w)。因此d應(yīng)該等于向前邊上的cap(v,w)-flow(v,w)與向后邊上的flow(v,w)的最小值。也就是殘流網(wǎng)絡(luò)中P的最大容量。增廣路定理：設(shè)flow是網(wǎng)絡(luò)G的一個(gè)可行流，如果不存在從s到t關(guān)于flow的可增廣路P，則flow是G的一個(gè)最大流。62算法描述最大流的增廣路算法如下。該
