Chapter 7 Network Optimization Problems 最小费用流问题的特殊类型P248网络最优化问题 (五种重要的类型) 1.运输问题:有出发地供应点供应量和目的地需求点需求量 没有转运点和弧的容量限制,目标:总运输成本最小(或总利润最 2.指派类型:出发地供应点供应量为)是人,目的地需求点需求 量为1)是任务,没有转运点和弧的容量限制,目标:总指派成本最 小(或总莉润最大) 3.转运问题:有出发地(供应点供应量和目的地需求点需求量 有转运点,但没有孤的容量限制或有容量限制),目标:总流量费 角最小(或总莉润最大) 4.最大问题有侏应点、需求点转运点弧的容量限制售没 有供应量和需求量的限制,自标:通过网络到自的地的总流量最大 5.最短路问题、有供应点供应量为1)、需求点需求量为1)、转 点、没有弧的容量限制,目标:通过网络到目的地的总距离最短 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 最小费用流问题的特殊类型 P248 （五种重要的类型） 1. 运输问题：有出发地(供应点-供应量)和目的地(需求点-需求量)， 没有转运点和弧的容量限制，目标：总运输成本最小（或总利润最 大） 2. 指派类型：出发地(供应点-供应量为1)是人，目的地(需求点-需求 量为1)是任务，没有转运点和弧的容量限制，目标：总指派成本最 小（或总利润最大） 3. 转运问题：有出发地(供应点-供应量)和目的地(需求点-需求量)， 有转运点，但没有弧的容量限制(或有容量限制)，目标：总流量费 用最小（或总利润最大） 4. 最大流问题：有供应点、需求点、转运点、弧的容量限制，但没 有供应量和需求量的限制，目标：通过网络到目的地的总流量最大 5. 最短路问题：有供应点(供应量为1) 、需求点(需求量为1) 、转运 点、没有弧的容量限制，目标：通过网络到目的地的总距离最短
Chapter 7 Network Optimization Problems 7.2 BMZ Case Study 网络最优化问题 案例研究:BMZ公司的最大流问题P249 BMZ公司从德国斯图 加特的工厂到洛杉矶的 配送中心的配送网络图 Ro Rotterdam nIts max 50 units max New York(Nrk 40 units max 70 units max ST) Stuttgart Bordeaux 40 units max max max. New Orlean Los Angeles Lis bon K70 units maxTINo mits max. RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 7. 2 BMZ Case Study 案例研究：BMZ 公司的最大流问题P249 • BMZ公司从德国斯图 加特的工厂到洛杉矶的 配送中心的配送网络图 ST L I BO RO NO NY L A New York Rotterdam Stuttgart Lisbon New Orleans {40 units max.] Bordeaux [70 units max.] Los Angeles [80 units max.] [60 units max.] [50 units max.] [30 units max.] [50 units max.] [40 units max.] [70 units max]
Chapter 7 Network Optimization Problems 网络最优化问题 作为最大流问题的BMZ 问题的网络模型P252 [60] [50 1801 40] BO [7O [50] RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 作为最大流问题的BMZ 问题的网络模型P252 ST L I BO RO NO NY L A [70] [80] [70] [60] [40] [50] [30] [50] [40]