第六章 运输问题和指派问题

运输问题和

指派问题运输问题

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

产

量

仓

库

分配量

贝林翰尤基尼

艾尔贝·李

75125100萨克拉门托

盐湖城

赖皮特城

奥尔巴古

80657085合

计

300合

计

300表6.2P＆T公司的单位卡车的运输成本（单位：美元）

至仓

库

萨克拉门托盐湖城

赖皮特城奥尔巴古

食品罐头厂贝林翰尤基尼艾尔贝·李464352995513416682

654690388

867791685从表6.3P＆T公司问题的参数表所有的这些数据都可总结在一个表格中，这个表格叫做参数表。P＆T公司问题的参数表如表6.3所示。目的地（仓库）单位成本（美元）萨克拉门托盐湖城赖皮特城奥尔巴古供应出发地（罐头厂）贝林翰尤基尼艾尔贝·李46435299551341668265469038886779168575125100需求80657085各种运输问题变体的建模例1：指定工厂生产产品求佳产品公司决定使用三个有生产余力的工厂进行四种新产品的生产制造。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量。这些数据在表6.6最右边一列给出。最后一行给出了要求的产品生产率（每天生产的产品数量），以满足计划的销售量。每一家工厂都可以制造这些产品，除了工厂2不能生产产品3以外。然而，每种产品在不同工厂中的单位成本是有差异的。如表6.6所示。表6.6求佳产品公司问题中的数据单位成本（美元）生产能力产品：1234工厂123要求的产量414037202729303028—273024232140757545现在管理者需要决定的是在哪个工厂里生产哪种产品，才能使总成本最低。（注意：在不止一个工厂里生产同样的一种产品是允许的。）可转化为运输问题，如表6.7所示。目的地（产品）单位成本（美元）供应量1234出发地（工厂）123需求量414037202729303028—273024232140757545表6.7运输问题的变形：求佳产品公司问题的数据例2：选择顾客耐芙迪公司在3个工厂中专门生产一种产品。这种产品有着优良的品质，所以现在公司接到了许多的订单，产品供不应求。在未来的4个月中，有四个处于国内不同区域的潜在顾客（批发商）很有可能大量订购。顾客1是公司最好的顾客，所以它的全部订购量都应该满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的1/3；对于顾客4，销售经理认为并不需要进行特殊考虑，所以不想向这位顾客供应货物。这样就有足够的货物满足最少数量。每一种工厂—顾客组合的单位利润如表6.8所示。最右边的一列中给出了下个月中每个工厂生产的单位数（总量为20000）；最后一行显示了顾客订购量（总量为30000）；倒数第二行给出了基于上面营销经理的决策的最少供应量（总量为12000）。顾客单位利润（美元）产量1234工厂123553729421859463251534835800050007000最小采购量7000300020000要求采购量7000900060008000表6.8耐芙迪公司问题中的数据营销经理现在需要确定的是需要向每一位顾客供应的产品的数量（考虑这些最小量）以及每一个工厂向每一位顾客供应多少单位的货物才能使利润最大化。运输问题变形的一些其他应用分配自然资源米德罗水管站（MetroWaterDistrict）是一个主管着广阔地域的水资源分配的机构。由于这个地域十分干燥，所以这个机构需要从外地引水。这些引入的水来自于科伦坡、塞克隆以及卡路里河这三条河流。引入这些水后，这个机构把水卖给这个地区的用户。它的主要客户是布都、劳斯戴维斯、圣歌以及豪利格拉斯等城市的供水部门。除了从卡路里河引入的水不能供给豪利格拉斯之外，从这三条河流之中引入的水都可以供给这四个城市。对于每一个从水源到城市的可能的组合，每立方英尺的成本在表6.9中给出。如果以100万立方英尺为单位的话，这个表的最后一行列出了在未来一年中每一个城市的用水需求量（总量为12.5）。最后一行中列出了每一年从每一条河流中可能引入的水量（总量为16）。表6.9米德罗水管站的水资源数据每立方英尺的成本（美元）可供应量布都劳斯戴维斯圣歌豪利格拉斯科伦坡河塞克隆河卡路里河160140190130130200220190230170150—565需求2541.5（百万立方英尺）由于总供应量大于总需求量，所以管理者需要确定从每一条河流中应该引入多少水，以及从每条河流中引入多少水到每一个城市。这个问题的目标就是要在满足每一个城市用水需求的前提下使得供水的成本最小。生产进度安排北方飞机制造公司为全世界的航空公司生产各种商务飞机。制造过程最后的一步是生产喷气发动机并把它们安装到已经完成的飞机框架之中去（非常快的一个操作）。按照公司的一些订单合同，不久公司要交付使用相当多数量的飞机。所以有必要现在为未来4个月这些飞机喷气发动机的生产制定计划。为了保证按时交付，公司必须要按照表6.10第二列的数量来供应需要安装的发动机。因此，在1~4月的月末需要完成的发动机数量分别是10、25、50、70台。正常时间（没有加班）内每月的最大生产能力如表6.10第三列所示。能够在加班时间内生产的数量第四列中给出。在正常时间以及加班时间内每生产一台发动机的成本分别在第五列和第六列中给出。表6.10北方飞机制造公司问题的生产进度安排数据月份计划安装量最大产量单位生产成本（百万美元）单位存储成本（美元）正常时间加班时间正常时间加班时间1234101525202030255101510101.081.111.101.131.101.121.111.15150001500015000生产管理人员需要制定出一个每月生产多少发动机的计划，使制造和存储的总成本达到最小。表6.11北方飞机制造公司的最优生产进度安排月份产量安装量储存量1(RT)2(RT)3(RT)3(OT)4(RT)2010251051015250201055100划分学生入学区域米德尔城学区(MiddletownSchoolDistrict)开办了第三所中学，需要为每一所学校重新划定这个城市内的服务区域。在初步计划中，这个城市被分成了拥有大致相同数量人口的9个区域。表6.12给出了每一所学校与每一个区域之间的近似距离。最右一列给出了明年每一个区域的高中学生数量（这些数字在未来几年之内估计会有缓慢的增长）。最下面两行表示了每一所学校所能够安排的最少和最多的学生数量。学区管理者认为划分入学区域界限的适当目标是要使学生到学校的平均路程最短。在这个初步的计划之中，他们要确定为了实现这一目标每一个区域内有多少学生要安排到每一所学校中，同时又要满足表6.12最后两行规定的约束条件。表6.12米德尔学区问题的数据学校距离学校的距离（英里）高中学生数量123区域1234567892.21.40.51.20.91.12.71.81.51.91.31.80.30.71.60.71.21.72.51.71.12.01.00.61.50.80.7500400450400500450450400500最小招生数最大招生数120018001100170010001500以经济的方式满足能源需求源丰公司（EnergeticCompany）需要为新的建筑物建立起能源系统。建筑物的能源需求主要来自于下面三方面：（1）电；（2）热水；（3）建筑物内取暖。每天这三类用途的能源需求（以相同的单位衡量）分别是10个单位、20个单位和30个单位。满足这些需求的三个可能的能源来源是：电、天然气和安装在屋顶上的太阳能加热装置。房屋屋顶的大小决定了太阳能加热装置每天所能够提供的能源量。但是对于电和天然气来说没有这种限制。电的需求只能够通过购买电来满足。但是对于其他的两种能源需求（热水和建筑物内取暖）来说，可以通过这三个能量来源中的一个或者是几个组合得到满足。表6.13源丰公司问题中的成本数据能源需求单位成本（美元）电能水加热建筑物内取暖能源来源电能天然气太阳能加热400——500600300600500400

通过这些能源来源来满足能源需求的单位成本如表6.13所示。管理层想要达到的目标是使得满足这些能源需求的成本最小。案例研究：特塞格公司的选址问题

特塞格公司（TexagoCorporation）是一家设在美国本土的大型一体化石油公司。这家公司大部分的石油在公司自己的油田中生产，所需的其他部分从中东地区进口。公司拥有大型配送网络，把石油运送到公司的炼油厂，然后再把石油产品从炼油厂运送到公司的配送中心。这些设施的所在地如表6.14所示。设施种类所处的位置油田1.有几个在得克萨斯州2.有几个在加利福尼亚3.有几个在阿拉斯加州炼油厂1.在路易斯安那州的新奥尔良附近2.在南卡罗莱纳州的查尔斯顿附近3.在华盛顿州的西雅图附近配送中心1.在宾夕法尼亚州的匹兹堡2.在佐治亚州的亚特兰大3.在密苏里州的堪萨斯城4.在加利福尼亚州的旧金山表6.14特塞格公司目前设施的所在地

特塞格公司正在持续增加其几种主要产品的市场占有率。因此管理层决定建立一个新的炼油厂来增加公司的产量，同时增加从中东地区进口石油的数量。接下来所要作出的决策就是确定在什么地方建设新的炼油厂。

管理层决定成立一个特别工作小组来专门研究在什么地点建造这个新的炼油厂的问题。经过大量的研究，特别工作组确定了三个非常有潜力和吸引力的备选地点。这些地点以及每一个地点的主要优势如表6.15所示。表6.15特塞格公司新炼油厂的备选建造地点以及它们的主要优势备选地点主要优势靠近加州的洛杉矶1.靠近加州的油田2.可以从阿拉斯加的油田取得原油3.十分靠近旧金山配送中心靠近德州的加尔维斯敦1.靠近得克萨斯油田2.可以从中东进口原油3.靠近公司总部靠近密苏里州的圣路易斯1.较低的运营成本2.处于配送中心的中央地域3.已经有了穿过密西西比河的输油途径收集必要的数据表6.16特塞格公司的生产数据炼油厂每年所需原油量（百万桶）油田每年原油产量（百万桶）新奥尔良查尔斯顿西雅图新的炼油厂1006080120得克萨斯州加利福尼亚阿拉斯加州8060100总量240总量360所需进口量=360–240=120表6.17特塞格向炼油厂运输原油的运输成本数据向炼油厂或潜在炼油厂运输原油的运输成本（百万美元每百万桶）新奥尔良查尔斯顿西雅图