1 1第三章第三章 运输问题运输问题第三章第三章 运输问题运输问题 运输问题的线性规划模型运输问题的线性规划模型 运输问题的运输表运输问题的运输表初始基础可行解的求法初始基础可行解的求法最优解的获得最优解的获得几种特殊的运输问题几种特殊的运输问题2 2第三章第三章 运输问题运输问题2312341运输问题网络图d1=22d2=13d3=12d4=13s2=27s3=19s1=14供应地运价需求地6753482759106供应量需求量总供应量60吨总需求量60吨供求平衡的运输问题3 3第三章第三章 运输问题运输问题1、运输问题的一般提法、运输问题的一般提法 收点收点发点发点 B1 B2 B3 B4 发发 量量 A1 A2 A39 18 1 1011 6 8 1814 12 2 16 9 10 6 收量收量4 9 7 5问：如何合理调运，才能使总运费最少？问：如何合理调运，才能使总运费最少？（供需平衡）（供需平衡） 一、运输问题线性规划模型一、运输问题线性规划模型4 4第三章第三章 运输问题运输问题供应地约束需求地约束设设Xij Xij 为发点运往收点的运输量为发点运往收点的运输量.i=1,2,3 j=1,2,3,4.i=1,2,3 j=1,2,3,4minZ=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 = 5X11 X12 X13 X14 X21 X22 X23 X24 X31 X32 X33 X34 05 5第三章第三章 运输问题运输问题 运输问题线性规划模型运输问题线性规划模型Xij 0s.t6 6第三章第三章 运输问题运输问题2、运输模型的特点、运输模型的特点 由于前m个供应地约束和后n个需求地约束是线性相关的，因此运输问题系数矩阵的秩m+n。可以证明，运输问题系数矩阵的秩为m+n-1,即基可基可行解只有行解只有m+n-1个变量个变量7 7第三章第三章 运输问题运输问题3) 对偶问题2、运输模型的特点、运输模型的特点8 8第三章第三章 运输问题运输问题 收点收点发点发点 B1 B2 B3 B4 发发 量量 A1 A2 A39 18 1 1011 6 8 1814 12 2 16 9 10 6 收量收量4 9 7 5Xijij运价检验数运量二、二、 运输表的表示运输表的表示9 9第三章第三章 运输问题运输问题运输问题的表格表示运价运量检验数ij1010第三章第三章 运输问题运输问题q 运输表中一个基必须具备的特点运输表中一个基必须具备的特点1、一个基应占表中的一个基应占表中的m+n-1格格;2、构成基的同行同列格子不能构成闭回路、构成基的同行同列格子不能构成闭回路;3、一个基在表中所占的格子应包括表的每行、一个基在表中所占的格子应包括表的每行和每列。和每列。运输表中一个基必须具备特点运输表中一个基必须具备特点1111第三章第三章 运输问题运输问题123412312341231234123123412312341231234123基在运输表中的表示1212第三章第三章 运输问题运输问题123412312341231234123123412312341231234123运输表中同行同列的变量组成回路1313第三章第三章 运输问题运输问题1、西北角法、西北角法2、最小元素法、最小元素法三、初始基础可行解的求法三、初始基础可行解的求法1414第三章第三章 运输问题运输问题1、西北角法8131314661515第三章第三章 运输问题运输问题2、最小元素法（1）1616第三章第三章 运输问题运输问题最小元素法（2）1717第三章第三章 运输问题运输问题最小元素法（3）1818第三章第三章 运输问题运输问题最小元素法（4）1919第三章第三章 运输问题运输问题最小元素法（5）2020第三章第三章 运输问题运输问题最小元素法（6）2121第三章第三章 运输问题运输问题闭回路闭回路从调运方案的某一空格出发，沿水平或垂直的方向前进，遇到一个适当的数字格便按与前进方向垂直的路径前进。经过若干次后，再回到原来出发的那个格，由此形成的封闭折线称为闭回路。 闭回路的性质：闭回路的性质： 以空格出发的闭回路存在且唯一； 不存在所有顶点都为数字格的闭回路。 四、最优解的获得四、最优解的获得1、检验数的求法：闭回路法、检验数的求法：闭回路法第三章第三章 运输问题运输问题-5非基变量xij的检验数zij-cij闭回路法(1)算法：空格（算法：空格（i,j)的检验系数的检验系数ij可表示为：由空格所作出的闭回路中所有可表示为：由空格所作出的闭回路中所有偶数格偶数格对应的单位运价之和减去所有对应的单位运价之和减去所有 奇数格奇数格对应的单位运价之和的差。对应的单位运价之和的差。12=z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5第三章第三章 运输问题运输问题-513=z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-5闭回路法(2)第三章第三章 运输问题运输问题-5z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7-7-5闭回路法(3)第三章第三章 运输问题运输问题-5z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9-9-5-7闭回路法(4)第三章第三章 运输问题运输问题-5z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11+11-5-7-9闭回路法(5)第三章第三章 运输问题运输问题-5z32-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-23232第三章第三章 运输问题运输问题（一）产销不平衡的运输问题一）产销不平衡的运输问题1 1、供大于求、供大于求解决问题的思路：产销不平衡产销平衡五、几种特殊的运输问题五、几种特殊的运输问题3333第三章第三章 运输问题运输问题供大于求供大于求，则虚设收地，运价为零，则虚设收地，运价为零,这样就把供求不平这样就把供求不平衡问题转化为供求平衡问题。衡问题转化为供求平衡问题。1231356 222427 181210117004在新问题中，新得到的问题的最优解，实际上就是各在新问题中，新得到的问题的最优解，实际上就是各发地存储多少、运出多少、运往何地，使总运价最低。发地存储多少、运出多少、运往何地，使总运价最低。3434第三章第三章 运输问题运输问题不平衡问题如左图，相应的平衡问题如右图不平衡问题如左图，相应的平衡问题如右图152512123101010324121003535第三章第三章 运输问题运输问题利用西北角法给出初始解12341856 10527109 51010101015 10 002510-2-5+63636第三章第三章 运输问题运输问题X21进基，x22离基12341856 51027109 51010101015 10 002510+4+1-63737第三章第三章 运输问题运输问题X13进基，x11离基12341856 10527109 10510101015 10 002510-4-3-23838第三章第三章 运输问题运输问题2 2、供不应求、供不应求3939第三章第三章 运输问题运输问题v供不应求供不应求，则虚设发地，运价为零，则虚设发地，运价为零123135620 242710 1217113100004040第三章第三章 运输问题运输问题（二）无运输通路（二）无运输通路如：至无运输通路4141第三章第三章 运输问题运输问题v无运输通路无运输通路，则运价为，则运价为M M1231356 222427 18121011M4242第三章第三章 运输问题运输问题例题，从发点2到收点2没有路线，虚设一条通路，并设c22=M123185625101527M915M-45101020108-M4343第三章第三章 运输问题运输问题X12进基，x22离基123185625520427M91554-M101020104444第三章第三章 运输问题运输问题X13进基，x11离基123185625-420527M915108-M51020104545第三章第三章 运输问题运输问题（三）运输问题的退化基础可行解：基变量的个数小于m+n-1 为了使基变量的个数保持m+n-1个，需要增加一个xij=0的基变量，但不能构成闭回路。第三章第三章 运输问题运输问题确定初始基础可行解西北角法最小元素法求非基变量的检验数闭回路法确定进基变量确定离基变量得到新的基础可行解运输问题单纯形法总结沿回路调整运量第三章第三章 运输问题运输问题1234181271135291061448313515122747131110304138263535638422530z=1428例题：用西北角法得到初始基础可行解第三章第三章 运输问题运输问题1234181271135352910614486384313515122722547131110303041382635-3z12-c12=(c11-c21+c22)-c12=(8-9+10)-12=-3z=1428用闭回路法求各非基变量的检验数第三章第三章 运输问题运输问题1234181271135291061448313515122747131110304138263535638422530-3-2用闭回路法求各非基变量的检验数第三章第三章 运输问题运输问题1234181271135291061448313515122747131110304138263535638422530-3-2-9用闭回路法求各非基变量的检验数第三章第三章 运输问题运输问题1234181271135291061448313515122747131110304138263535638422530-3-2-9-11用闭回路法求各非基变量的检验数第三章第三章 运输问题运输问题1234181271135291061448313515122747131110304138263535638422530-3-2-9-11+5用闭回路法求各非基变量的检验数第三章第三章 运输问题运输问题1234181271135291061448313515122747131110304138263535638422530-3-2-9-11+5+14用闭回路法求各非基变量的检验数第三章第三章 运输问题运输问题1234181271135291061448313515122747131110304138263535638422530-3-2-9-11+5+14+9用闭回路法求各非基变量的检验数第三章第三章 运输问题运输问题1234181271135291061448313515122747131110304138263535638422530-3-2-9-11+5+14+9+4用闭回路法求各非基变量的检验数第三章第三章 运输问题运输问题1234181271135291061448313515122747131110304138263535638422530-3-2-9-11+5+14+9+4+2用闭回路法求各非基变量的检验数第三章第三章 运输问题运输问题1234181271135291061448313515122747131110304138263535638422530-3-2-9-11+5+14+9+4+2x32进基，x33离基第三章第三章 运输问题运输问题12341812711352910614483135151227471311103041382635356162622530-3-2+5+3-9-14-5-10-12重新用闭回路法计算非基变量的检验数第三章第三章 运输问题运输问题12341812711352910614483135151227471311103041382635356162622530-3-2+5+3-9-14-5-10-12x14进基，x34离基第三章第三章 运输问题运输问题123418127113529106144831351512274713111030413826353011112627530-3-2-5-2-9-140-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 在什么范围内变化，以上最在什么范围内变化，以上最优解保持不变？优解保持不变？