Chapter 7 Network Optimization Problems 更加有效地解决大规模的 网络最优化问题 最小费用流问题P246 网络单纯法( Network Simplex Method): 可以用于解决大型的运输问题 现在,许多公司都使用网络单纯法来解决他 们的最小费用流问题。有些问题是非常庞大 的,有着数万个节点和弧。有时,弧的数量 甚至可能会多得多,达到几百万条。 但 Excel“规划求解”软件中没有网络单纯法 但其他的线性规划的商业软件包通常都有 这种方法。 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 更加有效地解决大规模的 最小费用流问题 P246 ▪ 网络单纯法（Network Simplex Method）： 可以用于解决大型的运输问题 ▪ 现在，许多公司都使用网络单纯法来解决他 们的最小费用流问题。有些问题是非常庞大 的，有着数万个节点和弧。有时，弧的数量 甚至可能会多得多，达到几百万条。 ▪ 但Excel “规划求解”软件中没有网络单纯法 ，但其他的线性规划的商业软件包通常都有 这种方法
Some applications Chapter 7 些实际应用P247 Network Optimization Problems 网络最优化问题 表71几类典型的最小费用流问题的应用 应用类型供应点转运点需求点 配送网络的运作货源 中间存储设施客户 固体废弃物管理固体废弃物源处理设施 固体废弃物掩埋地 供应网络的运作供应商 中间仓库 加工设备 工厂协调产品组合工厂 某一特定产品某一特定产品的市场 的生产 现金流管理 某一特定时间短期投资期权在特定时间对现金的 的现金来源 需求 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 Some Applications 一些实际应用 P247 应用类型 供应点 转运点 需求点 配送网络的运作 货源 中间存储设施 客户 固体废弃物管理 固体废弃物源 处理设施 固体废弃物掩埋地 供应网络的运作 供应商 中间仓库 加工设备 工厂协调产品组合 工厂 某一特定产品 的生产 某一特定产品的市场 现金流管理 某一特定时间 的现金来源 短期投资期权 在特定时间对现金的 需求 表7.1 几类典型的最小费用流问题的应用
Chapter 7 Network Optimization Problems Some applications 网络最优化问题 些实际应用P247 国际纸业公司( International Paper Company 配送网络( interfaces1988年3-4) 世界上最大的纸浆、纸和纸类产品的制造商以及木材 和夹板的主要生产者。拥有2000万英亩的林区或其权 益。分布在不同地方的林区是它配送网络的供应点。 但是,在公司的产品最终到达需求点(客户)以前, 供应流必须经过一系列很长的转运点。它通过配送网 络的一条典型的路径就是: 林区→木材堆积场→锯木厂→造纸厂 →纸制品加工厂→仓库→客户 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 Some Applications 一些实际应用 P247 国际纸业公司（International Paper Company） 配送网络（Interfaces 1988年3~4） 世界上最大的纸浆、纸和纸类产品的制造商以及木材 和夹板的主要生产者。拥有2000万英亩的林区或其权 益。分布在不同地方的林区是它配送网络的供应点。 但是，在公司的产品最终到达需求点（客户）以前， 供应流必须经过一系列很长的转运点。它通过配送网 络的一条典型的路径就是： 林区→木材堆积场→锯木厂→造纸厂 →纸制品加工厂→仓库→客户
Chapter 7 Network Optimization Problems Some applications 网络最优化问题 些实际应用P248 马歇尔公司( Marshalls,Inc.) 配送网络( Interfaces1987年7~8) 家折扣连锁零售店,现在和以前是如何使 用微型计算机去处理一个最小费用流问题。 应用中公司力图使得从供应商到加工中心, 再从加工中心到零售店的商流最优。其中的 些网络有超过20,000条弧。 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 Some Applications 一些实际应用 P248 马歇尔公司（Marshalls, Inc.） 配送网络（Interfaces 1987年7～8） 一家折扣连锁零售店，现在和以前是如何使 用微型计算机去处理一个最小费用流问题。 应用中公司力图使得从供应商到加工中心， 再从加工中心到零售店的商流最优。其中的 一些网络有超过20,000条弧
Some applications Chapter 7 一些实际应用P248 Network Optimization Problems 现金流管理(动态规划问题) 网络最优化问题 不同的节点可以代表发生在不同时间的事件。在这个 应用中,每一个供应点代表了一个特定的时间(或 个时期),在这个时间的供应量就是那时所能得到的 现金量。同理,每个需求点代表了某个特定的时间 或时期)公司所需的现金储备。每个需求点的需求量 就是到时所需要的现金量。 目标:使得公司在每个从有现金闲置到有现金需求期 间的现金投资所得收入最大。 因此,每个转运点代表在特定的时间间隔里对一种特 定的短期投资期权(如从银行购买存款单)的选择 得到的网络将有一个连续流,代表了从有现金闲置、 投资现金到在投资到期后利用现金的计划。 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 Some Applications 一些实际应用 P248 现金流管理（动态规划问题） 不同的节点可以代表发生在不同时间的事件。在这个 应用中，每一个供应点代表了一个特定的时间（或一 个时期），在这个时间的供应量就是那时所能得到的 现金量。同理，每个需求点代表了某个特定的时间（ 或时期）公司所需的现金储备。每个需求点的需求量 就是到时所需要的现金量。 目标：使得公司在每个从有现金闲置到有现金需求期 间的现金投资所得收入最大。 因此，每个转运点代表在特定的时间间隔里对一种特 定的短期投资期权（如从银行购买存款单）的选择。 得到的网络将有一个连续流，代表了从有现金闲置、 投资现金到在投资到期后利用现金的计划