网络优化模型与算法.ppt

Outline What is Network Optimization? Typical Models Algorithms Minimum Spanning Tree (最小(生成)树) Minimum Arborescence (最小树形图) Shortest Path (最短路) Maximum Flow (最大流) Minimum Cost Flow (最小费用流) Matching (匹配) …… Some Modeling Examples 最小（生成）树算法 破圈法 ----- 复杂度高 避圈法 ---- 贪婪算法(Greedy Algorithm) Kruskal 算法（1956 ） Prim 算法（1957） ：即“边割法” Dijkstra算法（1959） Sollin 算法 （1961） 最小树形图算法：朱(永津)-刘(振宏)算法（1965） 最短路算法：标号设定/修正算法 无圈网络：拓扑排序 + 动态规划 圈的检测 正费用网络：Dijkstra算法（1959） 一般网络，单一起点（或终点） Bellman - Ford算法 (1956)： O(mn) 一般网络，所有点对 Floyd-Warshall算法(1962)： O(n3) 负圈检测 最大流算法 增广路算法 Ford-Fulkerson标号算法 (1956) 最大容量增广路算法 容量变尺度算法 最短增广路算法： O(n2m) 预流推进算法 最高标号预流推进算法： O(n2m1/2) 最小费用流算法 消圈算法 最小费用路算法 原始-对偶算法 Ford和Forkerson(1957,1962) 瑕疵算法(Out-Of-Kilter Algorithm) 松弛(Relaxation)算法 网络单纯形算法 匹配算法 二部基数匹配 增广路算法：O(mn) 简单网络上的最大流算法：O(mn1/2) 一般基数匹配 “花”算法: O(n3) 二部赋权匹配（指派问题） 最小费用流算法（如匈牙利算法）: O(n3) 一般赋权匹配 原始-对偶算法: O(n3) 网络优化的评注 许多实际问题可以直接用网络优化建模 许多实际问题可能用到网络优化建模 许多实际问题是网络优化的变种 网络优化问题通常可以用整数规划建模 西气东送（钢管运输）问题（CUMCM-2000B) 西气东送（钢管运输）问题（CUMCM-2000B) 二次规划（常用解法） 最小费用流问题？ （清华大学队，获网易杯） 线性模型（网络规模较大，有现成算法） 非线性模型（网络规模较小，需要自己设计算法） 基本问题 ---- 最小运费矩阵的计算 两种运输方式（铁路／公路）混合最短路问题 是普通最短路问题的变种，需要自己设计算法 铁路／公路混合运输最短路问题 最小运费矩阵算法（四川大学/清华大学等队） Dijkstra算法 或 Floyd-Warshall算法 铁路最短路问题 最短路 ==〉铁路最小运费矩阵 公路最短路问题 最短路 ==〉公路最小运费矩阵 铁路/公路混合运输最短路问题 铁路/公路混合运输网络 最短路 ==〉铁路/公路混合运输最小运费矩阵 套汇: 46.4＊2.5＊0.0091　=　1.0556 1 两边取倒数(乘积1)，再取对数（求和0） 可以变成检测负圈的问题 套汇（Arbitrage）问题 化乘积为求和的技术，也常用于“可靠性问题” 　可能是完全有向图； 　弧上的权就是汇率的倒数的对数值！ * 网 络 优 化 模 型 与 算 法 Network Optimization: Models Algorithms 清华大学数学科学系 谢金星 Email:jxie@ /~jxie 2004年7月~8月 ---- 江西 庐山 网 络 优 化 简 介 网络：网络社会 ---- 计算机信息网络？ 电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等 网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益 网 络 优 化 简 介 网络(Network)：数学模型、数学结构 ---- 图 优化(Optimization) : 从若干可能的方案中寻求某种意义下的最优方案 与图论有联系，也有区别（侧重点不同） 网络优化就是研究与（赋权）图有关的最优化问题 图论： 图的性质 网络优化： 与（赋权）图有关的优化问题 组合数学 组合优化 Optimization T