运运输输规规划划(TransportationProblem)运输规划的数学模型运输规划的数学模型表上作业法表上作业法产销不平衡的运输问题产销不平衡的运输问题例：某运输问题的资料如下：例：某运输问题的资料如下：单位 销地 运价产地产量2910291342584257销量3846一、运输问题的数学模型一、运输问题的数学模型数学模型的一般形式数学模型的一般形式已知资料如下：已知资料如下：单 销 产 量产地产量销 量当产销平衡时，其模型如下：当产销平衡时，其模型如下：当产大于销时，其模型是：当产大于销时，其模型是：当产小于销时，其模型是：当产小于销时，其模型是： 特征：特征： 1 1、平衡运输问题必有可行解，也、平衡运输问题必有可行解，也必有最优解；必有最优解； 2 2、运输问题的基本可行解中应包、运输问题的基本可行解中应包括括 m+n1 个基变量。个基变量。 . .重复重复. . ，直到找到最优解为止。，直到找到最优解为止。步骤：步骤： . .找出初始基本可行解（初始调运方案，一找出初始基本可行解（初始调运方案，一般般m+n-1m+n-1个数字格），用西北角法、最小元素法；个数字格），用西北角法、最小元素法； . .求出各非基变量的检验数，判别是否达到求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用最优解。如果是停止计算，否则转入下一步，用位势法计算；位势法计算； . .改进当前的基本可行解（确定换入、换改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；出变量），用闭合回路法调整； 二、表上作业法二、表上作业法例一、某运输资料如下表所示：例一、某运输资料如下表所示：单位单位销地销地运价运价产地产地产量产量311310719284741059销量销量36561 1、求初始方案：、求初始方案： . .西北角法（或左上角法）：西北角法（或左上角法）： 此法是纯粹的人为的规定，没有理论依据和实际背此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下：而受欢迎。方法如下：3 6 5 63 6 5 67 7 4 4 9 93 34 4 4 4 9 90 6 5 60 6 5 64 40 0 4 4 9 90 2 5 60 2 5 62 20 0 2 2 9 90 0 5 60 0 5 62 20 0 0 0 9 90 0 3 60 0 3 63 63 60 0 0 00 0 0 00 0 0 0 0 03 4 0 03 4 0 00 2 2 00 2 2 00 0 3 60 0 3 6总的运费总的运费(3(33)3)(4(411)11)(2(29)9)(2(22)2)(3(310)10)(6(65)5)135135元元B1B2B3B4产量产量A17A2 4A39销量销量3656311310192741058341633 . .最小元素法：最小元素法： 基本思想是就近供应，即从运价最小的地方开始供基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。应（调运），然后次小，直到最后供完为止。总的运输费用（总的运输费用（3 31 1）（）（6 64 4） （4 43 3）（）（1 12 2）（）（3 31010）（）（3 35 5）8686元元 ijij0 0 （因为目标函数要求最小化）（因为目标函数要求最小化） 表格中有调运量的地方为基变量，空格处为非基变表格中有调运量的地方为基变量，空格处为非基变 量。基变量的检验数量。基变量的检验数ijij0，非基变量的检验数，非基变量的检验数ijij0 0。 ijij0表示运费增加。表示运费增加。2 2、最优解的判别（检验数的求法）：、最优解的判别（检验数的求法）： . .闭合回路法：闭合回路法： B1B2B3B4产量产量A17A24A39销量销量3656313463（1）（1）（1）（1）计算如下：空格处（计算如下：空格处（A1B1）(13) (1)3 (12) (1)1 1 此数即为该空格处的检验数。此数即为该空格处的检验数。1B1B2B3B4产量产量A17A24A39销量销量365631363124B1B2B3B4产量产量A17A24A39销量销量36563136312-14B1B2B3B4产量产量A17A24A39销量销量365631363121-14B1B2B3B4产量产量A17A24A39销量销量365631363121-1124B1B2B3B4产量产量A17A24A39销量销量365631363121-112104检验数中有负数，说明原方案不是最优解。检验数中有负数，说明原方案不是最优解。B1B2B3B4产量产量A17A24A39销量销量365600000121-112100 运输问题的约束条件共有运输问题的约束条件共有m+n个，其中：个，其中：m是产地产量的限制；是产地产量的限制；n是销地销量的限制。是销地销量的限制。其对偶问题也应有其对偶问题也应有m+n个变量，据此：个变量，据此：ij=cij(ui+vj),其中前其中前m个计为个计为ui（i=1.2m）,前前n个个计为计为vj（j=1.2n）由单纯形法可知，基变量的由单纯形法可知，基变量的ij0 cij(ui+vj) 0 因此因此ui,vj可以求出。可以求出。.位势法位势法接上例：接上例：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表成本表B1B2B3B4A1293100A218291A33425529310 u2+v1=1 u2+v3=2 u3+v2=4u1+v4=10u1+v3=3u3+v4=5令：令：u10u10v12u2 1v29u3 5v33v410(ui+vj)按按ij=cij(ui+vj)计算检验数，并以计算检验数，并以ij0 检验，检验，或用或用(ui+vj)cij0 检验。检验。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A334-25(ui+vj)B1B2B3B4A11200A20101A3100120表中还有负数，表中还有负数，说明还未得到最说明还未得到最优解，应继续调优解，应继续调整。整。ij 闭合回路调整法（原理同单纯形法一样）闭合回路调整法（原理同单纯形法一样）接上例：接上例：B1B2B3B4产量产量A17A24A39销量销量3656313463（1）（1）（1）（1）3 3、改进的方法、改进的方法B1B2B3B4产量产量A1527A2314A3639销量销量36566563销量销量9A34A27A1产量产量B4B3B2B1313463（1）（1）（1）（1）B1B2B3B4A10200A20210A390120经检验经检验所有所有ijij0 0得到最优解，得到最优解，最小运费为最小运费为8585元。元。0v4v3v2v1u354A3u281A2u1103A1B4B3B2B1成本表成本表1039355242A328171A2010393A1B4B3B2B1(ui+vj) . .无穷多最优解：产销平衡的运输问题必定存最无穷多最优解：产销平衡的运输问题必定存最优解。如果非基变量的优解。如果非基变量的ij0，则该问题有无穷多最，则该问题有无穷多最优解。如上例：优解。如上例：（1.1）中的检验数是中的检验数是0，经过调整，经过调整，可得到另一个最优解。可得到另一个最优解。 . .退化：表格中一般要有退化：表格中一般要有(m+n-1)个数字格。但有个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时时，在分配运量时则需要同时划去一行和一列，这时需要补一个需要补一个0 0，以保证有，以保证有(m+n-1)个数字格。一般可在个数字格。一般可在划去的行和列的任意空格处加一个划去的行和列的任意空格处加一个 0 0 即可。即可。4 4、表上作业法计算中的问题、表上作业法计算中的问题例例1：B1B2B3B4A178143A226355A3142782176213552682176 例例2：B1B2B3A11221A23132A32314124B1B2B3A111A222A3441240001 1、产大于销：模型、产大于销：模型方法是先将原问题变成平衡问题，需假设一个销地方法是先将原问题变成平衡问题，需假设一个销地(Bn+1 )(实际上考虑产地的存量实际上考虑产地的存量)，三、产销不平衡的运输问题及其求解方法三、产销不平衡的运输问题及其求解方法模型为：模型为： 2 2、销大于产：同样假设一个产地即可，变化同上。、销大于产：同样假设一个产地即可，变化同上。单位运价表中的单位运价为单位运价表中的单位运价为B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5A121134070A210359050A378120702030406040B1B2B3B4B5A170A250A370203040604040303020302020用最小元素法用最小元素法求初始方案求初始方案例题：例题：已知某运输问题的资料如下表所示已知某运输问题的资料如下表所示B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125 1 1、表中的发量、收量单位为：吨，运价单位为：元、表中的发量、收量单位为：吨，运价单位为：元/ /吨吨 试求出最优运输方案试求出最优运输方案. . 练习：练习： 2 2、如将、如将A2的发量改为的发量改为1717，其它资料不变，试求最优调，其它资料不变，试求最优调 运方案。运方案。B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125解：解：1、用最小元素法求初始方案、用最小元素法求初始方案B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4A153A211A324运费为运费为108108元元/ /吨吨2 2、用位势法判断：、用位势法判断：B1B2B3B4uiA153u1A211u2A324u3vjv1v2v3v4成本表成本表B1B2B3B4uiA153u1A211u2A324u3vjv1v2v3v4u1+v3=5u2+v4=1u1+v4=3u3+v2=2u2+v1=1u3+v4=4令：令：u10u10v13u22v21u31v35v43B1B2B3B4uiA1530A2112A3241vj3153B1B2B3B4uiA131530A211312A342641vj3153(ui+vj)B1B2B3B4A12653A21321A33274B1B2B3B4A13153A21131A34264cijB1B2B3B4A11500A20410A31010表中还有负数，说表中还有负数，说明没有得到最优解，明没有得到最优解，调整运输方案。调整运输方案。ij(ui+vj)B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A31302222新的运送方案新的运送方案B1B2B3B4A153A212A324新的成本表新的成本表B1B2B3B4uiA141530A212203A352641vj4153(ui+vj)1 总的运费总的运费105元元/吨吨B1B2B3B4A14153A21220A35264B1B2B3B4A12653A21321A33274B1B2B3B4A12500A20501A32010表中还有负数，说表中还有负数，说明没有得到最优解，明没有得到最优解，继续调整运输方案。继续调整运输方案。cij(ui+vj)1 (ij)1 013A3210A2510A1B4B3B2B13512vj14623A330221A203512A1uiB4B3B2B1(ui+vj)2 42A32A2352A1B4B3B2B1新的成本表新的成本表013A312A25010A1B4B3B2B1新的运送方案新的运送方案总的运费总的运费85元元/吨吨B1B2B3B4A12653A21321A33274cijB1B2B3B4A12153A21 220A33264(ui+vj)2B1B2B3B4A10500A22501A30010(ij)2表中没有负数，说表中没有负数，说明已经得到最优解。明已经得到最优解。但有无穷多最优解。但有无穷多最优解。013A312A2510A1B4B3B2B1最终的运送方案最终的运送方案总的运费总的运费85元元/吨吨B1B2B3B4发量发量A131215A27512A313013收量收量1013125B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125B1B2B3B4A125A211A327B1B2B3B4uiA125u1A211u2A327u3vjv1v2v3v4成本表成本表u1+v1=2u2+v4=1u1+v3=5u3+v2=2u2+v1=1u3+v3=7令：令：u10u10v12u21v20u32v35v42B1B2B3B4uiA120520A21-141-1A342742vj2052(ui+vj)B1B2B3B4A12653A21321A33274cijB1B2B3B4uiA10601A204-20A3-1000vjijB1B2B3B4发量发量A131215A27512A313013收量收量1013125B1B2B3B4发量发量A110515A27512A313013收量收量1013125B1B2B3B4B5发量发量A110515A2102517A313013收量收量10131255B1B2B3B4B5发量发量A12653015A21321017A33274013收量收量10131255B1B2B3B4B5A150A2121A324B1B2B3B4B5uiA150u1A2121u2A324u3vjv1v2v3v4v5成本表成本表u1+v3=5u2+v3=2u1+v5=0u2+v4=1u2+v1=1u3+v2=2u3+v4=4令：令：u10u10v14u2-3v22u30v35v44v50B1B2B3B4B5uiA1425400A21-121-3-3A3425400vj42540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5A1-240-10A204004A3-10200ij505B45121310收量收量1313A317210A215510A1发量发量B5B3B2B1B1B2B3B4B5发量发量A1100515A212517A313013收量收量10131255B1B2B3B4B5A1250A221A324B1B2B3B4B5uiA1250u1A221u2A324u3vjv1v2v3v4v5成本表成本表u1+v1=2u2+v4=1u1+v3=5u3+v2=2u1+v5=0u3+v4=4u2+v3=2令：令：u10u10v12u2-3v22u30v35v44v50B1B2B3B4B5uiA1225400A2-1-121-3-3A3225400vj22540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5A1040-10A224004A310200ijB1B2B3B4B5发量发量A1100515A212517A313013收量收量10131255B1B2B3B4B5发量发量A1100515A212517A313013收量收量10131255B1B2B3B4B5发量发量A110515A212517A31313收量收量10131255C=75已知资料如下表所示，问如何供电能使总的输电费已知资料如下表所示，问如何供电能使总的输电费用为最小？用为最小？发电厂 发电量A1700A2200A3100城市需电量B1500B2250B3100B4150电力供需表电力供需表B1B2B3B4A110523A24312A35634单位输电费用单位输电费用作业：作业：B1B2B3B4A1A2A3初始方案初始方案10010050250400100B1B2B3B4A110523A24312A35634单位输电费用单位输电费用发电厂 发电量A1700A2200A3100城市需电量B1500B2250B3100B4150电力供需表电力供需表B1B2B3B4A11053A212A35B1B2B3B4uiA1105230A29412-1A350-3-2-5vj10523B1B2B3B4uiA10000A2-5-100A30666vjij成本表成本表- (ui+vj) =cij (ui+vj) A3A2A1B4B3B2B1初始方案初始方案10010050250400100B1B2B3B4A140025050A2100100A3100B1B2B3B4A1300250150A2100100A3100B1B2B3B4A11053A241A35成本表成本表B1B2B3B4uiA1105730A24-11-3-6A3502-2-5vj10573 (ui+vj) 调运方案调运方案B1B2B3B4uiA100-50A20405A30616vjij- (ui+vj) =cijB1B2B3B4A1300250150A2100100A3100B1B2B3B4A1200250100150A2200A3100B1B2B3B4A110523A24A35成本表成本表调运方案调运方案B1B2B3B4uiA1105230A24-1-4-3-6A350-3-2-5vj10523 (ui+vj) B1B2B3B4uiA10000A20455A30666vjij- (ui+vj) =cijB1B2B3B4A1200250100150A2200A3100C=5200 试用表上作业法求最优解试用表上作业法求最优解 2002006060555545454040销量销量75758 87 77 79 9A A3 370704 46 63 35 5A A2 255556 62 26 63 3A A1 1产量产量B B4 4B B3 3B B2 2B B1 1 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量产量A A1 1404015155555A A2 2454525257070A A3 3404035357575销量销量4040454555556060200200最小总费用为最小总费用为945945。