广工管理运筹学第三章-运输问题课件.ppt

1、A1A2Am产地B1B2Bn销地a1a2amb1b2bnc11c12c1nc21c22c2ncm1cm2cmn若 则称该问题为平衡运输问题，否则称为非平衡运输问题。njjmiiba11 B1 B2 Bn c11 c12 c1n A1 x11 x12 x1n a1 c21 c22 c2n A2 x21 x22 x2n a2 cm1 cm2 cmn Am xm1 xm2 xmn am b1 b2 bn 这个表常称为运输表 njmixnjbxmiaxxczijjmiijnjiijminjijij,2,1;,2,1,0,2,1,2,1,min1111各产地运出的物资数量等于其产量各销地接受的物资数量等

2、于其销量其中njjmiiba11miijiijaQnjmiQbax1;,2,1;,2,1,其中运输问题系数矩阵的特点111111111111111111212222111211mnmmnnxxxxxxxxxmn上述矩阵的列向量具有形式00100100ijP第i个第(m+j)个因此运输问题约束条件系数矩阵的元素只能是0或1，对应变量xij列除了第i个与第(m+j)个分量为1外，其它分量均为零014=+12=+14=+8=+22=+10=+16=+6+11+5+8+9+3+01+2+11+4+21+4=min343332312423222114131211342414332313322212312

3、111343332312423222114131211343332312423222114131211xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxs.t.xxxxxxxxxxxxz供应地约束需求地约束 1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 8864814 1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 初始基可行解最小元素法82101486沃格尔（Vogel）法 1 2 3 4 4 12 4 11 1 16

4、 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 2(5)130111421(3)0128(2)1201812（7）61224 1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 821014862123131111cccc 1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 8210148613234141212cccc2检验数的计算检验数的计算闭回路法（闭回路法（3）1 2 3 4 4 12 4 11 1 16 2 1

5、0 3 9 2 10 8 5 11 6 3 22 8 14 12 14 82101486132341413232222cccccc21检验数的计算检验数的计算闭回路法（闭回路法（4）1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 8210148611413232424cccc21-1检验数的计算检验数的计算闭回路法（闭回路法（5）1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 82101486134141323213131cccccc21-11

6、0 1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 检验数的计算检验数的计算闭回路法（闭回路法（6）1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 8210148613414133333cccc21-11012,2121mmvvvuuuY均无约束jiijjinjjjmiiivunjmicvuvbuaw,2,1;,2,1,max11利用单纯形法的矩阵表示可知，变量利用单纯形法的矩阵表示可知，变量xij的检的检验数可以表示为验数可以表示为)(1ji

7、ijijijijBijijvucPYcPBCc另一方面，对于另一方面，对于(m+n-1)个基变量而言，个基变量而言，检验数等于零，故可以得到包含检验数等于零，故可以得到包含(m+n)个个变量的变量的(m+n-1)个方程个方程由该方程组求出对偶变量后即可计算出所由该方程组求出对偶变量后即可计算出所有的检验数。有的检验数。通常指定通常指定u1=0.)(0jiijvuc 1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 检验数的计算对偶变量法82101486u1=0v3=4v4=11u2=-1u3=-5v1=3v2=10121

8、-11012 1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 82101486-1 1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 81214842解的改进 1 2 3 4 4 12 4 11 1 16 2 10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 81214842u1=0v3=4v4=11u2=-2u3=-5v1=4v2=100221912最优解（最优调运方案）1 2 3 4 4 12 4 11 1 16 2

9、10 3 9 2 10 8 5 11 6 3 22 8 14 12 14 81214842最小运费：244861452982411124z这时有njjmiiba11，数学模型为),2,1;,2,1(0),2,1(),2,1(min1111njmixnjbxmiaxxczijjmiijinjijminjijij处理的办法为增加一个假想的销地Bn+1，其销量为njjmiinbab111各个产地运送物质到假想销地的单位运价为零，即ci(n+1)=0 B1 B2 Bn Bn+1 c11 c12 c1n 0 A1 a1 c21 c22 c2n 0 A2 a2 cm1 cm1 cmn 0 Am am b1

10、 b2 bn bn+1 假想的销地这时有njjmiiba11，数学模型为),2,1;,2,1(0),2,1(),2,1(min1111njmixnjbxmiaxxczijjmiijinjijminjijij处理的办法为增加一个假想的产地Am+1，其产量为miinjjmaba111假想产地运送物质到各个销地的单位运价为零，即c(m+1),1=0 B1 B2 Bn c11 c12 c1n A1 a1 c21 c22 c2n A2 a2 cm1 cm1 cmn Am am 0 0 0 Am+1 am+1 b1 b2 bn 假想的产地243156324B11046A1A2A3B2B31161 a72a43a