交通运输与物流工程专业

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,交通运输与物流工程专业,运 筹 学 教 程,同济大学,2006,1,第三章 运输问题,运输问题及其数学模型,运输问题基本理论,运输问题表上作业法,运输问题模型建立,2,3.1 运输问题及其数学模型,一、一般运输问题,设某种货物有,m,个产地,A1，A2，,Am,产量分别为,a1,a2,am,有,n,个销地,B1,B2,Bn,销量分别为,b1,b2,bn，,而且从,Ai,到,Bj,的单位运价为,Cij,。若产销平衡（,ai=bj），,问如何制定调运方案，可以使总运费最小？,3,B,1, B,2, , B,n,产地,销量,b,1, b,2, , b,n,产量,销地,a,i,=b,j,产销平衡表/单位运价表,4,设,X,ij,表示从产地,Ai,调运至销地,Bj,的货物量,i=1,2,m; j=1,2,n，,则运输问题的,（,LP）,模型如下：,min z =,j=1,2,n,i=1,2,m,X,ij,=0,二、运输问题模型,5,B,1, B,2, , B,n,Ai,b,j,b,1, b,2, , b,n,a,i,Bj,运输问题的上述,（LP）,模型，,可以形象地表示如下：,6,B,1, B,2, , B,n,Ai,b,j,b,1, b,2, , b,n,a,i,Bj,若隐含,m*n,个决策变量，,可以省略地表示如下如下：,运输模型,7,2,3,2,1,3,4,1,s,2,=27,s,3,=19,d,1,=22,d,2,=13,d,3,=12,d,4,=13,s,1,=14,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,例1：,8,（,LP）,模型,供应地约束,需求地约束,9,B1,B2,B3,B4,6,7,5,3,A1,x,11,x,12,x,13,x,14,14,8,4,2,7,A2,x,21,x,22,x,23,x,24,27,5,9,10,6,A3,x,31,x,32,x,33,x,34,19,22,13,12,13,运输模型,10,B1,B2,B3,B4,6,7,5,3,A1,14,8,4,2,7,A2,27,5,9,10,6,A3,19,22,13,12,13,运输模型,11,3.2 运输问题基本理论,一、运输问题基本特征,（一）决策变量的个数：,m*n;,（二）约束方程的个数：,m+n；,（三）独立方程的个数：,m+n-1：,（,WHY）,（四）系数矩阵的特殊结构（,P80）,变量,X,ij,的系数向量,A,ij,A,ij,=(,0,0,1,0,0,0,1,0,),T,i,分量,j,分量,12,二、运输问题的对偶问题,设,U,i,，V,j,，i=1,2,mj=1,2,n，,为运输问题,的对偶变量，则运输问题的对偶问题如下：,max w =,U,i,+V,j,0,得到最优解。,Min z=61+3 13+8 2+4 13+2 12+5 19=142,11,5,5,4,8,2,41,3.4 运输问题模型建立,P118,例3-8,P119,例3-9,P120,例3-10,P125,例3-15,42,