网络优化模型与算法谢金星课件.ppt

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

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

3、同）与图论有联系，也有区别（侧重点不同）网络优化就是研究与（赋权）图有关的最优化问题网络优化就是研究与（赋权）图有关的最优化问题图论：图论：图的性质图的性质 网络优化网络优化：与（赋权）图有关的优化问题与（赋权）图有关的优化问题组合数学组合数学组合优化组合优化5Optimization Tree http:/www-fp.mcs.anl.gov/otc/Guide/OptWeb/6网网 络络 优优 化化 简简 介介主要参考书：主要参考书：谢金星谢金星、邢文训邢文训，网络优化网络优化，清华大学出版社，清华大学出版社，2000年年8月；月；2003年年9月。月。Ahuja,R.K.,Magnant

4、i T.L.,Orlin J.B.Network Flows:Theory,Algorithms,and Applications.Prentice Hall,1993:Englewood Cliffs,New Jersey.网络优化模型网络优化模型网络优化算法及其复杂性网络优化算法及其复杂性网络优化网络优化或或网络流网络流（Network Flows)或或网络规划网络规划（Network Programming)7图与网络图与网络 基本概基本概念念5a1a1v2v3a3v4a4v5v2a6a图G=(V，A)，其中顶点集V=弧集A=弧,54321vvvvv,654321aaaaaa),(211

5、vva),(212vva),(323vva),(434vva),(145vva),(336vva 8例：例：公路连接问题公路连接问题某一地区有若干个主要城市，现准备修建高速公路某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，把这些城市连接起来，使得从其中任何一个城市使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市都可以经高速公路直接或间接到达另一个城市.假假定已经知道了任意两个城市之间修建高速公路的成定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？使得总成本最小？网

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

7、生成所有其它行的元素.R1R3R2R4C13C12C24最最小小树树网络优化问题的例子网络优化问题的例子 10“直接方式直接方式”：总经理直接传达；：总经理直接传达；“接力方式接力方式”：总经理只给某些部门经理打电话，而让这：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理部门经理，依此类推，最后将信息传达到所有部门经理.如何决定传达信息的途径？如何决定传达信息的途径？信息传播是有向的，有一个信息传播是有向的，有一个“根根”。信息传播途径（忽略方向时）是一

8、棵树。信息传播途径（忽略方向时）是一棵树。以上结构称为树形图，上面这样一类问题称为最小树形图问题以上结构称为树形图，上面这样一类问题称为最小树形图问题.例：例：信息传播信息传播最小树形图 例11例例 最短路问题（最短路问题（SPP-Shortest Path Problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地往乙地.从甲地到乙地的公路网纵横交错，因此有多种行车从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问

9、题相当于需要找到一条从甲地到度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路乙地的最短路.网络优化问题的例子网络优化问题的例子 A A F F 5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 12例：计划评审技术例：计划评审技术,即即PERT(Project Evaluation&PERT(Project Evaluation&Review Technique),Review Technique),又称网络计划技术或统筹法又称网络计划技术或统筹法)大型复杂工程项目大型复杂工程项目(Project)(Project)往往被分成

10、许多子项目往往被分成许多子项目,子项目之子项目之间有一定的先后顺序间有一定的先后顺序(偏序偏序)要求要求,每一子项目需要一定的时间每一子项目需要一定的时间完成完成.PERT.PERT网络的每条弧表示一个子项目网络的每条弧表示一个子项目,如果以弧长表示每一如果以弧长表示每一子项目需要的时间子项目需要的时间,则最早完工时间对应于网络中的最长路则最早完工时间对应于网络中的最长路 (关关键路线键路线).).工程上所谓的关键路线法工程上所谓的关键路线法(CPM:Critical Path(CPM:Critical Path Method)Method)基本上也是计划评审技术的一部分基本上也是计划评审技术

11、的一部分.项目网络不含圈（其最长路问题和最短路问题都是可解的）项目网络不含圈（其最长路问题和最短路问题都是可解的）(开始开始)A)A F(F(结束结束)5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 13例：最大流例：最大流 /最小费用流最小费用流从甲地到乙地的公路网纵横交错，每天每条路上的通从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限车量有上限.从甲地到乙地的每天最多能通车多少辆从甲地到乙地的每天最多能通车多少辆?考虑每条路上的通行成本考虑每条路上的通行成本,如何确定某个车队的具体行如何确定某个车队的具体行车路线车路线,使总

12、成本最小使总成本最小?(甲甲)A)A F (F (乙乙)5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 14例：例：运输问题运输问题(Transportation Problem)某种原材料有某种原材料有M个产地，现在需要将原材料从产地运往个产地，现在需要将原材料从产地运往N个个使用这些原材料的工厂使用这些原材料的工厂.假定假定M个产地的产量和个产地的产量和N家工厂的家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？知，那么如何安排运输

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

14、题费用流问题（二部图，（二部图，|S|=|T|=N）16最小费用流模型的特例及扩展最小费用流模型的特例及扩展 最 小 费 用 流 问 题指 派问 题运 输问 题最大流问题最短路问题带 增 益 的最小费用流问题线性规划问题凹费用网络的最小费用流问题凸费用网络的最小费用流问题狭义模型 广义模型 凸规划 17例：匹配例：匹配问题问题(Matching Problem)在一次有在一次有m个大学毕业生和个大学毕业生和n家公司参加的供需见面会上，家公司参加的供需见面会上，每个毕业生愿意加入到若干家公司中的一家工作，而每个每个毕业生愿意加入到若干家公司中的一家工作，而每个公司愿意接收若干毕业生中的一人到公司

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

16、破圈法破圈法-复杂度高复杂度高 避圈法避圈法-贪婪算法贪婪算法(Greedy Algorithm)Kruskal 算法（算法（1956）Prim 算法（算法（1957）：即：即“边割法边割法”Dijkstra算法（算法（1959）Sollin 算法算法（1961）最小（生成）树算法最小（生成）树算法19最小树形图算法：最小树形图算法：朱朱(永津永津)-刘刘(振宏振宏)算法（算法（1965）最大分枝最大分枝算法：算法：Edmons算法（算法（1968）基本思想：收缩基本思想：收缩 展开展开 20n 无圈网络：拓扑排序无圈网络：拓扑排序 +动态规划动态规划圈的检测圈的检测n 正费用网络：正费用网络

17、：Dijkstra算法（算法（1959）n 一般网络，单一起点（或终点）一般网络，单一起点（或终点）Bellman-Ford算法算法(1956)：O(mn)n 一般网络，所有点对一般网络，所有点对Floyd-Warshall算法算法(1962)：O(n3)n 负圈检测负圈检测最短路最短路算法：标号设定算法：标号设定/修正算法修正算法21n 增广路算法增广路算法Ford-Fulkerson标号算法标号算法(1956)最大容量增广路算法最大容量增广路算法容量变尺度算法容量变尺度算法最短增广路算法：最短增广路算法：O(n2m)n 预流推进算法预流推进算法最高标号预流推进算法最高标号预流推进算法：O(

18、n2m1/2)最大流最大流算法算法实际计算效率高22n 消圈算法消圈算法n 最小费用路算法最小费用路算法n 原始原始-对偶算法对偶算法Ford和和Forkerson(1957,1962)n 瑕疵算法瑕疵算法(Out-Of-Kilter Algorithm)n 松弛松弛(Relaxation)算法算法n 网络单纯形算法网络单纯形算法最小费用流最小费用流算法算法实际计算效率高23n 二部基数匹配二部基数匹配增广路算法：增广路算法：O(mn)简单网络上的最大流算法：简单网络上的最大流算法：O(mn1/2)n 一般基数匹配一般基数匹配“花花”算法算法:O(n3)n 二部赋权匹配（指派问题）二部赋权匹配

19、（指派问题）最小费用流算法（如匈牙利算法）最小费用流算法（如匈牙利算法）:O(n3)n 一般赋权匹配一般赋权匹配原始原始-对偶算法对偶算法:O(n3)匹配匹配算法算法24网络优化的评注 许多实际问题可以直接用网络优化建模 许多实际问题可能用到网络优化建模 许多实际问题是网络优化的变种 网络优化问题通常可以用整数规划建模25西气东送（钢管运输）问题西气东送（钢管运输）问题（CUMCM-2000B)A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306019520272

20、0690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程300301350351400401450451500运价202326293226西气东送（钢管运输）问题西气东送（钢管运输）问题（CUMCM-2000B)二次规划（常用解法）二次规划（常用解法）最小费用流问题？最小费用流问题？（清华大学队，获网易杯）（清华大学队，获网易杯）线性模型（网络规模较大，有现成算法）线性模型（网络规模较大，有现成算法）非线性模型（网络规模较小，需要自己设计算法）非线性模型（

21、网络规模较小，需要自己设计算法）基本问题基本问题-最小运费矩阵的计算最小运费矩阵的计算两种运输方式（铁路公路）混合最短路问题两种运输方式（铁路公路）混合最短路问题是普通最短路问题的变种，需要自己设计算法是普通最短路问题的变种，需要自己设计算法27铁路公路混合运输最短路问题铁路公路混合运输最短路问题 最小运费矩阵算法（四川大学最小运费矩阵算法（四川大学/清华大学等队）清华大学等队）Dijkstra算法算法 或或 Floyd-Warshall算法算法 铁路最短路问题铁路最短路问题最短路最短路 =铁路最小运费矩阵铁路最小运费矩阵 公路最短路问题公路最短路问题最短路最短路 =公路最小运费矩阵公路最小运

22、费矩阵 铁路铁路/公路混合运输最短路问题公路混合运输最短路问题铁路铁路/公路混合运输网络公路混合运输网络最短路最短路 =铁路铁路/公路混合运输最小运费矩阵公路混合运输最小运费矩阵28例：中国邮递员问题例：中国邮递员问题(CPP-Chinese Postman Problem)一名邮递员负责投递某个街区的邮件一名邮递员负责投递某个街区的邮件.如何设计一条最短如何设计一条最短的投递路线的投递路线(从邮局出发，经过投递区内每条街道至少一次，从邮局出发，经过投递区内每条街道至少一次，最后返回邮局最后返回邮局)？由于这一问题是我国学者？由于这一问题是我国学者管梅谷管梅谷教授教授19601960年首先提出

23、的，所以国际上称之为中国邮递员问题年首先提出的，所以国际上称之为中国邮递员问题.网络优化问题的其他例子网络优化问题的其他例子 单向？双向？风向？29例：例：旅行商问题旅行商问题(TSP-Traveling Salesman Problem)一名推销员准备前往若干城市推销产品一名推销员准备前往若干城市推销产品.如何为他如何为他(她她)设计设计一条最短的旅行路线一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，从驻地出发，经过每个城市恰好一次，最后返回驻地最后返回驻地)？这一问题的研究历史十分悠久，通常称之？这一问题的研究历史十分悠久，通常称之为旅行商问题为旅行商问题.网络优化问题的例子网络优

24、化问题的例子 BACDEFGHI30灾情巡视路线(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.42.50.00

25、91=1.0556单位单位A货币货币网络优化问题的例子网络优化问题的例子 可以变成检测负圈的可以变成检测负圈的问题问题现在假设给定了若干种货币及其两两之间的兑现在假设给定了若干种货币及其两两之间的兑换率，请你帮助找到换率，请你帮助找到一种一种套汇方式（或判定该外汇市套汇方式（或判定该外汇市场上不存在套汇的可能）。场上不存在套汇的可能）。32套汇套汇:46.42.50.0091=1.0556 1两边取倒数两边取倒数(乘积乘积1)，再取对数（求和，再取对数（求和0）可以变成检测负圈的问题可以变成检测负圈的问题套汇（套汇（Arbitrage）问题）问题化乘积为求和化乘积为求和的技术，也常用于的技术，

26、也常用于“可靠性可靠性问题问题”可能是完全有向图；可能是完全有向图；弧上的权就是汇率的倒数的对数值！弧上的权就是汇率的倒数的对数值！33例：例：逃生路线问题逃生路线问题n*n网格节点上有网格节点上有m个房间，逃到边上节点就算逃生成功个房间，逃到边上节点就算逃生成功如何规划逃生路线，使这些路线互不相交？如何规划逃生路线，使这些路线互不相交？网络优化问题的例子网络优化问题的例子 可以变成可以变成最大流问题最大流问题逃生逃生成功成功没有没有逃生逃生路线路线34m个房间是供应节点（源，供应量为）个房间是供应节点（源，供应量为）只有边上节点可以是吸收节点（汇，吸收量为只有边上节点可以是吸收节点（汇，吸收

27、量为）多源多汇，容易变成单源单汇多源多汇，容易变成单源单汇每条边容量为每条边容量为每个节点容量为（通过增加节点和边，变成边容量）每个节点容量为（通过增加节点和边，变成边容量）逃生路线问题逃生路线问题变成变成最大流问题最大流问题逃生逃生成功成功没有没有逃生逃生路线路线其他目标？其他目标？35例：例：空间实验问题空间实验问题某航天公司计划进行一次空间载人飞行，宇航员将在飞某航天公司计划进行一次空间载人飞行，宇航员将在飞行中进行一系列科学实验。目前该公司收到了多个不同行中进行一系列科学实验。目前该公司收到了多个不同的科学实验申请，完成每个实验要求携带相应的一种或的科学实验申请，完成每个实验要求携带相

28、应的一种或多种仪器设备（不同的实验所需要的仪器设备中有些可多种仪器设备（不同的实验所需要的仪器设备中有些可能是相同的，而另外有些可能是不同的）。能是相同的，而另外有些可能是不同的）。已知完成每个实验后公司所得到的相应报酬（不同实验已知完成每个实验后公司所得到的相应报酬（不同实验的报酬可能不同），并已知飞行器携带每种仪器设备的的报酬可能不同），并已知飞行器携带每种仪器设备的相应费用（不同仪器设备的费用可能不同）。相应费用（不同仪器设备的费用可能不同）。公司希望你帮助选定此次飞行究竟从事哪些科学实验，公司希望你帮助选定此次飞行究竟从事哪些科学实验，以及需要携带哪些仪器设备，使此次飞行的总利润最大以

29、及需要携带哪些仪器设备，使此次飞行的总利润最大（总利润（总利润=总报酬总费用）。总报酬总费用）。网络优化问题的例子网络优化问题的例子 可以变成可以变成最大流问题最大流问题36空间实验问题空间实验问题最大流最大流(最小割最小割)问题问题设备 实验n个实验(报酬pi)m类设备(成本ci)12m12ncipist计划有限割有限割的容量：TiiTiiiiTiiSiicppcpST37例例:学生分区学生分区问题问题假设某个城市分为假设某个城市分为L个区个区,每个区有若干男孩和若干女孩每个区有若干男孩和若干女孩需要上学需要上学.假设每个区有一所小学假设每个区有一所小学,每所小学所能容纳的学生总数已每所小学

30、所能容纳的学生总数已知知,并且按照规定并且按照规定,每所小学所能容纳的男孩和女孩比例每所小学所能容纳的男孩和女孩比例不能太大或太小不能太大或太小.假设每两个区之间的路程已知假设每两个区之间的路程已知(同一区内认为路程近似为同一区内认为路程近似为0),如何为需要上学的小孩分配学校如何为需要上学的小孩分配学校,使得所有小孩上学所使得所有小孩上学所走的总路程最少走的总路程最少?网络优化问题的例子网络优化问题的例子 可以变成可以变成最小费用流最小费用流的的问题问题38L=2为例：为例：bi 男孩；男孩；gi 女孩；女孩；ui 学校容量学校容量(p,q)男孩比例上下限；男孩比例上下限；dij距离距离学学

31、生生分分区区问问题题最小费用最小费用流问题流问题b1b2g1g2(0,u1)(0,u2)t),0(容量d11d12d21d22d11d12d21d22(pu1,qu1)(pu2,qu2),0(),0(费用为39例例:一类排序一类排序(Scheduling)问题问题某车间接受了某车间接受了p项不同的加工任务，要求在车间的项不同的加工任务，要求在车间的q台完台完全相同的机器上加工全相同的机器上加工每项任务所需要的加工时间是相同的，且只需要在其中每项任务所需要的加工时间是相同的，且只需要在其中的任何一台机器上加工完成即可的任何一台机器上加工完成即可每项任务在同一时刻不能在两个或两个以上的机器上加每项

32、任务在同一时刻不能在两个或两个以上的机器上加工，且每项任务的加工都必须一次完成（即一旦开始加工，且每项任务的加工都必须一次完成（即一旦开始加工，加工中不能间断工，加工中不能间断每台机器在同一时刻不能加工两项或两项以上的任务每台机器在同一时刻不能加工两项或两项以上的任务从当前时刻开始计时，如果第从当前时刻开始计时，如果第 j 项任务的完工时间为项任务的完工时间为tj，则该车间的信誉损失为则该车间的信誉损失为cj(tj)（假设该函数为增函数）（假设该函数为增函数）车间希望制订一个加工计划，使总的信誉损失最小车间希望制订一个加工计划，使总的信誉损失最小网络优化问题的例子网络优化问题的例子 可以变成可

33、以变成最小费用流最小费用流的的问题问题40一类排序一类排序(Scheduling)问题问题12p12r111-q-q-q p个工件；q台机器;加工时间ac1(a)c1(2a)c1(ra)c2(a)c2(2a)cp(2a)c2(ra)cp(a)cp(ra)每台机器加工的工件数：r=p/q(不妨设为整数)工件加工位置变成变成最小费用流最小费用流的的问题问题41网络优化问题的例子网络优化问题的例子 例例 稳定婚配问题稳定婚配问题(Stable Marriage Problem)假设有假设有n个男人和个男人和n个女人个女人,每人都希望从每人都希望从n个异性中选择一位个异性中选择一位自己的配偶自己的配偶

34、.假设每人都对假设每人都对n个异性根据自己的偏好进行了排个异性根据自己的偏好进行了排序序,以此作为选择配偶的基础以此作为选择配偶的基础.当给定一种婚配方案当给定一种婚配方案(即给每人即给每人指定一个配偶指定一个配偶)后后,如果存在一个男人和一个女人不是互为配如果存在一个男人和一个女人不是互为配偶偶,但该男人喜欢该女人胜过其配偶但该男人喜欢该女人胜过其配偶,且该女人喜欢该男人也且该女人喜欢该男人也胜过其配偶胜过其配偶,则该婚配方案称为不稳定的则该婚配方案称为不稳定的.安排稳定的婚配方安排稳定的婚配方案的问题称为案的问题称为稳定婚配问题稳定婚配问题。二部完美匹配二部完美匹配存在性？算法？其他目标42MCM中的一些网络优化问题 1999 1999 扫雪车扫雪车问题问题1991 Steiner1991 Steiner树问题树问题1994 1994 通讯网络问题通讯网络问题2000 2000 无线信道分配问题无线信道分配问题?43Thats all.Any Questions?Thank you for your attendance!最后，祝大家在数学建模活动中不断提高综合素质，在数学建模竞赛中取得更好的成绩！