數(shù)學規(guī)劃問題講座

1、(Linear Programming, LP)一. 線性規(guī)劃問題及其數(shù)學模型一、問題提出一、問題提出（生產(chǎn)計劃問題）某企業(yè)利用（生產(chǎn)計劃問題）某企業(yè)利用A、B、C三種資源，三種資源，在計劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)在計劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品資源的消耗、單位產(chǎn)品利潤等數(shù)據(jù)如下表，問如品資源的消耗、單位產(chǎn)品利潤等數(shù)據(jù)如下表，問如何安排生產(chǎn)計劃使企業(yè)利潤最大？何安排生產(chǎn)計劃使企業(yè)利潤最大？ 產(chǎn)產(chǎn) 品品資資 源源甲甲乙乙資源限制資源限制ABC120111300kg400kg250kg單位產(chǎn)品利潤單位產(chǎn)品利潤(元元/件件)50100n決策變量決策變量：x1、x2分別代表

2、甲、乙兩分別代表甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量。種產(chǎn)品的生產(chǎn)數(shù)量。目標函數(shù)：max z=50 x1+100 x2約束條件： x1 + x2300 2x1 + x2400 x2250即有： max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20稱之為上述問題的線性規(guī)劃模型。二二、線性規(guī)劃問題的標準形式、線性規(guī)劃問題的標準形式(Standard form)n規(guī)定如下形式的線性規(guī)劃數(shù)學模型為規(guī)定如下形式的線性規(guī)劃數(shù)學模型為LP標準形式。標準形式。max z=c1x1+c2x2+cnxn 目標函數(shù)目標函數(shù) a11x1+a12x2+a1nxn= b1 a2

3、1x1+a22x2+a2nxn= b2 約束條件約束條件 am1x1+am2x2+amnxn= bm x1，x2，xn0n特點特點：Zmax；約束條件為等號；變量非負；約束條件為等號；變量非負；右端常數(shù)項大等于零。右端常數(shù)項大等于零。上述標準形式的線性規(guī)劃模型還可寫成如下一些形式上述標準形式的線性規(guī)劃模型還可寫成如下一些形式: :njjj=1nijjij=1jmaxz =c xa x = bi = 1, . ,mx0 j = 1, . ,n0njjj=1jm axz = cXp x= bxj = 1, . ,n(1)(2)0njjj=1jmaxz = cXp x = bxj = 1, . ,n

4、m axz = cXAX = bX0Xmaxz =cX R = X AX =b,X0R R (4) (3)(5) Integer (Linear )Programming,IP整數(shù)整數(shù)(線性線性)規(guī)劃規(guī)劃整整 數(shù)數(shù) 規(guī)規(guī) 劃劃n整數(shù)規(guī)劃問題與模型整數(shù)規(guī)劃問題與模型n應用案例應用案例線性整數(shù)規(guī)劃模型線性整數(shù)規(guī)劃模型n一般整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型n0-1整數(shù)規(guī)劃模型整數(shù)規(guī)劃模型n混合整數(shù)規(guī)劃模型混合整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型 為整數(shù)為整數(shù)xxbAxtsxc, 0.min 0-1整數(shù)規(guī)劃模型整數(shù)規(guī)劃模型 nixbAxtsxci,.,2 , 1; 1 , 0.min 混合整數(shù)規(guī)劃

5、模型混合整數(shù)規(guī)劃模型pixxbAxtsxci,.,2 , 1,0. .min為整數(shù) 整數(shù)規(guī)劃問題整數(shù)規(guī)劃問題n實例實例應用案例應用案例n投資組合問題投資組合問題n旅游售貨員問題旅游售貨員問題n背包問題背包問題投資組合問題投資組合問題n背背 景景n實實 例例n模模 型型背背 景景n證券投資證券投資：把一定的資金投入到合適的：把一定的資金投入到合適的有價證券上以規(guī)避風險并獲得最大的利有價證券上以規(guī)避風險并獲得最大的利潤。潤。n項目投資項目投資：財團或銀行把資金投入到若：財團或銀行把資金投入到若干項目中以獲得中長期的收益最大干項目中以獲得中長期的收益最大。案案 例例n某財團有某財團有 萬元的資金，經(jīng)

6、出其考察選中萬元的資金，經(jīng)出其考察選中 個投資項目，每個項目只能投資一個。其個投資項目，每個項目只能投資一個。其中第中第 個項目需投資金額為個項目需投資金額為 萬元，預計萬元，預計5年后獲利年后獲利 （ ）萬元，問應如何）萬元，問應如何選擇項目使得選擇項目使得5年后總收益最大？年后總收益最大？Bnjcjbnj.,2 , 1j模模 型型n變量變量每個項目是否投資每個項目是否投資n約束約束總金額不超過限制總金額不超過限制n目標目標總收益最大總收益最大0 , 1 jxnj.,2 , 1 Bxbnjjj 1 njjjxc1max njxBxbtsxcjnjjjnjjj.,2 , 1; 0 , 1.ma

7、x11旅游售貨員問題旅游售貨員問題n背景背景n案例案例n模型模型背背 景景n旅游線路安排旅游線路安排 預定景點走且只走一次預定景點走且只走一次 路上時間最短路上時間最短n配送線路配送線路貨郎擔問題貨郎擔問題 送貨地到達一次送貨地到達一次 總路程最短總路程最短案案 例例n有一旅行團從有一旅行團從 出發(fā)要遍游城市出發(fā)要遍游城市 ，已知從，已知從 到到 的旅費的旅費為為 ，問應如何安排行程使總費，問應如何安排行程使總費用最小用最小？0vnvvv,.,21jvivijc模模 型型n變量變量是否從是否從i第個城市到第第個城市到第j個城市個城市n約束約束 每個城市只能到達一次、離開一次每個城市只能到達一次

8、、離開一次; 0 , 1ijxnjxnixniijnjij,.2 , 1; 1,.2 , 1; 100n避免出現(xiàn)斷裂避免出現(xiàn)斷裂 每個點給個位勢每個點給個位勢 ui , , 除了初始點外要除了初始點外要求前點比后點大求前點比后點大n目標目標總費用最小總費用最小ijninjijxc00njnixnjinnxuunjxnixtsxcijijjiniijnjijijninjij,.,2 , 1,.,2 , 1, 0 , 11 ; 1,.,2 , 1; 1,.,2 , 1; 1. .min0000背包問題背包問題n背景背景n案例案例n模型模型背背 景景n郵遞包裹郵遞包裹 把形狀可變的包裹用盡量少的車輛

9、運走把形狀可變的包裹用盡量少的車輛運走n旅行背包旅行背包 容量一定的背包里裝盡可能的多的物品容量一定的背包里裝盡可能的多的物品實實 例例n某人出國留學打點行李，現(xiàn)有三個旅行包，容某人出國留學打點行李，現(xiàn)有三個旅行包，容積大小分別為積大小分別為1000毫升、毫升、1500毫升和毫升和2000毫毫升，根據(jù)需要列出需帶物品清單，其中一些物升，根據(jù)需要列出需帶物品清單，其中一些物品是必帶物品共有品是必帶物品共有7件，其體積大小分別為件，其體積大小分別為400、300、150、250、450、760、190、（單位毫升）。尚有（單位毫升）。尚有10件可帶可不帶物品，如件可帶可不帶物品，如果不帶將在目的地

10、購買，通過網(wǎng)絡查詢可以得果不帶將在目的地購買，通過網(wǎng)絡查詢可以得知其在目的地的價格（單位美元）。這些物品知其在目的地的價格（單位美元）。這些物品的容量及價格分別見下表，試給出一個合理的的容量及價格分別見下表，試給出一個合理的安排方案把物品放在三個旅行包里。安排方案把物品放在三個旅行包里。 物品物品12345678910體積體積200350500430320120700420250100價格價格1545100705075200902030問題分析問題分析n變量變量對每個物品要確定是否帶同時要確定對每個物品要確定是否帶同時要確定放在哪個包裹里，如果增加一個虛擬的包裹把放在哪個包裹里，如果增加一個虛

11、擬的包裹把不帶的物品放在里面，則問題就轉(zhuǎn)化為確定每不帶的物品放在里面，則問題就轉(zhuǎn)化為確定每個物品放在哪個包裹里。如果直接設變量為每個物品放在哪個包裹里。如果直接設變量為每個物品放在包裹的編號，則每個包裹所含物品個物品放在包裹的編號，則每個包裹所含物品的總?cè)萘烤秃茈y寫成變量的函數(shù)。為此我們設的總?cè)萘烤秃茈y寫成變量的函數(shù)。為此我們設變量為第變量為第i個物品是否放在第個物品是否放在第j個包裹個包裹中中3 , 2 , 1,17.,2 , 1; 0 , 1jixijn約束約束3 , 2 , 1;171jrxcjijii7.,2 , 1; 131ixjij17.,2 , 8; 131ixjij包裹容量限制

12、包裹容量限制必帶物品限制必帶物品限制選帶物品限制選帶物品限制n目標函數(shù)目標函數(shù)未帶物品購買費用最小未帶物品購買費用最小17.,2 , 8;131ixjij)1 (31178jijiixp模模 型型)1 (min31178jijiixp3 , 2 , 1;171jrxcjijii7.,2 , 1; 131ixjij17.,2 , 8; 131ixjij3 , 2 , 1,17.,2 , 1; 0 , 1jixij應用案例分析應用案例分析n人力資源分配問題人力資源分配問題n應急設施選址問題應急設施選址問題人力資源分配問題人力資源分配問題n某個中型百貨商場對售貨人員（周工某個中型百貨商場對售貨人員（

13、周工資資200元）的需求經(jīng)統(tǒng)計如下表元）的需求經(jīng)統(tǒng)計如下表 為了保證銷售人員充分休息，銷售人為了保證銷售人員充分休息，銷售人員每周工作員每周工作5天，休息天，休息2天。問應如何天。問應如何安排銷售人員的工作時間，使得所配安排銷售人員的工作時間，使得所配售貨人員的總費用最??？售貨人員的總費用最?。啃瞧谛瞧谝灰欢乃奈逦辶咂呷藬?shù)人數(shù) 12 15 12 14 16 18 19模型假設模型假設n每天工作每天工作8小時，不考慮夜班的情況；小時，不考慮夜班的情況；n每個人的休息時間為連續(xù)的兩天時每個人的休息時間為連續(xù)的兩天時間；間；n每天安排的人員數(shù)不得低于需求量，每天安排的人員數(shù)不得低于需求量

14、，但可以超過需求量但可以超過需求量問題分析問題分析因素因素 不可變因素不可變因素：需求量、休息時間、單位費用；：需求量、休息時間、單位費用； 可變因素可變因素：安排的人數(shù)、每人工作的時間、總費用；：安排的人數(shù)、每人工作的時間、總費用；方案方案 確定每天工作的人數(shù)，由于連續(xù)休息確定每天工作的人數(shù)，由于連續(xù)休息2天，當確定每天，當確定每個人開始休息的時間就等于知道工作的時間，因而確定個人開始休息的時間就等于知道工作的時間，因而確定每天開始休息的人數(shù)就知道每天開始工作的人數(shù)，從而每天開始休息的人數(shù)就知道每天開始工作的人數(shù)，從而求出每天工作的人數(shù)。求出每天工作的人數(shù)。變量變量 每天開始休息的人數(shù)每天開

15、始休息的人數(shù) 約束條件約束條件 1.每人休息時間每人休息時間2天，自然滿足。天，自然滿足。 7,.,2 , 1, ixi 2. 每天工作人數(shù)不低于需求量，第每天工作人數(shù)不低于需求量，第i天工作的人數(shù)天工作的人數(shù)就是從第就是從第i天往前數(shù)天往前數(shù)5天內(nèi)開始工作的人數(shù)，所以有約束：天內(nèi)開始工作的人數(shù)，所以有約束：1265432xxxxx 1576543xxxxx 1217654xxxxx 1421765xxxxx 1632176xxxxx 1843217xxxxx 1954321xxxxx 3.變量非負約束：變量非負約束：7,.,2 , 1, 0ixi 目標函數(shù)目標函數(shù)：總費用最小，總費用與使用的

16、總總費用最小，總費用與使用的總?cè)藬?shù)成正比。由于每個人必然在且僅在某一人數(shù)成正比。由于每個人必然在且僅在某一天開始休息，所以總?cè)藬?shù)等于天開始休息，所以總?cè)藬?shù)等于 71iix 模模 型型應急選址問題應急選址問題 某城市要在市區(qū)設置某城市要在市區(qū)設置k個應急服務中心個應急服務中心,經(jīng)過初步篩選確定了經(jīng)過初步篩選確定了m個備選地，現(xiàn)已個備選地，現(xiàn)已知共有知共有n個居民小區(qū)，各小區(qū)到個備選地個居民小區(qū)，各小區(qū)到個備選地的距離為的距離為 為了使為了使得各小區(qū)能及時得到應急服務，要求各得各小區(qū)能及時得到應急服務，要求各小區(qū)到最近的服務中心的距離盡可能的小區(qū)到最近的服務中心的距離盡可能的短，試給出中心選址方案

17、。短，試給出中心選址方案。,.,2 , 1,.,2 , 1,mjnidij 問題分析問題分析 該問題與傳統(tǒng)的選址問題的該問題與傳統(tǒng)的選址問題的主要區(qū)別主要區(qū)別在在于其目標不再是要求費用最小，而是要于其目標不再是要求費用最小，而是要求最長距離最短。也就是離服務中心距求最長距離最短。也就是離服務中心距離最遠的小區(qū)離最近的服務中心距離最離最遠的小區(qū)離最近的服務中心距離最小。小。 變量變量：當中心的位置確定下來后，各?。寒斨行牡奈恢么_定下來后，各小區(qū)對應的最近中心也就確定，所以真正區(qū)對應的最近中心也就確定，所以真正的變量也就是小區(qū)的位置。設的變量也就是小區(qū)的位置。設 ,.,2,1,1 ,0mjxj 問

18、題分析問題分析 為了便于說明問題引入間接變量，第為了便于說明問題引入間接變量，第i小區(qū)是否由第小區(qū)是否由第j個中心服務個中心服務 以及最遠的距離以及最遠的距離 約束條件約束條件 小區(qū)服務約束小區(qū)服務約束,.,2 , 1,.,2 , 1, 1 , 0mjniyij ,.,2 , 1,.,2 , 1,mjnixyjij ,.,2 , 1, 11niymjij , z問問 題題 分分 析析最遠距離約束最遠距離約束中心個數(shù)約束中心個數(shù)約束目標函數(shù)目標函數(shù)：最遠距離：最遠距離 最小最小mjnizydijij,.,2 , 1,.,2 , 1, z,1kxmjj 模模 型型0,.,2 , 1,.,2 , 1

19、, 1 , 0,.,2 , 1,.,2 , 1,.,2 , 1, 1,.,2 , 1,.,2 , 1,. .min11zmjniyxkxmjnizydniymjnixytszijjmjjijijmjijjij競賽建模舉例飛行管理問題飛行管理問題一個飛行管理問題 在約10000m高空的某邊長160km的正方形區(qū)域內(nèi),經(jīng)常有若干架飛機作水平飛行,區(qū)域內(nèi)每架飛機的位置和速度向量均由計算機記錄其數(shù)據(jù),以便進行飛行管理.當一架欲進入該區(qū)域的飛機到達邊界區(qū)域邊緣時, 記錄其數(shù)據(jù)后,要立即 計算并判斷是否會與其區(qū)域內(nèi)的飛機發(fā)生碰撞.如果會碰撞 ,則應計算如何調(diào)整各架(包括新進入的)飛機飛行的方向角,以避免碰

20、撞.現(xiàn)假設條件如下: 1) 不碰撞的標準為任意兩架飛機的距離大于8km; 2)飛機飛行方向角調(diào)整的幅度不應超過30度; 3)所有飛機飛行速度均為每小時為800km; 4)進入該區(qū)域的飛機在到達區(qū)域邊緣時,與區(qū)域內(nèi)飛機的距離應在 60km以上; 5)最多考慮6架飛機; 6)不必考慮飛機離開此區(qū)域后的狀況;請你對這個避免碰撞的飛行管理問題建立數(shù)學模型.列出計算步驟,對以下數(shù)據(jù)進行計算(方向角誤差不超過0.01度),要求飛機飛行方向角調(diào)整的幅度盡量小 .設該區(qū)域4個頂點坐標為(0,0),(160,0),(160,160),(0,160).記錄數(shù)據(jù)為: 飛機編號 橫坐標x 縱坐標y 方向角(度) 1

21、150 140 243 2 85 85 236 3 150 155 220.5 4 145 50 159 5 130 150 230 新進入 0 0 52注: 方向角指飛行方向與x軸正向的夾角兩架飛機不碰撞的條件兩架飛機不碰撞的條件222)()()(tjttjtijyyxxtrii,sin,cos00iitiitivtyyvtxxi064)()(2trtfijij（0 t Tij） Ti為第為第i架飛機飛出區(qū)域的時刻架飛機飛出區(qū)域的時刻不碰撞條件不碰撞條件000),(iiiyxiii0 初始位置 時刻t飛機的位置兩架飛機的距離（平方）),min(jiijTTT 0000000000000000

22、0000tan,223tan,23,sin,tan,23tan,2,cos,tan,2tan,20,sin,tan,223tan,20,cosiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiixDyorxyifvyxyorxyDifvxxyDorxDyDifvxDxDyorxDyDifvxDT不必考慮在區(qū)域外的碰撞兩架飛機都在區(qū)域中的時間具體來看，第i架飛機在區(qū)域內(nèi)的時間飛機飛出區(qū)域的時刻飛機飛出區(qū)域的時刻.)(2ijijijijijczbztf整理： fij(t)的最小值 (- bij2 / 4 + cij ) ；此時其中： .2sin4*jiijijvbt不

23、碰撞條件的等價表述不碰撞條件的等價表述 最后，優(yōu)化模型為最后，優(yōu)化模型為 0*ijt若fij(t)大于等于肯定成立ijijTt *若fij(t)大于等于等價于0)(ijijTfijijTt *0若fij(t)大于等于等價于0)(*ijtfij, 042ijijcbLINGOLINGO求解求解283. 0800/2160/2maxvDT一個簡化的數(shù)學模型一個簡化的數(shù)學模型任何一架飛機在區(qū)域中停留最長時間 放松到任兩架飛機在這段時間不碰撞甚至放松到任兩架飛機永遠不碰撞000),(iiiyxiii0.61iiMin其他目標調(diào)整后的方向角 總的調(diào)整量最小總的調(diào)整量最小 |max6,.,1iiMin最大

24、調(diào)整量最小最大調(diào)整量最小 初始位置與方向角基于相對運動觀點的模型)22sin(),22(cos(2sin2)2cos,2sin(2sin2)2cos2sin,2sin2sin(2)sinsin,coscos(jijijijijijijijijijiijijvvvvvvvvvijijr基于相對運動觀點的模型,8sin1ijijr于是 . 6 , 1,30, 6 , 1,)(. .21612ijijitsMiniijjiijii數(shù)學規(guī)劃模型 三三.圖與網(wǎng)絡分析圖與網(wǎng)絡分析p圖的基本知識圖的基本知識p最短路徑問題最短路徑問題p網(wǎng)絡最大流問題網(wǎng)絡最大流問題p網(wǎng)絡最小費用流問題網(wǎng)絡最小費用流問題引引 言

25、言AB圖8-1 a）CD圖8-1 b）ACDB例例 中國郵遞員問題中國郵遞員問題（CPPChinese postman problem） 一名郵遞員負責投遞某個街區(qū)的郵件。如一名郵遞員負責投遞某個街區(qū)的郵件。如何為他（她）設計一條最短的投遞路線（從郵何為他（她）設計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問題是我國管梅谷教后返回郵局）？由于這一問題是我國管梅谷教授授19601960年首先提出的，所以國際上稱之為中國年首先提出的，所以國際上稱之為中國郵遞員問題。郵遞員問題。例例 旅行商問題（哈密頓問題）旅行商問

26、題（哈密頓問題）（TSPtraveling salesman problem） 一名推銷員準備前往若干城市推銷產(chǎn)品。一名推銷員準備前往若干城市推銷產(chǎn)品。如何為他（她）設計一條最短的旅行路線（從如何為他（她）設計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。稱之為旅行商問題。 圖論中常用點和點之間的線所構(gòu)成的圖論中常用點和點之間的線所構(gòu)成的圖，反映實際生產(chǎn)和生活中的某些特定對圖，反映實際生產(chǎn)和生活中的某些特定對象之間的特定關系。一般來說，通常用

27、點象之間的特定關系。一般來說，通常用點表示研究對象、用點與點之間的線表示研表示研究對象、用點與點之間的線表示研究對象之間的特定關系。究對象之間的特定關系。 在一般情況下，圖中的相對位置如何，在一般情況下，圖中的相對位置如何，點與點之間線的長短曲直，對于反映研究點與點之間線的長短曲直，對于反映研究對象之間的關系，顯的并不重要。對象之間的關系，顯的并不重要。 因此，圖論中的圖與幾何圖，工程圖因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。等本質(zhì)上是不同的。 通常把點與點之間不帶箭頭的線叫做通常把點與點之間不帶箭頭的線叫做邊邊，帶箭，帶箭頭的線叫做頭的線叫做弧弧。 如果一個圖是由點和邊所構(gòu)成的，那

28、么，稱為為如果一個圖是由點和邊所構(gòu)成的，那么，稱為為無向圖無向圖，記作，記作G =(V，E)，其中，其中V V表示圖表示圖G的點集合的點集合，E表示圖表示圖G的邊集合。連接點的邊集合。連接點vi ,vjV的邊記作的邊記作 vi ,vj ，或者或者 vj ,vi 。 如果一個圖是由點和弧所構(gòu)成的，那么稱為它為如果一個圖是由點和弧所構(gòu)成的，那么稱為它為有向圖有向圖，記作，記作D =(V,A)，其中，其中V 表示有向圖表示有向圖D D的點集合，的點集合，A表示有向圖表示有向圖D D的弧集合。一條方向從的弧集合。一條方向從vi指向指向vj的弧，記的弧，記作作( (vi,vj) )。例如例如.下下圖是一

29、個無向圖圖是一個無向圖G=（V，E）其中其中V = v1,v2,v3,v4 E = v1,v2,v2,v1,v2,v3, v3,v4,v1,v4, v2,v4, v3,v3 v3v2v1v4下圖是一個有向圖下圖是一個有向圖D=（V，A）其中其中V = v1,v2,v3,v4,v5,v6,v7 A = (v1 ,v2),(v1 ,v3),(v3 ,v2), (v3 ,v4), (v2 ,v4),(v4 ,v5),(v4 ,v6),(v5 ,v3), (v5 ,v4),(v5 ,v6),(v6 ,v7)v7v5v3v4v2v1v61.1.最短路徑問題最短路徑問題 最短路徑問題是圖論中十分重要的最優(yōu)

30、化問題之一，它作為一個經(jīng)常被用到的基本工具，可以解決生產(chǎn)實際中的許多問題，比如城市中的管道鋪設，線路安排，工廠布局，設備更新等等。也可以用于解決其它的最優(yōu)化問題。最短路問題一一、引例：、引例：如下圖中如下圖中V1：油田，：油田，V9：原油加工廠：原油加工廠求使從求使從V1到到V9總鋪路設管道最短方案?？備伮吩O管道最短方案。 V1V4V2V3V6V9V8V7V542466234442二、最短路算法二、最短路算法1、情況一： wij0(E.W.Dijkstra算法)原理：Bellman最優(yōu)性定理方法：圖上作業(yè)法（標號法）標號：對于點,若已求出到vi的最短值，標號（i,i) i ：表示到的最短路值

31、i:表示最短路中最后經(jīng)過的點標號法步驟：1）給v1標號(0, vs)2）把所有頂點分成兩部分,P：已標號的點；T未標號的點考慮與已標號點相鄰的弧是存在這樣的?。?vi ，vj ）, vi P, vj T若不存在，此問題無解，否則轉(zhuǎn)3）3）選取未標號中所有入線的起點與未標號的點vj進行計算:mini + wij= j并對其進行標號(j, vi)，重復2）2、情況二： wij0設從v1到vj(j=1,2,t)的最短路長為p1jv1到vj無任何中間點 p1j（1）= wijv1到vj中間最多經(jīng)過一個點 p1j（2）= min p1j（1）+wijv1到vj中間最多經(jīng)過兩個點 p1j（3）= min

32、p1j（2）+wij.v1到vj中間最多經(jīng)過t-2個點 p1j（t-1）= min p1j（t-2）+wij終止原則：1）當p1j（k）=p1j（k+1）可停止，最短路p1j*= p1j（k）2）當p1j（t-1）= p1j（t-2）時，再多迭代一次p1j（t） ，若p1j（t） = p1j（t-1） ，則原問題無解，存在負回路。 例： 求下圖所示有向圖中從v1到各點的最短路。v1v4v2v3v5v6v7v825-34674-23-1-342 wij d(t)(v1,vj) v1 v2 v3 v4 v5 v6 v7 v8v1v2 v3 v4v5v6v7v80 25-30 -2406400-3

33、0720320t=1 t=2 t=3 t=4 t=5 t=6025-3020-3611020-36615020-3361410020-336910020-336910說明：表中空格處為說明：表中空格處為+ 。例例 設備更新問題設備更新問題制訂一設備更新問題，使得總費用最小制訂一設備更新問題，使得總費用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 購買費購買費 13 14 16 19 24 使用年數(shù)使用年數(shù) 0-1 1-2 2-3 3-4 4-5 維修費維修費 8 10 13 18 27 解設以vi(i=1,2,3,4,5)表示“第i年初購進一臺新設備”這種狀態(tài)，以v6表示“

34、第5年末”這種狀態(tài)；以弧(vi, vj)表示“第i年初購置的一臺設備一直使用到第j年初”這一方案，以wij表示這一方案所需購置費和維護費之和。v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(0，V1)(31, V1)(44,V1)(62,V1)(78,V3)這樣，可建立本例的網(wǎng)絡模型。于是，該問題就這樣，可建立本例的網(wǎng)絡模型。于是，該問題就可歸結(jié)為從圖中找出一條從可歸結(jié)為從圖中找出一條從v1到到v6的最短路問題。的最短路問題。用用Dijkstra標號法，求得最短路為標號法，求得最短路為 v1v3v6 即第一年初購置的設備使用到第三年初予以更新，

35、即第一年初購置的設備使用到第三年初予以更新，然后一直使用到第五年末。這樣五年的總費用最然后一直使用到第五年末。這樣五年的總費用最少，為少，為78。 2.2.網(wǎng)絡系統(tǒng)的最大流問題網(wǎng)絡系統(tǒng)的最大流問題基本概念基本概念 定義定義 設賦權(quán)有向圖設賦權(quán)有向圖D=(V,A), 在在V中指定一中指定一個個發(fā)點發(fā)點vs和一個和一個收收點點vt , 其他的點叫做中間點。其他的點叫做中間點。對于對于D中的每一個弧中的每一個弧 (vi ,vj)A, 都有一個權(quán)都有一個權(quán) cij 叫做弧的叫做弧的容量容量。我們把這樣的圖。我們把這樣的圖 D 叫做一個網(wǎng)叫做一個網(wǎng)絡系統(tǒng)，簡稱絡系統(tǒng)，簡稱網(wǎng)絡網(wǎng)絡，記做，記做D =（V，

36、A，C）。）。2. 最大流問題最大流問題 如下是一運輸網(wǎng)絡，弧上的數(shù)字表示每條弧如下是一運輸網(wǎng)絡，弧上的數(shù)字表示每條弧上的容量，問：該網(wǎng)絡的最大流量是多少？上的容量，問：該網(wǎng)絡的最大流量是多少？vsv2v1v3v4vt432312234基本概念和基本定理基本概念和基本定理1、網(wǎng)絡與流定義1：給定一個有向圖D=(V,A),在V中有一個發(fā)點vs和一收點vt，其余的點為中間點。對于每一條弧(vi,vj),對應有一個c(vi,vj)0,(cij)稱為弧的容量。這樣的有向圖稱為網(wǎng)絡。記為D=(V,A,C)。網(wǎng)絡的流：定義在弧集合A上的一個函數(shù)f=f(vi,vj)，稱f(vi,vj)為弧(vi,vj)上的

37、流量，簡記fij 。2、可行流與最大流、可行流與最大流定義定義2 滿足下列條件的流稱為滿足下列條件的流稱為可行流可行流：1) 0 fijcij2)平衡條件：平衡條件：中間點中間點 fij = fji(vi,vj) A(vj,vi) A發(fā)點發(fā)點vs fsj fjs=v(f)(vs,vj) A(vj,vs)A ftj fjt= v(f)(vt,vj)A收點收點vt，(vj,vt)A式中v(f)稱為這個可行流的流量，即發(fā)點的凈輸出量（或收點的凈輸入量）。3、增廣鏈增廣鏈 給定可行流f=fij，使fij=cij的弧稱為飽和弧，使fij0的弧稱為非零流弧。 若是網(wǎng)絡中連接發(fā)點vs和收點vt的一條鏈，定義

38、鏈的方向是從vs到vt，則鏈上的弧被分成兩類：前向弧：弧的方向與鏈的方向一致 全體+后向?。夯〉姆较蚺c鏈的方向相反 全體定義3 設f是一可行流，是從vs到vt的一條鏈，若滿足下列條件，則稱之為（關于流f的）一條增廣鏈： 在弧(vi,vj)+上，0fijcij 在弧(vi,vj)上，0fijcij步驟：2、 標號過程1、選取一個可行流（可選擇零流?。?從vs出發(fā)，在前向弧上(vi,vj) ，若fij0，則給vj標號( vi,l(vj)，其中l(wèi)(vj)=minl(vi)，fji。尋找最大流的標號法(Ford Fulkerson) 思想：從一可行流出發(fā)，檢查關于此流是否存在增廣鏈。若存在增廣鏈，則增

39、大流量，使此鏈變?yōu)榉窃鰪V鏈；這時再檢查是非還有增廣鏈，若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。 3、若標號延續(xù)到vt，表明得到一條從vs到vt的增廣鏈，轉(zhuǎn)入調(diào)整階段4，否則當前流即為最大流。4、調(diào)整過程令調(diào)整量為= l(vt)令 fij+ (vi,vj)+ fij= fij (vi,vj) fij (vi,vj)去掉所有的標號，對新的可行流f=fij，重新進入標號過程?？山Y(jié)合下圖理解其實際涵義?？山Y(jié)合下圖理解其實際涵義。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2) 在實際的網(wǎng)絡系統(tǒng)中，當涉及到有關在實際的網(wǎng)絡系統(tǒng)中，當涉及到

40、有關流的問題的時候，我們往往不僅僅考慮的流的問題的時候，我們往往不僅僅考慮的是流量，還經(jīng)常要考慮費用的問題。比如是流量，還經(jīng)常要考慮費用的問題。比如一個鐵路系統(tǒng)的運輸網(wǎng)絡流，即要考慮網(wǎng)一個鐵路系統(tǒng)的運輸網(wǎng)絡流，即要考慮網(wǎng)絡流的貨運量最大，又要考慮總費用最小。絡流的貨運量最大，又要考慮總費用最小。最小費用最大流問題就是要解決這一類問最小費用最大流問題就是要解決這一類問題。題。3.3.網(wǎng)絡系統(tǒng)的最小費用最大流問題網(wǎng)絡系統(tǒng)的最小費用最大流問題 設一個網(wǎng)絡D = (V1，A，C )，對于每一個弧(vi ,vj)A, 給定一個單位流量的費用bij 0，網(wǎng)絡系統(tǒng)的最小費用最大流問題，是指要尋求一個最大流

41、f ，并且流的總費用 b ( f ) = bij fij 達到最小。 （vi ,vj）A 在一個網(wǎng)絡D 中，當沿可行流 f 的一條增廣鏈，以調(diào)整量=1改進 f ，得到的新可行流 f 的流量，有 v( f ) = v( f ) + 1， 此時總費用 b( f ) 比 b( f ) 增加了 b(f)-b(f)=bij(fij-fij)- bij(fij-fij)= bij-bij + - + -將bij-bij叫做這條增廣鏈的費用。 如果可行流在流量為如果可行流在流量為v(f)的所有可行流中的所有可行流中的費用最小，并且是的費用最小，并且是 關于關于f 的所有增廣鏈中的的所有增廣鏈中的費用最小的增

42、廣鏈。那么沿增廣鏈費用最小的增廣鏈。那么沿增廣鏈調(diào)整可行流調(diào)整可行流f，得到的新可行流，得到的新可行流f，也是流量為，也是流量為v(f)的所有的所有可行流中的最小費用流。可行流中的最小費用流。 依次類推，當依次類推，當f是最大流時，就是所要求的是最大流時，就是所要求的最小費用最大流。最小費用最大流。 顯然，零流f =0是流量為0的最小費用流。一般地，尋求最小費用流，從零流f=0開始。問題是：如果已知f 是流量為 v ( f ) 的最小費用流，那么就要去尋找關于f 的最小費用增廣鏈。 重新構(gòu)造一個賦權(quán)有向圖重新構(gòu)造一個賦權(quán)有向圖M( f )，其頂點，其頂點是原網(wǎng)絡是原網(wǎng)絡D的頂點，而將的頂點，而將D中的每一條弧中的每一條弧(vi,vj)變變成兩個相反方向的?。ǔ蓛蓚€相反方向的?。╲i,v