管理运筹学 运输问题.ppt

华东交大经济,管理学院,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,SHUFE,管理运筹学,运输问题,第五章 运输问题,运输问题是线性规划问题的特例。,产地,：货物发出的地点。,销地,：货物接收的地点。,产量,：各产地的可供货量。,销量,：各销地的需求数量。,运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。,2,第一节 运输模型,某饮料在国内有三个生产厂，分布在城市,A,1,、A,2,、A,3,其一级,承销商有4个，分布在城市,B,1,、B,2,、B,3,、B,4,，,已知各厂的产量、各承销商的销售量及从,A,i,到,B,j,的每吨饮料运费为,C,ij,，,为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。,一、运输问题举例,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,6,3,2,5,5,A,2,7,5,8,4,2,A,3,3,2,9,7,3,销量,2,3,1,4,3,第一节 运输模型,(1)决策变量,。设从,A,i,到,B,j,的运输量为,x,ij,，,(2),目标函数,minZ,=6,x,11,+3,x,12,+2,x,13,+5,x,14,+7,x,21,+5,x,22,+8,x,23,+4,x,24,+,3,x,31,+2,x,32,+9,x,33,+7,x,34,(3),约束条件,。,产量之和等于销量之和,故要满足,：,供应平衡条件,x,11,+,x,12,+,x,13,+,x,14,=5,x,21,+,x,22,+,x,23,+,x,24,=2,x,31,+,x,32,+,x,33,+,x,34,=3,销售平衡条件,x,11,+,x,21,+,x,31,=2,x,12,+,x,22,+,x,32,=3,x,13,+,x,23,+,x,33,=1,x,14,+,x,24,+,x,34,=1,非负性约束,x,ij,0 (,i,=1,2,3；,j,=1,2,3,4),运输问题的,LP,模型,4,第一节 运输模型,销地,产地,二、表,式,运输模型,A,1,A,2,A,m,产量,a1,a,2,a,m,B,1,B,2,B,n,销地,b,1,b,2,b,n,c,11,c,12,c,1n,c,21,c,22,c,2n,c,m1,c,m2,c,mn,x,11,x,12,x,1n,x,21,x,22,x,2n,x,m1,x,m2,x,mn,5,第一节 运输模型,产销平衡,三、运输问题的三种类型,6,第一节 运输模型,产大于销,7,第一节 运输模型,产小于销,8,第一节 运输模型,系数矩阵的结构如下：,（决策变量,m,n，,约束方程,m+n,个）,四、运输模型的特点,x,11,x,12,x,1n,x,21,x,22,x,2n,x,m1,x,m2,x,mn,m,行,n,列,9,五、运输问题的应用,产销不平衡的运输问题,增加一个销地,产大于销,销地,产地,B,1,B,2,B,3,产量,A,1,5,9,2,15,A,2,3,1,7,18,A,3,6,2,8,17,销量,18,12,16,销地,产地,B,1,B,2,B,3,产量,A,1,5,9,2,15,A,2,3,1,7,18,A,3,6,2,8,17,销量,18,12,16,50-46,B,4,0,0,0,4,50,46,50,50,10,增加一个产地,产小于销,销地,产地,B,1,B,2,B,3,产量,A,1,4,1,2,10,A,2,3,4,3,12,销量,8,10,5,销地,产地,B,1,B,2,B,3,产量,A,1,4,1,2,10,A,2,3,4,3,12,A,3,销量,8,10,5,23-22,0,0,0,1,22,23,23,23,11,P129,页:例4,特别的:由于供不应求,决定一区供应量可以减少0至200吨,二区需求全部满足,三区供应量不少于1700吨,12,转运问题:,P136,页:例8,产地 中转地 销售地,1,3,5,6,7,8,4,2,对于发点:,产量=流出量,对于中转点:,流入量=流出量,对于销售点:,流入量=需求量,令,x,ij,表示两点间,的运量,则有,600,400,200,150,350,300,13,第二节 表上作业法,表上作业法适合于产销平衡的运输问题,求解步骤：,找出初始方案（初始基可行解）：在,m,n,维,产销平衡表上给出,m,+,n,-1,个数字。,最优性检验：计算各非基变量的检验数，当,ij,0,最优。,方案调整与改进：确定进基变量和离基变量，找出新的基可行解。,14,第二节 表上作业法,最小元素法,“就近运给”，,从单位运价表中最小运价开始确定供销关系，,逐次挑选最小元素，安排运量,min,a,i,b,j,。,最大差额法,不能按最小运费就近供应，就考虑次小运费。,各行(各列)的最小运费与次小运费之差称为行差(列查)。差额越大，说明不能按最小运费调运时，运费增加最多。,对最大差额处就采用最小运费调运。,一、确定初始方案,15,第二节 表上作业法,从单位运价表中逐次挑选最小元素，安排运量,min,a,i,b,j,。,然后，划去该元素所在行或列：,当产大于销，划去该元素所在列；,当产小于销，划去该元素所在行。,最小元素法,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,6,3,2,5,5,A,2,7,5,8,4,2,A,3,3,2,9,7,3,销量,2,3,1,4,1,3,0,2,2,2,初始基可行解：,x,11,=2,x,13,=1,x,14,=2,x,24,=2,x,31,=0,x,32,=3，Z=38,16,第二节 表上作业法,判别方法是计算非基变量的检验数,：,ij,=,c,ij,C,B,P,ij,=,c,ij,C,B,B1,P,ij,运输问题的目标函数要求为最小，即当,ij,0,视为最优。,位势法,计算检验数(原理不做要求),ij,=,c,ij,C,B,P,ij,=,c,ij,C,B,B,-1,P,ij,ij,=,c,ij,(,u,i,+,v,j,),u,i,代表产地,A,i,的位势量，,v,j,代表销地,B,j,的位势量。,基变量的检验数为0，即,ij,=,c,ij,u,i,v,j,=0，,并令,u,1,=0，,计算各行各列的,位势量。,二、最优性检验,17,第二节 表上作业法,基变量的检验数,ij,=,c,ij,u,i,v,j,=0，,即,c,ij,=,u,i,+,v,j,，,且令,u,1,=0，,计算位势量,u,i,和,v,j,位势法,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,6,2,3,2,1,5,2,5,A,2,7,5,8,4,2,2,A,3,3,0,2,3,9,7,3,销量,2,3,1,4,u,i,v,j,0,6,2,5,-1,-3,5,18,第二节 表上作业法,计算非基变量的检验数,ij,=,c,ij,u,i,v,j,位势法（续,）,销地,产地,B,1,B,2,B,3,B,4,产量,u,i,A,1,6,2,3,2,1,5,2,5,0,A,2,7,5,8,4,2,2,-1,A,3,3,0,2,3,9,7,3,-3,销量,2,3,1,4,v,j,6,5,2,5,-2,2,1,7,10,5,非基变量,x,12,的检验数,12,=,c,12,u,1,v,2,=-2，,即让非基变量,x,12,从0增到1，可使总运费减少2个单位。,19,第二节 表上作业法,确定进基变量,检查非基变量,x,ij,的检验数,ij,，,按,min,ij,|,ij,0=,lk,确定,x,lk,进基。,确定离基变量,非基变量,x,lk,进基之后，能让它的运量增加多少呢？就要求它所在行和列的运量保持,产销平衡,。保持产销平衡的方法是,闭回路法,。,闭回路法：,以进基变量,x,lk,所在格为始点和终点，其余顶点均为基变量的封闭回路。,闭回路的画法,：从进基变量,x,lk,所在格开始，用水平或垂直线向前划，每碰到一个基变量格转90,，继续前进，直到返回始点。,奇偶点：,始点是偶点，依次奇偶相间标注；偶点标“+”，表示运量增加量；奇点标“-”，表示运量减少量。,调整量：,最小可减少的运量，即奇点运量的最小值。奇点运量的最小值所在格的基变量离基。,三、改进的方法（闭回路调整法）,20,第二节 表上作业法,x,12,进基,最小调整量为2，,x,11,离基,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,6,2,3,x,12,2,1,5,2,5,A,2,7,5,8,4,2,2,A,3,3,0,2,3,9,7,3,销量,2,3,1,4,+,-,+,-,21,第二节 表上作业法,非最优方案的调整,所有偶点的值都加上调整量；,所有奇点的值都减去调整量；,获得一个新的运输方案。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,6,3,2,1,5,2,5,A,2,7,5,8,4,2,2,A,3,3,2,9,7,3,销量,2,3,1,4,基可行解：,x,12,=2,x,13,=1,x,14,=2,x,24,=2,x,31,=2,x,32,=1，Z=34,2,0,3,2,2,1,22,第二节 表上作业法,基变量的检验数,ij,=,c,ij,u,i,v,j,=0，,且令,u,1,=0，,计算位势量,u,i,和,v,j,四、最优性检验,销地,产地,B,1,B,2,B,3,B,4产量,A,1,6,3,2,2,1,5,2,5,A,2,7,5,8,4,2,2,A,3,3,2,2,1,9,7,3,销量,2,3,1,4,u,i,v,j,0,4,-1,-1,3,2,5,所有非基变量,x,ij,的检验数,ij,=,c,ij,u,i,v,j,0,，,即得最优解。,23,第三节 产销不平衡问题,产销平衡的运输问题采取表上作业法求解。,产销不平衡的运输问题需划成产销平衡问题再求解。,产大于销：虚设一个销地,B,k,(,多于物资在产地存储)，其运价为0，销量(存储量)为产销量之差,b,k,=,a,i,-,b,j,。,产小于销：虚设一个产地,A,l,(,不足物资的脱销量)，其运价为0，产量(脱销量)为销产量之差,a,k,=,b,j,-,a,i,。,24,第三节 产销不平衡问题,增加一个销地,一、产大于销,销地,产地,B,1,B,2,B,3,产量,A,1,5,9,2,15,A,2,3,1,7,18,A,3,6,2,8,17,销量,18,12,16,销地,产地,B,1,B,2,B,3,产量,A,1,5,9,2,15,A,2,3,1,7,18,A,3,6,2,8,17,销量,18,12,16,50-46,B,4,0,0,0,4,50,46,50,50,25,第三节 产销不平衡问题,初始基可行解,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,5,9,2,0,15,A,2,3,1,7,0,18,A,3,6,2,8,0,17,销量,18,12,16,4,12,15,6,12,1,4,初始基可行解：,x,13,=15,x,21,=6,x,22,=12,x,31,=12,x,33,=1,x,34,=4，Z=140,26,第三节 产销不平衡问题,最优性检验,销地,产地,B,1,B,2,B,3,B,4,产量,u,i,A,1,5,9,2,15,0,15,A,2,3,6,1,12,7,0,18,A,3,6,12,2,8,1,0,4,17,销量,18,12,16,4,v,j,0,2,6,0,-6,3,-2,5,11,6,2,3,-2,非基变量,x,32,的检验数,32,=-2，即让非基变量,x,32,进基。,27,第三节 产销不平衡问题,闭回路调整,x,32,进基,最小调整量为12，,x,31,离基,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,5,9,2,15,0,15,A,2,3,6,1,12,7,0,18,A,3,6,12,2,x,32,8,1,0,4,17,销量,18,12,16,4,-,+,-,+,28,第三节 产销不平衡问题,非最优方案的调整,所有偶点的值都加上调整量；所有奇点的值都减去调整量,。,基可行解：,x,13,=15,x,21,=18,x,31,=0,x,32,=12,x,31,=1,x,34,=4，Z=34,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,5,9,2,15,0,15,A,2,3,1,7,0,18,A,3,6,2,8,1,0,4,17,销量,18,12,16,4,6,12,12,18,0,12,29,第三节 产销不平衡问题,基变量的检验数,ij,=,c,ij,u,i,v,j,=0，,且令,u,1,=0，,计算位势量,u,i,和,v,j,最优性检验,所有非基变量,x,ij,的检验数,ij,=,c,ij,u,i,v,j,0,，,即得最优解。,销地,产地,B,1,B,2,B,3,B,4,产量,u,i,A,1,5,9,2,15,0,15,A,2,3,18,1,7,0,18,A,3,6,0,2,12,81,0,4,17,销量,18,12,16,4,v,j,0,2,6,0,-4,-6,3,5,13,6,2,3,2,30,第三节 产销不平衡问题,增加一个产地,二、产小于销,销地,产地,B,1,B,2,B,3,产量,A,1,4,1,2,10,A,2,3,4,3,12,销量,8,10,5,销地,产地,B,1,B,2,B,3,产量,A,1,4,1,2,10,A,2,3,4,3,12,A,3,销量,8,10,5,23-22,0,0,0,1,22,23,23,23,31,第三节 产销不平衡问题,初始基可行,解,销地,产地,B,1,B,2,B,3,产量,A,1,4,1,2,10,A,2,3,4,3,12,A,3,0,0,0,1,销量,8,10,5,10,0,5,7,1,初始基可行解：,x,12,=10,x,13,=0,x,21,=7,x,23,=5,x,31,=1，Z=46,32,第三节 产销不平衡问题,最优性检验,销地,产地,B,1,B,2,B,3,产量,u,i,A,1,4,1,10,2,0,10,A,2,3,7,4,3,5,12,A,3,0,1,0,0,1,销量,8,10,5,v,j,0,1,2,1,2,-2,2,2,1,0,检验数,ij,0,，,得最优解:,x,12,=10,x,13,=0,x,21,=7,x,23,=5,x,31,=1，Z=46,由于非基变量,x,33,的检验数,33,0,，,为多最优解。让,x,33,进基,x,31,离基,得另一最优解:,x,12,=10,x,13,=0,x,21,=8,x,23,=4,x,33,=1,33,第四节 运输模型的应用,短缺资源分配，“产小于销”，需注意产销配比问题。,上例,x,12,=10,x,13,=0,x,21,=7,x,23,=5,x,31,=1，,表示销地,B,1,脱销1个单位；然而,x,12,=10,x,13,=0,x,21,=8,x,23,=4,x,33,=1，,则表示销地,B,3,脱销1个单位；但销地,B,3,的销量为5，本身就很少，不允许脱销，如何处理呢？,自来水分配问题：,水价90元/,kt,，,管理费45元/,kt,，,引水费如下表：,一、短缺资源的分配问题,供区,水库,甲,乙,丙,丁,供水量,kt,/d,A,16,13,22,17,50,B,14,13,19,15,60,C,19,20,23,-,50,最低需求,kt,/d,30,70,0,10,最高需求,kt,/d,50,70,30,不限,如何分配供水量，保障各区最低需求，获利最大？,34,第四节 运输模型的应用,利润=收入-成本，收入最大，成本最小，则利润最大。,收入：,每天供水总量是一常数，水价也是常数，则每天总收入也是常数。,每天供水总量若能全部售出，每天总收入则能达到最大。,丁区最高需求不限，每天总供水量能全售出。,每天总收入是常数与水量分配无关，可以不与考虑。,成本：,各区管理费相同45元/,kt,，,每天售水总量是一常数，则管理费也是常数。,各区引水费不同，如果总的引水费达到最小，总成本则最低。,如何分配水量，既满足最低需求，又使总的引水费最低？,最大需求量：,供水总量=50+60+50=160，四区最低需求量=30+70+10=110，故丁区最大需求量160-110+10=60。,四区最大需求=50+70+30+60=210，比供水总量160多50，则是一个产小于销的不平衡问题。,分析,35,第四节 运输模型的应用,产小于销的运输问题化为平衡问题，虚设水库,D，,供水量50。,各区的最低需求为基本需求，不允许脱销不能由虚设水库,D,供水，故单位引水费（运费）为,M。,各区的最大需求与最低需求的差为额外需求，可以由虚设水库,D,供水，故单位引水费（运费）为,0,。,供区,水库,供水量,A,50,B,60,C,50,甲1,甲2,乙,丙,丁1,丁2,16,16,13,22,17,17,14,14,13,19,15,15,19,19,20,23,M,M,销量,30,20,70,30,10,50,D,M,0,M,0,M,0,50,36,第四节 运输模型的应用,用表上作业法求得最优方案,供区,水库,甲1,甲2,乙,丙,丁1,丁2,供水量,A,50,50,B,20,10,30,60,C,30,20,0,50,D,30,20,50,销量,30,20,70,30,10,50,最优分配方案：水库,A,向乙区供水50，水库,B,分别向乙区、丁区供水20和40，水库,C,向甲区供水50，不给丙区供水。,最小引水费：13,50+1320+15(10+30)+19(30+20)=2460,引水,管理费：45(50+60+50)=7200 总成本：2460+7200=9600 总收入：90(50+60+50)=14400 最大获利：14400-9600=4740,37,第四节 运输模型的应用,产地与销地之间存在转运站。,面粉转运问题：,三个面粉加工厂，两个糕点生产厂,，,两个中转站。,二、资源转运问题,终点,始点,面粉厂,中转站,糕点厂,生产能力,A,1,A,2,A,3,T,1,T,2,B,1,B,2,面粉厂,A,1,3,2,3,-,6,8,3,A,2,4,2,5,2,13,7,4,A,3,-,2,3,2,11,4,3,中转站,T,1,3,5,2,6,2,5,T,2,-,3,2,7,-,2,糕点厂,B,1,6,-,-,2,-,9,4,B,2,-,-,4,-,3,9,6,如何调运，总运费最低？,38,第四节 运输模型的应用,最小转运能力,t,=max,a,i,，,b,j,=10,销地,产地,面粉厂,中转站,糕点厂,产 量,A,1,A,2,A,3,T,1,T,2,B,1,B,2,面粉厂,A,1,A,2,A,3中转站,T,1,T,2,糕点厂,B,1,B,2,销量,0,3,2,3,M,6,8,4,0,2,5,2,13,7,M,2,0,3,2,11,4,3,5,2,0,6,2,5,M,3,2,7,0,M,2,6,M,M,2,M,0,9,M,M,4,M,3,9,0,13,14,13,10,10,10,10,面粉厂产量:,a,i,+t,糕点厂产量:,t,转运站产量:,t,面粉厂销量:,t,糕点厂销量:,b,j,+t,转运站销量:,t,10,10,10,10,10,14,16,3,2,3,-,6,8,3,4,2,5,2,13,7,4,-,2,3,2,11,4,3,3,5,2,6,2,5,-,3,2,7,-,2,6,-,-,2,-,9,4,-,-,4,-,3,9,6,39,第四节 运输模型的应用,用表上作业法求得最优方案,最优分配方案：面粉厂,A,3,向糕点厂,B,2,直接运输2吨，,A,1,、,A,2,、,A,3,向中转站,T,1,和,T,2,运输3、4、1吨，中转站,T,1,和,T,2,分别向糕点厂,B,1,、,B,2,运输4、4吨。,最小运费：3,3+24+31+42+24+24=44,销地,产地,面粉厂,中转站,糕点厂,产 量,A,1,A,2,A,3,T,1,T,2,B,1,B,2,面粉厂,A,1,A,2,A,3,中转站,T,1,T,2,糕点厂,B,1,B,2,销量,10,3,13,10,4,14,10,1,2,13,6,4,10,6,4,10,10,10,10,10,10,10,10,10,10,14,16,3,3,4,4,1,2,3,4,4,4,6,40,