《运输问题》PPT课件.ppt
运筹学OPERATIONAL RESEARCH,第三章 运输问题,第一节 运输问题及其数学模型,一、运输问题的典型形式及其数学模型,1.引例,求最小运费的运输方案,minZ=6x11+4x12+5x13+6x21+5x22+5x23,x11+x12+x13=300 x21+x22+x23=200 x11+x21=150 x12+x22=150 x13+x23=200 xij 0,A1,Am,B1,B2,Bn,a1,cij,A2,a2,am,bn,b2,b1,求最小运费的运输方案,2.典型的运输问题：,c11,c12,cm1,c21,c22,c2n,c1n,cmn,cm2,c11,c12,cm1,c21,c22,c2n,c1n,cmn,cm2,minZ=6x11+4x12+5x13+6x21+5x22+5x23,x11+x12+x13=300 x21+x22+x23=200 x11+x21=150 x12+x22=150 x13+x23=200 xij 0,3.运输问题的数学模型,i=1,2,j=1,2,3,xij 0,i=1,2,m,j=1,2,n,xij 0,典型运输问题的数学模型,二、运输问题数学模型的特点：运输问题一定有最优解；运输问题约束条件的系数矩阵：,x11+x12+x13=300 x21+x22+x23=200 x11+x21=150 x12+x22=150 x13+x23=200 xij 0,2个,3个,系数矩阵的特点：（1）约束条件的系数矩阵的元素只有两个：0、1。（2）元素 xij 对应于每一个变量在前m个约束方程中(第i个方程中)出现一次，在后n个约束方程中（第m+j 个方程中）也出现一次。（3）产销平衡问题为等式约束。（4）产销平衡问题中各产地产量之和与各销售地点的销量之和相等。,3.运输问题基变量的个数：m+n-1个,第二节 表上作业法,一、表上作业法的基本思想和步骤：1.基本思想：同单纯形法的基本思想,2.表上作业法的步骤（1）寻找初始基可行解；最小元素法、西北角法、沃格尔法（2）求出非基变量检验数（空格检验数），判断是否为最优解；闭回路法、位势法（3）换基改进，找到新的基可行解闭回路调整法（4）重复（2）（3）,二、确定初始基可行解（一）最小元素法：,求运费最小的运输方案。,例题（P82例1）,0,0,6,0,0,6,（二）西北角法,（二）西北角法,（三）沃格尔法,伏格尔法思路：一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而，对差额最大处，就应当采用最小运费调运,罚数=次小费用-最小费用,1、在运价表中分别计算出各行、列的行罚数和列罚数，并填入该表的最右列和最下行。2、从行或列差额中选出最大者，选择它所在行或列的最小元素。按类似于最小元素法优先供应，划去相应的行或列。3、对表中未划去的元素重复1，2步，直至所有的行和列被划掉为止。,沃格尔法基本步骤：,三、最优解的判别,(一)闭回路法 闭回路：从空格出发，遇到数字格可以旋转90度，最后回到空格所构成的回路。,思路：计算空格（非基变量）检验数,求空格检验数有两种方法,11=4-4+3-2=1 12=12-11+6-5=222=10-3+4-11+6-5=1 24=9-11+4-3=-131=8-2+3-4+11-6=10 33=11-6+11-4=12,（1）每一空格有且仅有一条闭回路；,（2）不允许由全部顶点是数字格构成的闭回路。,注：,minZ=c11x11+c12x12+c1nx1n+cm1xm1+cm2xm2+cmnxmn,(二)对偶变量法（位势法）,1.基本原理,设对偶变量向量为 Y=(u1,u2,um,v1,v2,vn)对偶规划为,j=C j-CBB-1 Pj=Cj-Y Pj ij=C ij-CBB-1 Pij=Cij-Y Pij=Cij-(u1,u2,um,v1,v2,vn)Pij=Cij-(ui+vj)当xij 为基变量时 ij=Cij-(ui+vj)=0 上式共m+n-1个，而对偶变量有m+n个，因此，任选一个对偶变量为0，可求出其余所有的ui，vj。再根据ij=Cij-(ui+vj)求出所有非基变量的检验数。,11=4-(3+0)=1 12=12-(10+0)=222=10-(10-1)=1 24=9-(11-1)=-131=8-(-5+3)=10 33=11-(-5+4)=12,四、解的改进闭回路调整法,1,3,2,4,以x24为换入变量，以(A2,B4)为第一个奇数顶点，对闭回路上顶点依此编号,找偶数点中最小运输量，闭回路上奇数顶点加上此数，偶数顶点减去此数,11=4-11+9-2=0 12=12-11+6-5=222=10-9+6-5=2 23=3-9+11-4=131=8-6+9-2=9 33=11-6+11-4=12,五、需要注意的问题（1）多个空格（非基变量）的检验数为负，任一个都可作为换入变量。一般ij0中最小的对应变量作为换入变量。（2）最优解时，如果有某非基变量的检验数为0，则说明该运输问题有无穷多最有解。（3）迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0(它的位置是在对应的同时划去的那行或那列的所有空格中对应单位运价最小的任一空格),练习：,求最小运费的运输方案,第三节 运输问题的进一步讨论一、产销不平衡的运输问题例1：,产大于销时，增加一个假想的销地,当产大于销时，即,加入假想销地Bn+1（假想仓库），销量为 运费为0,i=1,2,m,j=1,2,n,xij 0,i=1,2,m,j=1,2,n，n+1,xij 0,当销大于产时，即,加入假想产地Am+1，产量为 运费为0,i=1,2,m,j=1,2,n,xij 0,i=1,2,m，m+1,j=1,2,n,xij 0,A1,B1,B2,B3,A2,二、有转运的运输问题,产地,销地,m个产地n个销地都可以作为中间转运站，从而发送地接收地都有m+n个,将m个产地与n个销地统一编号，产地排在前，销地排在后，则有,假设为产销平衡问题，即,数学模型,其中t i为第i个地点转运物品的数量,ti或tj移到等式左侧，等式两端加Q 得：,其中t i为第i个地点转运物品的数量,令xii=Q-ti,xjj=Q-tj,cii=-c i,53,课件,其中c i为地i个地点转运单位物品的费用,运输表,运价表,1,3,5,2,4,10,5,4,3,2,6,5,2,20,5,30,4,1,3,5,3,40,例：两个产地1，2，两个销地4，5及中间转运站3,-4,5,3,M,M,4,2,5,5,-3,6,5,4,2,M,2,2,5,3,-3,5,M,-1,6,-5,用最小元素法得初始运输方案，再经两次迭代得最优解。,
