网络优化问题的例子 例最短路问题( SPP-Shortest Path Problen) 名货柜车司机奉命在最短的时间内将一车货物从甲地运 往乙地.从甲地到乙地的公路网纵横交错,因此有多种行车 路线,这名司机应选择哪条线路呢?假设货柜车的运行速 度是恒定的,那么这一问题相当于需要找到一条从甲地到 乙地的最短路 B 6 4 4 5 3 E
11 例 最短路问题（SPP-Shortest Path Problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运 往乙地. 从甲地到乙地的公路网纵横交错，因此有多种行车 路线，这名司机应选择哪条线路呢？假设货柜车的运行速 度是恒定的，那么这一问题相当于需要找到一条从甲地到 乙地的最短路. 网络优化问题的例子 A F 5 6 6 7 4 4 5 1 3 B E D C
例:计划评审技术,即PERT( Project Evaluation& Review Technique),又称网络计划技术或统筹法) 大型复杂工程项目( Project)往往被分成许多子项目,子项目之 间有一定的先后顺序(偏序)要求,每一子项目需要一定的时间 完成.PERT网络的每条弧表示一个子项目,如果以弧长表示每 子项目需要的时间,则最早完工时间对应于网络中的最长路 (关键路线).工程上所谓的关键路线法(CPM: Critical path Method)基本上也是计划评审技术的一部分 64 (开始)A (结束) 3 项目网络不含圈(其最长路问题和最短路问题都是可解的)
12 例：计划评审技术, 即PERT(Project Evaluation & Review Technique), 又称网络计划技术或统筹法) 大型复杂工程项目(Project)往往被分成许多子项目,子项目之 间有一定的先后顺序(偏序)要求, 每一子项目需要一定的时间 完成. PERT网络的每条弧表示一个子项目,如果以弧长表示每 一子项目需要的时间,则最早完工时间对应于网络中的最长路 (关键路线). 工程上所谓的关键路线法(CPM: Critical Path Method)基本上也是计划评审技术的一部分. 项目网络不含圈（其最长路问题和最短路问题都是可解的） (开始) A F (结束) 5 6 6 7 4 4 5 1 3 B E D C
例:最大流/最小费用流 从甲地到乙地的公路网纵横交错,每天每条路上的通 车量有上限.从甲地到乙地的每天最多能通车多少辆? 6 6 (甲)A4 )(乙) 5 C 3也 考虑每条路上的通行成本,如何确定某个车队的具体行 车路线,使总成本最小?
13 例：最大流 / 最小费用流 从甲地到乙地的公路网纵横交错，每天每条路上的通 车量有上限. 从甲地到乙地的每天最多能通车多少辆? 考虑每条路上的通行成本,如何确定某个车队的具体行 车路线,使总成本最小? (甲) A F (乙) 5 6 6 7 4 4 5 1 3 B E D C
网络优化问题的例子 例:运输问题( Transportation Problem) 某种原材料有M个产地,现在需要将原材料从产地运往N个 使用这些原材料的工厂.假定M个产地的产量和N家工厂的 需要量已知,单位产品从任一产地到任一工厂的的运费已 知,那么如何安排运输方案可以使总运输成本最低? 特殊的最小费 T 用流问题 (二部图, S|=M,T|=N)
14 例： 运输问题(Transportation Problem) 某种原材料有M个产地，现在需要将原材料从产地运往N个 使用这些原材料的工厂. 假定M个产地的产量和N家工厂的 需要量已知，单位产品从任一产地到任一工厂的的运费已 知，那么如何安排运输方案可以使总运输成本最低？ 网络优化问题的例子 S T 特殊的最小费 用流问题 （二部图, |S|=M, |T|=N）