1、第三章 运输问题,运输问题的线性规划模型 运输问题的运输表初始基础可行解的求法最优解的获得几种特殊的运输问题,运输问题网络图,供应地,运价,需求地,供应量,需求量,总供应量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
2、 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,
3、运价,检验数,运量,二、 运输表的表示,运输问题的表格表示,运价,运量,检验数,ij,运输表中一个基必须具备的特点1、一个基应占表中的m+n-1格;2、构成基的同行同列格子不能构成闭回路;3、一个基在表中所占的格子应包括表的每行和每列。,运输表中一个基必须具备特点,基在运输表中的表示,运输表中同行同列的变量组成回路,1、西北角法2、最小元素法,三、初始基础可行解的求法,1、西北角法,8,13,13,14,6,6,2、最小元素法（1）,最小元素法（2）,最小元素法（3）,最小元素法（4）,最小元素法（5）,最小元素法（6）,闭回路从调运方案的某一空格出发，沿水平或垂直的方向前进，遇到一个适当的数
4、字格便按与前进方向垂直的路径前进。经过若干次后，再回到原来出发的那个格，由此形成的封闭折线称为闭回路。 闭回路的性质： 以空格出发的闭回路存在且唯一； 不存在所有顶点都为数字格的闭回路。,四、最优解的获得,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,闭
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）将具有最大正检验数的变量作为入基
6、变量；（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,调整运量, 重新计算检验数,所
7、有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,在新问题中，新得到的问题的最优解，实际上就是各发地存储多少、运出多少、运往何地，使总运价最低。,不平衡问题如左图，相应的平衡问题如右图,1525,1,2,1,2,3,10,10,10,3,2,4,1,2,1,0,0,利用西北角法给出初始解,15,10,0,0,2
8、5,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的基变量，但不能构成闭回路。,确定初始基础可行解,西北角
9、法,最小元素法,求非基变量的检验数,闭回路法,确定进基变量,确定离基变量,得到新的基础可行解,运输问题单纯形法总结,沿回路调整运量,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,用闭回路法求各非基变
10、量的检验数,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,
11、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,27,5,30,-3,-2,-5,-2,-9,-14,0,-5,-7,重新计算各非基变量的检验数,已获得最优解。x11=30，x14=5，x21=11，x22=11，x23=26，x32=27，x44=30，min z=1095,问题：从A1到B1的运价C11=8，从A1到B2的运价C12=12 在什么范围内变化，以上最优解保持不变？,
