运筹学 三章(运输问题).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,浙江科技学院经济管理学院管工系,*,第三章 运输问题,3.1,运输问题及其数学模型,3.2,表上作业法,3.3,运输问题的进一步讨论,1/30/2026,1,浙江科技学院经济管理学院管工系,本章学习要求,掌握表上作业法及其在产销平衡运输问题求解中的应用,掌握产销不平衡运输问题的求解方法,1/30/2026,2,浙江科技学院经济管理学院管工系,3.1,运输问题及其数学模型,1.,运输问题的一般提法,：,假设有,m,个生产地点，可以供应某种物资（以后称为产地），用,A,i,来表示，,i=1,m,有,n,个销地，用,B,j,来表示，,j=1,n,，产地的产量和销地的销量分别为,a,i,b,j,，从产地,A,i,到销地,B,j,运输一个单位物资的运价为,C,ij,，这些数据可汇总于下表，在假设产销平衡的条件下，即,a,i,=,b,j,，问该如何调运物品使总运费最小？,B,1,B,2,B,n,产量,A,1,C,11,C,12,C,1n,a,1,A,2,C,21,C,22,C,2n,a,2,A,m,C,m1,C,m2,C,mn,a,m,销量,b,1,b,2,b,n,1/30/2026,3,浙江科技学院经济管理学院管工系,建模：设,x,ij,表示从,A,i,到,B,j,的运量，则所求的数学模型为：,min=,c,ij,x,ij,s.t.,x,ij,=,a,i,i=1,m,x,ij,=,b,j,j=1,n,j=1,n,i=1,m,i=1,m,j=1,n,x,ij,0 i=1,m,j,=1,n,1/30/2026,4,浙江科技学院经济管理学院管工系,2.,例如,：三个产地四个销地，用网络表示,2,3,1,2,3,4,1,b,1,=22,b,2,=13,b,3,=12,b,4,=13,a,2,=27,a,3,=19,a,1,=14,产地,运价,销地,6,7,5,3,4,8,2,7,5,9,10,6,产量,销量,总产量,60,吨,总销量,60,吨,产销平衡的运输问题,1/30/2026,5,浙江科技学院经济管理学院管工系,运输问题线性规划模型,产地约束,销地约束,1/30/2026,6,浙江科技学院经济管理学院管工系,运输问题的表格表示,1/30/2026,7,浙江科技学院经济管理学院管工系,注意：,运输问题有可行解的充要条件为：,平衡运输问题有最优解,平衡运输问题的约束方程组的系数矩阵的系数矩阵,A,的秩为,m+n-1,运输问题的求解过程与单纯形法类似，只是更简单，通常称表上作业法，而且是求解极小化问题。,运输问题的系数矩阵具有什么特点？,运输问题的,LD,是怎样的？,1/30/2026,8,浙江科技学院经济管理学院管工系,3.2,表上作业法,初始基可行解的确定,最优性检验,基变换,1/30/2026,9,浙江科技学院经济管理学院管工系,运输问题基的表示,m,个产地、,n,个销地的运输问题，除了满足可行的条件外，任何一个基要满足以下条件：,基变量的个数为,m+n-1,；,基变量不能形成闭回路；,1/30/2026,10,浙江科技学院经济管理学院管工系,1,2,3,4,1,2,3,1,2,3,4,1,2,3,1,2,3,4,1,2,3,1,2,3,4,1,2,3,1,2,3,4,1,2,3,1,2,3,4,1,2,3,基在运输表中的表示,1/30/2026,11,浙江科技学院经济管理学院管工系,1,2,3,4,1,2,3,1,2,3,4,1,2,3,1,2,3,4,1,2,3,1,2,3,4,1,2,3,1,2,3,4,1,2,3,1,2,3,4,1,2,3,运输表中同行同列组成回路的变量,1/30/2026,12,浙江科技学院经济管理学院管工系,一,.,初始基可行解的确定,西北角法,最小元素法,沃格尔法,1/30/2026,13,浙江科技学院经济管理学院管工系,1.,西北角法,8,13,13,14,6,6,方法：优先满足运输表中左上角空格的供销要求,填一个数字只能划去一行或一列,1/30/2026,14,浙江科技学院经济管理学院管工系,2.,最小元素法,12,0,15,13,0,1,13,0,2,19,3,0,1,2,0,2,0,0,方法：按单位运价的大小，决定供应的先后，优先满足单位运价最小者的供销要求（就近供应）,1/30/2026,15,浙江科技学院经济管理学院管工系,3.,沃格尔法,3,2,12,3,2,3,3,1,1,*,3,1,13,行罚数,列罚数,4,1,4,*,13,*,1,2,19,方法：计算出每一行及每一列中单位运价最小和次小的两个元素之间的差值，再从差值最大的行或列中找出单位运价最小者，优先满足其供销关系。,1/30/2026,16,浙江科技学院经济管理学院管工系,二,.,最优性检验求,非基变量的检验数,闭回路法,位势法,1/30/2026,17,浙江科技学院经济管理学院管工系,1.,闭回路法,方法,求非基变量检验数,ij,以该变量所在格为顶点，其他顶点为基变量找一个闭回路，从该非基变量顶点为“”，“”，“”，“”依次加减其运价，即为检验数。,意义：,以该非基变量充当基变量时单位运量运费的损失。当所有的,ij,0,，则已得运输问题的最优解。即单位物品由,i-j,引起总运费的变化。,1/30/2026,18,浙江科技学院经济管理学院管工系,8,13,13,14,6,6,1.,闭回路法,(1),12,=c,12,-c,22,+c,21,-c,11,=7-4+8-6=5,5,1/30/2026,19,浙江科技学院经济管理学院管工系,8,13,13,14,6,6,1.,闭回路法,(2),5,13,=c,13,-c,23,+c,21,-c,11,=5-2+8-6=5,5,1/30/2026,20,浙江科技学院经济管理学院管工系,8,13,13,14,6,6,1.,闭回路法,(3),5,5,14,=(c,14,-c,34,+c,33,-c,23,+c,21,-c,11,)=3-6+10-2+8-6=7,7,1/30/2026,21,浙江科技学院经济管理学院管工系,8,13,13,14,6,6,1.,闭回路法,(4),5,5,7,12,=c,24,-c,34,+c,33,-c,23,=7-6+10-2=9,9,1/30/2026,22,浙江科技学院经济管理学院管工系,8,13,13,14,6,6,1.,闭回路法,(5),5,5,7,9,32,=c,32,-c,24,+c,23,-c,33,=9-4+2-10=-3,-3,1/30/2026,23,浙江科技学院经济管理学院管工系,8,13,13,14,6,6,1.,闭回路法,(6),5,5,7,9,-3,31,=c,31,-c,21,+c,23,-c,32,=5-8+2-10=-11,-11,1/30/2026,24,浙江科技学院经济管理学院管工系,2.,位势法,该法也称对偶变量法，我们知道一般标准运输问题的对偶问题为：,U,i,V,j,无约束,由,LP,中,ij,的定义：,ij,=C,ij,-C,B,B,-1,P,ij,C,ij,-Y,P,ij,=C,ij,-(u,1,u,2,u,m,v,1,v,2,v,n,)P,ij,=,c,ij,-(u,i,+v,j,),对基变量而言：,c,ij,=,(,u,i,+v,j,),由,m+n-1,个基变量对应,m+n-1,个线性方程,而,LD,的变量有,m+n,个，对偶问题有无穷多解，则可设其中一个最优解为,0,，而推导出其他分量。从而求出非基变量的检验数。,1/30/2026,25,浙江科技学院经济管理学院管工系,8,13,13,14,6,6,2.,位势法,(1),u,i,v,j,0,6,2,2,0,10,-4,1/30/2026,26,浙江科技学院经济管理学院管工系,8,13,13,14,6,6,2.,位势法,(2),u,i,v,j,0,6,2,2,0,10,-4,5,5,7,9,-13,-3,1/30/2026,27,浙江科技学院经济管理学院管工系,三,.,基变换闭回路法,与单纯形法一样，如果所有非基变量检验数,ij,0,，则该基解为最优解，否则不是最优解，需要进行基变换，换入变量的确定方法一样，设换入变量,x,lk,的检验数为,lk,，,换出,变量为,x,sf,以,x,lk,和基变量为顶点找一个闭回路，分别标号,”,+”,”-”,”+”,”_”,；在标号为,”,-”,的最小的运量为调整量，在闭回路上进行调整，“”的加“,-”,的减，当存在,x,sf,为,0,时，为换出变量，得一新的基可行解，再求检验数。,1/30/2026,28,浙江科技学院经济管理学院管工系,8,13,13,14,6,6,1.,基变换,-,确定换入换出变量,5,5,7,9,-3,-11,-11,-,-,6,1/30/2026,29,浙江科技学院经济管理学院管工系,8,13,13,14,6,6,1.,基变换得新的基解,-,-,6,2,12,1/30/2026,30,浙江科技学院经济管理学院管工系,13,13,14,1.,基变换得新的基解,6,2,12,1/30/2026,31,浙江科技学院经济管理学院管工系,确定初始基础可行解,西北角法,沃格尔法,求非基变量的检验数,闭回路法,对偶变量法,确定进基变量,确定离基变量,得到新的基础可行解,表上作业法总结,沿闭回路调整运量,最小元素法,1/30/2026,32,浙江科技学院经济管理学院管工系,单纯形法与表上作业法比较,单纯形法（,Min,）,表上作业法,确定初始基变量,X,B,+,松驰变量,+,（人工变量）,X,B,系数矩阵为,I,，,m,个,其余,X,N,最小元素法、沃格尔法等,X,B,数字格，,m+n-1,个,X,N,空格,检验数,基变量,j,=0,非基变量,j,=c,j,-c,B,B,-1,p,j,基变量,ij,=0,非基变量,ij,=,c,ij,-U,i,-V,j,调整,进基：,min,j,j,0,出基：,minb,i,/a,ik,，,a,ik,0,进基：,min,ij,ij,总销量时，,可增加一个假想销地,B,n+1,销量,a,i,b,j,，,C,i,n+1,=0,，,当总产量,b,j,（产量,销量）所以要虚构一销地,B,5,，其销量,b,5,=30,，而,c,i5,=0,，这样，就转化成了一个产销平衡问题。,B,1,B,2,B,3,B,4,B,5,产量,A,1,30,50,80,40,0,30,A,2,70,40,80,60,0,50,A,3,100,30,50,20,0,60,销量,15,10,40,45,30,140,140,1/30/2026,39,浙江科技学院经济管理学院管工系,例如：,B,1,B,2,B,3,B,4,产量,A,1,3,11,3,10,9,A,2,1,9,2,8,4,A,3,7,4,10,5,7,销量,13,6,15,6,20,40,1/30/2026,40,浙江科技学院经济管理学院管工系,二、一些变形和推广,1,、最大化问题,1,）找出单位物资效益表（,c,ij,）中的最大元素,M,，即,M=,maxc,ij,2),令,c,ij,=M-,c,ij,，并视为运价。,3,）由,c,ij,构成单位运价表，按通常的表上作业法求解，求得最优解后把所得结果转换为原问题的答案。,2,、销量不确定,（有最高需求和最低需求）,设销地,B,k,的最低需求为,b,k,，最高需求为,b,k,”,，这时可把看作,B,k,和,B,k,”,两个销地，,B,k,需求量,b,k,，,B,k,”,的需求量,b,k,”,-,b,k,1/30/2026,41,浙江科技学院经济管理学院管工系,例：设某种材料有,A,1,、,A,2,、,A,3,三个生产厂家，其产品供应,B,1,、,B,2,、,B,3,、,B,4,四个城市，假定等量的材料在这些城市的使用效果相同，已知各建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材的运价如表所示，求使运费最少的调运方案？,B,1,B,2,B,3,B,4,产量,A,1,16,13,22,17,50,A,2,14,13,19,15,60,A,3,19,20,23,M,50,最低需求,30,70,0,10,最高需求,50,70,30,不限,1/30/2026,42,浙江科技学院经济管理学院管工系,B,1,B,2,B,3,B,4,产量,A,1,16,13,22,17,50,A,2,14,13,19,15,60,A,3,19,20,23,M,50,最低需求,30,70,0,10,最高需求,50,70,30,不限,B,1,B,1,B,2,B,3,B,4,B,4,销量,30,20,70,30,10,50,A1,A,2,A,3,A,4,产量,50,60,50,50,16,14,19,M,16,14,19,0,13,13,20,M,22,19,23,0,17,15,M,M,17,15,M,0,1/30/2026,43,浙江科技学院经济管理学院管工系,4,、缺货损失问题,如下表，设销地,1,不允许缺货；销地,2,缺货，单位损失费,3,元；销地,3,缺货，单位损失费,2,元，问如何处理？,B,1,B,2,B,3,产量,A,1,5,1,7,10,A,2,6,4,6,80,A,3,3,2,5,15,销量,65,55,25,B,1,B,2,B,3,产量,A,1,5,1,7,10,A,2,6,4,6,80,A,3,3,2,5,15,销量,65,55,25,A,4,40,M,3,2,3,、指定销售问题,如规定销地,1,的需求量必须由产地,4,供应，如何处理？,1,）直接令,x,41,=b,1,2),令,c,41,=-M,，或者,c,11,=c,21,=c,31,=M,这样销地,1,的需求量肯定是由产地,1,供应了。,1/30/2026,44,浙江科技学院经济管理学院管工系,三、生产与存储问题,例：某厂按合同须于当年每个季度末分别提供,10,、,15,、,25,、,20,台同一规格的起重机，已知该厂各季度的生产能力及生产每台起重机的成本如表所示，若生产出来的起重机当季不交货，每台每积压一个季度工厂需支付保管及维护费,0.15,万元，试问在按合同完成任务的情况下，工厂应如何安排生产计划才能使全年消耗的生产与存贮费用的总和最少？,季度,工厂生产能力（台,/,季）,成本（万元,/,台）,交货量（台）,1,25,10.8,10,2,35,11.10,15,3,30,11.00,25,4,10,11.30,20,1/30/2026,45,浙江科技学院经济管理学院管工系,发货点：生产起重机的四个季度发货量：生产能力收货点：按合同交付起重机的四个季度收货量：按合同提供起重机的数量,c,ij,=,第,i,季度每台起重机的生产成本,+,（,j-i,）个季度每台起重机的存贮费（,ji,）,1,2,3,4,5,发量（台）,1,25,2,35,3,30,4,10,收量（台）,10,15,25,20,30,10.80,10.95,11.10,11.25,M,11.10,11.25,11.40,M,M,11.00,11.15,M,M,M,11.30,0,0,0,0,1/30/2026,46,浙江科技学院经济管理学院管工系,四、有转运的运输问题,1,、运输表的构成,1,）产地：原产地、中间转运站、转运物资的销地,2,）销地：原销地、中间转运站、转运物资的产地,3,）设各转运站转运物资的数量均为,a,i,这样专职转运站的产量和销量均为,a,i,而原产地,Ai,的产量均为（,a,i,+,a,i,）,原销地,B,j,的销量均为（,b,j,+,a,i,）,4),将各条线路实际的运输单位列成单位运价表，其中不可能的运输其单位运价用,M,表示。,1/30/2026,47,浙江科技学院经济管理学院管工系,2,、举例：,A,、,B,两个化肥厂每年各生产磷肥,900,万吨、,600,万吨，这些化肥要通过公路运到三个港口，然后再装船运往其他各地，已知三个港口,C,、,D,、,E,每年能承担的船运量分别为,700,、,400,、,300,万吨，两个工厂及三个港口之间均有公路相通，且已知单位运价如表所示，为按需要把磷肥运到各港口，怎样安排运输才能使运费最少？,A,B,C,D,E,A,0,2,9,10,7,B,2,0,7,10,10,C,9,7,0,3,4,D,10,10,3,0,2,E,7,10,4,2,0,1/30/2026,48,浙江科技学院经济管理学院管工系,A,B,C,D,E,A,0,2,9,10,7,B,2,0,7,10,10,C,9,7,0,3,4,D,10,10,3,0,2,E,7,10,4,2,0,P,发量,收量,2400,2100,1500,1500,1500,1500,1500,2200,1900,1800,100,0,0,0,0,0,1/30/2026,49,浙江科技学院经济管理学院管工系,习题：,3.10,3.12,1/30/2026,50,浙江科技学院经济管理学院管工系,