运输问题和指派问题.pptx

运输问题和指派问题运输问题 P&T公司是一家由家族经营的小公司。它收购生菜并在三个食品罐头厂（贝林翰、尤基尼、艾尔贝李）中把它们加工成为罐头，再用卡车把这些罐头食品运送到美国西部的四个分销仓库（萨克拉门托、盐湖城、赖皮特城、奥尔巴古），然后再卖出去。对于即将来临的收获季节，每一个罐头厂的产量都进行了估计，并且每一个仓库都从罐头总供应量中分到了一定的比例，这些数据如表6.1所示，试问要制定怎样一个运输计划，才能使总运输成本最小？案例研究：P&T公司的配送问题表6.1 PT公司的运输数据表（单位：车）罐头加工厂 产 量 仓 库 分配量 贝林翰 尤基尼 艾尔贝李 75 125 100 萨克拉门托 盐湖城 赖皮特城 奥尔巴古 80 65 70 85 合 计 300 合 计 300 表6.2 PT公司的单位卡车的运输成本（单位：美元）至仓 库 萨克拉门托盐湖城 赖皮特城奥尔巴古 食品罐头厂 贝林翰 尤基尼 艾尔贝李464352995513416682 654 690 388 867 791685从表6.3 PT公司问题的参数表 所有的这些数据都可总结在一个表格中，这个表格叫做参数表。PT公司问题的参数表如表6.3所示。目的地（仓库）单位成本（美元）萨克拉门托 盐湖城赖皮特城奥尔巴古供 应出发地（罐头厂）贝林翰 尤基尼 艾尔贝李46435299551341668265469038886779168575125100 需 求80657085各种运输问题变体的建模例1：指定工厂生产产品 求佳产品公司决定使用三个有生产余力的工厂进行四种新产品的生产制造。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量。这些数据在表6.6最右边一列给出。最后一行给出了要求的产品生产率（每天生产 的产品数量），以满足计划的销售量。每一家工厂都可以制造这些产品，除了工厂2不能生产产品3以外。然而，每种产品在不同工厂中的单位成本是有差异的。如表6.6所示。表6.6 求佳产品公司问题中的数据单位成本（美元）生产能力产品：1234工厂123要求的产量414037202729303028273024232140757545 现在管理者需要决定的是在哪个工厂里生产哪种产品，才能使总成本最低。（注意：在不止一个工厂里生产同样的一种产品是允许的。）可转化为运输问题，如表6.7所示。目的地（产品）单位成本（美元）供应量1234出发地（工厂）123需求量414037202729303028273024232140757545表6.7 运输问题的变形：求佳产品公司问题的数据例2：选择顾客 耐芙迪公司在3个工厂中专门生产一种产品。这种产品有着优良的品质，所以现在公司接到了许多的订单，产品供不应求。在未来的4个月中，有四个处于国内不同区域的潜在顾客（批发商）很有可能大量订购。顾客1是公司最好的顾客，所以它的全部订购量都应该满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的1/3；对于顾客4，销售经理认为并不需要进行特殊考虑，所以不想向这位顾客供应货物。这样就有足够的货物满足最少数量。每一种工厂 顾客组合的单位利润如表6.8所示。最右边的一列中给出了下个月中每个工厂生产的单位数（总量为20000）；最后一行显示了顾客订购量（总量为30000）；倒数第二行给出了基于上面营销经理的决策的最少供应量（总量为12000）。顾 客单位利润（美元）产 量1234工厂123553729421859463251534835800050007000最小采购量7000300020000要求采购量7000900060008000表6.8 耐芙迪公司问题中的数据 营销经理现在需要确定的是需要向每一位顾客供应的产品的数量（考虑这些最小量）以及每一个工厂向每一位顾客供应多少单位的货物才能使利润最大化。运输问题变形的一些其他应用分配自然资源 米德罗水管站（Metro Water District）是一个主管着广阔地域的水资源分配的机构。由于这个地域十分干燥，所以这个机构需要从外地引水。这些引入的水来自于科伦坡、塞克隆以及卡路里河这三条河流。引入这些水后，这个机构把水卖给这个地区的用户。它的主要客户是布都、劳斯戴维斯、圣歌以及豪利格拉斯等城市的供水部门。除了从卡路里河引入的水不能供给豪利格拉斯之外，从这三条河流之中引入的水都可以供给这四个城市。对于每一个从水源到城市的可能的组合，每立方英尺的成本在表6.9中给出。如果以100万立方英尺为单位的话，这个表的最后一行列出了在未来一年中每一个城市的用水需求量（总量为12.5）。最后一行中列出了每一年从每一条河流中可能引入的水量（总量为16）。表6.9 米德罗水管站的水资源数据每立方英尺的成本（美元）可供应量布都劳斯戴维斯圣歌豪利格拉斯科伦坡河塞克隆河卡路里河160140190130130200220190230170150565需求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划分学生入学区域 米德尔城学区(Middletown School District)开办了第三所中学，需要为每一所学校重新划定这个城市内的服务区域。在初步计划中，这个城市被分成了拥有大致相同数量人口的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以经济的方式满足能源需求 源丰公司（Energetic Company）需要为新的建筑物建立起能源系统。建筑物的能源需求主要来自于下面三方面：（1）电；（2）热水；（3）建筑物内取暖。每天这三类用途的能源需求（以相同的单位衡量）分别是10个单位、20个单位和30个单位。满足这些需求的三个可能的能源来源是：电、天然气和安装在屋顶上的太阳能加热装置。房屋屋顶的大小决定了太阳能加热装置每天所能够提供的能源量。但是对于电和天然气来说没有这种限制。电的需求只能够通过购买电来满足。但是对于其他的两种能源需求（热水和建筑物内取暖）来说，可以通过这三个能量来源中的一个或者是几个组合得到满足。表6.13 源丰公司问题中的成本数据能源需求单位成本（美元）电能水加热建筑物内取暖能源来源电能天然气太阳能加热400500600300600500400 通过这些能源来源来满足能源需求的单位成本如表6.13所示。管理层想要达到的目标是使得满足这些能源需求的成本最小。案例研究：特塞格公司的选址问题 特塞格公司（Texago Corporation）是一家设在美国本土的大型一体化石油公司。这家公司大部分的石油在公司自己的油田中生产，所需的其他部分从中东地区进口。公司拥有大型配送网络，把石油运送到公司的炼油厂，然后再把石油产品从炼油厂运送到公司的配送中心。这些设施的所在地如表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 特塞格向炼油厂运输原油的运输成本数据向炼油厂或潜在炼油厂运输原油的运输成本（百万美元每百万桶）新奥尔良查尔斯顿西雅图 洛杉矶加尔维斯 敦圣路易斯出发地得克萨斯加利福尼亚阿拉斯加中东地区245245735335314413531474表6.18 特塞格公司把石油制品运送到配送中心的运输成本数据把石油制品运输到配送中心的单位成本（百万美元）匹兹堡亚特兰大堪萨斯城旧金山炼油厂 新奥尔良 查尔斯顿 西雅图未来的炼油厂 洛杉矶 加尔维斯敦 圣路易斯6.5778545.558643644331873265所需要的单位数1008080100表6.19 特塞格公司在每一个备选地点建造新炼油厂的估计运营成本数据地 点每年的运营成本（百万美元）洛杉矶 加尔维斯敦 圣路易斯620570530 最后一个关键数据是每一个备选地点新炼油厂的运营成本。要对这些数据进行估计就要派出几名特别工作组的成员来收集相关的劳动力成本、赋税等详细数据。参照一个现在正在运营的炼油厂运营成本，可以帮助我们对这些数据进行提炼。而且特别工作组还要收集在这个地点建设新炼油厂所需要的土地成本、建设成本以及其他成本，然后以年金的形式摊销这些成本，就可以得到如表6.19所示的计算结果。表6.20 特塞格炼油厂每一个备选厂址所带来的年变动成本 地 点运输原油的总成本（百万美元）运输石油制品的总成本（10亿美元）新炼油厂的运营成本（百万美元）总变动成本（10亿美元）洛杉矶 加尔维斯敦圣路易斯8809209601.571.631.436205705303.073.122.92提供给管理层的信息 现在，特别工作组完成了对这三个建造新炼油厂备选地点的财务分析。表 6.20 显示了对于三个可能建造新炼油厂的每一个备选地点每年所有主要的可变成本。指派问题例子：塞尔默公司的问题 塞尔默公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他雇佣了四个临时工（安、伊恩、琼、肖恩），每一个人负责完成下面的一项任务：1.书面陈述的文字处理。2.制作口头和书面陈述的电脑图。3.会议材料的准备，包括书面材料的抄写和组织。4.处理与会者的提前和当场注册报名。现在他需要确定要将哪一项任务指派给哪一个人。虽然这四个临时工都有完成这四项任务所需的基本能力，但是在他们完成每一项任务时所表现出来的有效程度是有很大差异的。表6.21显示了每一个人完成每一项任务所用的时间（单位：小时）。最右一列给出了以每个人能力为基础的小时薪水。表6.21 塞尔默公司问题的数据临时工每一项任务所需要的时间（小时）每小时工资（美元）文字处理绘 图材料准备记 录安伊恩琼肖恩3547393241455651273236254051434614121315对指派问题变形的建模例子1：在各个地点分派设备 娇普肖普公司（Job Shop Company）购买了三种不同类型的新设备。但是在车间里却有五个不同的地点可供安装，其中某些地点比其他的地点更为需要某些设备，原因是他们十分接近工作中心，流入和流出这些设备的工作很多（在新设备之间并没有工作流）。因此，该问题的目标是把这些设备安装到有效的地点上，使物料处理成本达到最小。每一个设备处理原料的单位成本已经在表6.22中列了出来。地点2不能安装设备2，所以这里没有给出成本。表6.22 娇普肖普公司问题中的原料处理成本数据位 置每小时成本（美元）12345机器123131541671213101420615167例子2：指派工厂生产产品 现在我们来看一下前面所讲到的一个例子。求佳产品公司需要安排三个工厂来生产四种新产品。相关的数据如表6.23所示。表6.23 求佳产品公司问题中的数据单位成本（美元）生产能力产品：1234工厂123要求的产量414037202729303028273024232140757545 已知如表6.23所示的数据，使把每一个工厂指派给至少一个新的产品（每一种产品只能在一个工厂里生产）的总成本达到最小。由于我们有四种产品和三个工厂，所以就有两个工厂各只能生产一种新的产品，第三个工厂生产两种产品。只有工厂1和工厂2拥有生产两种产品的能力。新问题的陈述例子3：设计学生入学区域 现在我们又回到前面所讲到的一个例子。米德尔城学区管理人员在设计学区时所遇到的问题。相关的数据如表6.24所示。学区管理层决定禁止将一个区域分割给两个学校。另外，为了使学生在学校间的分布相对均衡，管理层还要求向每一所学校指派三个区域。已知如表6.24所示的数据，当每一个区域都完全指派给一所学校（没有区域分割）且每一所学校都被指派了三个区域之后，所有的学生到达学校的总路程最小。新问题的陈述表6.24 米德尔学区问题的数据学校距离学校的距离（英里）高中学生数量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