Network Optimization: Models & Algorithms

Presentation on theme: "Network Optimization: Models & Algorithms"— Presentation transcript:

1 Network Optimization: Models & Algorithms
网 络 优 化 模 型 与 算 法 Network Optimization: Models & Algorithms 2004年7月~8月 江西 庐山 清华大学数学科学系 谢金星

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 网 络 优 化 简 介 网络：网络社会 ---- 计算机信息网络？ 电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等
网 络 优 化 简 介 网络：网络社会 ---- 计算机信息网络？ 电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等 网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益

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

5 Optimization Tree

6 网 络 优 化 简 介 网络优化模型 网络优化算法及其复杂性 《网络优化》或《网络流》（Network Flows)
网 络 优 化 简 介 网络优化模型 网络优化算法及其复杂性 主要参考书： 谢金星 、邢文训，《网络优化》 ，清华大学出版社，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 Programming)

7 图与网络 – 基本概念 图G=(V，A)，其中顶点集V= 弧集A= 弧

8 网络优化问题的例子 例： 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？ 1 3 2 5 4 6 8 7 最小(生成)树 也称为 最小(支撑)树

9 网络优化问题的例子 例： 二维矩阵数据存贮问题
某些蛋白质的氨基酸序列差异不多，如果用二维矩阵的每一行记录一种蛋白质氨基酸序列，行与行之间的差异很小. 其中一种方法是只存贮其中一行作为参照行，再存贮行与行之间的一部分差异信息，使得我们可以在需要时根据参照行生成所有其它行的元素. R1 最小树 C13 C12 C24 R3 R2 R4

10 最小树形图 – 例 例： 信息传播 “直接方式”：总经理直接传达；
例： 信息传播 “直接方式”：总经理直接传达； “接力方式”：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理. 如何决定传达信息的途径？ 信息传播是有向的，有一个“根”。 信息传播途径（忽略方向时）是一棵树。 以上结构称为树形图，上面这样一类问题称为最小树形图问题.

11 网络优化问题的例子 A F 5 6 7 4 1 3 B E D C 例 最短路问题（SPP-Shortest Path Problem）
一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地. 从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路. A F 5 6 7 4 1 3 B E D C

12 例：计划评审技术, 即PERT(Project Evaluation & Review Technique), 又称网络计划技术或统筹法)
大型复杂工程项目(Project)往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求, 每一子项目需要一定的时间完成. PERT网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路 (关键路线). 工程上所谓的关键路线法(CPM: Critical Path Method)基本上也是计划评审技术的一部分. (开始) A F (结束) 5 6 7 4 1 3 B E D C 项目网络不含圈（其最长路问题和最短路问题都是可解的）

13 例：最大流 / 最小费用流 从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限. 从甲地到乙地的每天最多能通车多少辆? (甲) A
F (乙) 5 6 7 4 1 3 B E D C 考虑每条路上的通行成本,如何确定某个车队的具体行车路线,使总成本最小?

14 网络优化问题的例子 特殊的最小费用流问题 （二部图, |S|=M, |T|=N） S T
例： 运输问题(Transportation Problem) 某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂. 假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？ 特殊的最小费用流问题 （二部图, |S|=M, |T|=N） S T

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

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

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

18 最小（生成）树算法 破圈法 ----- 复杂度高 避圈法 ---- 贪婪算法(Greedy Algorithm)
Kruskal 算法（1956 ） Prim 算法（1957） ：即“边割法” Dijkstra算法（1959） Sollin 算法 （1961）

19 最小树形图算法： 朱(永津)-刘(振宏)算法（1965）
最大分枝算法： Edmons算法（1968） 基本思想：收缩 – 展开

20 最短路算法：标号设定/修正算法 无圈网络：拓扑排序 + 动态规划 正费用网络：Dijkstra算法（1959） 一般网络，单一起点（或终点）
无圈网络：拓扑排序 + 动态规划 圈的检测 正费用网络：Dijkstra算法（1959） 一般网络，单一起点（或终点） Bellman - Ford算法 (1956)： O(mn) 一般网络，所有点对 Floyd-Warshall算法(1962)： O(n3) 负圈检测

21 最大流算法 增广路算法 预流推进算法 实际计算效率高 Ford-Fulkerson标号算法 (1956) 最大容量增广路算法 容量变尺度算法
最短增广路算法： O(n2m) 预流推进算法 最高标号预流推进算法： O(n2m1/2) 实际计算效率高

22 最小费用流算法 实际计算效率高 消圈算法 最小费用路算法 原始-对偶算法 瑕疵算法(Out-Of-Kilter Algorithm)
Ford和Forkerson(1957,1962) 瑕疵算法(Out-Of-Kilter Algorithm) 松弛(Relaxation)算法 网络单纯形算法 实际计算效率高

23 匹配算法 二部基数匹配 一般基数匹配 二部赋权匹配（指派问题） 一般赋权匹配 增广路算法：O(mn)
“花”算法: O(n3) 二部赋权匹配（指派问题） 最小费用流算法（如匈牙利算法）: O(n3) 一般赋权匹配 原始-对偶算法: O(n3)

24 网络优化的评注 许多实际问题可以直接用网络优化建模 许多实际问题可能用到网络优化建模 许多实际问题是网络优化的变种
网络优化问题通常可以用整数规划建模

25 西气东送（钢管运输）问题 （CUMCM-2000B)
A1 3 2 5 80 10 31 20 12 42 70 88 62 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 3060 195 202 720 690 520 170 462 160 320 110 290 1150 1100 1200 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 铁路运价表 里程 ≤300 301～350 351～400 401～450 451～500 … 运价 20 23 26 29 32

26 西气东送（钢管运输）问题 （CUMCM-2000B)
二次规划（常用解法） 最小费用流问题？ （清华大学队，获网易杯） 线性模型（网络规模较大，有现成算法） 非线性模型（网络规模较小，需要自己设计算法） 基本问题 ---- 最小运费矩阵的计算 两种运输方式（铁路／公路）混合最短路问题 是普通最短路问题的变种，需要自己设计算法

27 铁路／公路混合运输最短路问题 最小运费矩阵算法（四川大学/清华大学等队） Dijkstra算法 或 Floyd-Warshall算法
铁路最短路问题 最短路 ==〉铁路最小运费矩阵 公路最短路问题 最短路 ==〉公路最小运费矩阵 铁路/公路混合运输最短路问题 铁路/公路混合运输网络 最短路 ==〉铁路/公路混合运输最小运费矩阵

28 网络优化问题的其他例子 单向？ 双向？ 风向？ 例：中国邮递员问题(CPP-Chinese Postman Problem)
一名邮递员负责投递某个街区的邮件. 如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题. 单向？ 双向？ 风向？

29 网络优化问题的例子 例：旅行商问题(TSP-Traveling Salesman Problem)
一名推销员准备前往若干城市推销产品. 如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题. B A C D E F G H I

30 灾情巡视路线(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 套汇（Arbitrage）问题 套汇: 46.4＊2.5＊0.0091 = 1.0556 > 1
套汇: ＊2.5＊0.0091　=　 > 1 两边取倒数(乘积<1)，再取对数（求和<0） 可以变成检测负圈的问题 　可能是完全有向图； 　弧上的权就是汇率的倒数的对数值！ 化乘积为求和的技术，也常用于“可靠性问题”

33 网络优化问题的例子 例：逃生路线问题 n*n网格节点上有m个房间，逃到边上节点就算逃生成功 如何规划逃生路线，使这些路线互不相交？
没有逃生路线 可以变成最大流问题

34 逃生路线问题 逃生成功 没有逃生路线 m个房间是供应节点（源，供应量为１） 只有边上节点可以是吸收节点（汇，吸收量为１ ）
多源多汇，容易变成单源单汇 每条边容量为１ 每个节点容量为１（通过增加节点和边，变成边容量） 变成最大流问题 其他目标？

35 网络优化问题的例子 例：空间实验问题 某航天公司计划进行一次空间载人飞行，宇航员将在飞行中进行一系列科学实验。目前该公司收到了多个不同的科学实验申请，完成每个实验要求携带相应的一种或多种仪器设备（不同的实验所需要的仪器设备中有些可能是相同的，而另外有些可能是不同的）。 已知完成每个实验后公司所得到的相应报酬（不同实验的报酬可能不同），并已知飞行器携带每种仪器设备的相应费用（不同仪器设备的费用可能不同）。 公司希望你帮助选定此次飞行究竟从事哪些科学实验，以及需要携带哪些仪器设备，使此次飞行的总利润最大（总利润=总报酬－总费用）。 可以变成最大流问题

36 空间实验问题 S T 设备 实验 1 n个实验(报酬pi) m类设备(成本ci) 2 … m n t s pi ci 计划有限割
设备　　　　 实验 1 2 … m n ci pi s t S T n个实验(报酬pi) m类设备(成本ci) 计划有限割 有限割的容量： 最大流(最小割)问题

37 网络优化问题的例子 例: 学生分区问题 假设某个城市分为L个区, 每个区有若干男孩和若干女孩需要上学.
例: 学生分区问题 假设某个城市分为L个区, 每个区有若干男孩和若干女孩需要上学. 假设每个区有一所小学, 每所小学所能容纳的学生总数已知, 并且按照规定, 每所小学所能容纳的男孩和女孩比例不能太大或太小. 假设每两个区之间的路程已知(同一区内认为路程近似为0), 如何为需要上学的小孩分配学校, 使得所有小孩上学所走的总路程最少? 可以变成最小费用流的问题

38 学生分区问题 b1 b2 g1 g2 (pu1,qu1) (0,u1) (0,u2) t (pu2,qu2)
L=2为例：bi 男孩； gi 女孩； ui 学校容量 (p,q)男孩比例上下限； dij距离 d11 d12 d21 d22 学生分区问题 b1 b2 g1 g2 (pu1,qu1) (0,u1) (0,u2) t (pu2,qu2) 最小费用流问题 容量 费用为０

39 网络优化问题的例子 例: 一类排序(Scheduling)问题 某车间接受了p项不同的加工任务，要求在车间的q台完全相同的机器上加工
每项任务所需要的加工时间是相同的，且只需要在其中的任何一台机器上加工完成即可 每项任务在同一时刻不能在两个或两个以上的机器上加工，且每项任务的加工都必须一次完成（即一旦开始加工，加工中不能间断 每台机器在同一时刻不能加工两项或两项以上的任务 从当前时刻开始计时，如果第 j 项任务的完工时间为tj，则该车间的信誉损失为cj(tj)（假设该函数为增函数） 车间希望制订一个加工计划，使总的信誉损失最小 可以变成最小费用流的问题

40 一类排序(Scheduling)问题 p个工件； q台机器; 加工时间a 工件 加工位置 1 2 … p r -q 每台机器加工的工件数：
工件　　　　加工位置 c1(a) c1(2a) c1(ra) c2(a) c2(2a) cp(2a) c2(ra) cp(a) cp(ra) 1 2 … p r -q 每台机器加工的工件数： r=p/q (不妨设为整数) 变成最小费用流的问题

41 网络优化问题的例子 例 稳定婚配问题(Stable Marriage Problem)
假设有n个男人和n个女人, 每人都希望从n个异性中选择一位自己的配偶. 假设每人都对n个异性根据自己的偏好进行了排序, 以此作为选择配偶的基础. 当给定一种婚配方案(即给每人指定一个配偶)后, 如果存在一个男人和一个女人不是互为配偶, 但该男人喜欢该女人胜过其配偶, 且该女人喜欢该男人也胜过其配偶, 则该婚配方案称为不稳定的. 安排稳定的婚配方案的问题称为稳定婚配问题。 二部完美匹配 　存在性？ 　算法？ 　其他目标

42 MCM中的一些网络优化问题 1999 扫雪车问题 1991 Steiner树问题 1994 通讯网络问题 2000 无线信道分配问题
????

43 Thank you for your attendance! 最后，祝大家 在数学建模活动中 不断提高综合素质， 在数学建模竞赛中
　　在数学建模活动中 　　　　　　不断提高综合素质， 　　在数学建模竞赛中 　　　　　　取得更好的成绩！ That’s all. Any Questions?