数学建模——网 络 优 化

《数学建模——网 络 优 化》由会员分享，可在线阅读，更多相关《数学建模——网 络 优 化（43页珍藏版）》请在金锄头文库上搜索。

1、1,网 络 优 化 模 型 与 算 法,Network Optimization: Models & Algorithms,清华大学数学科学系 谢金星 Email: http:/ - 江西 庐山,2,Outline,What is Network Optimization? Typical Models & Algorithms Minimum Spanning Tree (最小(生成)树) Minimum Arborescence (最小树形图) Shortest Path (最短路) Maximum Flow (最大流) Minimum Cost Flow (最小费用流) Matching

2、 (匹配) Some Modeling Examples,3,网 络 优 化 简 介,网络：网络社会 - 计算机信息网络？,电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等,网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益,4,网 络 优 化 简 介,网络(Network)：数学模型、数学结构 - 图,优化(Optimization) : 从若干可能的方案中寻求某种意义下的最优方案,与图论有联系，也有区别（侧重点不同）,网络优化就是研究与（赋权）图有关的最优化问题,图论： 图的性质,网络优化： 与（赋权）图有关的优化问题,组合数学,组合优化,5

3、,Optimization Tree http:/www-fp.mcs.anl.gov/otc/Guide/OptWeb/,6,网 络 优 化 简 介,主要参考书：谢金星 、邢文训，网络优化 ，清华大学出版社，2000年8月；2003年9月。Ahuja, R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993: Englewood Cliffs, New Jersey.,网络优化模型 网络优化算法及其复杂性,网络优化或网络流（Netwo

4、rk Flows) 或网络规划（Network Programming),7,图与网络 基本概念,图G=(V，A)，其中顶点集V= 弧集A= 弧,8,例： 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？,网络优化问题的例子,最小(生成)树 也称为 最小(支撑)树,9,例： 二维矩阵数据存贮问题 某些蛋白质的氨基酸序列差异不多，如果用二维矩阵的每一行记录一种蛋白质氨基酸序列，行与行之间的差异很

5、小. 其中一种方法是只存贮其中一行作为参照行，再存贮行与行之间的一部分差异信息，使得我们可以在需要时根据参照行生成所有其它行的元素.,R1,R3,R2,R4,C13,C12,C24,最小树,网络优化问题的例子,10,“直接方式”：总经理直接传达； “接力方式”：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理. 如何决定传达信息的途径？,信息传播是有向的，有一个“根”。,信息传播途径（忽略方向时）是一棵树。,以上结构称为树形图，上面这样一类问题称为最小树形图问题.,例： 信息传播,最小树形图 例,11,例

6、最短路问题（SPP-Shortest Path Problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地. 从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路.,网络优化问题的例子,12,例：计划评审技术, 即PERT(Project Evaluation & Review Technique), 又称网络计划技术或统筹法),大型复杂工程项目(Project)往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求, 每一子项目需要一定的时间完成. PERT网络的每条

7、弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路 (关键路线). 工程上所谓的关键路线法(CPM: Critical Path Method)基本上也是计划评审技术的一部分.,项目网络不含圈（其最长路问题和最短路问题都是可解的）,13,例：最大流 / 最小费用流,从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限. 从甲地到乙地的每天最多能通车多少辆?,考虑每条路上的通行成本,如何确定某个车队的具体行车路线,使总成本最小?,14,例： 运输问题(Transportation Problem) 某种原材料有M个产地，现在需要将原材料从产地运往N个使用

8、这些原材料的工厂. 假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？,网络优化问题的例子,特殊的最小费用流问题 （二部图, |S|=M, |T|=N）,15,例： 指派问题(Assignment Problem) 一家公司经理准备安排N名员工去完成N项任务，每人一项. 由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的. 如何分配工作方案可以使总回报最大？,网络优化问题的例子,特殊的最小费用流问题 （二部图， |S|=|T|=N）,16,最小费用流模型的特例及扩展,最 小 费 用 流 问 题,狭义

9、模型,广义模型,17,例：匹配问题(Matching Problem)在一次有m个大学毕业生和n家公司参加的供需见面会上，每个毕业生愿意加入到若干家公司中的一家工作，而每个公司愿意接收若干毕业生中的一人到公司工作. 那么，最后最多有多少人可以在这次供需见面会上找到工作（即最多有多少家公司可以在这次供需见面会上招聘到员工）？如果每个毕业生到每一家公司工作将会产生的效益不同，那么，为了使得最后产生的总效益最大，最多有多少人可以在这次供需见面会上找到工作？,网络优化问题的例子,二部基数 / 赋权匹配,18,破圈法 - 复杂度高避圈法 - 贪婪算法(Greedy Algorithm) Kruskal

10、算法（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,增广路算

11、法 Ford-Fulkerson标号算法 (1956) 最大容量增广路算法 容量变尺度算法 最短增广路算法： O(n2m)预流推进算法 最高标号预流推进算法： O(n2m1/2),最大流算法,22,消圈算法 最小费用路算法 原始-对偶算法 Ford和Forkerson(1957,1962) 瑕疵算法(Out-Of-Kilter Algorithm) 松弛(Relaxation)算法 网络单纯形算法,最小费用流算法,23,二部基数匹配 增广路算法：O(mn) 简单网络上的最大流算法：O(mn1/2)一般基数匹配 “花”算法: O(n3)二部赋权匹配（指派问题） 最小费用流算法（如匈牙利算法）:

12、O(n3)一般赋权匹配 原始-对偶算法: O(n3),匹配算法,24,网络优化的评注,许多实际问题可以直接用网络优化建模许多实际问题可能用到网络优化建模许多实际问题是网络优化的变种网络优化问题通常可以用整数规划建模,25,西气东送（钢管运输）问题 （CUMCM-2000B),铁路运价表,26,西气东送（钢管运输）问题 （CUMCM-2000B),二次规划（常用解法）最小费用流问题？ （清华大学队，获网易杯） 线性模型（网络规模较大，有现成算法） 非线性模型（网络规模较小，需要自己设计算法）基本问题 - 最小运费矩阵的计算 两种运输方式（铁路公路）混合最短路问题 是普通最短路问题的变种，需要自己

13、设计算法,27,铁路公路混合运输最短路问题,最小运费矩阵算法（四川大学/清华大学等队） Dijkstra算法 或 Floyd-Warshall算法铁路最短路问题 最短路 =铁路最小运费矩阵 公路最短路问题 最短路 =公路最小运费矩阵 铁路/公路混合运输最短路问题 铁路/公路混合运输网络 最短路 =铁路/公路混合运输最小运费矩阵,28,例：中国邮递员问题(CPP-Chinese Postman Problem) 一名邮递员负责投递某个街区的邮件. 如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上

14、称之为中国邮递员问题.,网络优化问题的其他例子,单向？ 双向？ 风向？,29,例：旅行商问题(TSP-Traveling Salesman Problem) 一名推销员准备前往若干城市推销产品. 如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.,网络优化问题的例子,30,灾情巡视路线(CUMCM-1998B),多人TSP问题的扩展,31,例：套汇（Arbitrage）问题在外汇市场上，将1单位的某种货币通过多次兑换，获得多于1单位的同种货币，称为套汇。如：1单位的A货币 (兑换) 46.4单位B货币1单位

15、的B货币 (兑换) 2.5单位C货币1单位的C货币 (兑换) 0.0091单位A货币则: 1单位的A货币 (通过三次兑换获得)46.42.50.0091=1.0556 单位A货币,网络优化问题的例子,可以变成检测负圈的问题,现在假设给定了若干种货币及其两两之间的兑换率，请你帮助找到一种套汇方式（或判定该外汇市场上不存在套汇的可能）。,32,套汇: 46.42.50.0091 = 1.0556 1两边取倒数(乘积1)，再取对数（求和0）可以变成检测负圈的问题,套汇（Arbitrage）问题,化乘积为求和的技术，也常用于“可靠性问题”,可能是完全有向图；弧上的权就是汇率的倒数的对数值！,33,例：逃生路线问题 n*n网格节点上有m个房间，逃到边上节点就算逃生成功 如何规划逃生路线，使这些路线互不相交？,网络优化问题的例子,可以变成最大流问题,34,m个房间是供应节点（源，供应量为） 只有边上节点可以是吸收节点（汇，吸收量为 ） 多源多汇，容易变成单源单汇 每条边容量为 每个节点容量为（通过增加节点和边，变成边容量）,