运输问题和指派问题课件.ppt

《运输问题和指派问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运输问题和指派问题运输问题P&T公司是一家由家族经营的小公司。它收购生菜并在三个食品罐头厂（贝林翰、尤基尼、艾尔贝·李）中把它们加工成为罐头，再用卡车把这些罐头食品运送到美国西部的四个分销仓库（萨克拉门托、盐湖城、赖皮特城、奥尔巴古），然后再卖出去。对于即将来临的收获季节，每一个罐头厂的产量都进行了估计，并且每一个仓库都从罐头总供应量中分到了一定的比例，这些数据如表6.1所示，试问要制定怎样一个运输计划，才能使总运输成本最小？案例研究：P&T公司的配送问题表6.1P＆T公司的运输数据表（单位：车）罐头加工厂产量仓库分配量贝林翰尤基尼艾尔贝·李7

2、5125100萨克拉门托盐湖城赖皮特城奥尔巴古80657085合计300合计300表6.2P＆T公司的单位卡车的运输成本（单位：美元）至仓库萨克拉门托盐湖城赖皮特城奥尔巴古食品罐头厂贝林翰尤基尼艾尔贝·李464352995513416682654690388867791685从表6.3P＆T公司问题的参数表所有的这些数据都可总结在一个表格中，这个表格叫做参数表。P＆T公司问题的参数表如表6.3所示。目的地（仓库）单位成本（美元）萨克拉门托盐湖城赖皮特城奥尔巴古供应出发地（罐头厂）贝林翰尤基尼艾尔贝·李46435299551341668265469

3、038886779168575125100需求80657085各种运输问题变体的建模例1：指定工厂生产产品求佳产品公司决定使用三个有生产余力的工厂进行四种新产品的生产制造。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量。这些数据在表6.6最右边一列给出。最后一行给出了要求的产品生产率（每天生产的产品数量），以满足计划的销售量。每一家工厂都可以制造这些产品，除了工厂2不能生产产品3以外。然而，每种产品在不同工厂中的单位成本是有差异的。如表6.6所示。表6.6求佳产品公司问题中的数据单位成本（美元）生产能力产品：1

4、234工厂123要求的产量414037202729303028—273024232140757545现在管理者需要决定的是在哪个工厂里生产哪种产品，才能使总成本最低。（注意：在不止一个工厂里生产同样的一种产品是允许的。）可转化为运输问题，如表6.7所示。目的地（产品）单位成本（美元）供应量1234出发地（工厂）123需求量414037202729303028—273024232140757545表6.7运输问题的变形：求佳产品公司问题的数据例2：选择顾客耐芙迪公司在3个工厂中专门生产一种产品。这种产品有着优良的品质，所以现在公司接到了许多的订单，

5、产品供不应求。在未来的4个月中，有四个处于国内不同区域的潜在顾客（批发商）很有可能大量订购。顾客1是公司最好的顾客，所以它的全部订购量都应该满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的1/3；对于顾客4，销售经理认为并不需要进行特殊考虑，所以不想向这位顾客供应货物。这样就有足够的货物满足最少数量。每一种工厂—顾客组合的单位利润如表6.8所示。最右边的一列中给出了下个月中每个工厂生产的单位数（总量为20000）；最后一行显示了顾客订购量（总量为30000）；倒数第二行给出了基于上面营销经理的决策的最少供

6、应量（总量为12000）。顾客单位利润（美元）产量1234工厂123553729421859463251534835800050007000最小采购量7000300020000要求采购量7000900060008000表6.8耐芙迪公司问题中的数据营销经理现在需要确定的是需要向每一位顾客供应的产品的数量（考虑这些最小量）以及每一个工厂向每一位顾客供应多少单位的货物才能使利润最大化。运输问题变形的一些其他应用分配自然资源米德罗水管站（MetroWaterDistrict）是一个主管着广阔地域的水资源分配的机构。由于这个地域十分干燥，所以这个机构需要

7、从外地引水。这些引入的水来自于科伦坡、塞克隆以及卡路里河这三条河流。引入这些水后，这个机构把水卖给这个地区的用户。它的主要客户是布都、劳斯戴维斯、圣歌以及豪利格拉斯等城市的供水部门。除了从卡路里河引入的水不能供给豪利格拉斯之外，从这三条河流之中引入的水都可以供给这四个城市。对于每一个从水源到城市的可能的组合，每立方英尺的成本在表6.9中给出。如果以100万立方英尺为单位的话，这个表的最后一行列出了在未来一年中每一个城市的用水需求量（总量为12.5）。最后一行中列出了每一年从每一条河流中可能引入的水量（总量为16）。表6.9米德罗水管站的水资源数据

8、每立方英尺的成本（美元）可供应量布都劳斯戴维斯圣歌豪利格拉斯科伦坡河塞克隆河卡路里河16014019013013020022019023