網(wǎng)

絡(luò)

優(yōu)

化模型與算法NetworkOptimization:Models&Algorithms

Email:2004年7月~8月----江西廬山1OutlineWhatisNetworkOptimization?TypicalModels&AlgorithmsMinimumSpanningTree(最小(生成)樹)MinimumArborescence(最小樹形圖)ShortestPath(最短路)MaximumFlow(最大流)MinimumCostFlow(最小費用流)Matching(匹配)……SomeModelingExamples2網(wǎng)

絡(luò)

優(yōu)

化

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

人際關(guān)系網(wǎng)絡(luò)等等網(wǎng)絡(luò)優(yōu)化就是研究如何有效地計劃、管理和控制網(wǎng)絡(luò)系統(tǒng)，使之發(fā)揮最大的社會和經(jīng)濟效益3OptimizationTree

5網(wǎng)

絡(luò)

優(yōu)

化

簡介主要參考書：

謝金星、邢文訓(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)6圖與網(wǎng)絡(luò)–基本概念圖G=(V，A)，其中頂點集V=

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

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

AF566744513BEDC11例：最大流/最小費用流從甲地到乙地的公路網(wǎng)縱橫交錯，每天每條路上的通車量有上限.從甲地到乙地的每天最多能通車多少輛?考慮每條路上的通行成本,如何確定某個車隊的具體行車路線,使總成本最小?(甲)AF(乙)566744513B

EDC13例：

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

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

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

ST特殊的最小費用流問題（二部圖，|S|=|T|=N）15例：匹配問題(MatchingProblem)在一次有m個大學(xué)畢業(yè)生和n家公司參加的供需見面會上，每個畢業(yè)生愿意加入到若干家公司中的一家工作，而每個公司愿意接收若干畢業(yè)生中的一人到公司工作.那么，最后最多有多少人可以在這次供需見面會上找到工作（即最多有多少家公司可以在這次供需見面會上招聘到員工）？如果每個畢業(yè)生到每一家公司工作將會產(chǎn)生的效益不同，那么，為了使得最后產(chǎn)生的總效益最大，最多有多少人可以在這次供需見面會上找到工作？網(wǎng)絡(luò)優(yōu)化問題的例子

二部基數(shù)/賦權(quán)匹配17破圈法-----復(fù)雜度高避圈法----貪婪算法(GreedyAlgorithm)Kruskal算法（1956）Prim算法（1957）：即“邊割法”Dijkstra算法（1959）Sollin算法（1961）最?。ㄉ桑渌惴?8最小樹形圖算法：

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

Edmons算法（1968）基本思想：收縮–展開19增廣路算法Ford-Fulkerson標(biāo)號算法(1956)最大容量增廣路算法容量變尺度算法最短增廣路算法：O(n2m)預(yù)流推進(jìn)算法最高標(biāo)號預(yù)流推進(jìn)算法：O(n2m1/2)最大流算法實際計算效率高21消圈算法最小費用路算法原始-對偶算法Ford和Forkerson(1957,1962)瑕疵算法(Out-Of-KilterAlgorithm)松弛(Relaxation)算法網(wǎng)絡(luò)單純形算法最小費用流算法實際計算效率高22二部基數(shù)匹配增廣路算法：O(mn)簡單網(wǎng)絡(luò)上的最大流算法：O(mn1/2)一般基數(shù)匹配“花”算法:O(n3)二部賦權(quán)匹配（指派問題）最小費用流算法（如匈牙利算法）:O(n3)一般賦權(quán)匹配原始-對偶算法:O(n3)匹配算法23西氣東送（鋼管運輸）問題

（CUMCM-2000B)A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7鐵路運價表里程≤300301～350351～400401～450451～500…運價2023262932…25西氣東送（鋼管運輸）問題

（CUMCM-2000B)二次規(guī)劃（常用解法）最小費用流問題？（清華大學(xué)隊，獲網(wǎng)易杯）線性模型（網(wǎng)絡(luò)規(guī)模較大，有現(xiàn)成算法）非線性模型（網(wǎng)絡(luò)規(guī)模較小，需要自己設(shè)計算法）基本問題----最小運費矩陣的計算兩種運輸方式（鐵路／公路）混合最短路問題是普通最短路問題的變種，需要自己設(shè)計算法26例：旅行商問題(TSP-TravelingSalesmanProblem)一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品.如何為他(她)設(shè)計一條最短的旅行路線(從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地)？這一問題的研究歷史十分悠久，通常稱之為旅行商問題.

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

BACDEFGHI29災(zāi)情巡視路線(CUMCM-1998B)多人TSP問題的擴展30例：套匯（Arbitrage）問題 在外匯市場上，將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)化問題的例子

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

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

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

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

可以變成最小費用流的問題37L=2為例：bi

男孩；gi

女孩；ui

學(xué)校容量(p,q)男孩比例上下限；dij距離學(xué)生分區(qū)問題最小費用流問題b1b2g1g2(0,u1)(0,u2)t容量d11d12d21d22d11d12d21d22(pu1,qu1)(pu2,qu2)費用為０38例:一類排序(Scheduling)問題某車間接受了p項不同的加工任務(wù)，要求在車間的q臺完全相同的機器上加工每項任務(wù)所需要的加工時間是相同的，且只需要在其中的任何一臺機器上加工完成即可每項任務(wù)在同一時刻不能在兩個或兩個以上的機器上加工，且每項任務(wù)的加工都必須一次完成（即一旦開始加工，加工中不能間斷每臺機器在同一時刻不能加工兩項或兩項以上的任務(wù)從當(dāng)前時刻開始計時，如果第j項任務(wù)的完工時間為tj，則該車間的信譽損失為cj(tj)（假設(shè)該函數(shù)為增函數(shù)）車間希望制訂一個加工計劃，使總的信譽損失最小網(wǎng)絡(luò)優(yōu)化問題的例子

可以變成最小費用流的問題39一類排序(Scheduling)問題12…p12…r11…1-q-q

…-q

p個工件；q臺機器;加工時間ac1(a)c1(2a)c1(ra)c2(a)c