數(shù)學(xué)建模網(wǎng)絡(luò)優(yōu)化

數(shù)學(xué)建模網(wǎng)絡(luò)優(yōu)化第一頁，共四十二頁，2022年，8月28日1OutlineWhatisNetworkOptimization?TypicalModels&AlgorithmsMinimumSpanningTree(最小(生成)樹)MinimumArborescence(最小樹形圖)ShortestPath(最短路)MaximumFlow(最大流)MinimumCostFlow(最小費(fèi)用流)Matching(匹配)……SomeModelingExamples第二頁，共四十二頁，2022年，8月28日2網(wǎng)

絡(luò)

優(yōu)

化

簡(jiǎn)介網(wǎng)絡(luò)：網(wǎng)絡(luò)社會(huì)----計(jì)算機(jī)信息網(wǎng)絡(luò)？電話通信網(wǎng)絡(luò)運(yùn)輸服務(wù)網(wǎng)絡(luò)能源和物質(zhì)分派網(wǎng)絡(luò)

人際關(guān)系網(wǎng)絡(luò)等等網(wǎng)絡(luò)優(yōu)化就是研究如何有效地計(jì)劃、管理和控制網(wǎng)絡(luò)系統(tǒng)，使之發(fā)揮最大的社會(huì)和經(jīng)濟(jì)效益第三頁，共四十二頁，2022年，8月28日3網(wǎng)

絡(luò)

優(yōu)

化

簡(jiǎn)介網(wǎng)絡(luò)(Network)：數(shù)學(xué)模型、數(shù)學(xué)結(jié)構(gòu)----圖優(yōu)化(Optimization):從若干可能的方案中尋求某種意義下的最優(yōu)方案與圖論有聯(lián)系，也有區(qū)別（側(cè)重點(diǎn)不同）網(wǎng)絡(luò)優(yōu)化就是研究與（賦權(quán)）圖有關(guān)的最優(yōu)化問題圖論：圖的性質(zhì)網(wǎng)絡(luò)優(yōu)化：與（賦權(quán)）圖有關(guān)的優(yōu)化問題組合數(shù)學(xué)組合優(yōu)化第四頁，共四十二頁，2022年，8月28日4OptimizationTree

第五頁，共四十二頁，2022年，8月28日5網(wǎng)

絡(luò)

優(yōu)

化

簡(jiǎn)介主要參考書：

謝金星、邢文訓(xùn)，《網(wǎng)絡(luò)優(yōu)化》，清華大學(xué)出版社，2000年8月；2003年9月。Ahuja,R.K.,MagnantiT.L.,OrlinJ.B.NetworkFlows:Theory,Algorithms,andApplications.PrenticeHall,1993:EnglewoodCliffs,NewJersey.網(wǎng)絡(luò)優(yōu)化模型網(wǎng)絡(luò)優(yōu)化算法及其復(fù)雜性《網(wǎng)絡(luò)優(yōu)化》或《網(wǎng)絡(luò)流》（NetworkFlows)或《網(wǎng)絡(luò)規(guī)劃》（NetworkProgramming)第六頁，共四十二頁，2022年，8月28日6圖與網(wǎng)絡(luò)–基本概念圖G=(V，A)，其中頂點(diǎn)集V=

弧集A=弧第七頁，共四十二頁，2022年，8月28日7例：公路連接問題某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市.假定已經(jīng)知道了任意兩個(gè)城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最小？

網(wǎng)絡(luò)優(yōu)化問題的例子

1132546385247最小(生成)樹也稱為最小(支撐)樹第八頁，共四十二頁，2022年，8月28日8例：二維矩陣數(shù)據(jù)存貯問題某些蛋白質(zhì)的氨基酸序列差異不多，如果用二維矩陣的每一行記錄一種蛋白質(zhì)氨基酸序列，行與行之間的差異很小.其中一種方法是只存貯其中一行作為參照行，再存貯行與行之間的一部分差異信息，使得我們可以在需要時(shí)根據(jù)參照行生成所有其它行的元素.R1R3R2R4C13C12C24最小樹網(wǎng)絡(luò)優(yōu)化問題的例子

第九頁，共四十二頁，2022年，8月28日9“直接方式”：總經(jīng)理直接傳達(dá)；“接力方式”：總經(jīng)理只給某些部門經(jīng)理打電話，而讓這些得到信息的部門經(jīng)理打電話將信息進(jìn)一步傳達(dá)給其他某些部門經(jīng)理，依此類推，最后將信息傳達(dá)到所有部門經(jīng)理.如何決定傳達(dá)信息的途徑？信息傳播是有向的，有一個(gè)“根”。信息傳播途徑（忽略方向時(shí)）是一棵樹。以上結(jié)構(gòu)稱為樹形圖，上面這樣一類問題稱為最小樹形圖問題.例：信息傳播最小樹形圖–例第十頁，共四十二頁，2022年，8月28日10例最短路問題（SPP-ShortestPathProblem）一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地.從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路.網(wǎng)絡(luò)優(yōu)化問題的例子

AF566744513BEDC第十一頁，共四十二頁，2022年，8月28日11例：計(jì)劃評(píng)審技術(shù),即PERT(ProjectEvaluation&ReviewTechnique),又稱網(wǎng)絡(luò)計(jì)劃技術(shù)或統(tǒng)籌法)大型復(fù)雜工程項(xiàng)目(Project)往往被分成許多子項(xiàng)目,子項(xiàng)目之間有一定的先后順序(偏序)要求,每一子項(xiàng)目需要一定的時(shí)間完成.PERT網(wǎng)絡(luò)的每條弧表示一個(gè)子項(xiàng)目,如果以弧長(zhǎng)表示每一子項(xiàng)目需要的時(shí)間,則最早完工時(shí)間對(duì)應(yīng)于網(wǎng)絡(luò)中的最長(zhǎng)路(關(guān)鍵路線).工程上所謂的關(guān)鍵路線法(CPM:CriticalPathMethod)基本上也是計(jì)劃評(píng)審技術(shù)的一部分.項(xiàng)目網(wǎng)絡(luò)不含圈（其最長(zhǎng)路問題和最短路問題都是可解的）(開始)AF(結(jié)束)566744513B

EDC第十二頁，共四十二頁，2022年，8月28日12例：最大流/最小費(fèi)用流從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，每天每條路上的通車量有上限.從甲地到乙地的每天最多能通車多少輛?考慮每條路上的通行成本,如何確定某個(gè)車隊(duì)的具體行車路線,使總成本最小?(甲)AF(乙)566744513B

EDC第十三頁，共四十二頁，2022年，8月28日13例：

運(yùn)輸問題(TransportationProblem)某種原材料有M個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往N個(gè)使用這些原材料的工廠.假定M個(gè)產(chǎn)地的產(chǎn)量和N家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？

網(wǎng)絡(luò)優(yōu)化問題的例子

ST特殊的最小費(fèi)用流問題（二部圖,|S|=M,|T|=N）第十四頁，共四十二頁，2022年，8月28日14例：指派問題(AssignmentProblem)一家公司經(jīng)理準(zhǔn)備安排N名員工去完成N項(xiàng)任務(wù)，每人一項(xiàng).由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的.如何分配工作方案可以使總回報(bào)最大？網(wǎng)絡(luò)優(yōu)化問題的例子

ST特殊的最小費(fèi)用流問題（二部圖，|S|=|T|=N）第十五頁，共四十二頁，2022年，8月28日15最小費(fèi)用流模型的特例及擴(kuò)展

最小費(fèi)用流問題指派問題運(yùn)輸問題最大流問題最短路問題帶增益的最小費(fèi)用流問題線性規(guī)劃問題凹費(fèi)用網(wǎng)絡(luò)的最小費(fèi)用流問題凸費(fèi)用網(wǎng)絡(luò)的最小費(fèi)用流問題狹義模型

廣義模型凸規(guī)劃第十六頁，共四十二頁，2022年，8月28日16例：匹配問題(MatchingProblem)在一次有m個(gè)大學(xué)畢業(yè)生和n家公司參加的供需見面會(huì)上，每個(gè)畢業(yè)生愿意加入到若干家公司中的一家工作，而每個(gè)公司愿意接收若干畢業(yè)生中的一人到公司工作.那么，最后最多有多少人可以在這次供需見面會(huì)上找到工作（即最多有多少家公司可以在這次供需見面會(huì)上招聘到員工）？如果每個(gè)畢業(yè)生到每一家公司工作將會(huì)產(chǎn)生的效益不同，那么，為了使得最后產(chǎn)生的總效益最大，最多有多少人可以在這次供需見面會(huì)上找到工作？網(wǎng)絡(luò)優(yōu)化問題的例子

二部基數(shù)/賦權(quán)匹配第十七頁，共四十二頁，2022年，8月28日17破圈法-----復(fù)雜度高避圈法----貪婪算法(GreedyAlgorithm)Kruskal算法（1956）Prim算法（1957）：即“邊割法”Dijkstra算法（1959）Sollin算法（1961）最?。ㄉ桑渌惴ǖ谑隧摚菜氖?，2022年，8月28日18最小樹形圖算法：

朱(永津)-劉(振宏)算法（1965）最大分枝算法：

Edmons算法（1968）基本思想：收縮–展開第十九頁，共四十二頁，2022年，8月28日19無圈網(wǎng)絡(luò)：拓?fù)渑判?動(dòng)態(tài)規(guī)劃圈的檢測(cè)正費(fèi)用網(wǎng)絡(luò)：Dijkstra算法（1959）一般網(wǎng)絡(luò)，單一起點(diǎn)（或終點(diǎn)）Bellman-Ford算法(1956)：

O(mn)一般網(wǎng)絡(luò)，所有點(diǎn)對(duì)Floyd-Warshall算法(1962)：

O(n3)負(fù)圈檢測(cè)最短路算法：標(biāo)號(hào)設(shè)定/修正算法第二十頁，共四十二頁，2022年，8月28日20增廣路算法Ford-Fulkerson標(biāo)號(hào)算法(1956)最大容量增廣路算法容量變尺度算法最短增廣路算法：O(n2m)預(yù)流推進(jìn)算法最高標(biāo)號(hào)預(yù)流推進(jìn)算法：O(n2m1/2)最大流算法實(shí)際計(jì)算效率高第二十一頁，共四十二頁，2022年，8月28日21消圈算法最小費(fèi)用路算法原始-對(duì)偶算法Ford和Forkerson(1957,1962)瑕疵算法(Out-Of-KilterAlgorithm)松弛(Relaxation)算法網(wǎng)絡(luò)單純形算法最小費(fèi)用流算法實(shí)際計(jì)算效率高第二十二頁，共四十二頁，2022年，8月28日22二部基數(shù)匹配增廣路算法：O(mn)簡(jiǎn)單網(wǎng)絡(luò)上的最大流算法：O(mn1/2)一般基數(shù)匹配“花”算法:O(n3)二部賦權(quán)匹配（指派問題）最小費(fèi)用流算法（如匈牙利算法）:O(n3)一般賦權(quán)匹配原始-對(duì)偶算法:O(n3)匹配算法第二十三頁，共四十二頁，2022年，8月28日23網(wǎng)絡(luò)優(yōu)化的評(píng)注許多實(shí)際問題可以直接用網(wǎng)絡(luò)優(yōu)化建模許多實(shí)際問題可能用到網(wǎng)絡(luò)優(yōu)化建模許多實(shí)際問題是網(wǎng)絡(luò)優(yōu)化的變種網(wǎng)絡(luò)優(yōu)化問題通常可以用整數(shù)規(guī)劃建模第二十四頁，共四十二頁，2022年，8月28日24西氣東送（鋼管運(yùn)輸）問題

（CUMCM-2000B)A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7鐵路運(yùn)價(jià)表里程≤300301～350351～400401～450451～500…運(yùn)價(jià)2023262932…第二十五頁，共四十二頁，2022年，8月28日25西氣東送（鋼管運(yùn)輸）問題

（CUMCM-2000B)二次規(guī)劃（常用解法）最小費(fèi)用流問題？（清華大學(xué)隊(duì)，獲網(wǎng)易杯）線性模型（網(wǎng)絡(luò)規(guī)模較大，有現(xiàn)成算法）非線性模型（網(wǎng)絡(luò)規(guī)模較小，需要自己設(shè)計(jì)算法）基本問題----最小運(yùn)費(fèi)矩陣的計(jì)算兩種運(yùn)輸方式（鐵路／公路）混合最短路問題是普通最短路問題的變種，需要自己設(shè)計(jì)算法第二十六頁，共四十二頁，2022年，8月28日26鐵路／公路混合運(yùn)輸最短路問題最小運(yùn)費(fèi)矩陣算法（四川大學(xué)/清華大學(xué)等隊(duì)）Dijkstra算法或Floyd-Warshall算法鐵路最短路問題最短路==〉鐵路最小運(yùn)費(fèi)矩陣公路最短路問題最短路==〉公路最小運(yùn)費(fèi)矩陣鐵路/公路混合運(yùn)輸最短路問題鐵路/公路混合運(yùn)輸網(wǎng)絡(luò)最短路==〉鐵路/公路混合運(yùn)輸最小運(yùn)費(fèi)矩陣第二十七頁，共四十二頁，2022年，8月28日27例：中國郵遞員問題(CPP-ChinesePostmanProblem)一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件.如何設(shè)計(jì)一條最短的投遞路線(從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局)？由于這一問題是我國學(xué)者管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題.網(wǎng)絡(luò)優(yōu)化問題的其他例子

單向？雙向？風(fēng)向？第二十八頁，共四十二頁，2022年，8月28日28例：旅行商問題(TSP-TravelingSalesmanProblem)一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品.如何為他(她)設(shè)計(jì)一條最短的旅行路線(從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地)？這一問題的研究歷史十分悠久，通常稱之為旅行商問題.

網(wǎng)絡(luò)優(yōu)化問題的例子

BACDEFGHI第二十九頁，共四十二頁，2022年，8月28日29災(zāi)情巡視路線(CUMCM-1998B)多人TSP問題的擴(kuò)展第三十頁，共四十二頁，2022年，8月28日30例：套匯（Arbitrage）問題 在外匯市場(chǎng)上，將1單位的某種貨幣通過多次兌換，獲得多于1單位的同種貨幣，稱為套匯。如：1單位的A貨幣＝(兌換)46.4單位B貨幣1單位的B貨幣＝(兌換)2.5單位C貨幣1單位的C貨幣＝(兌換)0.0091單位A貨幣則:1單位的A貨幣＝(通過三次兌換獲得)46.4＊2.5＊0.0091=1.0556單位A貨幣網(wǎng)絡(luò)優(yōu)化問題的例子

可以變成檢測(cè)負(fù)圈的問題 現(xiàn)在假設(shè)給定了若干種貨幣及其兩兩之間的兌換率，請(qǐng)你幫助找到一種套匯方式（或判定該外匯市場(chǎng)上不存在套匯的可能）。第三十一頁，共四十二頁，2022年，8月28日31套匯:46.4＊2.5＊0.0091=1.0556>1兩邊取倒數(shù)(乘積<1)，再取對(duì)數(shù)（求和<0）可以變成檢測(cè)負(fù)圈的問題套匯（Arbitrage）問題化乘積為求和的技術(shù)，也常用于“可靠性問題”可能是完全有向圖；弧上的權(quán)就是匯率的倒數(shù)的對(duì)數(shù)值！第三十二頁，共四十二頁，2022年，8月28日32例：逃生路線問題n*n網(wǎng)格節(jié)點(diǎn)上有m個(gè)房間，逃到邊上節(jié)點(diǎn)就算逃生成功如何規(guī)劃逃生路線，使這些路線互不相交？網(wǎng)絡(luò)優(yōu)化問題的例子

可以變成最大流問題逃生成功沒有逃生路線第三十三頁，共四十二頁，2022年，8月28日33m個(gè)房間是供應(yīng)節(jié)點(diǎn)（源，供應(yīng)量為１）只有邊上節(jié)點(diǎn)可以是吸收節(jié)點(diǎn)（匯，吸收量為１）多源多匯，容易變成單源單匯每條邊容量為１每個(gè)節(jié)點(diǎn)容量為１（通過增加節(jié)點(diǎn)和邊，變成邊容量）逃生路線問題變成最大流問題逃生成功沒有逃生路線其他目標(biāo)？第三十四頁，共四十二頁，2022年，8月28日34例：空間實(shí)驗(yàn)問題某航天公司計(jì)劃進(jìn)行一次空間載人飛行，宇航員將在飛行中進(jìn)行一系列科學(xué)實(shí)驗(yàn)。目前該公司收到了多個(gè)不同的科學(xué)實(shí)驗(yàn)申請(qǐng)，完成每個(gè)實(shí)驗(yàn)要求攜帶相應(yīng)的一種或多種儀器設(shè)備（不同的實(shí)驗(yàn)所需要的儀器設(shè)備中有些可能是相同的，而另外有些可能是不同的）。已知完成每個(gè)實(shí)驗(yàn)后公司所得到的相應(yīng)報(bào)酬（不同實(shí)驗(yàn)的報(bào)酬可能不同），并已知飛行器攜帶每種儀器設(shè)備的相應(yīng)費(fèi)用（不同儀器設(shè)備的費(fèi)用可能不同）。公司希望你幫助選定此次飛行究竟從事哪些科學(xué)實(shí)驗(yàn)，以及需要攜帶哪些儀器設(shè)備，使此次飛行的總利潤最大（總利潤=總報(bào)酬－總費(fèi)用）。

網(wǎng)絡(luò)優(yōu)化問題的例子

可以變成最大流問題第三十五頁，共四十二頁，2022年，8月28日35空間實(shí)驗(yàn)問題最大流(最小割)問題設(shè)備實(shí)驗(yàn)n個(gè)實(shí)驗(yàn)(報(bào)酬pi)m類設(shè)備(成本ci)12…m12…ncipist計(jì)劃有限割有限割的容量：ST第三十六頁，共四十二頁，2022年，8月28日36例:學(xué)生分區(qū)問題假設(shè)某個(gè)城市分為L(zhǎng)個(gè)區(qū),每個(gè)區(qū)有若干男孩和若干女孩需要上學(xué).假設(shè)每個(gè)區(qū)有一所小學(xué),每所小學(xué)所能容納的學(xué)生總數(shù)已知,并且按照規(guī)定,每所小學(xué)所能容納的男孩和女孩比例不能太大或太小.假設(shè)每?jī)蓚€(gè)區(qū)之間的路程已知(同一區(qū)內(nèi)認(rèn)為路程近似為0),如何為需要上學(xué)的小孩分配學(xué)校,使得所有小孩上學(xué)所走的總路程最少?網(wǎng)絡(luò)優(yōu)化問題的例子

可以變成最小費(fèi)用流的問題第三十七頁，共四十二頁，2022年，8月28日37L=2為例：bi

男孩；gi

女孩；ui

學(xué)校容量(p,q)男孩比例上下限；dij距離學(xué)生分區(qū)問題最小費(fèi)用流問題b1b2g1g2(0,u1)(0,u2)t容量d11d12d21d22d11d12d21d22(pu1,qu1)(pu2,qu2)費(fèi)用為０第三十八頁，共四十二頁，2022年，8月28日38例:一類排序(Scheduling)問題某車間接受了p項(xiàng)不同的加工任務(wù)，要求在車間的q臺(tái)完全相同的機(jī)器上加工每項(xiàng)任務(wù)所需要的加工時(shí)間是相同的，且只需要在其中的任何一臺(tái)機(jī)器上加工完成即可每項(xiàng)任務(wù)在同一時(shí)刻不能在兩個(gè)或兩個(gè)以上的機(jī)器上加工，且每項(xiàng)任務(wù)的加