运筹学课件运输规划

运输规划(TransportationProblem)运输规划的数学模型表上作业法产销不平衡的运输问题例：某运输问题的资料如下：单位销地运价产地产量2910291342584257销量3846一、运输问题的数学模型

数学模型的一般形式

已知资料如下：单位销地运价产地产量销量当产销平衡时，其模型如下：当产大于销时，其模型是：当产小于销时，其模型是：特征：

1、平衡运输问题必有可行解，也必有最优解；

2、运输问题的基本可行解中应包括m+n－1

个基变量。

⑷.重复⑵.⑶，直到找到最优解为止。步骤：

⑴.找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法；

⑵.求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；

⑶.改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；二、表上作业法例一、某运输资料如下表所示：单位销地运价产地产量311310719284741059销量36561、求初始方案：

⑴.西北角法（或左上角法）：此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下：365674934490656404902562029005620090036360000000340002200036总的运费＝(3×3)＋(4×11)＋(2×9)＋(2×2)＋(3×10)＋(6×5)＝135元B1B2B3B4产量A17A2

4A39销量3656311310192741058341633

⑵.最小元素法：基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。总的运输费用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元

σij≥0（因为目标函数要求最小化）

表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数σij＝0，非基变量的检验数σij≥0。

σij<0表示运费减少，σij>0表示运费增加。2、最优解的判别（检验数的求法）：

⑴.闭合回路法：B1B2B3B4产量A17A24A39销量3656313463（＋1）（＋1）（－1）（－1）①②③③

计算如下：空格处（A1

B1

）＝

(1×3)＋｛(－1)×3｝＋(1×2)＋｛(－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.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=4u1+v4=10

u1+v3=3u3+v4=5

令：u1＝0u1＝0v1＝2u2＝－1v2＝9u3＝－5v3＝3v4＝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、改进的方法B1B2B3B4产量A1527A2314A3639销量36566563销量9A34A27A1产量B4B3B2B1313463（＋1）（＋1）（－1）（－1）B1B2B3B4A10200A20210A390120经检验所有σij≥0得到最优解，最小运费为85元。0v4v3v2v1u354A3u281A2u1103A1B4B3B2B1成本表10393－55－24－2A3－28171A2010393A1B4B3B2B1(ui+vj)

⑴.无穷多最优解：产销平衡的运输问题必定存最优解。如果非基变量的σij＝0，则该问题有无穷多最优解。如上例：（1.1）中的检验数是0，经过调整，可得到另一个最优解。

⑵.退化：表格中一般要有(m+n-1)个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格。一般可在划去的行和列的任意空格处加一个0即可。4、表上作业法计算中的问题例1：B1B2B3B4A178143A226355A3142782176213552682176

例2：B1B2B3A11221A23132A32314124B1B2B3A111A222A344124000

1、产大于销：模型方法是先将原问题变成平衡问题，需假设一个销地(Bn+1)(实际上考虑产地的存量)，三、产销不平衡的运输问题及其求解方法模型为：

2、销大于产：同样假设一个产地即可，变化同上。单位运价表中的单位运价为B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5

A121134070A210359050A378120702030406040B1B2B3B4B5

A170A250A370203040604040303020302020用最小元素法求初始方案例题：已知某运输问题的资料如下表所示B1B2B3B4发量A1265315A2132112A3327413收量1013125

1、表中的发量、收量单位为：吨，运价单位为：元/吨试求出最优运输方案.练习：

2、如将A2的发量改为17，其它资料不变，试求最优调运方案。B1B2B3B4发量A112315A210212A313013收量1013125B1B2B3B4发量A1265315A2132112A3327413收量1013125解：1、用最小元素法求初始方案B1B2B3B4发量A112315A210212A313013收量1013125B1B2B3B4A153A211A324运费为108元/吨2、用位势法判断：B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4成本表B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4

u1+v3=5u2+v4=1u1+v4=3u3+v2=2u2+v1=1u3+v4=4

令：u1＝0u1＝0v1＝3u2＝－2v2＝1u3＝1v3＝5v4＝3B1B2B3B4ui

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

表中没有负数，说明已经得到最优解。但有无穷多最优解。013A312A2510A1B4B3B2B1最终的运送方案总的运费85元/吨B1B2B3B4发量A131215A27512A313013收量1013125B1B2B3B4发量A1265315A2132112A3327413收量1013125B1B2B3B4A125A211A327B1B2B3B4ui

A125u1A211u2A327u3vj

v1v2v3v4成本表

u1+v1=2u2+v4=1u1+v3=5u3+v2=2u2+v1=1u3+v3=7

令：u1＝0u1＝0v1＝2u2＝－1v2＝0u3＝2v3＝5v4＝2B1B2B3B4ui

A120520A21-141-1A342742vj

2052(ui+vj)B1B2B3B4A12653A21321A33274cijB1B2B3B4ui

A10601A204-20A3-1000vj

σijB1B2B3B4发量A131215A27512A313013收量1013125B1B2B3B4发量A110515A27512A313013收量1013125B1B2B3B4B5发量A110515A2102517A313013收量10131255B1B2B3B4B5发量A12653015A21321017A33274013收量10131255B1B2B3B4B5A150A2121A324B1B2B3B4B5ui

A150u1A2121u2A324u3vj

v1v2v3v4v5成本表

u1+v3=5u2+v3=2u1+v5=0u2+v4=1u2+v1=1u3+v2=2u3+v4=4令：u1＝0u1＝0v1＝4u2＝-3v2＝2u3＝0v3＝5v4＝4v5＝0B1B2B3B4B5ui

A1425400A21-121-3-3A3425400vj

42540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

A1-240-10A204004A3-10200σij505B45121310收量1313A317210A215510A1发量B5B3B2B1B1B2B3B4B5发量A1100515A212517A313013收量10131255B1B2B3B4B5A1250A221A324B1B2B3B4B5ui

A1250u1A221u2A324u3vj

v1v2v3v4v5成本表

u1+v1=2u2+v4=1u1+v3=5u3+v2=2u1+v5=0u3+v4=4u2+v3=2令：u1＝0u1＝0v1＝2u2＝-3v2＝2u3＝0v3＝5v4＝4v5＝0B1B2B3B4B5ui

A1225400A2-1-121-3-3A3225400vj

22540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

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

A1105230A29412-1A350-3-2-5vj

10523B1B2B3B4ui

A10000A2-5-100