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

网络优化
模型与算法Outline网络优化简介网络优化简介OptimizationTree
http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/网络优化简介图与网络–基本概念例：公路连接问题
某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？例：二维矩阵数据存贮问题
某些蛋白质的氨基酸序列差异不多，如果用二维矩阵的每一行记录一种蛋白质氨基酸序列，行与行之间的差异很小.其中一种方法是只存贮其中一行作为参照行，再存贮行与行之间的一部分差异信息，使得我们可以在需要时根据参照行生成所有其它行的元素.例最短路问题（SPP-ShortestPathProblem）
一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地.从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路.例：计划评审技术,即PERT(ProjectEvaluation&ReviewTechnique),又称网络计划技术或统筹法)例：最大流/最小费用流例：运输问题(TransportationProblem)
某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂.假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？例：指派问题(AssignmentProblem)
一家公司经理准备安排N名员工去完成N项任务，每人一项.由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的.如何分配工作方案可以使总回报最大？最小费用流模型的特例及扩展例：匹配问题(MatchingProblem)

在一次有m个大学毕业生和n家公司参加的供需见面会上，每个毕业生愿意加入到若干家公司中的一家工作，而每个公司愿意接收若干毕业生中的一人到公司工作.那么，最后最多有多少人可以在这次供需见面会上找到工作（即最多有多少家公司可以在这次供需见面会上招聘到员工）？如果每个毕业生到每一家公司工作将会产生的效益不同，那么，为了使得最后产生的总效益最大，最多有多少人可以在这次供需见面会上找到工作？破圈法-----复杂度高

避圈法----贪婪算法(GreedyAlgorithm)
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-KilterAlgorithm)
松弛(Relaxation)算法
网络单纯形算法二部基数匹配
增广路算法：O(mn)
简单网络上的最大流算法：O(mn1/2)

一般基数匹配
“花”算法:O(n3)

二部赋权匹配（指派问题）
最小费用流算法（如匈牙利算法）:O(n3)

一般赋权匹配
原始-对偶算法:O(n3)网络优化的评注西气东送（钢管运输）问题（CUMCM-2000B)西气东送（钢管运输）问题（CUMCM-2000B)铁路／公路混合运输最短路问题例：中国邮递员问题(CPP-ChinesePostmanProblem)
一名邮递员负责投递某个街区的邮件.如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.例：旅行商问题(TSP-TravelingSalesmanProblem)
一名推销员准备前往若干城市推销产品.如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.灾情巡视路线(CUMCM-1998B)例：套汇（Arbitrage）问题
在外汇市场上，将1单位的