苏州大学运筹学课件第三章运输问题ppt-第三章运输问题.pptVIP

第三章 运输问题,运输问题的线性规划模型 运输问题的运输表 初始基础可行解的求法 最优解的获得 几种特殊的运输问题,运输问题网络图,供应地,运价,需求地,供应量,需求量,总供应量60吨,总需求量60吨,供求平衡的运输问题,1、运输问题的一般提法,问：如何合理调运，才能使总运费最少？,（供需平衡）,一、运输问题线性规划模型,供应地约束,需求地约束,设Xij 为发点运往收点的运输量.i=1,2,3 j=1,2,3,4,minZ=9X11+18X12+X13+10X14+11X21+6X22+8X23+18X24+14X31+12X32+2X33+16X34,s.t X11+X12+X13+X14 = 9 X21+X22+X23+X24 = 10 X31+X32+X33+X34 = 6,X11 +X21 +X31 = 4 X12 +X22 +X32 = 9 X13 +X23 +X33 = 7 X14 +X24 +X34 = 5,X11 X12 X13 X14 X21 X22 X23 X24 X31 X32 X33 X34 0,运输问题线性规划模型,Xij 0,s.t,2、运输模型的特点,由于前m个供应地约束和后n个需求地约束是线性相关的，因此运输问题系数矩阵的秩m+n。可以证明，运输问题系数矩阵的秩为m+n-1,即基可行解只有m+n-1个变量,3) 对偶问题,2、运输模型的特点,Xij,ij,运价,检验数,运量,二、 运输表的表示,运输问题的表格表示,运价,运量,检验数,ij,运输表中一个基必须具备的特点 1、一个基应占表中的m+n-1格; 2、构成基的同行同列格子不能构成闭回路; 3、一个基在表中所占的格子应包括表的每行和每列。,运输表中一个基必须具备特点,基在运输表中的表示,运输表中同行同列的变量组成回路,1、西北角法 2、最小元素法,三、初始基础可行解的求法,1、西北角法,8,13,13,14,6,6,2、最小元素法（1）,最小元素法（2）,最小元素法（3）,最小元素法（4）,最小元素法（5）,最小元素法（6）,闭回路从调运方案的某一空格出发，沿水平或垂直的方向前进，遇到一个适当的数字格便按与前进方向垂直的路径前进。经过若干次后，再回到原来出发的那个格，由此形成的封闭折线称为闭回路。 闭回路的性质： 以空格出发的闭回路存在且唯一； 不存在所有顶点都为数字格的闭回路。,四、最优解的获得,1、检验数的求法：闭回路法,-5,非基变量xij的检验数zij-cij闭回路法(1),算法：空格（i,j)的检验系数ij可表示为：由空格所作出的闭回路中所有偶数格对应的单位运价之和减去所有 奇数格对应的单位运价之和的差。 12=z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5,-5,13=z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5,-5,闭回路法(2),-5,z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7,-7,-5,闭回路法(3),-5,z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9,-9,-5,-7,闭回路法(4),-5,z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11,+11,-5,-7,-9,闭回路法(5),-5,z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3,+3,-5,-7,-9,+11,闭回路法(6),（1）将具有最大正检验数的变量作为入基变量； （2）由入基变量出发，找出一条闭合回路，在其偶数号中，取值最小的变量为出基变量； （3）运输量的调整，对所有奇数号的变量都加上调整量的值，所有偶数号的变量减掉调整量的值； （4）在新的基础可行解的基础上重新计算检验数，直到所有的检验数都小于零。,2、进基和离基变量的选择,x31进基, minx21,x33=min8,6=6, x33离基,+3,-5,-5,-7,-9,+11,例题，入基变量与进基变量的选择,调整运量,重新计算检验数,确定进基、离基变量,x14进基, minx11,x34=min14,13=13, x34离基,-11,-5,-5,+4,+2,-8,调整运量, 重新计算检验数,所有zij-cij0,得到最优解。 Min z=61+3 13+8 2+4 13+2 12+5 19=142,-11,-5,-5,-4,-8,-2,（一）产销不平衡的运输问题,1、供大于求,解决问题的思路：产销不平衡产销平衡,五、几种特殊的运输问题,供大于求，则虚设收地，运价为零,这样就把供求不平衡问题转化为供求平衡问题。,7,0,0,4,在新问题中，新得到的问题的最优解，实际上就是各发地存储多少、运出多少、运往何地，使总运价最低。,不平衡问题如左图，相应的平衡问题如右图,15 25,1,2,1,2,3,10,10,10,3,2,4,1,2,1,0,0,利用西北角法给出初始解,15,10,0,0,25,10,-2,-5,+6,X21进基，x22离基,15,10,0,0,25,10,+4,+1,-6,X13进基，x11离基,15,10,0,0,25,10,-4,-3,-2,2、供不应求,供不应求，则虚设发地，运价为零,3,10,0,0,0,（二）无运输通路,如：至无运输通路,无运输通路，则运价为M,M,例题，从发点2到收点2没有路线，虚设一条通路，并设c22=M,8-M,X12进基，x22离基,X13进基，x11离基,（三）运输问题的退化基础可行解：基变量的个数小于m+n-1,为了使基变量的个数保持m+n-1个，需要增加一个xij=0的基变量，但不能构成闭回路。,确定初始基础可行解,西北角法,最小元素法,求非基变量的检验数,闭回路法,确定进基变量,确定离基变量,得到新的基础可行解,运输问题单纯形法总结,沿回路调整运量,35,6,38,4,22,5,30,z=1428,例题：用西北角法得到初始基础可行解,-3,z12-c12=(c11-c21+c22)-c12=(8-9+10)-12=-3,z=1428,用闭回路法求各非基变量的检验数,35,6,38,4,22,5,30,-3,-2,用闭回路法求各非基变量的检验数,35,6,38,4,22,5,30,-3,-2,-9,用闭回路法求各非基变量的检验数,35,6,38,4,22,5,30,-3,-2,-9,-11,用闭回路法求各非基变量的检验数,35,6,38,4,22,5,30,-3,-2,-9,-11,+5,用闭回路法求各非基变量的检验数,35,6,38,4,22,5,30,-3,-2,-9,-11,+5,+14,用闭回路法求各非基变量的检验数,35,6,38,4,22,5,30,-3,-2,-9,-11,+5,+14,+9,用闭回路法求各非基变量的检验数,35,6,38,4,22,5,30,-3,-2,-9,-11,+5,+14,+9,+4,用闭回路法求各非基变量的检验数,35,6,38,4,22,5,30,-3,-2,-9,-11,+5,+14,+9,+4,+2,用闭回路法求各非基变量的检验数,35,6,38,4,22,5,30,-3,-2,-9,-11,+5,+14,+9,+4,+2,x32进基，x33离基,35,6,16,26,22,5,30,-3,-2,+5,+3,-9,-14,-5,-10,-12,重新用闭回路法计算非基变量的检验数,35,6,16,26,22,5,30,-3,-2,+5,+3,-9,-14,-5,-10,-12,x14进基，x34离基,30,11,11,26,2