运筹学运输问题（PPT55页)

第四章运输问题运输问题的表示网络图、线性规划模型、运输表初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量运输问题的提出•运输问题的直接背景是单一品种的物质的运输调度问题，其典型情况是：设某物品有m个产地A1,A2,…,Am,各产地的产量分别为a1,a2,…,am;n个销地B1,B2,…,Bn,各销地的销量分别为b1,b2,…,bn.假定从产地Ai(i=1,2,…,m)向销地Bj(j=1,2,…,n)运输单位物质的运价为cij,问怎样调运这些物品才能使得总运费最小？运输问题的表示——网络图A1A2Am产地B1B2Bn销地a1a2amb1b2bnc11c12c1nc21c22c2ncm1cm2cmn若则称该问题为平衡运输问题，否则称为非平衡运输问题。njjmiiba11运输问题的表示—表格表示B1B2…Bnc11c12…c1nA1x11x12…x1na1c21c22…c2nA2x21x22…x2na2…………………………cm1cm2…cmnAmxm1xm2…xmnamb1b2…bn这个表常称为运输表运输问题的数学模型•平衡问题的数学模型为njmixnjbxmiaxxczijjmiijnjiijminjijij,,2,1;,,2,1,0,,2,1,,,2,1,min1111各产地运出的物资数量等于其产量各销地接受的物资数量等于其销量其中njjmiiba11运输问题数学模型的特点•运输问题一定存在最优解实际上是平衡运输问题的一个可行解。此外由于目标函数有下界，因此平衡运输问题存在最优解。miijiijaQnjmiQbax1;,2,1;,,2,1,其中•运输问题系数矩阵的特点111111111111111111212222111211mnmmnnxxxxxxxxxmn上述矩阵的列向量具有形式00100100ijP第i个第(m+j)个因此运输问题约束条件系数矩阵的元素只能是0或1，对应变量xij列除了第i个与第(m+j)个分量为1外，其它分量均为零此外产销平衡运输问题的数学模型还具有特点：•所有约束条件都是等式•前m个约束条件的和等于后n个约束条件的和（可以证明尽管有m+n个约束条件，但独立的约束条件只有m+n-1个）运输问题的例子—表格表示B1B2B3B4412411A1x11x12x13x141821039A2x21x22x23x241085116A3x31x32x33x3422814121448运输问题的例子—线性规划模型0≥14=++12=++14=++8=++22=+++10=+++16=+++6+11+5+8+9+3+01+2+11+4+21+4=min343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxs.t.xxxxxxxxxxxxz供应地约束需求地约束运输问题的解•运输问题的解可以表示为X=(xij),它表示一个运输方案，其中xij表示从产地Ai到销地Bj运送的物质数量•在用运输表表示运输问题时，也常将xij取的值填入对应的格子表示一个解。•但是对基可行解，通常仅将基变量取的值填入相应的格中，称之为数字格，而对应着非基变量的格子，则不填数字，称之为空格。注：在一个基可行解中，所有mn个变量（格子）中，只有m+n-1个基变量（数字格）求解运输问题的表上作业法求初始基可行解（初始调运方案）•西北角法•最小元素法•沃格尔法初始基可行解—西北角法1234412411116210392108511632281412148864814123441241111621039210851163228141214初始基可行解—最小元素法82101486沃格尔（Vogel）法1234412411116210392108511632281412142（5）130111421（3）0128（2）1201812（7）61224检验数的计算•两种方法：闭回路法和对偶变量法•闭回路法的原理：非基变量的检验数等于非基变量增加一个单位时，目标函数的改变量检验数的计算—闭回路法（1）1234412411116210392108511632281412148210148612123131111cccc检验数的计算—闭回路法（2）1234412411116210392108511632281412148210148613234141212cccc2检验数的计算—闭回路法（3）12344124111162103921085116322814121482101486132341413232222cccccc21检验数的计算—闭回路法（4）1234412411116210392108511632281412148210148611413232424cccc21-1检验数的计算—闭回路法（5）12344124111162103921085116322814121482101486134141323213131cccccc21-110123441241111621039210851163228141214检验数的计算—闭回路法（6）1234412411116210392108511632281412148210148613414133333cccc21-11012检验数的计算—对偶变量法对偶变量法也称为位势法，它是利用运输问题的对偶问题求检验数。设运输问题的对偶变量矩阵为则对偶问题为],,,,,,,['2121mmvvvuuuY均无约束jiijjinjjjmiiivunjmicvuvbuaw,,,2,1;,,2,1,max11利用单纯形法的矩阵表示可知，变量xij的检验数可以表示为)('1jiijijijijBijijvucPYcPBCc另一方面，对于(m+n-1)个基变量而言，检验数等于零，故可以得到包含(m+n)个变量的(m+n-1)个方程)(0jiijvuc由该方程组求出对偶变量后即可计算出所有的检验数。123441241111621039210851163228141214检验数的计算—对偶变量法82101486u1=0v3=4v4=11u2=-1u3=-5v1=3v2=10121-11012解的改进12344124111162103921085116322814121482101486-1解的改进12344124111162103921085116322814121481214842解的改进12344124111162103921085116322814121481214842u1=0v3=4v4=11u2=-2u3=-5v1=4v2=100221912最优解（最优调运方案）12344124111162103921085116322814121481214842最小运费：244861452982411124z表上作业法的几个问题•换入变量的确定•退化（两种情况）•无穷多个最优解的判别产销不平衡的运输问题•解决的基本思路：将其转化为产销平衡的运输问题求解产大于销的运输问题这时有njjmiiba11，数学模型为),,2,1;,,2,1(0),,2,1(),,2,1(min1111njmixnjbxmiaxxczijjmiijinjijminjijij处理的办法为增加一个假想的销地Bn+1，其销量为njjmiinbab111各个产地运送物质到假想销地的单位运价为零，即ci(n+1)=0B1B2…BnBn+1c11c12…c1n0A1a1c21c22…c2n0A2a2…………………cm1cm1…cmn0Amamb1b2…bnbn+1假想的销地这时有njjmiiba11，数学模型为),,2,1;,,2,1(0),,2,1(),,2,1(min1111njmixnjbxmiaxxczijjmiijinjijminjijij销大于产的运输问题处理的办法为增加一个假想的产地Am+1，其产量为miinjjmaba111假想产地运送物质到各个销地的单位运价为零，即c(m+1),1=0B1B2…Bnc11c12…c1nA1a1c21c22…c2nA2a2………………cm1cm1…cmnAmam00…0Am+1am+1b1b2…bn假想的产地•表上作业法的计算步骤：分析实际问题列出产销平衡表及单位运价表确定初始调运方案（最小元素法或Vogel法）求检验数（位势法）所有检验数≥0找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案得到最优方案，算出总运价表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取σij0中最小者对应的变量为换入变量。（2）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的σij＝0，则该问题有无穷多最优解。⑵退化解：※表格中一般要有(m+n-1)个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空格处加一个0即可。※利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调整量θ，选择任意一个最小运量对应的基变量作为出基变量，并打上“×”以示作为非基变量。销地产地B1B2B3B4产量A116A210A322销量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11检验数是0，经过调整，可得到另一个最优解。产销不平衡的运输问题运输问题运输问题的应用例：有三个供应地要将物资运往五个需求地区，各产地的产量和个地区的需求以及运费情况如下表。要求：其中B2地区的115个单位必须满足。供\求B1B2B3B4B5产量A1101520204050A22040153030100A33035405525130需要量25115603070产销不平问：应如何运输总运费最小？运输问题运输问题的应用供\求B1B2B3B4B5产量A1101520204050A22040153030100A33035405525130需要量25115603070产销不平解：由于产量小于需求，因此虚设以产地A4，其产量为供需的差额20。与此项有关的费用一般设为0。又因为B1地区的需求要保证，所以应该迫使虚设产地运输到该地区的运费成本极高，从而在优化过程中实现0运量。因此取该项费用为一个充分大的数M。由此可以建立如下的产销平衡运输费用表：运输问题运输问题的应用供\求B1B2B3B4B5产量A1101520204050A22040153030100A33035405525130需要量25115603070产销不平供\求B1B2B3B4B5产量A1101520204050A22040153030100A33035405525130A40M00020需要量25115603070产销平衡运输问题思考题1：某部有B1，B2，B3三个作战单位。每年分别需要某军用品3500吨、1100吨、2400吨，这些用品都要由A1,A2两兵工厂负责供应，两兵工厂生产的军用品质量均相同。假设A1,A2的供应