运输、指派问题与网络最优化.ppt

《运输、指派问题与网络最优化.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Data,ModelandDecisions数据、模型与决策第四讲运输、指派问题与网络最优化主要内容P&T公司配送问题运输问题运输问题的特征运输问题的一个获奖应用各种运输问题变体特赛格公司的选地址问题指派问题指派问题模型指派问题的变形指派问题的应用主要内容主要内容飞利浦石油公司运输工具替换计划网络最优化模型的应用网络最优化问题类型最小费用流问题最短路问题最小支撑树问题配送问题P&T公司是一家由家族经营的小公司。它收购生菜并在食品罐头厂中把它们家工成罐头，然后在把这些罐头食品分销到各地。公司的一个主要产品是豌豆罐头，在

2、三个食品罐头厂生产（靠近华盛顿的贝林翰；俄勒冈州的尤基尼；明尼苏达州的艾尔贝李）然后用卡车把它们运送到美国西部的四个分销仓库（加利福尼亚州的萨克拉门托；犹他州的盐湖城；南达科他州的赖皮特城；新墨西哥州的澳尔巴古）。实际问题配送问题实际问题配送问题当前的当前的运输策略：1．因为在贝林翰的罐头厂距离仓库最远，所以把它的产品运送到最近的一个仓库。也就是萨克拉门托的那个仓库。如果还有剩余的话，就把它们运送到盐湖城的仓库中去。2．因为在澳尔巴古的仓库距离食品罐头厂最远，所以就要从最近的一个罐头厂（艾尔贝·李的罐头厂）中运送产品

3、到澳尔巴古。如果还有剩余的话，就要运送到赖皮特城的仓库中。3．用尤基尼的罐头厂满足其他仓库的剩余需求。实际问题配送问题现在所要做的是要检查当前的运输计划，看看是否能够制定出一个新的运输计划，使总运输成本下降到一个绝对最小值。实际问题运输问题是物流中的一个普遍问题，如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）运输问题运输问题运输问题运输问题P&T公司运输问题运输问题P&T公司运输问题运输问题P&T公司运输问题运输问题P&T公司运

4、输问题运输问题P&T公司运输问题Excel建模运输问题每一个出发地都有一定的供应量（supply）配送到目的地，每一个目的地都有需要从一定的需求量（demand），接收从出发地发出的产品需求假设（TheRequirementsAssumption）可行解特性（TheFeasibleSolutionsProperty）成本假设（TheCostAssumption）整数解性质（IntegerSolutionsProperty）运输问题的特征运输问题特征需求假设（TheRequirementsAssumption）：每一个

5、出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足需求假设运输问题特征可行解特性（TheFeasibleSolutionsProperty）：当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解可行解特性运输问题特征成本假设（TheCostAssumption）：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量成本假设运输问题特征整数解性质（Intege

6、rSolutionsProperty）：只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件整数解性质运输问题特征P&G重新设计制造和配送体系：90’S成百上千个供应商50多个产品类别超过60个的工厂15个配送中心超过1000个的顾客群体运输问题的一个获奖应用获奖应用为每个单独的产品种类设计并求解运输问题对于针对还在运行的工厂的每一个选择，为每一个产品种类解决相应的运输问题体现了从这些工厂运送产品到配送中心或顾客区所需要的配送成本是多少

7、。在找出最好的新生产和配送系统的过程之中解决了许多这样的运输问题北美工厂数减少了20%，并且公司每年节省了2亿美元的税前费用运输问题的一个获奖应用获奖应用供应总量超出了需求总量供应总量小于需求总量一个目的地同时存在着最小需求和最大需求在配送中不能使用特定的出发地——目的地组合目标是与配送量有关的总利润最大不是成本最小各种运输问题变形运输问题变形求佳产品公司决定使用三个有生产余力的工厂进行四种新产品的生产制造。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量。求佳公司指定工厂生产产品运

8、输问题变形求佳公司指定工厂生产产品运输问题变形耐芙迪公司选择顾客耐芙迪公司在三个工厂中专门生产一种产品。这种产品有着优良的品质，所以现在公司接到了许多的订单，产品供不应求。公司也正在努力扩大生产，甚至计划要建立一个新的工厂，但是这个新的工厂要到明年才能投人运营。在未来的四个月中，有四个处于国内不同区域的潜在顾客（批发商）很有可能大量订购。顾客1