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

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

飛利浦石油公司運(yùn)輸工具替換計(jì)劃

ApplicationsofNetworkOptimization

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

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

MinimumCostNetworkFlowModel

最小費(fèi)用流問題SessionTopicsMaximumFlowProblems

最大流問題

ShortestPathProblem

最短路問題

MinimumSpanningTreeProblem

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

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

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

最小費(fèi)用流問題

MaximumFlowProblems

最大流問題

ShortestPathProblem

最短路問題

MinimumSpanningTreeProblem

最小支撐樹問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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