运筹学运输与指派问题-课件

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2021/3/30,第4章 运输问题和指派问题,运输问题和指派问题是实际中碰到的比较常见的一类线性规划问题，它们在变量的取值、约束条件的系数矩阵等具有一定的特殊性，所以可以找到比单纯形法更为简便的求解方法。,2021/3/30,1,第4章 运输问题和指派问题 运输问题和指派问题,4.1 运输问题模型及表上作业法求解,B,1,B,2,B,n,A1,A2,A3,c,11,c,21,c,m1,c,12,c,22,c,m2,c,1n,c,2n,c,mn,单位运价表(cij),B,1,B,2,B,n,产量,A,1,A,2,A,m,x,11,X,21,x,m1,x,12,X,22,x,m2,x,1n,X,2n,x,mn,a,1,a,2,a,m,销量,b,1,b,2,b,n,产销平衡表（决策变量x,ij,=0或1),产销平衡的运输问题:,2021/3/30,2,4.1 运输问题模型及表上作业法求解B1B2BnA1c11,精品资料,2021/3/30,3,精品资料2021/3/303,你怎么称呼老师？,如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？,你所经历的课堂，是讲座式还是讨论式？,教师的教鞭,“不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘”,“太阳当空照，花儿对我笑，小鸟说早早早”,2021/3/30,4,2021/3/304,运输问题的表上作业法,表上作业法是一种简便而有效的方法,实质是单纯形法.,例4.1,某公司下属有三个加工厂A,1,A,2,A,3,生产化肥,负责供应B,1,B,2,B,3,B,4,四个地区所需化肥，各厂化肥产量及各地区所需化肥、各化肥厂到各地区所的运输距离见下表：,单位 销地,运价,产地,B1,B2,B3,B4,产量(吨),A1,3,11,3,10,7,A2,1,9,2,8,4,A2,7,4,10,5,9,销量(吨),3,6,5,6,单位运价表(元),产销平衡表,B1,B2,B3,B4,产量(吨),A1,x11,x12,x13,x14,7,A2,x11,x12,x13,x14,4,A2,x11,x12,x13,x14,9,销量(吨),3,6,5,6,销地,运量,产地,2021/3/30,5,运输问题的表上作业法表上作业法是一种简便而有效的方法,实质是,给出初始解,给出初始解有西北角法、最小元素法和Vogel法,我们只介绍比较简单的,最小元素法.,步骤:在产销平衡的前提下,运价低的优先安排调运.,B,1,B,2,B,3,B,4,产量,A,1,(3),(11),(3),(10),7,A,2,(1),(9),(2),(8),4,A,3,(7),(4),(10),(5),9,销量,3,6,5,6,3,1,4,6,3,3,最小元素法初始方案,产 销,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,3,1,7,11,9,4,3,2,10,10,8,5,7,4,9,销量,3,6,5,6,20 20,单位运价表,2021/3/30,6,给出初始解给出初始解有西北角法、最小元素法和Vogel法,我,解的最优性检验,解的最优性检验主要有闭回路法和位势法,我们只介绍,位势法,.,位势法:,(1)把产销平衡表中初始方案中有数字格对应的运价写到检验数表中;,(2)对运输表上的每一行(列)赋予一个数值u,i,(v,j,),称为位势.各格子的位势等于行位势与列位势之和.,(3)求出检验数:,ij,=c,ij,-(,u,i,+,v,j,),B,1,B,2,B,3,B,4,(u,i,),A,1,(3)0,(10)0,A,2,(1)0,(2)0,A,3,(4)0,(5)0,(v,j,),2,-1,3,0,10,-5,9,B,1,B,2,B,3,B,4,A,1,3,11,3,10,A,2,1,9,2,8,A,3,7,4,10,5,单位运价表,位势法检验数计算表,(3),1,(11),2,(9),1,(8),-1,(7),10,(10),12,2021/3/30,7,解的最优性检验解的最优性检验主要有闭回路法和位势法,我们只介,运输方案的改进,当所有,ij,0,即为即优.当,ij,0时,由闭回路法修改方案.,闭回路法:,(1)找到最小的负检验数,其对应的变量为入基变量.,(2)从入基变量对应的格子出发,遇到有数字的格子可以转90（也可不转）,直到回到出发点,形成闭回路.,(3)根据供应量与需求量总量不变的原则,调整供需关系.,3,A,2,A,1,3,6,A,3,B,4,B,3,B,2,B,1,方案调整,-1,2,A,2,3,1,A,1,位势,(v,j,),11,9,A,3,位势(u,i,),B,4,B,3,B,2,B,1,检验数表,0+,3-,4+,1-,因供给非负,所以,=1,得新供给方案,2021/3/30,8,运输方案的改进当所有ij0,即为即优.当ijb,j,时,用产销平衡的数学模型,其约束会产生矛盾.此时模型应改为:,若用表上作业法求之,可设一个假想销地,使其销量为b,n+1,=a,i,-b,j,c,i,n+1,=0.,2021/3/30,11,0bn+1Bn+14.3 产销不平衡运输问题产销平衡:B1B,1,2,3,4,生产能力,1,10.8,10.95,11.10,11.25,25,2,11.10,11.25,11.40,35,3,11.0,11.5,30,4,11.3,10,需量,10,15,25,20,例4.2 按合同供货的生产计划问题（P109）,季度,生产的能力（台）,生产成本费（万元）,1,25,10.8,2,35,11.1,3,30,11.0,4,10,11.3,生产能力与生产成本,某厂按合同规定于当年每季度未分别提供10、15、25、20台同一规格柴油机。已知该厂的生产能力与生产成本如下表。若生产出的产品当季不交货，则需储存、维护等费用1500元。要求在完成合同的情况下，做出全年生产费用最小的决策。,分析：由题设我们可得第i季度生产，第j季度交货的成本如下表，因此可看成是供大于求的运输问题。,交货季度j,生产季度i,交货的成本,2021/3/30,12,1234生产能力110.810.9511.1011.2525,1,2,3,4,生产,能力,1,x,11,x,12,x,13,x,14,25,2,x,21,x,22,x,23,x,24,35,3,x,31,x,32,x,33,x,34,30,4,x,41,x,42,x,43,x,44,10,需量,10,15,25,20,交货季度j,生产季度i,设x,ij,表示第i季度生产，第j季度交货的柴油机数量，则,产销表,用Excel求解,2021/3/30,13,1234生产1x11x12x13x14252x21x22x2,0 0 0,a,m+1,A,m+1,产销平衡:,B,1,B,2,B,n,产量,A,1,A,2,A,m,c,11,c,21,c,m1,c,12,c,22,c,m2,c,1n,c,2n,c,mn,a,1,a,2,a,m,销量,b,1,b,2,b,n,产量小于销量,当a,i,b,j,时,用产销平衡的数学模型,其约束会产生矛盾.此时模型应改为:,若用表上作业法求之,可设一个假想产地,使其销量为a,m+1,=b,j,-a,i,c,m+1,j,=0.,2021/3/30,14,0 0 0am+1Am+1,销地,产地,B,1,B,2,B,3,产量,A,1,13,15,12,78,A,2,11,29,22,45,销量,53,36,65,产量小于销量运输问题的Excel求解（P113例4.3),1.ExcelORM,线性规划运输问题目标min,销地数4,产地数3,生成电子表模型,用Excel求解,2021/3/30,15,销地B1B2B3产量A113151278A211,产品,工厂,B,1,B,2,B,3,B,4,生产,能力,A,1,41,27,28,24,75,A,2,40,29,-,23,75,A,3,37,30,27,21,45,需求,20,30,30,40,变形运输问题的Excel求解（P115例4.4),1.ExcelORM,线性规划运输问题目标min,销地数4,产地数3,销量有弹性，生成电子表模型,用Excel求解,2021/3/30,16,产品B1B2B3B4生产A14127282475,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,55,42,46,53,8000,A,2,37,18,32,48,5000,A,3,29,59,51,35,7000,最低需求,最高需求,7000,7000,3000,9000,2000,6000,0,8000,需求有弹性的运输问题的Excel求解（P117例4.5),1.ExcelORM,线性规划运输问题目标min,销地数4,产地数3,销量有弹性，生成电子表模型,用Excel求解,2021/3/30,17,销地B1B2B3B4产量A15542465380,运价,1 2 n n+1,库存量,1,p,11,p,12,p,1n,p,1n+1,p,21,p,22,p,2n,p,2n+1,2,p,11,p,12,p,1n,p,1n+1,m,需量,例战备物资的调运,但有转运问题，,p,ij,与转运方式有关。,有转运的运输问题,2021/3/30,18,运价1 2,设x,k,（,=0或1）表示第k个中转站启用次数，x,ik,表示从第i个仓库运到第k个中转站的物资数量，y,kj,表示从第k个中转站运到第j个单位的物资数量，则,2021/3/30,19,设xk（=0或1）表示第k个中转站启用次数，xik表示从第,运输问题小结,B,1,B,2,B,n,产量,A,1,A,2,A,3,x,11,x,21,x,m1,x,12,x,22,x,m2,x,1n,x,2n,x,mn,a,1,a,2,a,m,销量,b,1,b,2,b,n,1.运输问题由一个产销平衡表和一个单位运价表构成.,B,1,B,2,B,n,A,1,A,2,A,3,c,11,c,21,c,m1,c,12,c,22,c,m2,c,1n,c,2n,c,mn,2.运输问题数学模型,产销平衡,产大于销,产小于销,3.表上作业法:最小元素法给出初始方案、位势法求检验数、闭回路法调整方案,5.非地理问题转化为运输问题,4.依据数学模型，用Excel求解。,2021/3/30,20,运输问题小结B1B2Bn产量A1A2A3x11x,指派问题（分派问题）（Assignment problem）,若需完成n项任务，分配给n个人承担。由于每人的专长、能力不同，各人完成任务的收益、成本也不同。于是产生应指派哪个人去完成哪项任务，才能使完成n项任务的总成本最低或总收益最高。这类问题统称为,指派问题。,指派问题的假设,1.被指派者的数量和任务的数量是相同的；,2.每个人只完成一项任务；,3.每项任务只能由一个人来完成；,4.每个人和每项任务的组合都会有一个相关成本（收益）；,5.目标总成本或总收益值是根据任务指派确定。,2021/3/30,21,指派问题（分派问题）（Assignment problem）,某单位有n项任务需要n个人去完成，每个人仅能完成一项任务，每项任务仅要一人去完成，每个人完成不同的任务效率不同（见表4-1），问如何安排任务可使任务完成效率最高？,设xij表示安排第i个人去完成第j项任务，则,2021/3/30,22,某单位有n项任务需要n个人去完成，每个人仅能完成一项任务，每,指派问题的模型,一般指派问题的数学模型,它可看作一种特殊的运输问题。只是这里要求a,i,=b,j,=1,且x,ij,=0,1.,因此其有类似于运输问题的变形问题，处理技巧也类似。,2021/3/30,23,指派问题的模型一般指派问题的数学模型 它可看作一种特殊的运输,工作所需时间,人员,A,B,C,D,每小时工资（元）,1,35,41,27,40,14,2