線性規(guī)劃與網(wǎng)絡(luò)流

線性規(guī)劃與網(wǎng)絡(luò)流1第一頁(yè)，共四十七頁(yè)，編輯于2023年，星期三8.1線性規(guī)劃問(wèn)題和單純形算法線性規(guī)劃問(wèn)題及其表示線性規(guī)劃問(wèn)題可表示為如下形式：

s.t.2第二頁(yè)，共四十七頁(yè)，編輯于2023年，星期三變量滿足約束條件(8.2)-(8.5)式的一組值稱為線性規(guī)劃問(wèn)題的一個(gè)可行解。所有可行解構(gòu)成的集合稱為線性規(guī)劃問(wèn)題的可行區(qū)域。使目標(biāo)函數(shù)取得極值的可行解稱為最優(yōu)解。在最優(yōu)解處目標(biāo)函數(shù)的值稱為最優(yōu)值。有些情況下可能不存在最優(yōu)解。通常有兩種情況：(1)根本沒(méi)有可行解，即給定的約束條件之間是相互排斥的，可行區(qū)域?yàn)榭占?2)目標(biāo)函數(shù)沒(méi)有極值，也就是說(shuō)在n維空間中的某個(gè)方向上，目標(biāo)函數(shù)值可以無(wú)限增大，而仍滿足約束條件，此時(shí)目標(biāo)函數(shù)值無(wú)界。3第三頁(yè)，共四十七頁(yè)，編輯于2023年，星期三這個(gè)問(wèn)題的解為(x1,x2,x3,x4)=(0,3.5,4.5,1)；最優(yōu)值為16。4第四頁(yè)，共四十七頁(yè)，編輯于2023年，星期三線性規(guī)劃基本定理

約束條件(8.2)-(8.5)中n個(gè)約束以等號(hào)滿足的可行解稱為線性規(guī)劃問(wèn)題的基本可行解。若n>m，則基本可行解中至少有n-m個(gè)分量為0，也就是說(shuō)，基本可行解中最多有m個(gè)分量非零。線性規(guī)劃基本定理：如果線性規(guī)劃問(wèn)題有最優(yōu)解，則必有一基本可行最優(yōu)解。上述定理的重要意義在于，它把一個(gè)最優(yōu)化問(wèn)題轉(zhuǎn)化為一個(gè)組合問(wèn)題，即在(8.2)-(8.5)式的m+n個(gè)約束條件中，確定最優(yōu)解應(yīng)滿足其中哪n個(gè)約束條件的問(wèn)題。由此可知，只要對(duì)各種不同的組合進(jìn)行測(cè)試，并比較每種情況下的目標(biāo)函數(shù)值，直到找到最優(yōu)解。Dantzig于1948年提出了線性規(guī)劃問(wèn)題的單純形算法。單純形算法的特點(diǎn)是：（1）只對(duì)約束條件的若干組合進(jìn)行測(cè)試，測(cè)試的每一步都使目標(biāo)函數(shù)的值增加；（2）一般經(jīng)過(guò)不大于m或n次迭代就可求得最優(yōu)解。5第五頁(yè)，共四十七頁(yè)，編輯于2023年，星期三約束標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題的單純形算法

當(dāng)線性規(guī)劃問(wèn)題中沒(méi)有不等式約束(8.2)和(8.4)式，而只有等式約束(8.3)和變量非負(fù)約束(8.5)時(shí)，稱該線性規(guī)劃問(wèn)題具有標(biāo)準(zhǔn)形式。為便于討論，不妨先考察一類更特殊的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題。這一類線性規(guī)劃問(wèn)題中，每一個(gè)等式約束中，至少有一個(gè)變量的系數(shù)為正，且這個(gè)變量只在該約束中出現(xiàn)。在每一約束方程中選擇一個(gè)這樣的變量，并以它作為變量求解該約束方程。這樣選出來(lái)的變量稱為左端變量或基本變量，其總數(shù)為m個(gè)。剩下的n-m個(gè)變量稱為右端變量或非基本變量。這一類特殊的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題稱為約束標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題。雖然約束標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題非常特殊，但是對(duì)于理解線性規(guī)劃問(wèn)題的單純形算法是非常重要的。稍后將看到，任意一個(gè)線性規(guī)劃問(wèn)題可以轉(zhuǎn)換為約束標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題。6第六頁(yè)，共四十七頁(yè)，編輯于2023年，星期三x2x3x5z0-13-2x173-12x412-240x610-4387第七頁(yè)，共四十七頁(yè)，編輯于2023年，星期三任何約束標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題，只要將所有非基本變量都置為0，從約束方程式中解出滿足約束的基本變量的值，可求得一個(gè)基本可行解。單純形算法的基本思想就是從一個(gè)基本可行解出發(fā)，進(jìn)行一系列的基本可行解的變換。每次變換將一個(gè)非基本變量與一個(gè)基本變量互調(diào)位置，且保持當(dāng)前的線性規(guī)劃問(wèn)題是一個(gè)與原問(wèn)題完全等價(jià)的標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題?；究尚薪鈞=(7,0,0,12,0,10)。單純形算法的第1步：選出使目標(biāo)函數(shù)增加的非基本變量作為入基變量。查看單純形表的第1行（也稱之為z行）中標(biāo)有非基本變量的各列中的值。選出使目標(biāo)函數(shù)增加的非基本變量作為入基變量。z行中的正系數(shù)非基本變量都滿足要求。在上面單純形表的z行中只有1列為正，即非基本變量相應(yīng)的列，其值為3。選取非基本變量x3作為入基變量。單純形算法的第2步：選取離基變量。在單純形表中考察由第1步選出的入基變量所相應(yīng)的列。在一個(gè)基本變量變?yōu)樨?fù)值之前，入基變量可以增到多大。8第八頁(yè)，共四十七頁(yè)，編輯于2023年，星期三如果入基變量所在的列與基本變量所在行交叉處的表元素為負(fù)數(shù)，那么該元素將不受任何限制，相應(yīng)的基本變量只會(huì)越變?cè)酱蟆Ｈ绻牖兞克诹械乃性囟际秦?fù)值，則目標(biāo)函數(shù)無(wú)界，已經(jīng)得到了問(wèn)題的無(wú)界解。如果選出的列中有一個(gè)或多個(gè)元素為正數(shù)，要弄清是哪個(gè)數(shù)限制了入基變量值的增加。受限的增加量可以用入基變量所在列的元素（稱為主元素）來(lái)除主元素所在行的“常數(shù)列”（最左邊的列）中元素而得到。所得到數(shù)值越小說(shuō)明受到限制越多。應(yīng)該選取受到限制最多的基本變量作為離基變量，才能保證將入基變量與離基變量互調(diào)位置后，仍滿足約束條件。上例中，惟一的一個(gè)值為正的z行元素是3，它所在列中有2個(gè)正元素，即4和3。min{12/4,10/3}=4，應(yīng)該選取x4為離基變量；入基變量x3取值為3。單純形算法的第3步：轉(zhuǎn)軸變換。轉(zhuǎn)軸變換的目的是將入基變量與離基變量互調(diào)位置。給入基變量一個(gè)增值，使之成為基本變量；修改離基變量，讓入基變量所在列中，離基變量所在行的元素值減為零，而使之成為非基本變量。9第九頁(yè)，共四十七頁(yè)，編輯于2023年，星期三解離基變量所相應(yīng)的方程，將入基變量x3用離基變量x4表示為再將其代入其他基本變量和所在的行中消去x3

，代入目標(biāo)函數(shù)得到形成新單純形表x2x4x5z91/2-3/4

-2x1105/21/22x33-1/21/40x61-5/2-3/4810第十頁(yè)，共四十七頁(yè)，編輯于2023年，星期三單純形算法的第4步：轉(zhuǎn)回并重復(fù)第1步，進(jìn)一步改進(jìn)目標(biāo)函數(shù)值。不斷重復(fù)上述過(guò)程，直到z行的所有非基本變量系數(shù)都變成負(fù)值為止。這表明目標(biāo)函數(shù)不可能再增加了。在上面的單純形表中，惟一的值為正的z行元素是非基本變量x2相應(yīng)的列，其值為1/2。因此，選取非基本變量x2作為入基變量。它所在列中有惟一的正元素5/2，即基本變量x1相應(yīng)行的元素。因此，選取x1為離基變量。再經(jīng)步驟3的轉(zhuǎn)軸變換得到新單純形表。新單純形表z行的所有非基本變量系數(shù)都變成負(fù)值，求解過(guò)程結(jié)束。整個(gè)問(wèn)題的解可以從最后一張單純形表的常數(shù)列中讀出。目標(biāo)函數(shù)的最大值為11；最優(yōu)解為：x*=(0,4,5,0,0,11)。x1x4x5z11-1/5-4/5

-12/5x245/21/104/5x351/53/102/5x6111-1/21011第十一頁(yè)，共四十七頁(yè)，編輯于2023年，星期三12第十二頁(yè)，共四十七頁(yè)，編輯于2023年，星期三13第十三頁(yè)，共四十七頁(yè)，編輯于2023年，星期三14第十四頁(yè)，共四十七頁(yè)，編輯于2023年，星期三15第十五頁(yè)，共四十七頁(yè)，編輯于2023年，星期三為了進(jìn)一步構(gòu)造標(biāo)準(zhǔn)型約束，還需要引入m個(gè)人工變量，記為zi。至此，原問(wèn)題已經(jīng)變換為等價(jià)的約束標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題。對(duì)極小化線性規(guī)劃問(wèn)題，只要將目標(biāo)函數(shù)乘以-1即可化為等價(jià)的極大化線性規(guī)劃問(wèn)題。16第十六頁(yè)，共四十七頁(yè)，編輯于2023年，星期三一般線性規(guī)劃問(wèn)題的2階段單純形算法

引入人工變量后的線性規(guī)劃問(wèn)題與原問(wèn)題并不等價(jià)，除非所有zi都是0。為了解決這個(gè)問(wèn)題，在求解時(shí)必須分2個(gè)階段進(jìn)行。第一階段用一個(gè)輔助目標(biāo)函數(shù)替代原來(lái)的目標(biāo)函數(shù)。這個(gè)線性規(guī)劃問(wèn)題稱為原線性規(guī)劃問(wèn)題所相應(yīng)的輔助線性規(guī)劃問(wèn)題。對(duì)輔助線性規(guī)劃問(wèn)題用單純形算法求解。如果原線性規(guī)劃問(wèn)題有可行解，則輔助線性規(guī)劃問(wèn)題就有最優(yōu)解，且其最優(yōu)值為0，即所有zi都為0。在輔助線性規(guī)劃問(wèn)題最后的單純形表中，所有zi均為非基本變量。劃掉所有zi相應(yīng)的列，剩下的就是只含xi和yi的約束標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題了。單純形算法第一階段的任務(wù)就是構(gòu)造一個(gè)初始基本可行解。單純形算法第二階段的目標(biāo)是求解由第一階段導(dǎo)出的問(wèn)題。此時(shí)要用原來(lái)的目標(biāo)函數(shù)進(jìn)行求解。如果在輔助線性規(guī)劃問(wèn)題最后的單純形表中，zi不全為0，則原線性規(guī)劃問(wèn)題沒(méi)有可行解，從而原線性規(guī)劃問(wèn)題無(wú)解。17第十七頁(yè)，共四十七頁(yè)，編輯于2023年，星期三退化情形的處理

用單純形算法解一般的線性規(guī)劃問(wèn)題時(shí)，可能會(huì)遇到退化的情形，即在迭代計(jì)算的某一步中，常數(shù)列中的某個(gè)元素的值變成0，使得相應(yīng)的基本變量取值為0。如果選取退化的基本變量為離基變量，則作轉(zhuǎn)軸變換前后的目標(biāo)函數(shù)值不變。在這種情況下，算法不能保證目標(biāo)函數(shù)值嚴(yán)格遞增，因此，可能出現(xiàn)無(wú)限循環(huán)?？疾煜旅娴挠葿eale在1955年提出的退化問(wèn)題的例子。按照2階段單純形算法求解該問(wèn)題將出現(xiàn)無(wú)限循環(huán)。18第十八頁(yè)，共四十七頁(yè)，編輯于2023年，星期三Bland提出避免循環(huán)的一個(gè)簡(jiǎn)單易行的方法。Bland提出在單純形算法迭代中，按照下面的2個(gè)簡(jiǎn)單規(guī)則就可以避免循環(huán)。規(guī)則1：設(shè)，取xe為入基變量。規(guī)則2：設(shè)取xk為離基變量。算法leave(col)已經(jīng)按照規(guī)則2選取離基變量。選取入基變量的算法enter(objrow)中只要加一個(gè)break語(yǔ)句即可。19第十九頁(yè)，共四十七頁(yè)，編輯于2023年，星期三20第二十頁(yè)，共四十七頁(yè)，編輯于2023年，星期三21第二十一頁(yè)，共四十七頁(yè)，編輯于2023年，星期三8.2最大網(wǎng)絡(luò)流問(wèn)題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)上的流量。22第二十二頁(yè)，共四十七頁(yè)，編輯于2023年，星期三（3）可行流滿足下述條件的流flow稱為可行流：(3.1)容量約束：對(duì)每一條邊(v,w)∈E，0≤flow(v,w)≤cap(v,w)。(3.2)平衡約束：對(duì)于中間頂點(diǎn)：流出量=流入量。即對(duì)每個(gè)v∈V(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流)。23第二十三頁(yè)，共四十七頁(yè)，編輯于2023年，星期三（4）邊流對(duì)于網(wǎng)絡(luò)G的一個(gè)給定的可行流flow，將網(wǎng)絡(luò)中滿足flow(v,w)=cap(v,w)的邊稱為飽和邊；flow(v,w)<cap(v,w)的邊稱為非飽和邊；flow(v,w)=0的邊稱為零流邊；flow(v,w)>0的邊稱為非零流邊。當(dāng)邊(v,w)既不是一條零流邊也不是一條飽和邊時(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)用定義為：24第二十四頁(yè)，共四十七頁(yè)，編輯于2023年，星期三（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)是G的一條邊。當(dāng)flow(v,w)>0時(shí)，（w,v）是G*中的一條邊，該邊的容量為cap*(w,v)=flow(v,w)；當(dāng)flow(v,w)<cap(v,w)時(shí)，(v,w)是G*中的一條邊，該邊的容量為cap*(v,w)=cap(v,w)-flow(v,w)。按照殘流網(wǎng)絡(luò)的定義，當(dāng)原網(wǎng)絡(luò)G中的邊(v,w)是一條零流邊時(shí)，殘流網(wǎng)絡(luò)G*中有唯一的一條邊(v,w)與之對(duì)應(yīng)，且該邊的容量為cap(v,w)。當(dāng)原網(wǎng)絡(luò)G中的邊(v,w)是一條飽和邊時(shí)，殘流網(wǎng)絡(luò)G*中有唯一的一條邊(w,v)與之對(duì)應(yīng)，且該邊的容量為cap(v,w)。當(dāng)原網(wǎng)絡(luò)G中的邊(v,w)是一條弱流邊時(shí)，殘流網(wǎng)絡(luò)G*中有2條邊(v,w)和(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)算法的重要工具。25第二十五頁(yè)，共四十七頁(yè)，編輯于2023年，星期三增廣路算法

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)<cap(v,w)，即P+中的每一條邊都是非飽和邊；（2）在P的所有向后邊(v,w)上，flow(v,w)>0，即P-中的每一條邊都是非零流邊。則稱P為關(guān)于可行流flow的一條可增廣路?？稍鰪V路是殘流網(wǎng)絡(luò)中一條容量大于0的路。將具有上述特征的路P稱為可增廣路是因?yàn)榭梢酝ㄟ^(guò)修正路P上所有邊流量flow(v,w)將當(dāng)前可行流改進(jìn)成一個(gè)流值更大的可行流。26第二十六頁(yè)，共四十七頁(yè)，編輯于2023年，星期三增流的具體做法是：（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既不能超過(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è)最大流。27第二十七頁(yè)，共四十七頁(yè)，編輯于2023年，星期三2算法描述最大流的增廣路算法如下。該算法也常稱作FordFulkerson算法。template<classGraph,classEdge>classMAXFLOW{constGraph&G;ints,t,maxf;vector<int>wt;vector<Edge*>st;intST(intv)const{returnst[v]->other(v);}voidaugment(ints,intt){intd=st[t]->capRto(t);for(intv=ST(t);v!=s;v=ST(v))if(st[v]->capRto(v)<d)d=st[v]->capRto(v);st[t]->addflowRto(t,d);maxf+=d;for(v=ST(t);v!=s;v=ST(v))st[v]->addflowRto(v,d);}boolpfs();public:MAXFLOW(constGraph&G,ints,intt,int&maxflow):G(G),s(s),t(t),st(G.V()),wt(G.V()),maxf(0){while(pfs())augment(s,t);maxflow+=maxf;}};28第二十八頁(yè)，共四十七頁(yè)，編輯于2023年，星期三3算法的計(jì)算復(fù)雜性增廣路算法的效率由下面2個(gè)因素所確定。（1）整個(gè)算法找增廣路的次數(shù)；（2）每次找增廣路所需的時(shí)間。給定的網(wǎng)絡(luò)中有n個(gè)頂點(diǎn)和m條邊，且每條邊的容量不超過(guò)M?？梢宰C明，在一般情況下，增廣路算法中找增廣路的次數(shù)不超過(guò)nM次。最短增廣路算法在最壞情況下找增廣路的次數(shù)不超過(guò)nm/2次。找1次增廣路最多需要O(m)計(jì)算時(shí)間。因此，在最壞情況下最短增廣路算法所需的計(jì)算時(shí)間為O(nm2)。當(dāng)給定的網(wǎng)絡(luò)是稀疏網(wǎng)絡(luò)，即m=O(n)時(shí)，最短增廣路算法所需的計(jì)算時(shí)間為O(n3)。最大容量增廣路算法在最壞情況下找增廣路的次數(shù)不超過(guò)2mlogM次。由于使用堆來(lái)存儲(chǔ)優(yōu)先隊(duì)列，找1次增廣路最多需要O(nlogn)計(jì)算時(shí)間。因此，在最壞情況下最大容量增廣路算法所需的計(jì)算時(shí)間為當(dāng)給定的網(wǎng)絡(luò)是稀疏網(wǎng)絡(luò)時(shí)，最大容量增廣路算法所需的計(jì)算時(shí)間為29第二十九頁(yè)，共四十七頁(yè)，編輯于2023年，星期三預(yù)流推進(jìn)算法

1算法基本思想增廣路算法的特點(diǎn)是找到增廣路后，立即沿增廣路對(duì)網(wǎng)絡(luò)流進(jìn)行增廣。每一次增廣可能需要對(duì)最多n-1條邊進(jìn)行操作。最壞情況下，每一次增廣需要O(n)計(jì)算時(shí)間。有些情況下，這個(gè)代價(jià)是很高的。下面是一個(gè)極端的例子。30第三十頁(yè)，共四十七頁(yè)，編輯于2023年，星期三無(wú)論用哪種增廣路算法，都會(huì)找到10條增廣路，每條路長(zhǎng)為10，容量為1。共需要10次增廣，每次增廣需要對(duì)10條邊進(jìn)行操作，每條邊增廣1個(gè)單位流量。10條增廣路中的前9個(gè)頂點(diǎn)（前8條邊）是完全一樣的。如果直接將前8條邊的流量增廣10個(gè)單位，而只對(duì)后面長(zhǎng)為2的不同的有向路單獨(dú)操作，就可以節(jié)省許多計(jì)算時(shí)間。這就是預(yù)流推進(jìn)（preflowpush)算法的基本思想。預(yù)流推進(jìn)算法注重對(duì)每一條邊的增流，而不必每次一定對(duì)一條增廣路增流。通常將沿一條邊增流的運(yùn)算稱為一次推進(jìn)（push）。在算法的推進(jìn)過(guò)程中，網(wǎng)絡(luò)流滿足容量約束，但一般不滿足流量平衡約束。從每個(gè)頂點(diǎn)（除s和t外）流出的流量之和總是小于等于流入該頂點(diǎn)的流量之和。這種流稱為預(yù)流（preflow）。這也是這類算法被稱為預(yù)流推進(jìn)算法的原因。下面先給出預(yù)流的嚴(yán)格定義。給定網(wǎng)絡(luò)G=(V,E)一個(gè)預(yù)流是定義在G的邊集E上的一個(gè)正邊流函數(shù)。該函數(shù)滿足容量約束，即對(duì)G的每一條邊(v,w)∈E，滿足0≤flow(v,w)≤cap(v,w)。31第三十一頁(yè)，共四十七頁(yè)，編輯于2023年，星期三G的每一中間頂點(diǎn)滿足流出量小于或等于流入量。即對(duì)每個(gè)v∈V(v≠s,t)有滿足條件的中間頂點(diǎn)v稱為活頂點(diǎn)。量稱為頂點(diǎn)v的存流。按此定義，源s和匯t不可能成為活頂點(diǎn)。對(duì)網(wǎng)絡(luò)G上的一個(gè)預(yù)流，如果存在活頂點(diǎn)，則說(shuō)明該預(yù)流不是可行流。預(yù)流推進(jìn)算法就是要選擇活頂點(diǎn)，并通過(guò)把一定的流量推進(jìn)到它的鄰點(diǎn)，盡可能地將當(dāng)前活頂點(diǎn)處正的存流減少為0，直至網(wǎng)絡(luò)中不再有活頂點(diǎn)，從而使預(yù)流成為可行流。如果當(dāng)前活頂點(diǎn)有多個(gè)鄰點(diǎn)，那么首先推進(jìn)到哪個(gè)鄰點(diǎn)呢?由于算法最后的目的是盡可能將流推進(jìn)到匯點(diǎn)t，因此算法應(yīng)尋求把流量推進(jìn)到它的鄰點(diǎn)中距頂點(diǎn)t最近的頂點(diǎn)。預(yù)流推進(jìn)算法中用到一個(gè)高度函數(shù)h來(lái)確定推流邊。對(duì)于給定網(wǎng)絡(luò)G=(V,E)的一個(gè)流，其高度函數(shù)h是定義在G的頂點(diǎn)集V上的一個(gè)非負(fù)函數(shù)。該函數(shù)滿足：（1）對(duì)于G的殘流網(wǎng)絡(luò)中的每一條邊(u,v)有，h(u)h(v)+1；（2）h(t)=0。G的殘流網(wǎng)絡(luò)中滿足h(u)=h(v)+1的邊(u,v)稱為G的可推流邊。32第三十二頁(yè)，共四十七頁(yè)，編輯于2023年，星期三一般的預(yù)流推進(jìn)算法一般的預(yù)流推進(jìn)算法的每次迭代是一次推進(jìn)運(yùn)算或者一次高度重新標(biāo)號(hào)運(yùn)算。如果推進(jìn)的流量等于推流邊上的殘留容量，則稱為飽和推進(jìn)，否則稱為非飽和推進(jìn)。算法終止時(shí)，網(wǎng)絡(luò)中不含有活頂點(diǎn)。此時(shí)只有頂點(diǎn)s和t的存流非零。此時(shí)的預(yù)流實(shí)際上已經(jīng)是一個(gè)可行流。算法預(yù)處理階段已經(jīng)令h(s)=n，而高度函數(shù)在計(jì)算過(guò)程中不會(huì)減少，因此算法在計(jì)算過(guò)程中可以保證網(wǎng)絡(luò)中不存在增廣路。根據(jù)增廣路定理，算法終止時(shí)的可行流是一個(gè)最大流。步驟0：構(gòu)造初始預(yù)流flow：對(duì)源頂點(diǎn)s的每條出邊(s,v)令flow(s,v)=cap(s,v)；對(duì)其余邊(u,v)令flow(u,v)=0。構(gòu)造一有效的高度函數(shù)h。步驟1：如果殘量網(wǎng)絡(luò)中不存在活頂點(diǎn)，則計(jì)算結(jié)束，已經(jīng)得到最大流；否則轉(zhuǎn)步驟2。步驟2：在網(wǎng)絡(luò)中選取活頂點(diǎn)v。如果存在頂點(diǎn)v的出邊為可推流邊，則選取一條這樣的可推流邊，并沿此邊推流。否則令h(v)=min{h(w)+1|(v,w)是當(dāng)前殘流網(wǎng)絡(luò)中的邊}，并轉(zhuǎn)步驟1。33第三十三頁(yè)，共四十七頁(yè)，編輯于2023年，星期三一般的預(yù)流推進(jìn)算法并未給出如何選擇活頂點(diǎn)和可推流邊。不同的選擇策略導(dǎo)致不同的預(yù)流推進(jìn)算法。在基于頂點(diǎn)的預(yù)流推進(jìn)算法中，選定一個(gè)活頂點(diǎn)后，算法沿該活頂點(diǎn)的所有推流邊進(jìn)行推流運(yùn)算，直至無(wú)可推流邊或該頂點(diǎn)的存變成0時(shí)為止。3算法的計(jì)算復(fù)雜性基于頂點(diǎn)的預(yù)流推進(jìn)算法用一個(gè)廣義隊(duì)列g(shù)Q存儲(chǔ)當(dāng)前活頂點(diǎn)集合。廣義隊(duì)列可以是通常的FIFO隊(duì)列，LIFO棧，隨機(jī)化隊(duì)列，隨機(jī)化棧，或按各種優(yōu)先級(jí)定義的優(yōu)先隊(duì)列。算法的效率與廣義優(yōu)先隊(duì)列的選擇密切相關(guān)。如果選用通常的FIFO隊(duì)列，則在最壞情況下，預(yù)流推進(jìn)算法求最大流所需的計(jì)算時(shí)間為O(mn2)，其中m和n分別為圖G的邊數(shù)和頂點(diǎn)數(shù)。如果以頂點(diǎn)高度值為優(yōu)先級(jí)，選用優(yōu)先隊(duì)列實(shí)現(xiàn)預(yù)流推進(jìn)算法，則在最壞情況下，求最大流所需的計(jì)算時(shí)間為這個(gè)算法也稱為最高頂點(diǎn)標(biāo)號(hào)預(yù)流推進(jìn)算法。近來(lái)已提出許多其它預(yù)流推進(jìn)算法的實(shí)現(xiàn)策略，在最壞情況下算法所需的計(jì)算時(shí)間已接近O(mn)。34第三十四頁(yè)，共四十七頁(yè)，編輯于2023年，星期三8.3最小費(fèi)用流問(wèn)題1網(wǎng)絡(luò)流的費(fèi)用在實(shí)際應(yīng)用中，與網(wǎng)絡(luò)流有關(guān)的問(wèn)題，不僅涉及流量，而且還有費(fèi)用的因素。網(wǎng)絡(luò)的每一條邊(v,w)除了給定容量cap(v,w)外，還定義了一個(gè)單位流量費(fèi)用cost(v,w)。對(duì)于網(wǎng)絡(luò)中一個(gè)給定的流flow，其費(fèi)用定義為：2最小費(fèi)用流問(wèn)題給定網(wǎng)絡(luò)G，要求G的一個(gè)最大用流flow，使流的總費(fèi)用最小。3最小費(fèi)用可行流問(wèn)題給定多源多匯網(wǎng)絡(luò)G，要求G的一個(gè)可行流flow，使可行流的總費(fèi)用最小。可行流問(wèn)題等價(jià)于最大流問(wèn)題。最小費(fèi)用可行流問(wèn)題也等價(jià)于最小費(fèi)用流問(wèn)題。35第三十五頁(yè)，共四十七頁(yè)，編輯于2023年，星期三消圈算法

1算法基本思想最小費(fèi)用流問(wèn)題有關(guān)的算法中，仍然沿用殘流網(wǎng)絡(luò)的概念。此時(shí)，殘流網(wǎng)絡(luò)中邊的費(fèi)用定義為：intcostRto(intv){returnfrom(v)?-pcost:pcost;}當(dāng)殘流網(wǎng)絡(luò)中的邊是向前邊時(shí)，其費(fèi)用不變。當(dāng)殘流網(wǎng)絡(luò)中的邊是向后邊時(shí)，其費(fèi)用為原費(fèi)用的負(fù)值。由于殘流網(wǎng)絡(luò)中存在負(fù)費(fèi)用邊，因此殘流網(wǎng)絡(luò)中就不可避免地會(huì)產(chǎn)生負(fù)費(fèi)用圈。在與最小費(fèi)用流問(wèn)題有關(guān)的算法中，負(fù)費(fèi)用圈是一個(gè)重要概念。最小費(fèi)用流問(wèn)題的最優(yōu)性條件網(wǎng)絡(luò)G的最大流flow是G的一個(gè)最小費(fèi)用流的充分且必要條件是flow所相應(yīng)的殘流網(wǎng)絡(luò)中沒(méi)有負(fù)費(fèi)用圈。36第三十六頁(yè)，共四十七頁(yè)，編輯于2023年，星期三最小費(fèi)用流的消圈算法步驟0：用最大流算法構(gòu)造最大流flow。步驟1：如果殘量網(wǎng)絡(luò)中不存在負(fù)費(fèi)用圈，則計(jì)算結(jié)束，已經(jīng)找到最小費(fèi)用流；否則轉(zhuǎn)步驟2。步驟2：沿找到的負(fù)費(fèi)用圈增流，并轉(zhuǎn)步驟1。37第三十七頁(yè)，共四十七頁(yè)，編輯于2023年，星期三3算法的計(jì)算復(fù)雜性給定網(wǎng)絡(luò)中有n個(gè)頂點(diǎn)和m條邊，且每條邊的容量不超過(guò)M，每條邊的費(fèi)用不超過(guò)C。最大流的費(fèi)用不超過(guò)mCM，而每次消去負(fù)費(fèi)用圈至少使得費(fèi)用下降1個(gè)單位，因此最多執(zhí)行mCM次找負(fù)費(fèi)用圈和增流運(yùn)算。用Bellman-Ford算法找1次負(fù)費(fèi)用圈需要O(mn)計(jì)算時(shí)間。最小費(fèi)用流的消圈算法在最壞情況下需要計(jì)算時(shí)間38第三十八頁(yè)，共四十七頁(yè)，編輯于2023年，星期三最小費(fèi)用路算法1算法基本思想消圈算法首先找到網(wǎng)絡(luò)中的一個(gè)最大流，然后通過(guò)消去負(fù)費(fèi)用圈使費(fèi)用降低。最小費(fèi)用路算法不用先找最大流，而是用類似于求最大流的增廣路算法的思想，不斷在殘流網(wǎng)絡(luò)中尋找從源s到匯t的最小費(fèi)用路，然后沿最小費(fèi)用路增流，直至找到最小費(fèi)用流。殘流網(wǎng)絡(luò)中從源s到匯t的最小費(fèi)用路是殘流網(wǎng)絡(luò)中從s到t的以費(fèi)用為權(quán)的最短路。殘流網(wǎng)絡(luò)中邊的費(fèi)用定義為：當(dāng)殘流網(wǎng)絡(luò)中邊(v,w)是向前邊時(shí)，其費(fèi)用為cost(v,w)；當(dāng)(v,w)是向后邊時(shí)，其費(fèi)用為-cost(w,v)。39第三十九頁(yè)，共四十七頁(yè)，編輯于2023年，星期三最小費(fèi)用流的最小費(fèi)用路算法步驟0：初始可行0流。步驟1：如果不存在最小費(fèi)用路，則計(jì)算結(jié)束，已經(jīng)找到最小費(fèi)用流；否則用最短路算法在殘流網(wǎng)絡(luò)中找從s到t的最小費(fèi)用可增廣路，轉(zhuǎn)步驟2。步驟2：沿找到的最小費(fèi)用可增廣路增流，并轉(zhuǎn)步驟1。40第四十頁(yè)，共四十七頁(yè)，編輯于2023年，星期三3算法的計(jì)算復(fù)雜性算法的主要計(jì)算量在于連續(xù)尋找最小費(fèi)用路并增流。給定網(wǎng)絡(luò)中有n個(gè)頂點(diǎn)和m條邊，且每條邊的容量不超過(guò)M，每條邊的費(fèi)用不超過(guò)C。每次增流至少使得流值增加1個(gè)單位，因此最多執(zhí)行M次找最小費(fèi)用路算法。如果找1次最小費(fèi)用路需要s(m,n,C)計(jì)算時(shí)間，則求最小費(fèi)用流的最小費(fèi)用路算法需要O(Ms(m,n,C))計(jì)算時(shí)間。41第四十一頁(yè)，共四十七頁(yè)，編輯于2023年，星期三網(wǎng)絡(luò)單純形算法

1算法基本思想消圈算法的計(jì)算復(fù)雜度不僅與算法找到的負(fù)費(fèi)用圈有關(guān)，而且與每次找負(fù)費(fèi)用圈所需的時(shí)間有關(guān)。網(wǎng)絡(luò)單純形算法是從解線性規(guī)劃問(wèn)題的單純形算法演變而來(lái)，但從算法的運(yùn)行機(jī)制來(lái)看，可以將網(wǎng)絡(luò)單純形算法看作另一類消圈算法。其基本思想是用一個(gè)可行支撐樹(shù)結(jié)構(gòu)來(lái)加速找負(fù)費(fèi)用圈的過(guò)程。對(duì)于給定的網(wǎng)絡(luò)G和一個(gè)可行流，相應(yīng)的可行支撐樹(shù)定義為G的一棵包含所有弱流邊的支撐樹(shù)。網(wǎng)絡(luò)單純形算法的第一步是構(gòu)造可行支撐樹(shù)。從一個(gè)可行流出發(fā)，不斷找由弱流邊組成的圈，然后沿找到的弱流圈增流，消除所有弱流圈。在剩下的所有弱流邊中加入零流邊或飽和邊構(gòu)成一棵可行支撐樹(shù)。在可行支撐樹(shù)結(jié)構(gòu)的基礎(chǔ)上，網(wǎng)絡(luò)單純形算法通過(guò)頂點(diǎn)的勢(shì)函數(shù)，巧妙地選擇非樹(shù)邊，使它與可行支撐樹(shù)中的