数学建模网络优化

数学建模网络优化第一页，共四十二页，2022年，8月28日1OutlineWhatisNetworkOptimization?TypicalModels&AlgorithmsMinimumSpanningTree(最小(生成)树)MinimumArborescence(最小树形图)ShortestPath(最短路)MaximumFlow(最大流)MinimumCostFlow(最小费用流)Matching(匹配)……SomeModelingExamples第二页，共四十二页，2022年，8月28日2网

络

优

化

简介网络：网络社会----计算机信息网络？电话通信网络运输服务网络能源和物质分派网络

人际关系网络等等网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益第三页，共四十二页，2022年，8月28日3网

络

优

化

简介网络(Network)：数学模型、数学结构----图优化(Optimization):从若干可能的方案中寻求某种意义下的最优方案与图论有联系，也有区别（侧重点不同）网络优化就是研究与（赋权）图有关的最优化问题图论：图的性质网络优化：与（赋权）图有关的优化问题组合数学组合优化第四页，共四十二页，2022年，8月28日4OptimizationTree

第五页，共四十二页，2022年，8月28日5网

络

优

化

简介主要参考书：

谢金星、邢文训，《网络优化》，清华大学出版社，2000年8月；2003年9月。Ahuja,R.K.,MagnantiT.L.,OrlinJ.B.NetworkFlows:Theory,Algorithms,andApplications.PrenticeHall,1993:EnglewoodCliffs,NewJersey.网络优化模型网络优化算法及其复杂性《网络优化》或《网络流》（NetworkFlows)或《网络规划》（NetworkProgramming)第六页，共四十二页，2022年，8月28日6图与网络–基本概念图G=(V，A)，其中顶点集V=

弧集A=弧第七页，共四十二页，2022年，8月28日7例：公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？

网络优化问题的例子

1132546385247最小(生成)树也称为最小(支撑)树第八页，共四十二页，2022年，8月28日8例：二维矩阵数据存贮问题某些蛋白质的氨基酸序列差异不多，如果用二维矩阵的每一行记录一种蛋白质氨基酸序列，行与行之间的差异很小.其中一种方法是只存贮其中一行作为参照行，再存贮行与行之间的一部分差异信息，使得我们可以在需要时根据参照行生成所有其它行的元素.R1R3R2R4C13C12C24最小树网络优化问题的例子

第九页，共四十二页，2022年，8月28日9“直接方式”：总经理直接传达；“接力方式”：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理.如何决定传达信息的途径？信息传播是有向的，有一个“根”。信息传播途径（忽略方向时）是一棵树。以上结构称为树形图，上面这样一类问题称为最小树形图问题.例：信息传播最小树形图–例第十页，共四十二页，2022年，8月28日10例最短路问题（SPP-ShortestPathProblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地.从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路.网络优化问题的例子

AF566744513BEDC第十一页，共四十二页，2022年，8月28日11例：计划评审技术,即PERT(ProjectEvaluation&ReviewTechnique),又称网络计划技术或统筹法)大型复杂工程项目(Project)往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求,每一子项目需要一定的时间完成.PERT网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路(关键路线).工程上所谓的关键路线法(CPM:CriticalPathMethod)基本上也是计划评审技术的一部分.项目网络不含圈（其最长路问题和最短路问题都是可解的）(开始)AF(结束)566744513B

EDC第十二页，共四十二页，2022年，8月28日12例：最大流/最小费用流从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限.从甲地到乙地的每天最多能通车多少辆?考虑每条路上的通行成本,如何确定某个车队的具体行车路线,使总成本最小?(甲)AF(乙)566744513B

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

运输问题(TransportationProblem)某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂.假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？

网络优化问题的例子

ST特殊的最小费用流问题（二部图,|S|=M,|T|=N）第十四页，共四十二页，2022年，8月28日14例：指派问题(AssignmentProblem)一家公司经理准备安排N名员工去完成N项任务，每人一项.由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的.如何分配工作方案可以使总回报最大？网络优化问题的例子

ST特殊的最小费用流问题（二部图，|S|=|T|=N）第十五页，共四十二页，2022年，8月28日15最小费用流模型的特例及扩展

最小费用流问题指派问题运输问题最大流问题最短路问题带增益的最小费用流问题线性规划问题凹费用网络的最小费用流问题凸费用网络的最小费用流问题狭义模型

广义模型凸规划第十六页，共四十二页，2022年，8月28日16例：匹配问题(MatchingProblem)在一次有m个大学毕业生和n家公司参加的供需见面会上，每个毕业生愿意加入到若干家公司中的一家工作，而每个公司愿意接收若干毕业生中的一人到公司工作.那么，最后最多有多少人可以在这次供需见面会上找到工作（即最多有多少家公司可以在这次供需见面会上招聘到员工）？如果每个毕业生到每一家公司工作将会产生的效益不同，那么，为了使得最后产生的总效益最大，最多有多少人可以在这次供需见面会上找到工作？网络优化问题的例子

二部基数/赋权匹配第十七页，共四十二页，2022年，8月28日17破圈法-----复杂度高避圈法----贪婪算法(GreedyAlgorithm)Kruskal算法（1956）Prim算法（1957）：即“边割法”Dijkstra算法（1959）Sollin算法（1961）最小（生成）树算法第十八页，共四十二页，2022年，8月28日18最小树形图算法：

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

Edmons算法（1968）基本思想：收缩–展开第十九页，共四十二页，2022年，8月28日19无圈网络：拓扑排序+动态规划圈的检测正费用网络：Dijkstra算法（1959）一般网络，单一起点（或终点）Bellman-Ford算法(1956)：

O(mn)一般网络，所有点对Floyd-Warshall算法(1962)：

O(n3)负圈检测最短路算法：标号设定/修正算法第二十页，共四十二页，2022年，8月28日20增广路算法Ford-Fulkerson标号算法(1956)最大容量增广路算法容量变尺度算法最短增广路算法：O(n2m)预流推进算法最高标号预流推进算法：O(n2m1/2)最大流算法实际计算效率高第二十一页，共四十二页，2022年，8月28日21消圈算法最小费用路算法原始-对偶算法Ford和Forkerson(1957,1962)瑕疵算法(Out-Of-KilterAlgorithm)松弛(Relaxation)算法网络单纯形算法最小费用流算法实际计算效率高第二十二页，共四十二页，2022年，8月28日22二部基数匹配增广路算法：O(mn)简单网络上的最大流算法：O(mn1/2)一般基数匹配“花”算法:O(n3)二部赋权匹配（指派问题）最小费用流算法（如匈牙利算法）:O(n3)一般赋权匹配原始-对偶算法:O(n3)匹配算法第二十三页，共四十二页，2022年，8月28日23网络优化的评注许多实际问题可以直接用网络优化建模许多实际问题可能用到网络优化建模许多实际问题是网络优化的变种网络优化问题通常可以用整数规划建模第二十四页，共四十二页，2022年，8月28日24西气东送（钢管运输）问题

（CUMCM-2000B)A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程≤300301～350351～400401～450451～500…运价2023262932…第二十五页，共四十二页，2022年，8月28日25西气东送（钢管运输）问题

（CUMCM-2000B)二次规划（常用解法）最小费用流问题？（清华大学队，获网易杯）线性模型（网络规模较大，有现成算法）非线性模型（网络规模较小，需要自己设计算法）基本问题----最小运费矩阵的计算两种运输方式（铁路／公路）混合最短路问题是普通最短路问题的变种，需要自己设计算法第二十六页，共四十二页，2022年，8月28日26铁路／公路混合运输最短路问题最小运费矩阵算法（四川大学/清华大学等队）Dijkstra算法或Floyd-Warshall算法铁路最短路问题最短路==〉铁路最小运费矩阵公路最短路问题最短路==〉公路最小运费矩阵铁路/公路混合运输最短路问题铁路/公路混合运输网络最短路==〉铁路/公路混合运输最小运费矩阵第二十七页，共四十二页，2022年，8月28日27例：中国邮递员问题(CPP-ChinesePostmanProblem)一名邮递员负责投递某个街区的邮件.如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.网络优化问题的其他例子

单向？双向？风向？第二十八页，共四十二页，2022年，8月28日28例：旅行商问题(TSP-TravelingSalesmanProblem)一名推销员准备前往若干城市推销产品.如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.

网络优化问题的例子

BACDEFGHI第二十九页，共四十二页，2022年，8月28日29灾情巡视路线(CUMCM-1998B)多人TSP问题的扩展第三十页，共四十二页，2022年，8月28日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货币网络优化问题的例子

可以变成检测负圈的问题 现在假设给定了若干种货币及其两两之间的兑换率，请你帮助找到一种套汇方式（或判定该外汇市场上不存在套汇的可能）。第三十一页，共四十二页，2022年，8月28日31套汇:46.4＊2.5＊0.0091=1.0556>1两边取倒数(乘积<1)，再取对数（求和<0）可以变成检测负圈的问题套汇（Arbitrage）问题化乘积为求和的技术，也常用于“可靠性问题”可能是完全有向图；弧上的权就是汇率的倒数的对数值！第三十二页，共四十二页，2022年，8月28日32例：逃生路线问题n*n网格节点上有m个房间，逃到边上节点就算逃生成功如何规划逃生路线，使这些路线互不相交？网络优化问题的例子

可以变成最大流问题逃生成功没有逃生路线第三十三页，共四十二页，2022年，8月28日33m个房间是供应节点（源，供应量为１）只有边上节点可以是吸收节点（汇，吸收量为１）多源多汇，容易变成单源单汇每条边容量为１每个节点容量为１（通过增加节点和边，变成边容量）逃生路线问题变成最大流问题逃生成功没有逃生路线其他目标？第三十四页，共四十二页，2022年，8月28日34例：空间实验问题某航天公司计划进行一次空间载人飞行，宇航员将在飞行中进行一系列科学实验。目前该公司收到了多个不同的科学实验申请，完成每个实验要求携带相应的一种或多种仪器设备（不同的实验所需要的仪器设备中有些可能是相同的，而另外有些可能是不同的）。已知完成每个实验后公司所得到的相应报酬（不同实验的报酬可能不同），并已知飞行器携带每种仪器设备的相应费用（不同仪器设备的费用可能不同）。公司希望你帮助选定此次飞行究竟从事哪些科学实验，以及需要携带哪些仪器设备，使此次飞行的总利润最大（总利润=总报酬－总费用）。

网络优化问题的例子

可以变成最大流问题第三十五页，共四十二页，2022年，8月28日35空间实验问题最大流(最小割)问题设备实验n个实验(报酬pi)m类设备(成本ci)12…m12…ncipist计划有限割有限割的容量：ST第三十六页，共四十二页，2022年，8月28日36例:学生分区问题假设某个城市分为L个区,每个区有若干男孩和若干女孩需要上学.假设每个区有一所小学,每所小学所能容纳的学生总数已知,并且按照规定,每所小学所能容纳的男孩和女孩比例不能太大或太小.假设每两个区之间的路程已知(同一区内认为路程近似为0),如何为需要上学的小孩分配学校,使得所有小孩上学所走的总路程最少?网络优化问题的例子

可以变成最小费用流的问题第三十七页，共四十二页，2022年，8月28日37L=2为例：bi

男孩；gi

女孩；ui

学校容量(p,q)男孩比例上下限；dij距离学生分区问题最小费用流问题b1b2g1g2(0,u1)(0,u2)t容量d11d12d21d22d11d12d21d22(pu1,qu1)(pu2,qu2)费用为０第三十八页，共四十二页，2022年，8月28日38例:一类排序(Scheduling)问题某车间接受了p项不同的加工任务，要求在车间的q台完全相同的机器上加工每项任务所需要的加工时间是相同的，且只需要在其中的任何一台机器上加工完成即可每项任务在同一时刻不能在两个或两个以上的机器上加工，且每项任务的加