数学建模――网 络 优 化

1网络优化模型与算法NetworkOptimization:Models&Algorithms清华大学数学科学系谢金星Email:[e-mail]~jxie2004年7月~8月----江西庐山2Outline•WhatisNetworkOptimization?•TypicalModels&Algorithms–MinimumSpanningTree(最小(生成)树)–MinimumArborescence(最小树形图)–ShortestPath(最短路)–MaximumFlow(最大流)–MinimumCostFlow(最小费用流)–Matching(匹配)–……•SomeModelingExamples3网络优化简介•网络：网络社会----计算机信息网络？电话通信网络运输服务网络能源和物质分派网络人际关系网络等等网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益4网络优化简介•网络(Network)：数学模型、数学结构----图•优化(Optimization):从若干可能的方案中寻求某种意义下的最优方案•与图论有联系，也有区别（侧重点不同）•网络优化就是研究与（赋权）图有关的最优化问题图论：图的性质网络优化：与（赋权）图有关的优化问题组合数学组合优化5OptimizationTree网络优化简介主要参考书：•谢金星、邢文训，《网络优化》，清华大学出版社，2000年8月；2003年9月。•Ahuja,R.K.,MagnantiT.L.,OrlinJ.B.NetworkFlows:Theory,Algorithms,andApplications.PrenticeHall,1993:EnglewoodCliffs,NewJersey.网络优化模型网络优化算法及其复杂性《网络优化》或《网络流》（NetworkFlows)或《网络规划》（NetworkProgramming)7图与网络–基本概念5a1a1v2v3a3v4a4v5v2a6a图G=(V，A)，其中顶点集V=弧集A=弧},,,,{54321vvvvv},,,,,{654321aaaaaa),(211vva),(212vva),(323vva),(434vva),(145vva),(336vva8例：公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？网络优化问题的例子1132546385247最小(生成)树也称为最小(支撑)树9例：二维矩阵数据存贮问题某些蛋白质的氨基酸序列差异不多，如果用二维矩阵的每一行记录一种蛋白质氨基酸序列，行与行之间的差异很小.其中一种方法是只存贮其中一行作为参照行，再存贮行与行之间的一部分差异信息，使得我们可以在需要时根据参照行生成所有其它行的元素.R1R3R2R4C13C12C24最小树网络优化问题的例子10“直接方式”：总经理直接传达；“接力方式”：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理.如何决定传达信息的途径？信息传播是有向的，有一个“根”。信息传播途径（忽略方向时）是一棵树。以上结构称为树形图，上面这样一类问题称为最小树形图问题.例：信息传播最小树形图–例11例最短路问题（SPP-ShortestPathProblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地.从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路.网络优化问题的例子AF566744513BEDC12例：计划评审技术,即PERT(ProjectEvaluation&ReviewTechnique),又称网络计划技术或统筹法)大型复杂工程项目(Project)往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求,每一子项目需要一定的时间完成.PERT网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路(关键路线).工程上所谓的关键路线法(CPM:CriticalPathMethod)基本上也是计划评审技术的一部分.项目网络不含圈（其最长路问题和最短路问题都是可解的）(开始)AF(结束)566744513BEDC13例：最大流/最小费用流从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限.从甲地到乙地的每天最多能通车多少辆?考虑每条路上的通行成本,如何确定某个车队的具体行车路线,使总成本最小?(甲)AF(乙)566744513BEDC14例：运输问题(TransportationProblem)某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂.假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？网络优化问题的例子ST特殊的最小费用流问题（二部图,|S|=M,|T|=N）15例：指派问题(AssignmentProblem)一家公司经理准备安排N名员工去完成N项任务，每人一项.由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的.如何分配工作方案可以使总回报最大？网络优化问题的例子ST特殊的最小费用流问题（二部图，|S|=|T|=N）16最小费用流模型的特例及扩展最小费用流问题指派问题运输问题最大流问题最短路问题带增益的最小费用流问题线性规划问题凹费用网络的最小费用流问题凸费用网络的最小费用流问题狭义模型广义模型凸规划17例：匹配问题(MatchingProblem)在一次有m个大学毕业生和n家公司参加的供需见面会上，每个毕业生愿意加入到若干家公司中的一家工作，而每个公司愿意接收若干毕业生中的一人到公司工作.那么，最后最多有多少人可以在这次供需见面会上找到工作（即最多有多少家公司可以在这次供需见面会上招聘到员工）？如果每个毕业生到每一家公司工作将会产生的效益不同，那么，为了使得最后产生的总效益最大，最多有多少人可以在这次供需见面会上找到工作？网络优化问题的例子二部基数/赋权匹配18•破圈法-----复杂度高•避圈法----贪婪算法(GreedyAlgorithm)–Kruskal算法（1956）–Prim算法（1957）：即“边割法”•Dijkstra算法（1959）–Sollin算法（1961）最小（生成）树算法19最小树形图算法：朱(永津)-刘(振宏)算法（1965）最大分枝算法：Edmons算法（1968）•基本思想：收缩–展开20无圈网络：拓扑排序+动态规划圈的检测正费用网络：Dijkstra算法（1959）一般网络，单一起点（或终点）Bellman-Ford算法(1956)：O(mn)一般网络，所有点对Floyd-Warshall算法(1962)：O(n3)负圈检测最短路算法：标号设定/修正算法21增广路算法Ford-Fulkerson标号算法(1956)最大容量增广路算法容量变尺度算法最短增广路算法：O(n2m)预流推进算法最高标号预流推进算法：O(n2m1/2)最大流算法实际计算效率高22消圈算法最小费用路算法原始-对偶算法Ford和Forkerson(1957,1962)瑕疵算法(Out-Of-KilterAlgorithm)松弛(Relaxation)算法网络单纯形算法最小费用流算法实际计算效率高23二部基数匹配增广路算法：O(mn)简单网络上的最大流算法：O(mn1/2)一般基数匹配“花”算法:O(n3)二部赋权匹配（指派问题）最小费用流算法（如匈牙利算法）:O(n3)一般赋权匹配原始-对偶算法:O(n3)匹配算法24网络优化的评注•许多实际问题可以直接用网络优化建模•许多实际问题可能用到网络优化建模•许多实际问题是网络优化的变种•网络优化问题通常可以用整数规划建模25西气东送（钢管运输）问题（CUMCM-2000B)A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程≤300301～350351～400401～450451～500…运价2023262932…26西气东送（钢管运输）问题（CUMCM-2000B)•二次规划（常用解法）•最小费用流问题？（清华大学队，获网易杯）线性模型（网络规模较大，有现成算法）非线性模型（网络规模较小，需要自己设计算法）•基本问题----最小运费矩阵的计算两种运输方式（铁路／公路）混合最短路问题是普通最短路问题的变种，需要自己设计算法27铁路／公路混合运输最短路问题最小运费矩阵算法（四川大学/清华大学等队）Dijkstra算法或Floyd-Warshall算法•铁路最短路问题最短路==〉铁路最小运费矩阵•公路最短路问题最短路==〉公路最小运费矩阵•铁路/公路混合运输最短路问题铁路/公路混合运输网络最短路==〉铁路/公路混合运输最小运费矩阵28例：中国邮递员问题(CPP-ChinesePostmanProblem)一名邮递员负责投递某个街区的邮件.如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.网络优化问题的其他例子•单向？•双向？•风向？29例：旅行商问题(TSP-TravelingSalesmanProblem)一名推销员准备前往若干城市推销产品.如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.网络优化问题的例子BACDEFGHI30灾情巡视路线(CUMCM-1998B)多人TSP问题的扩展31例：套汇（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货币网络优化问题的例子可以变成检测负圈的问题现在假设给定了若干种货币及其两两之间的兑换率，请你帮助找到一种套汇方式（或判定该外汇市场上不存在套汇的可能）。32套汇:46.4＊2.5＊0.0091=1.05561两边取倒数(乘积1)，再取对数（求和0）可以变成检测负圈的问题套汇（Arbitrage）问题化乘积为求和的技术，也常用于“可靠性问题”•可能是完全有向图；•弧上的权就是汇率的倒数的对数值！33例：逃生路线问题•n*n网格节点上有m个房间，逃到边上节点就算逃生成功•如何规划逃生路线，使这些路线互不相交？网络优化问题的例子可以变成最大流问题逃生成功没有逃生路线34•m个房间是供应节点（源，供应量为１）•只有边上节点可以是吸收节点（汇，吸收量为１）•多源多汇，容易变成单源单汇•每条边容量为１•每个节点容量为１（通过增加节点和边，变成边