第五章-运输问题和指派问题课件

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五章 运输问题和指派问题,运输问题和指派问题是两类相互联系的特殊线性规划问题,它们的基本形属于网络配送问题。本章的学习目的如下：,1.理解运输和指派问题以及这些问题的各种变形的特征；,2.掌握此类问题的建模方法和各种应用。,第五章 运输问题和指派问题运输问题和指派问题是两类相互联系,1,5.2案例研究：,P&T,公司的配送问题,P&T,公司是一家由家族经营的小公司。它收购生菜并在食品罐头厂中把它们加工成罐头，然后再把这些罐头分销到各地卖出去。,公司下属有三个罐头厂，即贝林翰的罐头厂1，尤基尼的罐头厂2和艾尔贝,李的罐头厂3。,5.2案例研究：P&T公司的配送问题P&T公司是一家由家族,2,公司要用卡车将3个罐头厂的产品运送到四个分销仓库，地点在萨克拉门托，盐湖城，赖皮特城和奥尔巴古。详细信息如下表：,罐头加工厂,产量,仓库,分配量,贝林翰,尤基尼,艾尔贝,李,75,125,100,萨克拉门托,盐湖城,赖皮特城,奥尔巴古,80,65,70,85,合计,300,合计,300,公司要用卡车将3个罐头厂的产品运送到四个分销仓库，地点在萨克,3,P&T,公司的单位卡车,的运送成本（单位：美元）,至 从,仓库,萨克拉门托,盐湖城,赖皮特城,奥尔巴古,食品罐头厂,贝林翰,尤基尼,艾尔贝李,464,352,995,513,416,682,654,690,388,867,791,685,P&T公司的单位卡车,4,至 从,仓库,萨克拉门托,盐湖城,赖皮特城,奥尔巴古,食品罐头厂,贝林翰,尤基尼,艾尔贝李,75,5,0,0,65,0,0,55,15,0,0,85,P&T公司的当前运送计划（单位：车）,至 从仓库萨克拉门托盐湖城赖皮特,5,公司当前的运输策略依据：,1.因为在贝林翰的罐头厂距离仓库较远，所以把它的产品运送到最近的一个仓库。也就是萨克拉门托的那个仓库。如果还有剩余的话，就要运送到盐湖城的仓库中去。,2.因为在奥尔巴古的仓库距离食品厂最远，所以就要从最近的一个罐头厂（艾尔贝李的罐头厂）中运送产品到奥尔巴古。,公司当前的运输策略依据：1.因为在贝林翰的罐头厂距离仓库较远,6,如果还有剩余的话，就要运送到赖皮特城的仓库中。,3.用尤基尼的罐头厂满足其他仓库的剩余需求。,当前运输计划下的总运输成本为：,75（464）5（352）65（416）55（690）15（388）85（685）165595（美元）,管理科学小组现在要做的工作就是检查当前的运输计划，看看是否能够制定出一个新的运输计划，使总运输成本下降到一个绝对最小值。,如果还有剩余的话，就要运送到赖皮特城的仓库中。,7,5.2 运输问题的特征,1.有关概念,产地（出发地），销地（目的地）,产量（供应量），销量（需求量）,单位运输费用（单位配送成本）,2.供求假设,每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，,5.2 运输问题的特征1.有关概念,8,整个需求量都必须由出发地满足。,在运输问题的基本模型中，供应量需求量,3.成本假设,从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量。,4.运输问题的代数模型（略）,整个需求量都必须由出发地满足。,9,5.整数解性质,只要它的供应量和需求量都是整数，任何有可行解的运输问题必然由所有决策变量都是整数的最优解。因此，在求解时，没有必要加上所有变量都是整数的约束条件。,6.,Excel,电子表格模型,Excel,工作表,P&T,公司的运输问题.,xls,5.整数解性质,10,5.3,各种运输问题变体的建模,P&T,公司问题是一个典型的运输问题，符合运输问题的每一个条件。但是在现实生活中这种情况很少出现。一个或几个特征不符合运输问题条件的运输问题在线性规划问题中经常出现。如：,1.供应总量超出了需求总量（供过于求）;,2.,供应总量小于需求总量（供不应求）；,3.一个目的地同时存在着最小需求和最大,5.3 各种运输问题变体的建模P&T公司问题是一个典型的运,11,需求，于是所有在这两个数值之间的数量都是可以接受的；,4.在配送中不能使用特定的出发地目的地组合；,5.目标是使与配送数量有关的总利润最大而不是使成本最小。,于是将具有上述一个或一些特征的运输问题转换为基本的运输问题然后求解基本的运输问题即可使问题得到解决。,需求，于是所有在这两个数值之间的数量都是可以接受的；,12,例1：求佳产品（,Better Product Co.）,公司决定使用三个有生产余力的工厂进行四种新产品的生产制造。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任一种产品的数量来衡量，有关参数列表如下：,单位成本（美元）,生产能力,产品：1,2,3,4,工厂1,2,3,41,40,37,27,29,30,28,27,24,23,21,75,75,45,要求的产量,20,30,30,40,例1：求佳产品（Better Prod,13,电子表格模型的建立,Excel,工作表求佳公司问题.,xls,例2：耐芙迪（,Nifty）,公司在三个工厂中专门生产一种产品。在未来四个月中，有四个处于国内不同区域的潜在顾客（批发商）很有可能大量订购。顾客1是公司最好的顾客，所以他的全部订单都应该满足；顾客2和3也是公司很重要的顾客，所以营销经理认为作为最低限度至少要满足他们的订单的13；对于顾客4，他认为并不需要进行特殊考虑。,电子表格模型的建立,14,耐芙迪公司问题中的数据,单位利润（美元）,产,量,顾客1,2,3,4,工厂1,2,3,55,37,29,42,18,59,46,32,51,53,48,35,8000,5000,7000,最小采购量,要求采购量,7000,7000,3000,9000,2000,6000,0,8000,耐芙迪公司问题中的数据单位利润（美元）产顾客1234工厂15,15,电子表格模型,Excel,工作表耐芙迪公司问题.,xls,电子表格模型,16,5.4 运输问题变形的其他一些应用,例1：米德罗水管站（,Metro Water District）,是一个主管着广阔地域的水资源分配的机构。由于这个地域十分干燥，所以这个机构需要从外地引水。这些引入的水来自科伦坡、赛克隆以及卡路里河这三条河流。引入这些水后，这个机构把水转卖给这个地区的用户。它的主要客户是布都、老斯戴维斯、圣哥以及豪利格拉斯等城市的供水部门。,5.4 运输问题变形的其他一些应用例1：米德罗水管站（Me,17,米德罗水管站的水资源数据,每立方英尺的成本（美元）,可供应量,布都,劳斯戴维斯,圣哥,豪斯格拉斯,科伦坡河,赛克隆河,卡路里河,160,140,190,130,130,200,220,190,230,170,150,5,6,5,需求,2,5,4,1.5,（百万立方英尺）,米德罗水管站的水资源数据每立方英尺,18,电子表格模型及求解,Excel,工作表米德罗水管站问题.,xls,例2：北方飞机制造公司（,Northern Airplane Company）,为全世界的航空公司生产各种商务飞机。制造过程的最后一步是生产喷气式发动机并把它们安装到已经完成的飞机框架之中去（非常快的一个操作）。按照公司的一些订单合同，不久公司要交付使用相当多数量的飞机。所以有必要制定今后四个月的生产计划。,电子表格模型及求解,19,北方飞机制造公司问题的生产进度安排数据,月份,计划安装量,最大产量,单位生产成本（百万美元）,单位存储成本（美元）,正常时间加班时间,正常时间加班时间,1,2,3,4,10,15,25,20,20,30,25,5,10,15,10,10,1.08,1.11,1.10,1.13,1.10,1.12,1.11,1.15,15000,15000,15000,北方飞机制造公司问题的生产进度安排数据月份计划安装量最大产量,20,电子表格模型及求解,Excel,工作表北方飞机制造公司问题.,xls,例3：米德尔城学区（,Middletown School District),开办了第三所中学，需要为每一所学校重新划定这个城市内的服务区域。在初步的计划中，这个城是被分为拥有大致相同数量人口的九个区域。学区管理者认为划分入学区域界线的适当目标是要使学生到学校的平均路程最短。在这个初步的计划之中，他们要确定为了实现这一目标每一个区域内有多少学生要安排到每一所学校中去。,电子表格模型及求解,21,米德尔学区问题的数据,距离学校的距离（英里）,高中学生数量,1,2,3,区域1,2,3,4,5,6,7,8,9,2.2,1.4,0.5,1.2,0.9,1.1,2.7,1.8,1.5,1.9,1.3,1.8,0.3,0.7,1.6,0.7,1.2,1.7,2.5,1.7,1.1,2.0,1.0,0.6,1.5,0.8,0.7,500,400,450,400,500,450,450,400,500,最小招生数,最大招生数,1200,1800,1100,1700,1000,1500,米德尔学区问题的数据距离学校的距离（英里）高中学生数量123,22,电子表格模型及求解,Excel,工作表米德尔学区问题.,xls,例4：源丰公司（,Energetic Company),需要为新的建筑物建立起能源系统。建筑物的能源需求主要来自于下面三个方面,（1）电，（2）热水，（3）建筑物内取暖。每天这三类用途的能源需求（以相同的单位衡量）分别是10个单位、20个单位和30个单位。点的需求只能通过购电来满足。但是对于其他的两种能源需求来说，可以通过这三个能量来源中的一个或者是几个组合得到满足。,电子表格模型及求解,23,电子表格模型及求解,Excel,工作表源丰公司问题.,xls,电子表格模型及求解,24,5.5,特赛格公司的选址问题,特赛格公司（,Texago Corporation）,是一家设在美国本土的大型一体化石油公司。这家公司大部分的石油在公司自己的油田中生产，所需的其他部分从中东地区进口。公司拥有大型配送网络，把石油运送到公司的炼油厂，然后再把石油产品从炼油厂运送到公司的配送中心。,特赛格公司正在持续增加其几种主要产品的市场占有率。因此管理层决定建立,5.5 特赛格公司的选址问题特赛格公司（Texago C,25,一个新的炼油厂来增加公司的产量，同时增加从中东地区进口石油的数量。接下来所要作出的决策就是确定在什么地方建设新的炼油厂。,新炼油厂的加入对整个配送系统都将产生巨大的影响,其中包括要确定从每个出发地运输到炼油厂的原油数量,以及从每一个炼油厂运送石油到每一个配送中心的数量.因此,管理者选择新炼油厂建设地点的三个关键因素是:,1.从出发地运送原油到所有炼油厂(包括新,一个新的炼油厂来增加公司的产量，同时增加从中东地区进口石油的,26,炼油厂）的成本;,2.从所有炼油厂（包括新炼油厂）运送石油制品到每一个配送中心的成本;,3.新的炼油厂的运作成本,包括劳动力成本、税赋、原料（不包括原油）成本、能源成本、保险成本，等等。（资金成本并不是一个所要关注的因素，因为任何地点的资金成本几乎都是一样的）。,我们现在的问题是要确定新的炼油厂的位置（地址），使得总成本最小。,炼油厂）的成本;,27,特赛格公司问题的解决办法,收集必要的数据,Excel,工作表特赛格公司的数据表.,doc,计算新炼油厂的每个位置选择带来的总的原油运输成本;,例1若新的炼油厂设在洛杉矶，则有如下的运输问题,Excel,工作表特赛格公司的选址问题.,xls,特赛格公司问题的解决办法收集必要的数据,28,计算新炼油厂的每个位置选择带来的总石油制品运输成本。,例2若新的炼油厂设在洛杉矶，则有如下的运输问题,Excel,工作表特赛格公司的选址问题.,xls,计算特赛格公司每一个备选厂址所带来的年变动成本。,例3 特赛格炼油厂每一个备选厂址所带来的年变动成本列表如下：,Excel,工作表特赛格公司的数据表.,doc,计算新炼油厂的每个位置选择带来的总石油制品运输成本。,29,5.6 指派问题的特征,指派问题就是给定一组任务和一组人,所需要确定的就是哪个人完成哪个任务。,指派问题的基本模型，需要满足下面的假设：,1.被指派者的数量和任务的数量是相同的；,2.每一个被指派者只完成一项任务；,3.每一项任务只能由一个被指派者来完成；,4.每一个被指派者和每一项任务的组合都会有一个相关的成本；,5.,问题的目标是要确定怎样进行指派才能使得总成本达到最小。,5.6 指派问题的特征指派问题就是给定一组任务和一组人,所,30,塞尔默（,Sellmore),公司的问题,塞尔默公司的营销经理将要主持召开一年一度的有营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他雇用了四个临时工（安、伊安、琼、肖恩），每一个人负责完成下面的一项任务：,1.书面陈述的文字处理；,2.只作口头和书面陈述的电脑图；,3.,会议材料的准备，包括书面材料的抄写和组织；,4.处理与会者的提前和当场注册报名。,现在他需要确定要将那一项任务指派给那一个人。,塞尔默（Sellmore)公司的问题,31,塞尔默公司问题的有关数据,塞尔默公司问题的电子表格模型,Excel,工作表塞尔默公司问题.,xls,临时工,每一项任务所需要的时间（小时）,每小时工资（美元）,文字处理,绘图,材料准备,记录,安,伊恩,琼,肖恩,35,47,39,32,41,45,56,51,27,32,36,25,40,51,43,46,14,12,13,15,塞尔默公司问题的有关数据临时工每一项任务所需要的时间（小时）,32,5.7 对指派问题变形的建模,当问题本身是一个指派的问题,但上一节基本的指派问题模型中的一个或多个假设不成立时,称它们为指派问题的变形。我们考虑下面一些特征：,1.有一些被指派者并不能进行某一些的人物。,2.虽然每一个被指派者完成一项任务，但是任务比被指派者多。所以其中某些任务并没有得到执行。,5.7 对指派问题变形的建模当问题本身是一个指派的问题,但,33,3.虽然每一项任务只由一个被指派者完成，但是这里被指派者比要完成的任务多。所以，其中有一些被指派者没有指派到任务。,4.每一个被指派者可以同时被派给多于一个任务。,5.每一项任务都可以有多个被指派者共同完成。,3.虽然每一项任务只由一个被指派者完成，但是这里被指派者比要,34,例1 娇普肖普（,Job Sho Company),购买了三种不同类型的新设备。但是在车间里却有五个不同的地点可供安装。其中某些地点比其他的地点更为需要某些设备，原因是他们十分接近工作中心，流入和流出这些设备的工作很多。因此该问题的目标是把这些设备安装到有效的地点上，使物料处理成本达到最小。,例1 娇普肖普（Job Sho Company)购买了三种,35,娇普肖普公司问题中的原料处理成本数据,娇普肖普问题的电子表格模型,Excel,工作表娇普肖普问题模型.,xls,位置,每小时成本（美元）,1,2,3,4,5,机器,1,2,3,13,15,4,16,7,12,13,10,14,20,6,15,16,7,娇普肖普公司问题中的原料处理成本数据位置每小时成本（美元）1,36,例2 现在我们再来看一下,5.3节所讲到的例子。求佳产品公司需要安排三个工厂来生产四种新产品。我们得到的最优结果是：第一个厂生产第二和第三种产品各30单位，第二个厂只生产第四种产品15单位，第三个厂生产第一和第四种产品分别为20，25单位，成本为$3260美元。从结果中可以看出，第四种产品分到了两个厂生产，这样会增加隐性成本。所以，我们加进一些新的要求：每个工厂至少完成一种产品，一种产品不能分到两个或两个以上的厂中生产。这样，就得到了新的模型：,Excel,工作表求佳公司问题.,xls,例2 现在我们再来看一下5.3节所讲到的例子。求佳产品公司,37,例3 现在我们再回到,5.4节中的米德尔城学区划分学生入学区域问题,从结果中可以看出,第五区域的学生被分配到两个学校;另外,容量最大的学校却被派去了最少的学生,虽然也可以接受,但是向这个学校指派更多的学生会更受欢迎。现在我们要求每个区域的学生只能去一所学校，每一所学校要接受三个区域的学生。这时问题又变了!,电子表格模型,Excel,工作表米德尔学区问题.,xls,例3 现在我们再回到5.4节中的米德尔城学区划分学生入学区,38,案例5.2项目选择,Excel,工作表案例5.2项目选择.,xls,Excel,工作表案例5.2项目选择（二）.,xls,案例5.2项目选择Excel工作表案例5.2项目选择.xl,39,第五章-运输问题和指派问题课件,40,第五章-运输问题和指派问题课件,41,第五章-运输问题和指派问题课件,42,第五章-运输问题和指派问题课件,43,第五章-运输问题和指派问题课件,44,