1网络优化模型与算法NetworkOptimization:Models&Algorithms清华大学数学科学系谢金星Email:jxie@math.tsinghua.edu.cnhttp://faculty.math.tsinghua.edu.cn/~jxie2004年7月~8月----江西庐山2Outline•WhatisNetworkOptimization?•TypicalModels&Algorithms–MinimumSpanningTree(最小(生成)树)–MinimumArborescence(最小树形图)–ShortestPath(最短路)–MaximumFlow(最大流)–MinimumCostFlow(最小费用流)–Matching(匹配)–……•SomeModelingExamples3网络优化简介•网络：网络社会----计算机信息网络？电话通信网络运输服务网络能源和物质分派网络人际关系网络等等网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益4网络优化简介•网络(Network)：数学模型、数学结构----图•优化(Optimization):从若干可能的方案中寻求某种意义下的最优方案•与图论有联系，也有区别（侧重点不同）•网络优化就是研究与（赋权）图有关的最优化问题图论：图的性质网络优化：与（赋权）图有关的优化问题组合数学组合优化5OptimizationTreehttp://www-fp.mcs.anl.gov/otc/Guide/OptWeb/6网络优化简介主要参考书：•谢金星、邢文训，《网络优化》，清华大学出版社，2000年8月；2003年9月。•Ahuja,R.K.,MagnantiT.L.,OrlinJ.B.NetworkFlows:Theory,Algorithms,andApplications.PrenticeHall,1993:EnglewoodCliffs,NewJersey.网络优化模型网络优化算法及其复杂性《网络优化》或《网络流》（NetworkFlows)或《网络规划》（NetworkProgramming)7图与网络–基本概念5a1a1v2v3a3v4a4v5v2a6a图G=(V，A)，其中顶点集V=弧集A=弧},,,,{54321vvvvv},,,,,{654321aaaaaa),(211vva),(212vva),(323vva),(434vva),(145vva),(336vva8例：公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？网络优化问题的例子1132546385247最小(生成)树也称为最小(支撑)树9例：二维矩阵数据存贮问题某些蛋白质的氨基酸序列差异不多，如果用二维矩阵的每一行记录一种蛋白质氨基酸序列，行与行之间的差异很小.其中一种方法是只存贮其中一行作为参照行，再存贮行与行之间的一部分差异信息，使得我们可以在需要时根据参照行生成所有其它行的元素.R1R3R2R4C13C12C24最小树网络优化问题的例子10“直接方式”：总经理直接传达；“接力方式”：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理.如何决定传达信息的途径？信息传播是有向的，有一个“根”。信息传播途径（忽略方向时）是一棵树。以上结构称为树形图，上面这样一类问题称为最小树形图问题.例：信息传播最小树形图–例11例最短路问题（SPP-ShortestPathProblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地.从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路.网络优化问题的例子AF566744513BEDC12例：计划评审技术,即PERT(ProjectEvaluation&ReviewTechnique),又称网络计划技术或统筹法)大型复杂工程项目(Project)往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求,每一子项目需要一定的时间完成.PERT网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路(关键路线).工程上所谓的关键路线法(CPM:CriticalPathMethod)基本上也是计划评审技术的一部分.项目网络不含圈（其最长路问题和最短路问题都是可解的）(开始)AF(结束)566744513BEDC13例：最大流/最小费用流从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限.从甲地到乙地的每天最多能通车多少辆?考虑每条路上的通行成本,如何确定某个车队的具体行车路线,...
