网络优化模型与算法.ppt

1 网络优化模型与算法 networkoptimization models algorithms 2 outline whatisnetworkoptimization typicalmodels algorithmsminimumspanningtree 最小 生成 树 minimumarborescence 最小树形图 shortestpath 最短路 maximumflow 最大流 minimumcostflow 最小费用流 matching 匹配 somemodelingexamples 3 网络优化简介 网络 网络社会 计算机信息网络 电话通信网络运输服务网络能源和物质分派网络人际关系网络等等 网络优化就是研究如何有效地计划 管理和控制网络系统 使之发挥最大的社会和经济效益 4 网络优化简介 网络 network 数学模型 数学结构 图 优化 optimization 从若干可能的方案中寻求某种意义下的最优方案 与图论有联系 也有区别 侧重点不同 网络优化就是研究与 赋权 图有关的最优化问题 图论 图的性质 网络优化 与 赋权 图有关的优化问题 组合数学 组合优化 5 optimizationtreehttp 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 图与网络 基本概念 图g v a 其中顶点集v 弧集a 弧 8 例 公路连接问题某一地区有若干个主要城市 现准备修建高速公路把这些城市连接起来 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市 假定已经知道了任意两个城市之间修建高速公路的成本 那么应如何决定在哪些城市间修建高速公路 使得总成本最小 网络优化问题的例子 最小 生成 树也称为最小 支撑 树 9 例 二维矩阵数据存贮问题某些蛋白质的氨基酸序列差异不多 如果用二维矩阵的每一行记录一种蛋白质氨基酸序列 行与行之间的差异很小 其中一种方法是只存贮其中一行作为参照行 再存贮行与行之间的一部分差异信息 使得我们可以在需要时根据参照行生成所有其它行的元素 r1 r3 r2 r4 c13 c12 c24 最小树 网络优化问题的例子 10 直接方式 总经理直接传达 接力方式 总经理只给某些部门经理打电话 而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理 依此类推 最后将信息传达到所有部门经理 如何决定传达信息的途径 信息传播是有向的 有一个 根 信息传播途径 忽略方向时 是一棵树 以上结构称为树形图 上面这样一类问题称为最小树形图问题 例 信息传播 最小树形图 例 11 例最短路问题 spp shortestpathproblem 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地 从甲地到乙地的公路网纵横交错 因此有多种行车路线 这名司机应选择哪条线路呢 假设货柜车的运行速度是恒定的 那么这一问题相当于需要找到一条从甲地到乙地的最短路 网络优化问题的例子 12 例 计划评审技术 即pert projectevaluation reviewtechnique 又称网络计划技术或统筹法 大型复杂工程项目 project 往往被分成许多子项目 子项目之间有一定的先后顺序 偏序 要求 每一子项目需要一定的时间完成 pert网络的每条弧表示一个子项目 如果以弧长表示每一子项目需要的时间 则最早完工时间对应于网络中的最长路 关键路线 工程上所谓的关键路线法 cpm criticalpathmethod 基本上也是计划评审技术的一部分 项目网络不含圈 其最长路问题和最短路问题都是可解的 13 例 最大流 最小费用流 从甲地到乙地的公路网纵横交错 每天每条路上的通车量有上限 从甲地到乙地的每天最多能通车多少辆 考虑每条路上的通行成本 如何确定某个车队的具体行车路线 使总成本最小 14 例 运输问题 transportationproblem 某种原材料有m个产地 现在需要将原材料从产地运往n个使用这些原材料的工厂 假定m个产地的产量和n家工厂的需要量已知 单位产品从任一产地到任一工厂的的运费已知 那么如何安排运输方案可以使总运输成本最低 网络优化问题的例子 特殊的最小费用流问题 二部图 s m t n 15 例 指派问题 assignmentproblem 一家公司经理准备安排n名员工去完成n项任务 每人一项 由于各员工的特点不同 不同的员工去完成同一项任务时所获得的回报是不同的 如何分配工作方案可以使总回报最大 网络优化问题的例子 特殊的最小费用流问题 二部图 s t n 16 最小费用流模型的特例及扩展 最小费用流问题 狭义模型 广义模型 17 例 匹配问题 matchingproblem 在一次有m个大学毕业生和n家公司参加的供需见面会上 每个毕业生愿意加入到若干家公司中的一家工作 而每个公司愿意接收若干毕业生中的一人到公司工作 那么 最后最多有多少人可以在这次供需见面会上找到工作 即最多有多少家公司可以在这次供需见面会上招聘到员工 如果每个毕业生到每一家公司工作将会产生的效益不同 那么 为了使得最后产生的总效益最大 最多有多少人可以在这次供需见面会上找到工作 网络优化问题的例子 二部基数 赋权匹配 18 破圈法 复杂度高避圈法 贪婪算法 greedyalgorithm kruskal算法 1956 prim算法 1957 即 边割法 dijkstra算法 1959 sollin算法 1961 最小 生成 树算法 19 最小树形图算法 朱 永津 刘 振宏 算法 1965 最大分枝算法 edmons算法 1968 基本思想 收缩 展开 20 无圈网络 拓扑排序 动态规划圈的检测正费用网络 dijkstra算法 1959 一般网络 单一起点 或终点 bellman ford算法 1956 o mn 一般网络 所有点对floyd warshall算法 1962 o n3 负圈检测 最短路算法 标号设定 修正算法 21 增广路算法ford fulkerson标号算法 1956 最大容量增广路算法容量变尺度算法最短增广路算法 o n2m 预流推进算法最高标号预流推进算法 o n2m1 2 最大流算法 22 消圈算法最小费用路算法原始 对偶算法ford和forkerson 1957 1962 瑕疵算法 out of kilteralgorithm 松弛 relaxation 算法网络单纯形算法 最小费用流算法 23 二部基数匹配增广路算法 o mn 简单网络上的最大流算法 o mn1 2 一般基数匹配 花 算法 o n3 二部赋权匹配 指派问题 最小费用流算法 如匈牙利算法 o n3 一般赋权匹配原始 对偶算法 o n3 匹配算法 24 网络优化的评注 许多实际问题可以直接用网络优化建模许多实际问题可能用到网络优化建模许多实际问题是网络优化的变种网络优化问题通常可以用整数规划建模 25 西气东送 钢管运输 问题 cumcm 2000b 铁路运价表 26 西气东送 钢管运输 问题 cumcm 2000b 二次规划 常用解法 最小费用流问题 清华大学队 获网易杯 线性模型 网络规模较大 有现成算法 非线性模型 网络规模较小 需要自己设计算法 基本问题 最小运费矩阵的计算两种运输方式 铁路 公路 混合最短路问题是普通最短路问题的变种 需要自己设计算法 27 铁路 公路混合运输最短路问题 最小运费矩阵算法 四川大学 清华大学等队 dijkstra算法或floyd warshall算法铁路最短路问题最短路 铁路最小运费矩阵公路最短路问题最短路 公路最小运费矩阵铁路 公路混合运输最短路问题铁路 公路混合运输网络最短路 铁路 公路混合运输最小运费矩阵 28 例 中国邮递员问题 cpp chinesepostmanproblem 一名邮递员负责投递某个街区的邮件 如何设计一条最短的投递路线 从邮局出发 经过投递区内每条街道至少一次 最后返回邮局 由于这一问题是我国学者管梅谷教授1960年首先提出的 所以国际上称之为中国邮递员问题 网络优化问题的其他例子 单向 双向 风向 29 例 旅行商问题 tsp travelingsalesmanproblem 一名推销员准备前往若干城市推销产品 如何为他 她 设计一条最短的旅行路线 从驻地出发 经过每个城市恰好一次 最后返回驻地 这一问题的研究历史十分悠久 通常称之为旅行商问题 网络优化问题的例子 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 套汇 46 4 2 5 0 0091 1 0556 1两边取倒数 乘积 1 再取对数 求和 0 可以变成检测负圈的问题 套汇 arbitrage 问题 化乘积为求和的技术 也常用于 可靠性问题 可能是完全有向图 弧上的权就是汇率的倒数的对数值 33 例 逃生路线问题n n网格节点上有m个房间 逃到边上节点就算逃生成功如何规划逃生路线 使这些路线互不相交 网络优化问题的例子 可以变成最大流问题 34 m个房间是供应节点 源 供应量为 只有边上节点可以是吸收节点 汇 吸收量为 多源多汇 容易变成单源单汇每条边容量为 每个节点容量为 通过增加节点和边 变成边容量 逃生路线问题 变成最大流问题 其他目标 35 例 空间实验问题某航天公司计划进行一次空间载人飞行 宇航员将在飞行中进行一系列科学实验 目前该公司收到了多个不同的科学实验申请 完成每个实验要求携带相应的一种或多种仪器设备 不同的实验所需要的仪器设备中有些可能是相同的 而另外有些可能是不同的 已知完成每个实验后公司所得到的相应报酬 不同实验的报酬可能不同 并已知飞行器携带每种仪器设备的相应费用 不同仪器设备的费用可能不同 公司希望你帮助选定此次飞行究竟从事哪些科学实验 以及需要携带哪些仪器设备 使此次飞行的总利润最大 总利润 总报酬 总费用 网络优化问题的例子 可以变成最大流问题 36 空间实验问题 最大流 最小割 问题 设备实验 n个实验 报酬pi m类设备 成本ci 计划 有限割有限割的容量 37 例 学生分区问题假设某个城市分为l个区 每个区有若干男孩和若干女孩需要上学 假设每个区有一所小学 每所小学所能容纳的学生总数已知 并且按照规定 每所小学所能容纳的男孩和女孩比例不能太大或太小 假设每两个区之间的路程已知 同一区内认为路程近似为0 如何为需要上学的小孩分配学校 使得所有小孩上学所走的总路程最少 网络优化问题的例子 可以变成最小费用流的问题 38 l 2为例 bi男孩 gi女孩 ui学校容量 p q 男孩比例上下限 dij距离 学生分区问题 最小费用流问题 b1b2g1g2 0 u1 0 u2 t 容量 d11d12d21d22d11d12d21d22 pu1 qu1 pu2 qu2 费用为 39 例 一类排序 scheduling 问题某车间接受了p项不同的加工任务 要求在车间的q台完全相同的机器上加工每项任务所需要的加工时间是相同的 且只需要在其中的任何一台机器上加工完成即可每项任务在同一时刻不能在两个或两个以上的机器上加工 且每项任务的加工都必须一次完成 即一旦开始加工 加工中不能间断每台机器在同一时刻不能加工两项或两项以上的任务从当前时刻开始计时 如果第j项任务的完工时间为tj 则该车间的信誉损失为cj tj 假设该函数为增函数 车间希望制订一个加工计划 使总的信誉损失最小 网络优化问题的例子 可以变成最小费用流的问题 40 一类排序 scheduling 问题 p个工件 q台机器 加工时间a 每台机器加工的工件数 r p q 不妨设为整数 工件加工位置 变成最小费用流的问题 41 网络优化问题的例子 例稳定婚配问题 stablemarriageproblem 假设有n个男人和n个女人 每人都希望从n个异性中选择一位自己的配偶 假设每人都对n个异性根据自己的偏好进行了排序 以此作为选择配