上海交通大學(xué)管理科學(xué)-運(yùn)籌學(xué)課件-文庫吧
2025-04-03 06:31 本頁面
【正文】 中從到各點(diǎn)的最短路。解：迭代初始條件為：有，，，。用表51表示全部計(jì)算過程。 表51 （表中空格為）ji wijD(t)(v1,vj)V1V2V3V4V5V6V7V8V101230000V26021555V330512222V48023777V510133V61017111V710555V835066 當(dāng)時(shí)，發(fā)現(xiàn)，表明已得到到各點(diǎn)的最短路的權(quán)，即表中最后一列數(shù)。如果需要知道點(diǎn)到各點(diǎn)的最短路徑，可以采用“反向追蹤”的辦法。如已知，因故記下。因，記下，從而從到的最短路徑是。遞推公式中實(shí)際意義為從到點(diǎn)，至多含有個(gè)中間點(diǎn)的最短路權(quán)。所以在含有個(gè)點(diǎn)的圖中，如果不含有總權(quán)小于零的回路，求從到任一點(diǎn)的最短路權(quán)，用上述算法最多經(jīng)過1次迭代必定收斂。顯然，如果圖中含有總權(quán)小于零的回路，最短路權(quán)沒有下界。應(yīng)用舉例例53 設(shè)備更新問題。某企業(yè)使用一臺(tái)設(shè)備，在每年年初，都要決定是否更新。若購置新設(shè)備，要付購買費(fèi)；若繼續(xù)使用舊設(shè)備，則支付維修費(fèi)用。試制定一個(gè)5年更新計(jì)劃，使總支出最少。若已知設(shè)備在各年的購買費(fèi)及不同機(jī)器役齡時(shí)的殘值和維修費(fèi)，如表52所示。 表52第1年第2年第3年第4年第5年購買費(fèi)1112131414機(jī)器役齡0112233445維修費(fèi)5681118殘值43210解：把這個(gè)問題化為最短路問題用表示第年初購進(jìn)一臺(tái)新設(shè)備，虛設(shè)一個(gè)點(diǎn)，表示第5年底；用弧表示第初購的設(shè)備一直使用到第年年底；弧上的數(shù)字表示第年初購進(jìn)設(shè)備，一直使用到第年底所需支付的購買、維修的全部費(fèi)用。例如，弧上的28是第1年初購買費(fèi)11加上3年的維修費(fèi)5，6，8，減去了3年役齡機(jī)器的殘值2；弧上的20是第2年初購買費(fèi)12減去機(jī)器殘值3與使用2年維修費(fèi)5，6之和，見圖511。這樣設(shè)備更新問題就變?yōu)椋呵髲牡降淖疃搪?，?jì)算結(jié)果表明為最短路，路長為49。即在第1年、第3年初各購買一臺(tái)新設(shè)備為最優(yōu)決策，這時(shí)5年的總費(fèi)用為49。 最大流問題最大流問題是一類應(yīng)用極為廣泛的問題。例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流；供水網(wǎng)絡(luò)中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊系統(tǒng)中有信息流；等等。20世紀(jì)50年代Ford ，F(xiàn)ulkerson建立的“網(wǎng)絡(luò)流理論”是網(wǎng)絡(luò)應(yīng)用的重要組成部分。圖512是輸油管道網(wǎng)，為起點(diǎn)，是終點(diǎn)，為中轉(zhuǎn)站，弧上的數(shù)表示該管道的最大輸油能力，問應(yīng)如何安排各管道輸油量，才能使從到的總輸油量最大？ 基本概念與基本定理⑴網(wǎng)絡(luò)與流定義 給一個(gè)有向圖，在中指定一點(diǎn)為發(fā)點(diǎn)，另一點(diǎn)為收點(diǎn)，其余的點(diǎn)叫中間點(diǎn)。對(duì)于每一個(gè)弧，對(duì)應(yīng)有一個(gè)（簡寫為），稱為弧的容量。這樣的叫做網(wǎng)絡(luò)，記作。所謂網(wǎng)絡(luò)上的流，是指定義在弧集合上的一個(gè)函數(shù)，并稱為弧上的流量，簡記作。⑵可行流與最大流①容量限制條件：每一?、谄胶鈼l件：對(duì)于中間點(diǎn)，有對(duì)于發(fā)點(diǎn)，收點(diǎn)，有稱為這個(gè)可行流的流量。可行流總是存在的，如零流。所謂最大流問題，就是求一個(gè)流，使其流量達(dá)到最大，并且滿足以上容量限制條件和平衡條件。其實(shí)最大流問題是一個(gè)特殊的線性規(guī)劃問題，但是利用它與圖的緊密關(guān)系求解，更為直觀簡便。⑶增廣鏈若是網(wǎng)絡(luò)中聯(lián)結(jié)發(fā)點(diǎn)和收點(diǎn)的一條鏈，且鏈的方向是從到，則與鏈的方向一致的弧叫前向弧，表示前向弧的集合；與鏈的方向相反的弧叫后向弧，表示后向弧的集合。定義 設(shè)是一個(gè)可行流，是從到的一條鏈，若滿足下列條件，是可行流的一條增廣鏈。① 弧上，即中每一弧是非飽和弧。② 弧上，即中每一弧是非零流弧。⑷截集與截量設(shè)，我們把始點(diǎn)在，終點(diǎn)在中的所有弧構(gòu)成的集合，記為。定義 給網(wǎng)絡(luò)，若點(diǎn)集被剖分為兩個(gè)非空集合和， ，使，則把弧集稱為分離，的截集。從定義可知截集是從到的必經(jīng)之道。定義 給一截集，把截集中所有弧的容量之和稱為這個(gè)截集的容量，記作不難證明，任何一個(gè)可行流的流量都不會(huì)超過任一截量的容量，即。顯然，若對(duì)于一個(gè)可行流，網(wǎng)絡(luò)中有一個(gè)截集，則必是最大流，而必定是的所有截集中容量最小的一個(gè)，即最小截量。最大流量最小截量定理：任一個(gè)網(wǎng)絡(luò)中，從到的最大流的流量等于分離，的最小截集的容量。定理1 可行流是最大流，當(dāng)且僅當(dāng)不存在關(guān)于的增廣鏈。證明 若是最大流，設(shè)中存在關(guān)于的增廣鏈，令由增廣鏈的定義，可知，令不難驗(yàn)證是一個(gè)可行流，且，這與是最大流假設(shè)矛盾?，F(xiàn)在設(shè)中不存在關(guān)于的增廣鏈，證明是最大流。令，若，且，則令；若，且，則令。因?yàn)椴淮嬖陉P(guān)于的增廣鏈，故。記，于是得到一個(gè)截集，顯然必有所以。于是必是最大流，定理得證。定理1為我們提供了尋求網(wǎng)絡(luò)最大流的一個(gè)方法。若可行流中存在增廣鏈，說明還有潛力可挖，只須沿增廣鏈調(diào)整流量，得到一個(gè)流量增大的新的可行流；否則是最大流。而判別是否存在增廣鏈，可以根據(jù)是否屬于來進(jìn)行。 尋求最大流的標(biāo)號(hào)法（Ford，F(xiàn)ulkerson）設(shè)已有一個(gè)可行流，標(biāo)號(hào)算
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1