第五章 运输问题与指派问题ppt课件

1、运输问题和指派问题是两类相互联络的特殊线性规划问题,它们的根本形属于网络配送问题。本章的学习目的如下：1.了解运输和指派问题以及这些问题的各种变形的特征；2.掌握此类问题的建模方法和各种运用。P&T公司是一家由家族运营的小公司。它收买生菜并在食品罐头厂中把它们加工成罐头，然后再把这些罐头分销到各地卖出去。公司下属有三个罐头厂，即贝林翰的罐头厂1，尤基尼的罐头厂2和艾尔贝李的罐头厂3。公司要用卡车将3个罐头厂的产品运送到四个分销仓库，地点在萨克拉门托，盐湖城，赖皮特城和奥尔巴古。详细信息如下表：罐头加工厂 产量仓库分配量贝林翰尤基尼艾尔贝李75125100萨克拉门托盐湖城赖皮特城奥尔巴古

2、80657085合计300合计300 P&T公司的单位卡车 的运送本钱单位：美圆 至 从仓库萨克拉门托 盐湖城 赖皮特城奥尔巴古食品罐头厂贝林翰尤基尼艾尔贝李464352995513416682654690388867791685 至 从仓库萨克拉门托 盐湖城赖皮特城奥尔巴古食品罐头厂贝林翰尤基尼艾尔贝李755006500551500851.由于在贝林翰的罐头厂间隔仓库较远，所以把它的产品运送到最近的一个仓库。也就是萨克拉门托的那个仓库。假设还有剩余的话，就要运送到盐湖城的仓库中去。2.由于在奥尔巴古的仓库间隔食品厂最远，所以就要从最近的一个罐头厂艾尔贝李的罐头厂中运送产品到奥尔巴古。

3、假设还有剩余的话，就要运送到赖皮特城的仓库中。3.用尤基尼的罐头厂满足其他仓库的剩余需求。当前运输方案下的总运输本钱为：75464535265416556901538885685165595美圆 管文科学小组如今要做的任务就是检查当前的运输方案，看看能否可以制定出一个新的运输方案，使总运输本钱下降到一个绝对最小值。1.有关概念产地出发地，销地目的地产量供应量，销量需求量单位运输费用单位配送本钱2.供求假设每一个出发地都有一个固定的供应量，一切的供应量都必需配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必需由出发地满足。 在运输问题的根本模型中，供应量需求量3.本钱假设

4、从任何一个出发地到任何一个目的地的货物配送本钱和所配送的数量成线性比例关系，因此这个本钱就等于配送的单位本钱乘以所配送的数量。4.运输问题的代数模型略5.整数解性质只需它的供应量和需求量都是整数，任何有可行解的运输问题必然由一切决策变量都是整数的最优解。因此，在求解时，没有必要加上一切变量都是整数的约束条件。6.Excel电子表格模型Excel任务表P&T公司的运输问题.xlsP&T公司问题是一个典型的运输问题，符合运输问题的每一个条件。但是在现实生活中这种情况很少出现。一个或几个特征不符合运输问题条件的运输问题在线性规划问题中经常出现。如：1.供应总量超出了需求总量供过于求;

5、2.供应总量小于需求总量供不应求；3.一个目的地同时存在着最小需求和最大需求，于是一切在这两个数值之间的数量都是可以接受的；4.在配送中不能运用特定的出发地目的地组合；5.目的是使与配送数量有关的总利润最大而不是使本钱最小。于是将具有上述一个或一些特征的运输问题转换为根本的运输问题然后求解根本的运输问题即可使问题得到处理。 例1：求佳产品Better Product Co.公司决议运用三个有消费余力的工厂进展四种新产品的消费制造。每单位产品需求等量的任务，所以工厂的有效消费才干以每天消费的任一种产品的数量来衡量，有关参数列表如下：单位成本（美元）生产能力产品：1234工厂12341403727

6、29302827242321757545要求的产量20303040电子表格模型的建立Excel任务表求佳公司问题.xls例2：耐芙迪Nifty公司在三个工厂中专门消费一种产品。在未来四个月中，有四个处于国内不同区域的潜在顾客零售商很有能够大量订购。顾客1是公司最好的顾客，所以他的全部订单都应该满足；顾客2和3也是公司很重要的顾客，所以营销经理以为作为最低限制至少要满足他们的订单的13；对于顾客4，他以为并不需求进展特殊思索。耐芙迪公司问题中的数据单位利润（美元）产量顾客1234工厂123553729421859463251534835800050007000最小采购量要求采购量70007000

7、300090002000600008000电子表格模型Excel任务表耐芙迪公司问题.xls例1：米德罗水管站Metro Water District是一个主管着宽广地域的水资源分配的机构。由于这个地域非常枯燥，所以这个机构需求从外地引水。这些引入的水来自科伦坡、赛克隆以及卡路里河这三条河流。引入这些水后，这个机构把水转卖给这个地域的用户。它的主要客户是布都、老斯戴维斯、圣哥以及豪利格拉斯等城市的供水部门。 米德罗水管站的水资源数据每立方英尺的成本（美元）可供应量布都劳斯戴维斯圣哥豪斯格拉斯科伦坡河赛克隆河卡路里河160140190130130200220190230170150565需求25

8、41.5（百万立方英尺）电子表格模型及求解Excel任务表米德罗水管站问题.xls例2：北方飞机制造公司Northern Airplane Company为全世界的航空公司消费各种商务飞机。制造过程的最后一步是消费喷气式发动机并把它们安装到曾经完成的飞机框架之中去非常快的一个操作。按照公司的一些订单合同，不久公司要交付运用相当多数量的飞机。所以有必要制定今后四个月的消费方案。北方飞机制造公司问题的消费进度安排数据月份计划安装量最大产量单位生产成本（百万美元）单位存储成本（美元）正常时间加班时间 正常时间加班时间1234101525202030255101510101.081.111.101.1

9、31.101.121.111.15150001500015000电子表格模型及求解Excel任务表北方飞机制造公司问题.xls例3：米德尔城学区Middletown School District)兴办了第三所中学，需求为每一所学校重新划定这个城市内的效力区域。在初步的方案中，这个城是被分为拥有大致一样数量人口的九个区域。学区管理者以为划分入学区域界限的适当目的是要使学生到学校的平均路程最短。在这个初步的方案之中，他们要确定为了实现这一目的每一个区域内有多少学生要安排到每一所学校中去。米德尔学区问题的数据距离学校的距离（英里）高中学生数量123区域1234567892.21.40.51.20.

10、91.12.71.81.51.91.31.80.30.71.60.71.21.72.51.71.12.01.00.61.50.80.7500400450400500450450400500最小招生数最大招生数120018001100170010001500电子表格模型及求解Excel任务表米德尔学区问题.xls例4：源丰公司Energetic Company)需求为新的建筑物建立起能源系统。建筑物的能源需求主要来自于下面三个方面1电，2热水，3建筑物内取暖。每天这三类用途的能源需求以一样的单位衡量分别是10个单位、20个单位和30个单位。点的需求只能经过购电来满足。但是对于其他的两种能源需求来

11、说，可以经过这三个能量来源中的一个或者是几个组合得到满足。电子表格模型及求解Excel任务表源丰公司问题.xls特赛格公司Texago Corporation是一家设在美国外乡的大型一体化石油公司。这家公司大部分的石油在公司本人的油田中消费，所需的其他部分从中东地域进口。公司拥有大型配送网络，把石油运送到公司的炼油厂，然后再把石油产品从炼油厂运送到公司的配送中心。 特赛格公司正在继续添加其几种主要产品的市场占有率。因此管理层决议建立一个新的炼油厂来添加公司的产量，同时添加从中东地域进口石油的数量。接下来所要作出的决策就是确定在什么地方建立新的炼油厂。 新炼油厂的参与对整个配送系统都将产生宏大的

12、影响,其中包括要确定从每个出发地运输到炼油厂的原油数量,以及从每一个炼油厂运送石油到每一个配送中心的数量.因此,管理者选择新炼油厂建立地点的三个关键要素是:1.从出发地运送原油到一切炼油厂(包括新炼油厂的本钱;2.从一切炼油厂包括新炼油厂运送石油制品到每一个配送中心的本钱;3.新的炼油厂的运作本钱,包括劳动力本钱、税赋、原料不包括原油本钱、能源本钱、保险本钱，等等。资金本钱并不是一个所要关注的要素，由于任何地点的资金本钱几乎都是一样的。我们如今的问题是要确定新的炼油厂的位置地址，使得总本钱最小。l搜集必要的数据lExcel任务表特赛格公司的数据表.docl计算新炼油厂的每个位置选择带来的总的原

13、油运输本钱;l例1假设新的炼油厂设在洛杉矶，那么有如下的运输问题lExcel任务表特赛格公司的选址问题.xlsl计算新炼油厂的每个位置选择带来的总石油制品运输本钱。l例2假设新的炼油厂设在洛杉矶，那么有如下的运输问题lExcel任务表特赛格公司的选址问题.xlsl计算特赛格公司每一个备选厂址所带来的年变动本钱。l例3 特赛格炼油厂每一个备选厂址所带来的年变动本钱列表如下：Excel任务表特赛格公司的数据表.doc指派问题就是给定一组义务和一组人,所需求确定的就是哪个人完成哪个义务。指派问题的根本模型，需求满足下面的假设：1.被指派者的数量和义务的数量是一样的；2.每一个被指派者只完成一项义务；

14、3.每一项义务只能由一个被指派者来完成；4.每一个被指派者和每一项义务的组合都会有一个相关的本钱；5.问题的目的是要确定怎样进展指派才干使得总本钱到达最小。塞尔默Sellmore)公司的问题塞尔默公司的营销经理将要主持召开一年一度的有营销区域经理以及销售人员参与的销售协商会议。为了更好地安排这次会议，他雇用了四个暂时工安、伊安、琼、肖恩，每一个人担任完成下面的一项义务：1.书面陈说的文字处置；2.只作口头和书面陈说的电脑图；3.会议资料的预备，包括书面资料的誊写和组织；4.处置与会者的提早和当场注册报名。如今他需求确定要将那一项义务指派给那一个人。塞尔默公司问题的有关数据塞尔默公司问题的电子表

15、格模型Excel任务表塞尔默公司问题.xls临时工每一项任务所需要的时间（小时）每小时工资（美元）文字处理绘图材料准备记录安伊恩琼肖恩3547393241455651273236254051434614121315当问题本身是一个指派的问题,但上一节根本的指派问题模型中的一个或多个假设不成立时,称它们为指派问题的变形。我们思索下面一些特征：1.有一些被指派者并不能进展某一些的人物。2.虽然每一个被指派者完成一项义务，但是义务比被指派者多。所以其中某些义务并没有得到执行。3.虽然每一项义务只由一个被指派者完成，但是这里被指派者比要完成的义务多。所以，其中有一些被指派者没有指派到义务。4.每一个被

16、指派者可以同时被派给多于一个义务。5.每一项义务都可以有多个被指派者共同完成。例1 娇普肖普Job Sho Company)购买了三种不同类型的新设备。但是在车间里却有五个不同的地点可供安装。其中某些地点比其他的地点更为需求某些设备，缘由是他们非常接近任务中心，流入和流出这些设备的任务很多。因此该问题的目的是把这些设备安装到有效的地点上，使物料处置本钱到达最小。娇普肖普公司问题中的原料处置本钱数据娇普肖普问题的电子表格模型Excel任务表娇普肖普问题模型.xls位置每小时成本（美元）12345机器123131541671213101420615167例2 如今我们再来看一下5.3节所讲到的例子。求佳产品公司需求安排三个工厂来消费四种新产品。我们得到的最优结果是：第一个厂消费第二和第三种产品各30单位，第二个厂只消费第四种产品15单位，第三个厂消费第一和第四种产品分别为20，25单位，本钱为$3260美圆。从结果中可以看出，第四种产品分到了两个厂消费，这样会添加隐性本钱。所以，我们加进一些新的要求：每个工厂至少完成一种产品，一种产品不能分到两个