网络优化模型与算法.ppt
《网络优化模型与算法.ppt》由会员分享,可在线阅读,更多相关《网络优化模型与算法.ppt(43页珍藏版)》请在三一文库上搜索。
1、1,网 络 优 化 模 型 与 算 法,Network Optimization: Models & Algorithms,2,Outline,What is Network Optimization? Typical Models & Algorithms Minimum Spanning Tree (最小(生成)树) Minimum Arborescence (最小树形图) Shortest Path (最短路) Maximum Flow (最大流) Minimum Cost Flow (最小费用流) Matching (匹配) Some Modeling Examples,3,网 络 优
2、 化 简 介,网络:网络社会 - 计算机信息网络?,电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等,网络优化就是研究如何有效地计划、管理和控制网络系统,使之发挥最大的社会和经济效益,4,网 络 优 化 简 介,网络(Network):数学模型、数学结构 - 图,优化(Optimization) : 从若干可能的方案中寻求某种意义下的最优方案,与图论有联系,也有区别(侧重点不同),网络优化就是研究与(赋权)图有关的最优化问题,图论: 图的性质,网络优化: 与(赋权)图有关的优化问题,组合数学,组合优化,5,Optimization Tree http:/www-fp.mcs.
3、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.,网络优化模型 网络优化算法及其复杂性,网络优化或网络流(Network Flows) 或网络规划(Network Programmin
4、g),7,图与网络 基本概念,图G=(V,A),其中顶点集V= 弧集A= 弧,8,例: 公路连接问题 某一地区有若干个主要城市,现准备修建高速公路把这些城市连接起来, 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市之间修建高速公路的成本,那么应如何决定在哪些城市间修建高速公路,使得总成本最小?,网络优化问题的例子,最小(生成)树 也称为 最小(支撑)树,9,例: 二维矩阵数据存贮问题 某些蛋白质的氨基酸序列差异不多,如果用二维矩阵的每一行记录一种蛋白质氨基酸序列,行与行之间的差异很小. 其中一种方法是只存贮其中一行作为参照行,再存贮行与行之间的一部
5、分差异信息,使得我们可以在需要时根据参照行生成所有其它行的元素.,R1,R3,R2,R4,C13,C12,C24,最小树,网络优化问题的例子,10,“直接方式”:总经理直接传达; “接力方式”:总经理只给某些部门经理打电话,而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理,依此类推,最后将信息传达到所有部门经理. 如何决定传达信息的途径?,信息传播是有向的,有一个“根”。,信息传播途径(忽略方向时)是一棵树。,以上结构称为树形图,上面这样一类问题称为最小树形图问题.,例: 信息传播,最小树形图 例,11,例 最短路问题(SPP-Shortest Path Problem) 一
6、名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地. 从甲地到乙地的公路网纵横交错,因此有多种行车路线,这名司机应选择哪条线路呢?假设货柜车的运行速度是恒定的,那么这一问题相当于需要找到一条从甲地到乙地的最短路.,网络优化问题的例子,12,例:计划评审技术, 即PERT(Project Evaluation & Review Technique), 又称网络计划技术或统筹法),大型复杂工程项目(Project)往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求, 每一子项目需要一定的时间完成. PERT网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间
7、对应于网络中的最长路 (关键路线). 工程上所谓的关键路线法(CPM: Critical Path Method)基本上也是计划评审技术的一部分.,项目网络不含圈(其最长路问题和最短路问题都是可解的),13,例:最大流 / 最小费用流,从甲地到乙地的公路网纵横交错,每天每条路上的通车量有上限. 从甲地到乙地的每天最多能通车多少辆?,考虑每条路上的通行成本,如何确定某个车队的具体行车路线,使总成本最小?,14,例: 运输问题(Transportation Problem) 某种原材料有M个产地,现在需要将原材料从产地运往N个使用这些原材料的工厂. 假定M个产地的产量和N家工厂的需要量已知,单位产
8、品从任一产地到任一工厂的的运费已知,那么如何安排运输方案可以使总运输成本最低?,网络优化问题的例子,特殊的最小费用流问题 (二部图, |S|=M, |T|=N),15,例: 指派问题(Assignment Problem) 一家公司经理准备安排N名员工去完成N项任务,每人一项. 由于各员工的特点不同,不同的员工去完成同一项任务时所获得的回报是不同的. 如何分配工作方案可以使总回报最大?,网络优化问题的例子,特殊的最小费用流问题 (二部图, |S|=|T|=N),16,最小费用流模型的特例及扩展,最 小 费 用 流 问 题,狭义模型,广义模型,17,例:匹配问题(Matching Problem
9、) 在一次有m个大学毕业生和n家公司参加的供需见面会上,每个毕业生愿意加入到若干家公司中的一家工作,而每个公司愿意接收若干毕业生中的一人到公司工作. 那么,最后最多有多少人可以在这次供需见面会上找到工作(即最多有多少家公司可以在这次供需见面会上招聘到员工)?如果每个毕业生到每一家公司工作将会产生的效益不同,那么,为了使得最后产生的总效益最大,最多有多少人可以在这次供需见面会上找到工作?,网络优化问题的例子,二部基数 / 赋权匹配,18,破圈法 - 复杂度高 避圈法 - 贪婪算法(Greedy Algorithm) Kruskal 算法(1956 ) Prim 算法(1957) :即“边割法”
10、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)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络 优化 模型 算法
链接地址:https://www.31doc.com/p-4223219.html