运输问题TransportationProblem.ppt

运运  输输  问问  题题(Transportation  Problem)运输问题的数学模型运输问题的数学模型表上作业法表上作业法产销不平衡的运输问题产销不平衡的运输问题例：某运输问题的资料如下：例：某运输问题的资料如下：单位      销地       运价产地产量2910791342584257销量3846一、运输问题的数学模型一、运输问题的数学模型      数学模型的一般形式数学模型的一般形式         已知资料如下：已知资料如下：单         销        产    量产地产量销  量当产销平衡时，其模型如下：当产销平衡时，其模型如下：当产大于销时，其模型是：当产大于销时，其模型是：当产小于销时，其模型是：当产小于销时，其模型是： 运输问题特征：运输问题特征： 1 1、、m m个供应地，个供应地，n n个需求地的运输问题；个需求地的运输问题； 2 2、、决决策策变变量量个个数数为为 m*nm*n 个个，，约约束束条条件件个个数数为为 m+nm+n个；个； 3 3、系数矩阵中元素为、系数矩阵中元素为0 0或或1 1；； 4 4、、每每个个决决策策变变量量在在 m m 个个供供应应量量约约束束和和 n n 个个需求量约束中各出现一次；需求量约束中各出现一次； 5 5、系数矩阵的秩等于、系数矩阵的秩等于( ( m+n-1m+n-1 ) )个；个； 6 6、基本解中基变量个数等于（、基本解中基变量个数等于（m+n-1m+n-1））个；个； 7 7、平衡运输问题必有可行解，也必有最优解。

平衡运输问题必有可行解，也必有最优解 ⑷.⑷.重复重复⑵. ⑶⑵. ⑶，直到找到最优解为止直到找到最优解为止步骤：步骤： ⑴.⑴.找出初始基本可行解（初始调运方案，一找出初始基本可行解（初始调运方案，一般般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×3)(3×3)＋＋(4×11)(4×11)＋＋(2×9)(2×9)＋＋(2×2)(2×2)＋＋(3×10)(3×10)＋＋(6×5)(6×5)＝＝135135元元B1B2B3B4产量产量A17A2      4A39销量销量3656311310192741058341633 ⑵.⑵.最小元素法：最小元素法： 基本思想是就近供应，即从运价最小的地方开始供基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。

应（调运），然后次小，直到最后供完为止总的运输费用＝（总的运输费用＝（3×13×1）＋（）＋（6×46×4）） ＋（＋（4×34×3）＋（）＋（1×21×2）＋（）＋（3×103×10）＋（）＋（3×53×5）＝）＝8686元元（（3）伏格尔法）伏格尔法            考考虑虑到到最最小小运运费费与与次次小小运运费费及及相相互互差差额额问问题差额最大处应用最小运费调运差额最大处应用最小运费调运Cij            销地销地供地供地B1       B2        B3       B4供应量供应量A1A2A33         11         3       101          9          2         87          4         10        5749需需 求求 量量3          6          5         6    Cij        销销地地供地供地B1       B2        B3       B4行差行差A1A2A33         11         3       101          9          2         87          4         10        50 0 0 71 1 1 61 2列列  差差2          5          1        32                  1        332                      1        2 Xij(0)                   销地销地供地供地B1          B2          B3          B4供应量供应量A1A2A3749需需 求求 量量3             6             5           6                                   5              2  3                                              1                   6                             3用伏格尔法用伏格尔法 得初始调运方案如下：得初始调运方案如下：   表表1 σσijij≥0 0 （（因为目标函数要求最小化）因为目标函数要求最小化） 表格中有调运量的地方为基变量，空格处为非基变表格中有调运量的地方为基变量，空格处为非基变 量。

基变量的检验数量基变量的检验数σσijij＝＝0，，非基变量的检验数非基变量的检验数σσijij≥0 0 σσijij< 0 表示运费减少，表示运费减少， σσijij> 0 表示运费增加表示运费增加2 2、最优解的判别（检验数的求法）：、最优解的判别（检验数的求法）： ⑴.⑴.闭合回路法：闭合回路法： B1B2B3B4产量产量A17A2④③4A39销量销量3656313463（＋（＋1））（＋（＋1））（－（－1））（－（－1））①②  计算如下：空格处（计算如下：空格处（ A1 B1 ）＝）＝ 3-3+2-1＝1  此数即为该空格处的检验数此数即为该空格处的检验数1B1B2B3B4产量产量A17A24A39销量销量365631363124B1B2B3B4产量产量A17A24A39销量销量36563136312-14B1B2B3B4产量产量A17A24A39销量销量365631363121-14B1B2B3B4产量产量A17A24A39销量销量365631363121-1124B1B2B3B4产量产量A17A24A39销量销量365631363121-112104           检验数中有负数，说明原方案不是最优解。

检验数中有负数，说明原方案不是最优解B1B2B3B4产量产量A17A24A39销量销量365600000121-112100 运输问题的约束条件共有运输问题的约束条件共有m+n个，其中：个，其中：m是产地产量的限制；是产地产量的限制；n是销地销量的限制是销地销量的限制     其对偶问题也应有其对偶问题也应有m+n个变量，据此：个变量，据此： σij=cij－(ui+vj) ,其中前其中前m个计为个计为ui（（i=1.2…m））,前前n个计为个计为vj （（j=1.2…n））     由单纯形法可知，基变量的由单纯形法可知，基变量的σij＝ 0      ∴∴ cij－(ui+vj) ＝0 因此因此ui ,vj可以求出可以求出⑵.⑵.位势法位势法接上例：接上例：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表成本表B1B2B3B4A1293100A21829－－1A3－－34－－25－－529310   u2+v1=1    u2+ v3 =2                          u3+v2=4    u1+ v4 =10                        u1+v3=3   u3+ v4 =5     令：令： u1＝＝0u1＝＝0          v1＝＝2u2 ＝－＝－1     v2 ＝＝9u3 ＝－＝－5     v3 ＝＝3                   v4 ＝＝10 (ui+vj)        按按σij=cij－(ui+vj) 计算检验数，并以计算检验数，并以σij≥0 检验，检验，或用或用(ui+vj) －cij ≤0 检验。

检验B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A3－－34-25(ui+vj)－－B1B2B3B4A11200A2010－－1A3100120＝表中还有负数，表中还有负数，说明还未得到最说明还未得到最优解，应继续调优解，应继续调整σij ————闭合回路调整法（原理同单纯形法一样）闭合回路调整法（原理同单纯形法一样）接上例：接上例：B1B2B3B4产量产量A17A24A39销量销量3656313463（＋（＋1））（＋（＋1））（－（－1））（－（－1））3 3、改进的方法、改进的方法B1B2B3B4产量产量A1527A2314A3639销量销量36566563销量销量9A34A27A1产量产量B4B3B2B1313463（＋（＋1））（＋（＋1））（－（－1））（－（－1））B1B2B3B4A10200A20210A390120经检验经检验所有所有σσijij≥0 0得到最优解，得到最优解，最小运费为最小运费为8585元0v4v3v2v1u354A3u281A2u1103A1B4B3B2B1成本表成本表10393－－55－－24－－2A3－－28171A2010393A1B4B3B2B1(ui+vj) ⑴.⑴.无穷多最优解：产销平衡的运输问题必定存最无穷多最优解：产销平衡的运输问题必定存最优解。

如果非基变量的优解如果非基变量的σij＝0，，则该问题有无穷多最则该问题有无穷多最优解如上例：优解如上例：（1.1）中的检验数是中的检验数是 0，经过调整，，经过调整，可得到另一个最优解可得到另一个最优解 ⑵.⑵.退化：表格中一般要有退化：表格中一般要有(m+n-1)个数字格但有个数字格但有时，在分配运量时则需要同时划去一行和一列，这时时，在分配运量时则需要同时划去一行和一列，这时需要补一个需要补一个0 0，以保证有，以保证有(m+n-1)个数字格一般可在个数字格一般可在划去的行和列的任意空格处加一个划去的行和列的任意空格处加一个 0 0 即可4 4、表上作业法计算中的问题、表上作业法计算中的问题例例1：：B1B2B3B4A178143A226355A31427821762   1             3          5        5           2   6   82   1   7   6   例例2：：B1B2B3A11221A23132A32314124B1B2B3A111A222A34412400 0   1 1、产大于销：模型、产大于销：模型      方法是先将原问题变成平衡问题，需假设一个销地方法是先将原问题变成平衡问题，需假设一个销地(Bn+1 )(实际上考虑产地的存量实际上考虑产地的存量)，三、产销不平衡的运输问题及其求解方法三、产销不平衡的运输问题及其求解方法   模型为：模型为： 2 2、销大于产：同样假设一个产地即可，变化同上。

销大于产：同样假设一个产地即可，变化同上单位运价表中的单位运价为单位运价表中的单位运价为B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5 A121134070A210359050A378120702030406040B1B2B3B4B5 A170A250A370203040604040303020302020用最小元素法用最小元素法求初始方案求初始方案例题：例题：          已知某运输问题的资料如下表所示已知某运输问题的资料如下表所示B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125 1 1、表中的发量、收量单位为：吨，运价单位为：元、表中的发量、收量单位为：吨，运价单位为：元/ /吨吨 试求出最优运输方案试求出最优运输方案. . 练习：练习： 2 2、如将、如将A2的发量改为的发量改为1717，其它资料不变，试求最优调，其它资料不变，试求最优调 运方案B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125解：解：1、用最小元素法求初始方案、用最小元素法求初始方案B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4A153A211A324运费为运费为108108元元/ /吨吨2 2、用位势法判断：、用位势法判断：B1B2B3B4ui A153u1A211u2A324u3vj v1v2v3v4成本表成本表B1B2B3B4ui A153u1A211u2A324u3vj v1v2v3v4 u1+v3=5      u2+v4 =1 u1+v4 =3     u3+v2=2 u2+v1=1      u3+v4 =4     令：令： u1＝＝0u1＝＝0         v1＝＝3u2＝－＝－2     v2 ＝＝1u3 ＝＝1         v3 ＝＝5                   v4 ＝＝3 B1B2B3B4ui A1530A211－－2A3241vj 3153B1B2B3B4ui A131530A21－－131－－2A342641vj 3153(ui+vj)B1B2B3B4A12653A21321A33274B1B2B3B4A13153A21－－131A34264cij－B1B2B3B4A1－－1500A204－－10A3－－1010＝表中还有负数，说表中还有负数，说明没有得到最优解，明没有得到最优解，调整运输方案。

调整运输方案σij(ui+vj)B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A3130＋2＋2－2－2新的运送方案新的运送方案B1B2B3B4A153A212A324新的成本表新的成本表B1B2B3B4ui A141530A21－－220－－3A352641vj 4153(ui+vj)1 总的运费总的运费       105元元/吨吨B1B2B3B4A14153A21－－220A35264B1B2B3B4A12653A21321A33274－＝B1B2B3B4A1－－2500A20501A3－－2010表中还有负数，说表中还有负数，说明没有得到最优解，明没有得到最优解，继续调整运输方案继续调整运输方案cij(ui+vj)1  (σij)1 013A3210A2510A1B4B3B2B13512vj 14623A3－－302－－2－－1A203512A1ui B4B3B2B1(ui+vj)2 42A32A2352A1B4B3B2B1新的成本表新的成本表013A312A25010A1B4B3B2B1新的运送方案新的运送方案总的运费总的运费        85元元/吨吨B1B2B3B4A12653A21321A33274cijB1B2B3B4A12153A2－－1 －－220A33264(ui+vj)2 －＝B1B2B3B4A10500A22501A30010 (σij)2 表中没有负数，说表中没有负数，说明已经得到最优解。

明已经得到最优解但有无穷多最优解但有无穷多最优解013A312A2510A1B4B3B2B1最终的运送方案最终的运送方案总的运费总的运费 85元元/吨吨B1B2B3B4发量发量A131215A27512A313013收量收量1013125B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125B1B2B3B4A125A211A327B1B2B3B4ui A125u1A211u2A327u3vj v1v2v3v4成本表成本表 u1+v1=2      u2+v4 =1 u1+v3 =5     u3+v2 =2 u2+v1=1      u3+v3 =7     令：令： u1＝＝0u1＝＝0         v1＝＝2u2＝－＝－1     v2 ＝＝0u3 ＝＝2       v3 ＝＝5                   v4 ＝＝2 B1B2B3B4ui A120520A21-141-1A342742vj 2052(ui+vj)B1B2B3B4A12653A21321A33274cijB1B2B3B4ui A10601A204-20A3-1000vj σijB1B2B3B4发量发量A131215A27512A313013收量收量1013125B1B2B3B4发量发量A110515A27512A313013收量收量1013125B1B2B3B4B5发量发量A110515A2102517A313013收量收量10131255B1B2B3B4B5发量发量A12653015A21321017A33274013收量收量10131255B1B2B3B4B5A150A2121A324B1B2B3B4B5ui A150u1A2121u2A324u3vj v1v2v3v4v5成本表成本表 u1+v3=5      u2+v3 =2 u1+v5 =0     u2+v4 =1 u2+v1=1      u3+v2=2  u3+v4=4 令：令： u1＝＝0u1＝＝0         v1＝＝4u2＝＝-3        v2 ＝＝2u3 ＝＝0         v3 ＝＝5                   v4 ＝＝4                    v5＝＝0B1B2B3B4B5ui A1425400A21-121-3-3A3425400vj 42540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5 A1-240-10A204004A3-10200σij505B45121310收量收量1313A317210A215510A1发量发量B5B3B2B1B1B2B3B4B5发量发量A1100515A212517A313013收量收量10131255B1B2B3B4B5A1250A221A324B1B2B3B4B5ui A1250u1A221u2A324u3vj v1v2v3v4v5成本表成本表 u1+v1=2      u2+v4 =1 u1+v3 =5     u3+v2 =2 u1+v5=0      u3+v4=4 u2+v3=2 令：令： u1＝＝0u1＝＝0         v1＝＝2u2＝＝-3        v2 ＝＝2u3 ＝＝0         v3 ＝＝5                   v4 ＝＝4                    v5＝＝0B1B2B3B4B5ui A1225400A2-1-121-3-3A3225400vj 22540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5 A1040-10A224004A310200σijB1B2B3B4B5发量发量A1100515A212517A313013收量收量10131255B1B2B3B4B5发量发量A1100515A212517A313013收量收量10131255B1B2B3B4B5发量发量A110515A212517A31313收量收量10131255C =75      已知资料如下表所示，问如何供电能使总的输电费已知资料如下表所示，问如何供电能使总的输电费用为最小？用为最小？发电厂 发电量A1700A2200A3100城市需电量B1500B2250B3100B4150电力供需表电力供需表B1B2B3B4A110523A24312A35634单位输电费用单位输电费用作业：作业：B1B2B3B4A1A2A3初始方案初始方案10010050250400100B1B2B3B4A110523A24312A35634单位输电费用单位输电费用发电厂 发电量A1700A2200A3100城市需电量B1500B2250B3100B4150电力供需表电力供需表B1B2B3B4A11053A212A35B1B2B3B4ui A1105230A29412-1A350-3-2-5vj 10523B1B2B3B4ui A10000A2-5-100A30666vj σij成本表成本表-  (ui+vj) =cij (ui+vj) A3A2A1B4B3B2B1初始方案初始方案10010050250400100B1B2B3B4A140025050A2100100A3100B1B2B3B4A1300250150A2100100A3100B1B2B3B4A11053A241A35成本表成本表B1B2B3B4ui A1105730A24-11-3-6A3502-2-5vj 10573 (ui+vj) 调运方案调运方案B1B2B3B4ui A100-50A20405A30616vj σij-  (ui+vj) =cijB1B2B3B4A1300250150A2100100A3100B1B2B3B4A1200250100150A2200A3100B1B2B3B4A110523A24A35成本表成本表调运方案调运方案B1B2B3B4ui A1105230A24-1-4-3-6A350-3-2-5vj 10523 (ui+vj) B1B2B3B4ui A10000A20455A30666vj σij-  (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 14040  1515  5555A A2 2  4545  25257070A A3 3    404035357575销量销量4040454555556060200200最小总费用为最小总费用为945945。