第六七次-session5網(wǎng)絡(luò)最優(yōu)化問題

Data,ModelandDecisions數(shù)據(jù)、模型與決策Session5NetworkOptimizationProblems網(wǎng)絡(luò)最優(yōu)化問題SessionTopicsPhillipsPetroleumVehicleReplacementPlanning

飛利浦石油公司運輸工具替換計劃

ApplicationsofNetworkOptimization

網(wǎng)絡(luò)最優(yōu)化模型的應(yīng)用TypesofNetworkOptimizationProblem

網(wǎng)絡(luò)最優(yōu)化問題類型

MinimumCostNetworkFlowModel

最小費用流問題SessionTopicsMaximumFlowProblems

最大流問題

ShortestPathProblem

最短路問題

MinimumSpanningTreeProblem

最小支撐樹問題飛利浦石油（PhillipsPetroleum）應(yīng)用最短路問題模型對各種高速公路運輸車、卡車和貨車運輸路線的優(yōu)化來降低成本提高競爭力PlanningVehicleReplacementatPhillipsPetroleum飛利浦石油的運輸工具替換計劃經(jīng)典應(yīng)用Waddell(1983)Jul-AugInterfacesarticle,“AModelforEquipmentReplacementDecisionsandPolicies”

有1500輛卡車和3800輛貨車用最短路模型建立替換戰(zhàn)略(20年時間跨度)每次為每一類運輸工具求解模型考慮成本有維護(hù)和運營成本、租賃成本、購買成本、

政府授權(quán)費用路稅和其他稅收（投資稅、折舊）開始做lease-or-buy決策，然后做替換戰(zhàn)略，目前擴(kuò)展到了其他的設(shè)備（非運輸工具）PlanningVehicleReplacementatPhillipsPetroleum飛利浦石油的運輸工具替換計劃經(jīng)典應(yīng)用ApplicationsofNetworkOptimization網(wǎng)絡(luò)最優(yōu)化模型的應(yīng)用網(wǎng)絡(luò)在交通、電子和通訊網(wǎng)絡(luò)遍及我們?nèi)粘Ｉ畹母鱾€方面，網(wǎng)絡(luò)規(guī)劃也廣泛用于解決不同領(lǐng)域中的各種問題，如生產(chǎn)、分配、項目計劃、廠址選擇、資源管理和財務(wù)策劃等等。網(wǎng)絡(luò)規(guī)劃為描述系統(tǒng)各組成部分之間的關(guān)系提供了非常有效直觀和概念上的幫助，廣泛應(yīng)用于科學(xué)、社會和經(jīng)濟(jì)活動的每個領(lǐng)域中Networkrepresentation網(wǎng)絡(luò)表述這種描述還有其他應(yīng)用嗎？想想看！TypesofNetworkOptimizationProblem網(wǎng)絡(luò)最優(yōu)化問題類型MinimumCostNetworkFlowModel

最小費用流問題

MaximumFlowProblems

最大流問題

ShortestPathProblem

最短路問題

MinimumSpanningTreeProblem

最小支撐樹問題

MinimumCostNetworkFlowModel最小費用流問題最小費用流問題的構(gòu)成：節(jié)點(nodes)（供應(yīng)點、需求點、轉(zhuǎn)運點）弧（arcs）

目標(biāo):通過網(wǎng)絡(luò)滿足需求提供供應(yīng)， 最小化流的總成本AssumptionsofMinimumCostNetworkFlow最小費用流問題的假設(shè)至少一個供應(yīng)點一個需求點剩下都是轉(zhuǎn)運點

通過弧的流只允許沿著箭頭方向流動，通過弧的 最大流量取決于該弧的容量

網(wǎng)絡(luò)中有足夠的弧提供足夠容量，使得所有在供 應(yīng)點中產(chǎn)生的流都能夠到達(dá)需求點

在流的單位成本已知前提下，通過每一條弧的流 的成本和流量成正比

CharacteristicofSolution解的特征具有可行解的特征：在以上的假設(shè)下，當(dāng)且僅當(dāng)供應(yīng)點所提供的流量總和等于需求點所需要的流量總和時，最小費用流問題有可行解具有整數(shù)解的特征：只要其所有的供應(yīng)、需求和弧的容量都是整數(shù)值，那么任何最小費用流問題的可行解就一定有所有流量都是整數(shù)的最優(yōu)解DistributionUnlimitedCo.無限配送公司無限配送公司的最小成本流問題的電子表格模型

實際舉例NetworkSimplexMethod網(wǎng)絡(luò)單純形法實際運用中解決比較大型問題時需要用不同的方法網(wǎng)絡(luò)單純形法可以用來解決那些對于單純形法來說太大而無法解決的大型問題

ExcelSolver軟件中沒有網(wǎng)絡(luò)單純形法，但是其他的線性規(guī)劃的商業(yè)軟件包通常都有這種方法

SomeApplications一些實際應(yīng)用國際紙業(yè)公司（InternationalPaperCompany）配送網(wǎng)絡(luò)（Interfaces

1988年3/4）世界上最大的紙漿、紙和紙類產(chǎn)品的制造商以及木材和夾板的主要生產(chǎn)者。擁有兩千萬英畝的林區(qū)或其權(quán)益。分布在不同地方的林區(qū)是它配送網(wǎng)絡(luò)的供應(yīng)點,供應(yīng)流必須經(jīng)過一系列很長的轉(zhuǎn)運點： 林區(qū)→木材堆積場→鋸木廠→造紙廠 →紙制品加工廠→倉庫→客戶

實務(wù)經(jīng)典SomeApplications一些實際應(yīng)用馬爾薩斯公司（Marshalls,Inc.）配送網(wǎng)絡(luò)（Interfaces

1987年7/8）一家折扣連鎖零售店，現(xiàn)在和以前是如何使用微型計算機(jī)去處理一個最小費用流問題。應(yīng)用中公司力圖使得從供應(yīng)商到加工中心，再從加工中心到零售店的商流最優(yōu)。其中的一些網(wǎng)絡(luò)有超過20,000條弧。實務(wù)經(jīng)典MaximumFlowProblems最大流問題最大流問題也與網(wǎng)絡(luò)中的流有關(guān)，但目標(biāo)不是使得流的成本最小化，而是尋找一個流的方案，使得通過網(wǎng)絡(luò)的流量最大這種問題有哪些應(yīng)用呢？想想看！BMZCaseStudyBMZ案例研究BMZ從德國斯圖加特工廠到洛杉磯配送中心的配送網(wǎng)絡(luò)案例研究BMZCaseStudyBMZ案例研究BMZ案例的網(wǎng)絡(luò)描述案例研究BMZCaseStudyBMZ案例研究BMZ案例求解案例研究AssumptionsofMaximumFlowProblems最大流問題的假設(shè)

網(wǎng)絡(luò)中所有流起源于一個叫做源的節(jié)點所有的流終止于一個叫做收點的節(jié)點其余所有的節(jié)點叫做轉(zhuǎn)運點通過每一個弧的流只允許沿著弧的箭頭方向流動目標(biāo)是使得從源到收點的總流量最大ShortestPathProblem最短路問題最短路問題的最普遍的應(yīng)用在兩個點之間尋找最短路這種問題有哪些應(yīng)用呢？LittletownFireStation里特城消防站實際舉例里特城的消防站和某一農(nóng)場社區(qū)間的道路系統(tǒng)LittletownFireStation里特城消防站實際舉例里特城的消防站道路系統(tǒng)的網(wǎng)絡(luò)表述LittletownFireStation里特城消防站實際舉例AssumptionsofshortestPathProblem最短路問題的假設(shè)

網(wǎng)絡(luò)中選擇一條路,始于某源點終于目標(biāo)地連接兩個節(jié)點的連線叫做邊（允許任一個方向行進(jìn)），?。ㄖ辉试S沿著一個方向行進(jìn)）和每條邊相關(guān)的一個非負(fù)數(shù)，叫做該邊的長度目標(biāo)是為了尋找從源到目標(biāo)地的最短路MinimumSpanningTreeProblem最小支撐樹問題給你網(wǎng)絡(luò)中的節(jié)點，但沒有給你邊。或者，給你可供選擇的邊和如果把它插入到網(wǎng)絡(luò)中后的每條邊的正的成本（或者相似的度量）在設(shè)計網(wǎng)絡(luò)時你希望通過插入足夠的邊，以滿足每兩個節(jié)點之間都存在一條路的需要目標(biāo)是尋找一種方法，使得在滿足要求的同時總成本最小TheSimpleAlgorithm簡單的算法選擇第一條邊：選擇成本最低的備選邊選擇下一條邊：在一個已經(jīng)有一條邊連接的節(jié)點和另一個還沒有邊連接的節(jié)點之間選擇成本最低的備選邊重復(fù)第二個步驟，直到所有的節(jié)點都有一條邊（可能會有多于一條邊）與其相連此時就得到了最優(yōu)解（最小支撐樹）SomeApplications一些實際應(yīng)用

電信網(wǎng)絡(luò)（計算機(jī)網(wǎng)絡(luò)、電話專用線網(wǎng)絡(luò)、有線電視網(wǎng)絡(luò)等等）的設(shè)計低負(fù)荷運輸網(wǎng)絡(luò)的設(shè)計，使得網(wǎng)絡(luò)中提供鏈接的部分（如鐵路、公路等等）的總成本最小高壓輸電線路網(wǎng)絡(luò)的設(shè)計電器設(shè)備線路網(wǎng)絡(luò)（如數(shù)字計算機(jī)系統(tǒng)）的設(shè)計，使得線路總長度最短連接多個場所的管道網(wǎng)絡(luò)設(shè)計實務(wù)應(yīng)用SessionSummary本講小結(jié)小結(jié)網(wǎng)絡(luò)表示在描繪網(wǎng)絡(luò)系統(tǒng)中各部分之間關(guān)聯(lián)上非常有用最小費用流問題的特殊類型包括運輸問題和指派問題最大流問題的目標(biāo)是使得從一個特定的起點（源）到一個特定的終點（收點）的總流量最大最短路問題也有始點（源）和終點（目標(biāo)地），但是，它的目標(biāo)是從源點到目標(biāo)地尋找一條總長度最短的路最小支撐樹問題的目標(biāo)是使得為任意