运输问题(TransportationProblem)

1、运运 输输 问问 题题(Transportation Problem)运输问题的数学模型运输问题的数学模型表上作业法表上作业法产销不平衡的运输问题产销不平衡的运输问题例：某运输问题的资料如下：例：某运输问题的资料如下：单位 销地 运价产地产量2910791342584257销量38464321 BBBB321AAA一、运输问题的数学模型一、运输问题的数学模型 )4 . 3 . 2 . 1, 3 . 2 . 1(06483759524824371092min3424143323133222123121113433323124232221141312113433323124232221141312

2、11jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij 约约束束条条件件：目目标标函函数数：为为运运量量设设 数学模型的一般形式数学模型的一般形式 已知资料如下：已知资料如下：单 销 产 量产地产量销 量nBB 1mAA 1maa 1nbb 1mnmncccc 1111 ) ( 0min11ijjijijiijminjijijxbabxaxxcZ当产销平衡时，其模型如下：当产销平衡时，其模型如下：当产大于销时，其模型是：当产大于销时，其模型是： ) ( 0min11ijjijijiijminjijijxbabxaxxcZ当产小于销时，其模型是：当产小于销

3、时，其模型是：0, 0, 0)(0min ijjijjiijjijiijijijcbabaxbxaxxcZ并并假假设设： 运输问题特征：运输问题特征： 1 1、m m个供应地，个供应地，n n个需求地的运输问题；个需求地的运输问题； 2 2、决策变量个数为、决策变量个数为 m m* *n n 个，约束条件个数个，约束条件个数为为 m+nm+n个；个； 3 3、系数矩阵中元素为、系数矩阵中元素为0 0或或1 1； 4 4、每个决策变量在、每个决策变量在 m m 个供应量约束和个供应量约束和 n n 个个需求量约束中各出现一次；需求量约束中各出现一次； 5 5、系数矩阵的秩等于、系数矩阵的秩等于(

4、 ( m+n-1m+n-1 ) )个；个； 6 6、基本解中基变量个数等于（、基本解中基变量个数等于（m+n-1m+n-1）个；）个； 7 7、平衡运输问题必有可行解，也必有最优解。、平衡运输问题必有可行解，也必有最优解。 . .重复重复. . ，直到找到最优解为止。，直到找到最优解为止。步骤：步骤： . .找出初始基本可行解（初始调运方案，一找出初始基本可行解（初始调运方案，一般般m+n-1m+n-1个数字格），用最小元素法、西北角法、个数字格），用最小元素法、西北角法、伏格尔法；伏格尔法； . .求出各非基变量的检验数，判别是否达到求出各非基变量的检验数，判别是否达到最优解。如果是停止计算

5、，否则转入下一步，用最优解。如果是停止计算，否则转入下一步，用位势法计算；位势法计算； . .改进当前的基本可行解（确定换入、换改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；出变量），用闭合回路法调整； 二、表上作业法二、表上作业法例一、某运输资料如下表所示：例一、某运输资料如下表所示：单位单位 销地销地 运价运价 产地产地产量产量311310719284741059销量销量36564321 BBBB321AAA1 1、求初始方案：、求初始方案： . .西北角法（或左上角法）：西北角法（或左上角法）： 此法是纯粹的人为的规定，没有理论依据和实际背此法是纯粹的人为的规定，没有理论

6、依据和实际背景，但它易操作，特别适合在计算机上编程计算，因景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下：而受欢迎。方法如下：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

7、(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元元（3）伏格尔法）伏格尔法 考虑到最小运费与

8、次小运费及相互差额问考虑到最小运费与次小运费及相互差额问题。差额最大处应用最小运费调运。题。差额最大处应用最小运费调运。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 3 1 32 1 2 Xij(0) 销地销地供地供地B1 B2 B3 B4供应量供应量A1A2A3749需需 求求 量量3 6 5 6 5 2 3 1 6

9、 3用伏格尔法用伏格尔法 得初始调运方案如下：得初始调运方案如下： 表表1 ijij0 0 （因为目标函数要求最小化）（因为目标函数要求最小化） 表格中有调运量的地方为基变量，空格处为非基变表格中有调运量的地方为基变量，空格处为非基变 量。基变量的检验数量。基变量的检验数ijij0，非基变量的检验数，非基变量的检验数ijij0 0。 ijij 0 表示运费增加。表示运费增加。2 2、最优解的判别（检验数的求法）：、最优解的判别（检验数的求法）： . .闭合回路法：闭合回路法： B1B2B3B4产量产量A17A24A39销量销量3656313463（1）（1）（1）（1） 计算如下：空格处（计算

10、如下：空格处（ A1 B1 ） 3-3+2-11 此数即为该空格处的检验数。此数即为该空格处的检验数。1B1B2B3B4产量产量A17A24A39销量销量365631363124B1B2B3B4产量产量A17A24A39销量销量36563136312-14B1B2B3B4产量产量A17A24A39销量销量365631363121-14B1B2B3B4产量产量A17A24A39销量销量365631363121-1124B1B2B3B4产量产量A17A24A39销量销量365631363121-112104 检验数中有负数，说明原方案不是最优解。检验数中有负数，说明原方案不是最优解。B1B2B3B

11、4产量产量A17A24A39销量销量365600000121-112100 运输问题的约束条件共有运输问题的约束条件共有m+n个，其中：个，其中：m是产地产量的限制；是产地产量的限制；n是销地销量的限制。是销地销量的限制。 其对偶问题也应有其对偶问题也应有m+n个变量，据此：个变量，据此： ij=cij(ui+vj) ,其中前其中前m个计为个计为ui（i=1.2m）,前前n个个计为计为vj （j=1.2n） 由单纯形法可知，基变量的由单纯形法可知，基变量的ij 0 cij(ui+vj) 0 因此因此ui ,vj可以求出。可以求出。. .位势法位势法接上例：接上例：B1B2B3B4A1310u1

12、A212u2A345u3v1v2v3v4成本表成本表B1B2B3B4A1293100A218291A33425529310 u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令：令： u10u10 v12u2 1 v2 9u3 5 v3 3 v4 10 (ui+vj) 按按ij=cij(ui+vj) 计算检验数，并以计算检验数，并以ij0 检验，检验，或用或用(ui+vj) cij 0 检验。检验。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A334-25(ui+vj)B1

13、B2B3B4A11200A20101A3100120表中还有负数，表中还有负数，说明还未得到最说明还未得到最优解，应继续调优解，应继续调整。整。ij 闭合回路调整法（原理同单纯形法一样）闭合回路调整法（原理同单纯形法一样）接上例：接上例：B1B2B3B4产量产量A17A24A39销量销量3656313463（1）（1）（1）（1）3 3、改进的方法、改进的方法B1B2B3B4产量产量A1527A2314A3639销量销量36566563销量销量9A34A27A1产量产量B4B3B2B1313463（1）（1）（1）（1）B1B2B3B4A10200A20210A390120经检验经检验所有所有

14、ijij0 0得到最优解，得到最优解，最小运费为最小运费为8585元。元。0v4v3v2v1u354A3u281A2u1103A1B4B3B2B1成本表成本表1039355242A328171A2010393A1B4B3B2B1(ui+vj) . .无穷多最优解：产销平衡的运输问题必定存最无穷多最优解：产销平衡的运输问题必定存最优解。如果非基变量的优解。如果非基变量的ij0，则该问题有无穷多最，则该问题有无穷多最优解。如上例：优解。如上例：（1.1）中的检验数是中的检验数是 0，经过调整，经过调整，可得到另一个最优解。可得到另一个最优解。 . .退化：表格中一般要有退化：表格中一般要有(m+n

15、-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 ) (

16、0min11ijjijijiijminjijijxbabxaxxcZ1 1、产大于销：模型、产大于销：模型 方法是先将原问题变成平衡问题，需假设一个销地方法是先将原问题变成平衡问题，需假设一个销地(Bn+1 )(实际上考虑产地的存量实际上考虑产地的存量)，三、产销不平衡的运输问题及其求解方法三、产销不平衡的运输问题及其求解方法 模型为：模型为： 0)min1111111ijminjnjjnjijijnjiijijijxbbbabxaxxcZm1i( 2 2、销大于产：同样假设一个产地即可，变化同上。、销大于产：同样假设一个产地即可，变化同上。单位运价表中的单位运价为单位运价表中的单位运价为01

17、,nicB1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5 A121134070A210359050A378120702030406040B1B2B3B4B5 A170A250A370203040604040303020302020用最小元素法用最小元素法求初始方案求初始方案例题：例题： 已知某运输问题的资料如下表所示已知某运输问题的资料如下表所示B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125 1 1、表中的发量、收量单位为：吨，运价单位为：元、表中的发量、收量单位为：吨，运价单位为：元/ /

18、吨吨 试求出最优运输方案试求出最优运输方案. . 练习：练习： 2 2、如将、如将A2的发量改为的发量改为1717，其它资料不变，试求最优调，其它资料不变，试求最优调 运方案。运方案。B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125解：解：1、用最小元素法求初始方案、用最小元素法求初始方案B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4A153A211A324运费为运费为108108元元/ /吨吨2 2、用

19、位势法判断：、用位势法判断：B1B2B3B4ui A153u1A211u2A324u3vj v1v2v3v4成本表成本表B1B2B3B4ui A153u1A211u2A324u3vj v1v2v3v4 u1+v3=5 u2+v4 =1 u1+v4 =3 u3+v2=2 u2+v1=1 u3+v4 =4 令：令： u10u10 v13u22 v2 1u3 1 v3 5 v4 3 B1B2B3B4ui A1530A2112A3241vj 3153B1B2B3B4ui A131530A211312A342641vj 3153(ui+vj)B1B2B3B4A12653A21321A33274B1B2B

20、3B4A13153A21131A34264cijB1B2B3B4A11500A20410A31010表中还有负数，说表中还有负数，说明没有得到最优解，明没有得到最优解，调整运输方案。调整运输方案。ij(ui+vj)B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A31302222新的运送方案新的运送方案B1B2B3B4A153A212A324新的成本表新的成本表B1B2B3B4ui A141530A212203A352641vj 4153(ui+vj)1 总的运费总的运费 105元元/吨吨B1B2B3B4A14153A21220A35264B1B2B3B4A1

21、2653A21321A33274B1B2B3B4A12500A20501A32010表中还有负数，说表中还有负数，说明没有得到最优解，明没有得到最优解，继续调整运输方案。继续调整运输方案。cij(ui+vj)1 (ij)1 013A3210A2510A1B4B3B2B13512vj 14623A330221A203512A1ui B4B3B2B1(ui+vj)2 42A32A2352A1B4B3B2B1新的成本表新的成本表013A312A25010A1B4B3B2B1新的运送方案新的运送方案总的运费总的运费 85元元/吨吨B1B2B3B4A12653A21321A33274cijB1B2B3B

22、4A12153A21 220A33264(ui+vj)2 B1B2B3B4A10500A22501A30010 (ij)2 表中没有负数，说表中没有负数，说明已经得到最优解。明已经得到最优解。但有无穷多最优解。但有无穷多最优解。013A312A2510A1B4B3B2B1最终的运送方案最终的运送方案总的运费总的运费 85元元/吨吨B1B2B3B4发量发量A131215A27512A313013收量收量1013125B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125B1B2B3B4A125A211A327B1B2B3B4ui A125u1A211u2A

23、327u3vj v1v2v3v4成本表成本表 u1+v1=2 u2+v4 =1 u1+v3 =5 u3+v2 =2 u2+v1=1 u3+v3 =7 令：令： u10u10 v12u21 v2 0u3 2 v3 5 v4 2 B1B2B3B4ui A120520A21-141-1A342742vj 2052(ui+vj)B1B2B3B4A12653A21321A33274cijB1B2B3B4ui A10601A204-20A3-1000vj ijB1B2B3B4发量发量A131215A27512A313013收量收量1013125B1B2B3B4发量发量A110515A27512A31301

24、3收量收量1013125B1B2B3B4B5发量发量A110515A2102517A313013收量收量10131255B1B2B3B4B5发量发量A12653015A21321017A33274013收量收量10131255B1B2B3B4B5A150A2121A324B1B2B3B4B5ui A150u1A2121u2A324u3vj v1v2v3v4v5成本表成本表 u1+v3=5 u2+v3 =2 u1+v5 =0 u2+v4 =1 u2+v1=1 u3+v2=2 u3+v4=4 令：令： u10u10 v14u2-3 v2 2u3 0 v3 5 v4 4 v50B1B2B3B4B5u

25、i A1425400A21-121-3-3A3425400vj 42540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5 A1-240-10A204004A3-10200ij505B45121310收量收量1313A317210A215510A1发量发量B5B3B2B1B1B2B3B4B5发量发量A1100515A212517A313013收量收量10131255B1B2B3B4B5A1250A221A324B1B2B3B4B5ui A1250u1A221u2A324u3vj v1v2v3v4v5成本表成本表 u1+v1=2 u2+v4

26、=1 u1+v3 =5 u3+v2 =2 u1+v5=0 u3+v4=4 u2+v3=2 令：令： u10u10 v12u2-3 v2 2u3 0 v3 5 v4 4 v50B1B2B3B4B5ui A1225400A2-1-121-3-3A3225400vj 22540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5 A1040-10A224004A310200ijB1B2B3B4B5发量发量A1100515A212517A313013收量收量10131255B1B2B3B4B5发量发量A1100515A212517A313013收量收量

27、10131255B1B2B3B4B5发量发量A110515A212517A31313收量收量10131255C =75 已知资料如下表所示，问如何供电能使总的输电费已知资料如下表所示，问如何供电能使总的输电费用为最小？用为最小？发电厂 发电量A1700A2200A3100城市需电量B1500B2250B3100B4150电力供需表电力供需表B1B2B3B4A110523A24312A35634单位输电费用单位输电费用作业：作业：B1B2B3B4A1A2A3初始方案初始方案10010050250400100B1B2B3B4A110523A24312A35634单位输电费用单位输电费用发电厂 发电量A1700A2200A3100城市需电量B1500B2250B3100B4150