網(wǎng)絡(luò)最優(yōu)化問題精編版

1、 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 2 無限配送公司的問題無限配送公司的問題 無限配送公司有兩個工廠生產(chǎn)產(chǎn)品，這無限配送公司有兩個工廠生產(chǎn)產(chǎn)品，這 些產(chǎn)品需要運到兩個倉庫里些產(chǎn)品需要運到兩個倉庫里 工廠工廠1 1生產(chǎn)生產(chǎn)8080個單位個單位 工廠工廠2 2生產(chǎn)生產(chǎn)7070個單位個單位 倉庫倉庫1 1需要需要6060個單位個單位 倉庫倉庫2 2需要需要9090個單位個單位 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 3 無限配送公司的問題無限配送公司的問題 在工廠在工廠1 1和倉庫和倉庫1 1之間以及工廠之間以及工廠2 2和倉和倉 庫庫2

2、 2之間各有一條鐵路運輸軌道之間各有一條鐵路運輸軌道 卡車司機至多可以從工廠運輸卡車司機至多可以從工廠運輸5050 個單位到配送中心，然后可以從個單位到配送中心，然后可以從 配送中心運輸配送中心運輸5050個單位到倉庫個單位到倉庫 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 4 配送網(wǎng)絡(luò)配送網(wǎng)絡(luò) Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 5 配送網(wǎng)絡(luò)的數(shù)據(jù)配送網(wǎng)絡(luò)的數(shù)據(jù) Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 6 最小費用流問題的網(wǎng)絡(luò)模型最小費用流問題的網(wǎng)絡(luò)模型 Copyright 2011 北京工商大學(xué)商學(xué)院北京工

3、商大學(xué)商學(xué)院 7 每條路線應(yīng)該運送多少每條路線應(yīng)該運送多少 單位的產(chǎn)品？單位的產(chǎn)品？ 無限配送公司的問題無限配送公司的問題 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 8 最優(yōu)解最優(yōu)解 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 9 最小費用流問題的術(shù)語最小費用流問題的術(shù)語 所有最小費用流問題都是用帶有通 過其中的流的網(wǎng)絡(luò)表示的 網(wǎng)絡(luò)中的圓圈被稱為節(jié)點 如果節(jié)點產(chǎn)生的凈流量流出減去流入 是一個確定的正數(shù)的話，這個節(jié)點就 是供應(yīng)點 如果節(jié)點產(chǎn)生的凈流量是一個確定的 負(fù)數(shù)的話，那么這個節(jié)點就稱為需求 點 Copyright 2011 北京工商大學(xué)商學(xué)

4、院北京工商大學(xué)商學(xué)院 10 最小費用流問題的術(shù)語最小費用流問題的術(shù)語 如果節(jié)點產(chǎn)生的凈流量恒為零，那么這個 節(jié)點就稱為轉(zhuǎn)運點，我們把流出節(jié)點的量 等于流入節(jié)點的量稱為流量守恒 網(wǎng)絡(luò)中的箭頭稱為弧 允許通過某一條弧的最大流量稱為該 弧的容量 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 11 最小費用流問題的假設(shè)最小費用流問題的假設(shè) 至少有一個節(jié)點是供應(yīng)點 至少有一個節(jié)點是需求點 所有剩下的節(jié)點都是轉(zhuǎn)運點 通過弧的流只允許沿著箭頭的方向 流動，通過弧的最大流量取決于該 弧的容量如果流是雙向的話，則需 要用一對箭頭指向相反的弧來表示 Copyright 2011 北京工商大學(xué)

5、商學(xué)院北京工商大學(xué)商學(xué)院 12 最小費用流問題的假設(shè)最小費用流問題的假設(shè) 網(wǎng)絡(luò)中有足夠的弧提供足夠的容 量，使得所有在供應(yīng)點中產(chǎn)生的 流都能夠達到需求點 在流的單位成本已知的前提下， 通過每一條弧的流的成本和流量 成正比 最小費用流問題的目標(biāo)是在滿足給定 需求的條件下，使得通過網(wǎng)絡(luò)供應(yīng)的 總成本最小或通過這樣做使得總利潤 最大化 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 13 最小費用流問題的特征最小費用流問題的特征 具有可行解的特征：在以上假設(shè)下，當(dāng)且 僅當(dāng)供應(yīng)點所提供的流量總和等于需求點 所需要的流量總和時，最小費用流問題有 可行解 具有整數(shù)解的特征：只要其所有的

6、供應(yīng)、 需求和弧的容量都是整數(shù)值，那么任何 最小費用流問題的可行解就一定有所有 流量都是整數(shù)的最優(yōu)解 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 14 電子表格描述電子表格描述 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 15 SUMIF SUMIF 函數(shù)函數(shù) SUMIF公式可以簡化節(jié)點流約束公式可以簡化節(jié)點流約束 SUMIF(Range A, x, Range B) 區(qū)域區(qū)域A中的每一個量滿足條件中的每一個量滿足條件x時，時，SUMIF函函 數(shù)就會計算區(qū)域數(shù)就會計算區(qū)域B中相應(yīng)內(nèi)容之和中相應(yīng)內(nèi)容之和 節(jié)點節(jié)點x的凈流出的凈流出流出流出-流入流入

7、就等于就等于 SUMIF(“From labels”, x, “Flow”) SUMIF(“To labels”, x, “Flow”) Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 16 對每一個節(jié)點有一個約束，必須遵循對每一個節(jié)點有一個約束，必須遵循“流量流量 守恒規(guī)則守恒規(guī)則” 轉(zhuǎn)運問題：凈流量=流出量-流入量 最小成本網(wǎng)絡(luò)流中將流量守恒規(guī)則應(yīng)用于每個節(jié)點 總供給總需求流出量-流入量=供給或需求 總供給=供給或需求 總供給=總需求流出量-流入量=供給或需求 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 17 對每一個節(jié)點有一個約束，必須遵循對每

8、一個節(jié)點有一個約束，必須遵循“流量流量 守恒規(guī)則守恒規(guī)則” 凈流量=流入量-流出量 最小成本網(wǎng)絡(luò)流中將流量守恒規(guī)則應(yīng)用于每個節(jié)點 總供給總需求流入量-流出量=供給或需求 總供給總需求流入量-流出量=供給或需求 總供給=總需求流入量-流出量=供給或需求 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 18 轉(zhuǎn)運問題 Newark港和港和Jacksonville港接受到進口到美國港接受到進口到美國 的汽車分別為的汽車分別為200輛和輛和300輛。輛。 B城，城，G城，城，Y城，城，R城和城和M城的經(jīng)銷商分別需城的經(jīng)銷商分別需 要要100輛，輛，60輛，輛，170輛、輛、80輛和

9、輛和70輛汽車。輛汽車。 根據(jù)各個城市間的運輸費用確定成本最小的根據(jù)各個城市間的運輸費用確定成本最小的 運送汽車的方式。運送汽車的方式。 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 19 凈流量凈流量= =流出量流出量- -流入量流入量 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 20 凈流量等于流入量凈流量等于流入量- -流出量流出量 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 21 請在電子表格里分別按照供給為正和供給 為負(fù)的情況，建立兩種情況下的模型，并 求解比較 Copyright 2011 北京工商大學(xué)商學(xué)院北京

10、工商大學(xué)商學(xué)院 22 供給為正、需求為負(fù)時的電子表格模型 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 23 供給為負(fù)、需求為正的電子表格模型 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 24 分析最優(yōu)解分析最優(yōu)解 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 25 廣義網(wǎng)絡(luò)流問題廣義網(wǎng)絡(luò)流問題 目前所考慮的網(wǎng)絡(luò)流問題，從一條弧線出 來的流量與進入的流量一定是相等的。 事實上是這種情況嗎？ Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 26 Coal Bank Hollow Coal Bank Hollo

11、w 再生公司再生公司 該公司使用兩種不同的再生過程來將報紙、 混合紙、白色辦公紙和紙板轉(zhuǎn)化為紙漿。 從再生原料提出再生紙漿的數(shù)量和紙漿的 提取成本由于使用不同的再生過程而不同。 通過兩種不同的再生過程產(chǎn)生的紙漿通過 其他處理轉(zhuǎn)化為新聞用紙、包裝用紙或高 質(zhì)量打印紙。 兩種處理過程的具體數(shù)據(jù)如下 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 27 紙漿生產(chǎn)問題提取紙漿數(shù)據(jù) 再生過程再生過程1 再生過程再生過程2 原料原料每噸成本每噸成本 產(chǎn)出結(jié)果產(chǎn)出結(jié)果每噸成本每噸成本 產(chǎn)出結(jié)果產(chǎn)出結(jié)果 報紙報紙13 90%1285% 混合紙混合紙11 80%1385% 白色辦白色辦 公紙

12、公紙 9 95%1090% 紙板紙板13 75%1485% Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 28 最終紙漿產(chǎn)出結(jié)果 新聞用紙包裝用紙打印紙 紙漿來源紙漿來源 每噸成本每噸成本 產(chǎn)出產(chǎn)出 每噸成本每噸成本 產(chǎn)出產(chǎn)出 每噸成本每噸成本 產(chǎn)出產(chǎn)出 過程1 5 95% 6 90% 8 90% 過程2 6 90% 8 95% 7 95% 如果有70噸報紙，50噸混合紙，30噸白色辦公紙 和40噸紙板。 如何轉(zhuǎn)化成60噸新聞用紙紙漿，40噸包裝用紙紙 漿，50噸打印紙紙漿，成本最低。 使用供給為負(fù)，需求為正的方法 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商

13、大學(xué)商學(xué)院 29 轉(zhuǎn)化為最小費用流問題的網(wǎng)絡(luò)圖轉(zhuǎn)化為最小費用流問題的網(wǎng)絡(luò)圖 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 30 電子表格模型 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 31 最優(yōu)解分析 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 32 流量守恒規(guī)則的應(yīng)用流量守恒規(guī)則的應(yīng)用 當(dāng)不確定總供給和總需求的關(guān)系時，假設(shè) 供給大于需求 如果沒有可行解，再更改為需求大于供給 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 33 最小費用流問題的應(yīng)用最小費用流問題的應(yīng)用 通過配送網(wǎng)絡(luò)的費用最小通過配送網(wǎng)

14、絡(luò)的費用最小 現(xiàn)金流管理現(xiàn)金流管理 工廠協(xié)調(diào)產(chǎn)品組合工廠協(xié)調(diào)產(chǎn)品組合 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 34 BMZBMZ公司的最大流問題公司的最大流問題 BMZBMZ公司是歐洲一家生產(chǎn)豪華汽車的制公司是歐洲一家生產(chǎn)豪華汽車的制 造商，其產(chǎn)品出口到美國尤為重要造商，其產(chǎn)品出口到美國尤為重要 BMZ公司的汽車尤其在加利福尼亞大受 歡迎，因此保持洛杉磯中心零部件的充 足供給，以便及時維修這些汽車就顯得 特別重要了 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 35 BMZBMZ公司的最大流問題公司的最大流問題 BMZ公司需要迅速執(zhí)行一項計劃，

15、下個月要 從位于斯圖加特和德國的主要工廠運送盡可 能多的配件到洛杉磯的配送中心 配件運送數(shù)量的限制因素就是公司配送網(wǎng)絡(luò) 的容量 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 36 BMZ BMZ 公司配送網(wǎng)絡(luò)公司配送網(wǎng)絡(luò) Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 37 BMZBMZ問題的網(wǎng)絡(luò)模型問題的網(wǎng)絡(luò)模型 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 38 通過每一條運送路線應(yīng)通過每一條運送路線應(yīng) 該運送多少配件，才能該運送多少配件，才能 使從斯圖加特到洛杉磯使從斯圖加特到洛杉磯 的總流量最大？的總流量最大？ BMZBM

16、Z公司的最大流問題公司的最大流問題 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 39 BMZBMZ公司的電子表格模型公司的電子表格模型 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 40 最大流問題的假設(shè)最大流問題的假設(shè) 網(wǎng)絡(luò)中所有流起源于一個節(jié)點，這個節(jié)點網(wǎng)絡(luò)中所有流起源于一個節(jié)點，這個節(jié)點 叫作源叫作源 起點起點 ，所有的流終止于另一個節(jié)，所有的流終止于另一個節(jié) 點，這個節(jié)點叫作收點點，這個節(jié)點叫作收點 終點終點 。BMZBMZ問題問題 中的源和收點分別代表工廠和配送中心中的源和收點分別代表工廠和配送中心 其余所有的節(jié)點叫作轉(zhuǎn)運點其余所有的節(jié)點

17、叫作轉(zhuǎn)運點 通過每一個弧的流只允許沿著弧的箭頭所通過每一個弧的流只允許沿著弧的箭頭所 指方向流動。由源發(fā)出的所有的弧背向源，指方向流動。由源發(fā)出的所有的弧背向源， 而所有終結(jié)于收點的弧都指向收點而所有終結(jié)于收點的弧都指向收點 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 41 最大流問題的假設(shè)最大流問題的假設(shè) 最大流問題的目標(biāo)是使得從源到收點最大流問題的目標(biāo)是使得從源到收點 的總流量最大。這個流量的大小可以的總流量最大。這個流量的大小可以 用兩種等價的方法來衡量，分別叫作用兩種等價的方法來衡量，分別叫作 從源點出發(fā)的流量和進入收點的流量從源點出發(fā)的流量和進入收點的流量 C

18、opyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 42 最大流問題和最小費用流問題區(qū)別最大流問題和最小費用流問題區(qū)別 最小費用流問題：供應(yīng)點、需最小費用流問題：供應(yīng)點、需 求點求點 最大流問題：源、收點最大流問題：源、收點 最小費用流問題的供應(yīng)量和需最小費用流問題的供應(yīng)量和需 求量都是固定的，而最大流問求量都是固定的，而最大流問 題的源和收點卻不是題的源和收點卻不是 最小費用流問題的供應(yīng)點和需最小費用流問題的供應(yīng)點和需 求點可能有多個，但最大流問求點可能有多個，但最大流問 題的源和收點只有一個題的源和收點只有一個 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)

19、院 43 BMZ BMZ 公司具有多個供應(yīng)點和需求點的案例公司具有多個供應(yīng)點和需求點的案例 BMZBMZ公司在柏林還有一家更小的工廠公司在柏林還有一家更小的工廠 一旦洛杉磯配送中心出現(xiàn)缺貨，位于西雅一旦洛杉磯配送中心出現(xiàn)缺貨，位于西雅 圖的配送中心就可以給有關(guān)的客戶供應(yīng)配圖的配送中心就可以給有關(guān)的客戶供應(yīng)配 件件 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 44 擴展的擴展的BMZBMZ問題的網(wǎng)絡(luò)模型問題的網(wǎng)絡(luò)模型 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 45 擴展的擴展的BMZBMZ問題問題 通過每一條運送路線通過每一條運送路線 應(yīng)該運送多

20、少配件，應(yīng)該運送多少配件， 才能使從斯圖加特和才能使從斯圖加特和 柏林到洛杉磯和西雅柏林到洛杉磯和西雅 圖的總流量最大？圖的總流量最大？ Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 46 電子表格描述電子表格描述 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 47 最大流問題的應(yīng)用最大流問題的應(yīng)用 通過配送網(wǎng)絡(luò)的流量最大，如通過配送網(wǎng)絡(luò)的流量最大，如BMZBMZ問題問題 通過從供應(yīng)商到處理設(shè)施的公司供應(yīng)網(wǎng)絡(luò)的流通過從供應(yīng)商到處理設(shè)施的公司供應(yīng)網(wǎng)絡(luò)的流 量最大量最大 通過管道運輸系統(tǒng)運送的油量最大通過管道運輸系統(tǒng)運送的油量最大 最大化通過輸水系統(tǒng)的水

21、量最大化通過輸水系統(tǒng)的水量 通過交通網(wǎng)絡(luò)的車流量最大通過交通網(wǎng)絡(luò)的車流量最大 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 48 網(wǎng)絡(luò)流與整數(shù)解網(wǎng)絡(luò)流與整數(shù)解 使用單純形法求解具有約束的右側(cè)值是整數(shù)使用單純形法求解具有約束的右側(cè)值是整數(shù) 的任何最小成本的網(wǎng)絡(luò)流模型，最優(yōu)解自動的任何最小成本的網(wǎng)絡(luò)流模型，最優(yōu)解自動 取整。取整。 但是如果加入了副約束，這樣不服從流量守但是如果加入了副約束，這樣不服從流量守 恒規(guī)則，就不能保證問題的線性規(guī)劃模型的恒規(guī)則，就不能保證問題的線性規(guī)劃模型的 解是整數(shù)。解是整數(shù)。 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 4

22、9 特殊建模的考慮特殊建模的考慮 26 5 4 31100 100 -75 0 0 -50 如果要求進入節(jié)點3的流量至少為50，進入節(jié)點4 的流量至少為60，如何建模？ Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 50 特殊建模的考慮特殊建模的考慮 輔助約束 -X13-X23=-50 -X14-X24=-60 必須加入虛節(jié)點或虛弧線 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 51 特殊建模的考慮特殊建模的考慮 26 5 40 301100 100 -75 0 0 -50 如果要求進入節(jié)點3的流量至少為50，進入節(jié)點4 的流量至少為60，如何建模

23、？ 3 4 $0 L.B.= -50 $0 L.B.= -60 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 52 特殊建模的考慮特殊建模的考慮 12 $8 $6 U.B.=35 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 53 特殊建模的考慮特殊建模的考慮 1 2 $8 $6 U.B.=35 10 $0 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 54 特殊建模的考慮特殊建模的考慮 24 $6 $3 U.B.=35 1 $4 3 U.B.=35 U.B.=30 $5,U.B.=40 100 100-80 -75 Copyr

24、ight 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 55 特殊建模的考慮特殊建模的考慮 24 $6 $3 U.B.=35 1 $4 3 U.B.=35 U.B.=30 $5,U.B.=40 -100 -100 +80 +75 0 U.B.=100 U.B.=100 200 $999 $999 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 56 輔助約束與整數(shù)解輔助約束與整數(shù)解 加入輔助約束，則不會自己取整 需要加入整數(shù)約束 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 57 里特城的消防隊問題里特城的消防隊問題 里特城是一個農(nóng)村的小鎮(zhèn)里特城是一

25、個農(nóng)村的小鎮(zhèn) 它的消防隊要為包括許多農(nóng)場社區(qū)在它的消防隊要為包括許多農(nóng)場社區(qū)在 內(nèi)的大片地區(qū)提供服務(wù)內(nèi)的大片地區(qū)提供服務(wù) 在這個地區(qū)有很多路，從消防站到任在這個地區(qū)有很多路，從消防站到任 何一個社區(qū)都有很多條路線可供選擇何一個社區(qū)都有很多條路線可供選擇 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 58 里特城的道路系統(tǒng)里特城的道路系統(tǒng) Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 59 最短路問題的網(wǎng)絡(luò)規(guī)劃最短路問題的網(wǎng)絡(luò)規(guī)劃 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 60 從消防站到某個特定從消防站到某個特定 的農(nóng)場社區(qū)

26、的最短路的農(nóng)場社區(qū)的最短路 線是那條？線是那條？ 里特城的消防隊問題里特城的消防隊問題 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 61 最短路問題的標(biāo)號法最短路問題的標(biāo)號法 q19591959年，年，DijkstraDijkstra提出提出 q算法步驟：算法步驟： v步驟步驟1 1：起點是已標(biāo)號點，：起點是已標(biāo)號點， 標(biāo)號為標(biāo)號為0 0 v步驟步驟2 2：從所有已標(biāo)號點：從所有已標(biāo)號點 向未標(biāo)號點擴散，得到未向未標(biāo)號點擴散，得到未 標(biāo)號點的臨時標(biāo)號標(biāo)號點的臨時標(biāo)號 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 62 最短路問題的標(biāo)號法最短路問題的

27、標(biāo)號法 上述公式也用于更新臨時標(biāo)號點的臨時標(biāo)號 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 63 最短路問題的標(biāo)號法最短路問題的標(biāo)號法 v步驟步驟3 3：某臨時標(biāo)號點：某臨時標(biāo)號點 的所有可能標(biāo)號的最小的所有可能標(biāo)號的最小 值即是其最終標(biāo)號，此值即是其最終標(biāo)號，此 時將該臨時標(biāo)號點標(biāo)記時將該臨時標(biāo)號點標(biāo)記 為已標(biāo)號點，并記錄其為已標(biāo)號點，并記錄其 前一節(jié)點前一節(jié)點 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 64 最短路問題的標(biāo)號法最短路問題的標(biāo)號法 v步驟步驟4 4：重復(fù)步驟：重復(fù)步驟2 2和和3 3直至找到最直至找到最 短路線，此時得到的最終

28、標(biāo)號即短路線，此時得到的最終標(biāo)號即 為其最短路線的長度為其最短路線的長度 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 65 最短路問題的標(biāo)號法最短路問題的標(biāo)號法 q優(yōu)點：優(yōu)點：DijkstraDijkstra的標(biāo)號的標(biāo)號 法是求解法是求解最短路問題最短路問題 的最優(yōu)化算法，也是的最優(yōu)化算法，也是 目前最好的算法，而目前最好的算法，而 且可以求得起點到各且可以求得起點到各 點的最短路點的最短路 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 66 最短路問題的網(wǎng)絡(luò)規(guī)劃最短路問題的網(wǎng)絡(luò)規(guī)劃 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)

29、院 67 電子表格描述電子表格描述 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 68 最短路問題的假設(shè)最短路問題的假設(shè) 在網(wǎng)絡(luò)中選擇一條路，這條路始于某在網(wǎng)絡(luò)中選擇一條路，這條路始于某 一節(jié)點，這節(jié)點叫作源，終于另一個一節(jié)點，這節(jié)點叫作源，終于另一個 節(jié)點，這個節(jié)點叫作目標(biāo)地節(jié)點，這個節(jié)點叫作目標(biāo)地 連接兩個節(jié)點的連線通常叫作邊連接兩個節(jié)點的連線通常叫作邊允許允許 任一個方向的行進任一個方向的行進，雖然也允許存在，雖然也允許存在 弧弧只允許沿著一個方向行進只允許沿著一個方向行進 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 69 最短路問題的假設(shè)最

30、短路問題的假設(shè) 和每條邊相關(guān)的一個非負(fù)數(shù)，叫作該邊的長度和每條邊相關(guān)的一個非負(fù)數(shù)，叫作該邊的長度 注意：在網(wǎng)絡(luò)中，除了在邊的旁邊表明了其長注意：在網(wǎng)絡(luò)中，除了在邊的旁邊表明了其長 度的準(zhǔn)確數(shù)字以外，所畫的每一條邊的長度并不度的準(zhǔn)確數(shù)字以外，所畫的每一條邊的長度并不 表明其真實的長度表明其真實的長度 目標(biāo)是尋找從源點到目標(biāo)地的最短路線目標(biāo)是尋找從源點到目標(biāo)地的最短路線 總長度總長度 最小的路最小的路 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 70 最短路問題的應(yīng)用最短路問題的應(yīng)用 行進的總距離最小行進的總距離最小 一系列活動的總成本最小一系列活動的總成本最小 一系列活動

31、的總時間最小一系列活動的總時間最小 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 71 總成本最小的例子總成本最小的例子: : 莎拉的汽車基金莎拉的汽車基金 莎拉剛剛高中畢業(yè)莎拉剛剛高中畢業(yè) 在畢業(yè)典禮上，她的父母給了她在畢業(yè)典禮上，她的父母給了她2100021000美美 元的汽車基金幫助她購買并保養(yǎng)一輛使用元的汽車基金幫助她購買并保養(yǎng)一輛使用 了三年的二手車，以供她上大學(xué)使用了三年的二手車，以供她上大學(xué)使用 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 72 總成本最小的例子總成本最小的例子: : 莎拉的汽車基金莎拉的汽車基金 由于開車費用和維修費

32、用隨著汽車的老化 而飛速上漲，所以，如果能夠最小化總的 凈成本，莎拉可能在接下來的三個夏天里， 一次或多次折價將她的汽車置換為其他使 用了三年的二手車。四年后，莎拉的父母 會把她的舊車置換成一輛新車，作為莎拉 的畢業(yè)禮物。 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 73 莎拉的成本數(shù)據(jù)莎拉的成本數(shù)據(jù) Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 74 總成本最小的例子總成本最小的例子: : 莎拉的汽車基金莎拉的汽車基金 在接下來的三個夏天在接下來的三個夏天 里，莎拉應(yīng)該何時折里，莎拉應(yīng)該何時折 價賣掉她的汽車？如價賣掉她的汽車？如 何考慮？如何轉(zhuǎn)

33、換成何考慮？如何轉(zhuǎn)換成 最短路問題？最短路問題？ Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 75 最短路的描述最短路的描述 權(quán)權(quán)= =購買成本購買成本+ +總使用和維護成本總使用和維護成本- -銷售收入銷售收入 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 76 電子表格描述電子表格描述 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 77 總時間最小化的例子總時間最小化的例子: : 奎克公司奎克公司 q 奎克公司獲悉它的一個競爭對手計劃 將把一種很有銷售潛力的新產(chǎn)品投放 市場 q 奎克公司也一直在研制一種類似的產(chǎn) 品，并計劃

34、在20個月后投放市場 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 78 總時間最小化的例子總時間最小化的例子: : 奎克公司奎克公司 q 奎克公司的管理者希望迅速推出產(chǎn)品去參 與競爭 q 現(xiàn)在還有四個階段沒有完成，每個階段都 可以正常水平、優(yōu)先水平和應(yīng)急水平加速 完成。正常水平由于后三個階段的實施速 度太慢而被排除了 q 有3000萬美元用于這四個階段的實施過程 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 79 各階段所需的時間和成本各階段所需的時間和成本 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 80 總時間最小化的例

35、子總時間最小化的例子: : 奎克公司奎克公司 每個階段應(yīng)該以什么每個階段應(yīng)該以什么 樣的速度進行？如何樣的速度進行？如何 考慮？如何轉(zhuǎn)換成最考慮？如何轉(zhuǎn)換成最 短路問題？短路問題？ Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 81 最短路問題的描述最短路問題的描述 虛擬 節(jié)點 節(jié)點節(jié)點: ( : (階段階段, , 剩余資金剩余資金) )；弧；弧: : 活動；權(quán)活動；權(quán): : 時間時間 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 82 電子表格描述電子表格描述 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 83 最優(yōu)解最優(yōu)解

36、Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 84 最小支撐樹最小支撐樹: 摩登公司的問題摩登公司的問題 摩登公司決定鋪設(shè)最先進的光纖網(wǎng)絡(luò)系統(tǒng) 以便在其主要中心之間提供高速通信，包 括數(shù)據(jù)、聲音和視頻等 為了充分利用光纖技術(shù)在中心之間高速通 信的優(yōu)勢，不需要在每兩個中心之間都用 一條光纜把它們直接連接起來，那些需要 光纜直接連接的中心有一系列的光纜連接 它們 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 85 摩登公司主要中心、纖維光纜的可能布局及成本摩登公司主要中心、纖維光纜的可能布局及成本 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商

37、大學(xué)商學(xué)院 86 應(yīng)該鋪設(shè)哪些光纖以應(yīng)該鋪設(shè)哪些光纖以 便在每兩個中心之間便在每兩個中心之間 提供高速通信？提供高速通信？ 最小支撐樹最小支撐樹: 摩登公司的問題摩登公司的問題 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 87 最小支撐樹的假設(shè)最小支撐樹的假設(shè) 給你網(wǎng)絡(luò)中的節(jié)點，但沒有給你邊?；蛘?，給 你可供選擇的邊和如果把它插入到網(wǎng)絡(luò)中后的 每條邊的正的成本或者相似的度量 在設(shè)計網(wǎng)絡(luò)時你希望通過插入足夠的邊，以滿 足每兩個節(jié)點之間都存在一條路的需要 目標(biāo)是尋找一種方法，使得在滿足要求的同時 總成本最小 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院

38、 88 最小支撐樹的算法最小支撐樹的算法 選擇第一條邊：選擇成本最低的備選邊選擇第一條邊：選擇成本最低的備選邊 選擇下一條邊：在一個已經(jīng)有一條邊連選擇下一條邊：在一個已經(jīng)有一條邊連 接的節(jié)點和另一個還沒有邊連接的節(jié)點接的節(jié)點和另一個還沒有邊連接的節(jié)點 之間選擇成本最低的備選邊之間選擇成本最低的備選邊 重復(fù)第二個步驟，直到所有的節(jié)點都重復(fù)第二個步驟，直到所有的節(jié)點都 有一條邊有一條邊 可能會有多于一條邊可能會有多于一條邊 與其與其 相連。此時就得到了最優(yōu)解相連。此時就得到了最優(yōu)解 最小支撐最小支撐 樹樹) ) 當(dāng)有幾條邊同時是成本最低的邊時，當(dāng)有幾條邊同時是成本最低的邊時， 任意選擇一條邊不會影

39、響最后的最優(yōu)任意選擇一條邊不會影響最后的最優(yōu) 值值 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 89 摩登公司的算法應(yīng)用摩登公司的算法應(yīng)用: 第一步第一步 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 90 摩登公司的算法應(yīng)用摩登公司的算法應(yīng)用: 第二步第二步 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 91 摩登公司的算法應(yīng)用摩登公司的算法應(yīng)用: 第三步第三步 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 92 摩登公司的算法應(yīng)用摩登公司的算法應(yīng)用: 第四步第四步 Copyright 2011 北京工

40、商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 93 摩登公司的算法應(yīng)用摩登公司的算法應(yīng)用: 第五步第五步 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 94 摩登公司的算法應(yīng)用摩登公司的算法應(yīng)用: 最后一步最后一步 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 95 最優(yōu)解最優(yōu)解 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 96 最小支撐樹問題最小支撐樹問題 避圈法：開始選一條最小權(quán)避圈法：開始選一條最小權(quán) 的邊，以后每一步中，總從的邊，以后每一步中，總從 未被選取的邊中選一條權(quán)最未被選取的邊中選一條權(quán)最 小的邊，并使之與已被選取小的邊，并

41、使之與已被選取 的邊不構(gòu)成圈的邊不構(gòu)成圈( (如果有兩條或如果有兩條或 兩條以上的邊都是權(quán)最小的兩條以上的邊都是權(quán)最小的 邊，則從中任選一條邊，則從中任選一條) ) Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 97 最小支撐樹問題最小支撐樹問題 q算例 A B C D E F G H I 6 3 1 2 2 1 6 10 4 2 6 3 2 4 3 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 98 最小支撐樹問題最小支撐樹問題 破圈法：任取一個圈，從圈破圈法：任取一個圈，從圈 中去掉權(quán)最大的邊中去掉權(quán)最大的邊( (如果有兩如果有兩 條或兩條以上的

42、邊都是權(quán)最條或兩條以上的邊都是權(quán)最 大的邊，則任意去掉其中一大的邊，則任意去掉其中一 條條) )。在余下的圖中，重復(fù)這。在余下的圖中，重復(fù)這 個步驟，一直到圖中不含圈個步驟，一直到圖中不含圈 為止。去邊的同時必須保證為止。去邊的同時必須保證 圖的連通性圖的連通性 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 99 最小支撐樹問題最小支撐樹問題 q算例 A B C D E F G H I 6 3 1 2 2 1 6 10 4 2 6 3 2 4 3 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 100 最小支撐樹的應(yīng)用最小支撐樹的應(yīng)用 電信網(wǎng)絡(luò)電信網(wǎng)絡(luò)

43、計算機網(wǎng)絡(luò)、電話專用線計算機網(wǎng)絡(luò)、電話專用線 網(wǎng)絡(luò)、有線電視網(wǎng)絡(luò)等等網(wǎng)絡(luò)、有線電視網(wǎng)絡(luò)等等的設(shè)計的設(shè)計 低負(fù)荷運輸網(wǎng)絡(luò)的設(shè)計，使得網(wǎng)絡(luò)低負(fù)荷運輸網(wǎng)絡(luò)的設(shè)計，使得網(wǎng)絡(luò) 中提供鏈接的部分中提供鏈接的部分如鐵路、公路等如鐵路、公路等 的總成本最小的總成本最小 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 101 最小支撐樹的應(yīng)用最小支撐樹的應(yīng)用 高壓輸電線路網(wǎng)絡(luò)的設(shè)計高壓輸電線路網(wǎng)絡(luò)的設(shè)計 連接多個場所的管道網(wǎng)絡(luò)設(shè)計連接多個場所的管道網(wǎng)絡(luò)設(shè)計 電器設(shè)備線路網(wǎng)絡(luò)電器設(shè)備線路網(wǎng)絡(luò)如數(shù)字計算機如數(shù)字計算機 系統(tǒng)系統(tǒng)的設(shè)計，使得線路總長度最的設(shè)計，使得線路總長度最 短短 Copyright 2011 北京工商大學(xué)商學(xué)院北京工商大學(xué)商學(xué)院 102 規(guī)劃問題總結(jié)規(guī)劃問題總結(jié) q線性規(guī)劃線性規(guī)劃 v資源分配問題資源分配問題 v成本收益平衡問題成本收益平衡問題 v網(wǎng)絡(luò)配送問題：運輸問題，指網(wǎng)絡(luò)配