第四章 运输问题

第三章运输问题4.1运输问题模型及有关概念4.2运输问题求解4.3运输问题的应用4.1运输问题的数学模型

例某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？产量销量产地销地解设为从产地到销地的运输量产量销量产地销地运价系数矩阵约束方程系数矩阵111000000111100100010010001001特点：1、共有2+3=5行，表示2个产地和3个销地；有2×3=6列，恰好对应6个变量；2、每列只有两个1，其余为0，表示只有一个产地和一个销地被使用；

一般运输问题的数学模型（产销平衡的运输问题）A1,

A2,…,Am

表示某物资的m个产地；B1,B2,…,Bn

表示该物资的n个销地；ai

表示产地Ai的产量；bj

表示销地Bj的销量；

cij

表示把物资从产地Ai运往销地Bj的单位运价。设为从产地运往销地的运输量，产量销量产地销地运价得到下列一般运输问题的模型：

其系数矩阵为变化：

1）有时目标函数求最大，如求利润最大或营业额最大等；2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；3）产销不平衡时，可加入虚设的产地（销大于产时）或销地（产大于销时）。求解思路是

基本可行解最优否结束

否

换基运输问题基变量的特点*运输问题的基变量共有m+n-1个，A的秩为m+n-1。*运输问题的可行解一定存在。

*运输问题的最优解一定存在。⑷.重复⑵.⑶，直到找到最优解为止。步骤：⑴.找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法,元素差额法；⑵.求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用闭回路法或位势法计算；⑶.改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；4.2运输问题的求解——表上作业法例一、某运输资料如下表所示：单位销地运价产地产量311310719284741059销量36561、求初始方案：⑴.西北角法（或左上角法）：此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下：365674934490656404902562029005620090036360000000340002200036总的运费＝(3×3)＋(4×11)＋(2×9)＋(2×2)＋(3×10)＋(6×5)＝135元（1）最小元素法总的运输费用为基本思想是就近供应，即从最小运价开始分配运输量，然后次小，直到最后供完为止。产量销量产地销地运价（2）元素差额法（Vogel法）产量销量产地销地运价差额列差额行总的运输费用为注：只剩下最后一行或一列时，就不再求差额了，从最小运价开始逐一进行即可。1、初始基本可行解的确定：（1）西北角法：从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。（2）最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。（3）元素差额法：在运价表中分别计算出各行各列最小元素与次小元素的差额，并分别列于差额行的第一行与差额列的第一列，在差额最大的行或列找出最小元素，先安排该位置，划去一行或一列。计算剩余行与列的最小元素与次小元素的差额，并分别列于差额行的第二行与差额列的第二列，在差额最大的行或列找出最小元素，先安排该位置，划去一行或一列，如此反复，直到划去所有的行与列。注：应用西北角法，最小元素法和元素差额法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列）在保留的列（行）任意没被划去的格内标一个0。注：除最后一个元素（相当于同时删去一行一列）外，每填一个数都只删去一行或一列。若当前的行、列同时满足，可在当前的行（或列）的一个格子标0，同时删去当前的列（或行）。2、最优性检验：

判别方法：计算ij=cij-CBB–1Pij,i=1,…,m;j=1,…,n。

因为目标函数求最小，当所有检验数均大于等于0时为最优解。（1）闭回路法从每一空格出发，用水平或垂直向前划，每碰到一合适的数字格转90度，直到回到初始空格，得一闭回路，而且是唯一的闭回路。

从每一空格出发一定存在和可以找到唯一的闭回路。因(m+n-1)个数字格(基变量)对应的系数向量是一个基。任一空格(非基变量)对应的系数向量是这个基的线性组合。如Pij,i,j∈N可表示为

其中Pik,Plk,Pls,Pus,Puj∈B。而这些向量构成了闭回路。

用下述方法找检验数Step1：写出初始基解的运价；Step2：利用“对角和相等”填空格，得新表；Step3：老运价表-新运价表=检验数表如上例的最小元素法所得初始解的检验数__==（2）位势法：

根据单纯形法中检验数的定义，从约束条件中解出基变量，代入目标函数中，消去目标函数中的基变量，得到的非基变量的系数就是检验数。位势：设对应基变量xij

的m+n-1个i、j，存在ui,vj

满足ui+vj=cij，i=1,…,m;j=1,…,n.称这些ui,vj

为该基本可行解对应的位势。由于有m+n个变量（ui,vj），m+n-1个方程（基变量个数），故有一个自由变量，位势不唯一。利用位势求检验数：

ij=cij-ui-vji=1,…,m;j=1,…,n前例，位势法求检验数：

step1从任意基变量对应的cij

开始，任取ui

或vj，然后利用公式cij=ui+vj

依次找出m+n个ui,vj；从

c14=10开始

step2计算非基变量的检验数ij=cij-ui-vj；填入圆圈内3、解的改进——闭回路调整法：（1）选负检验数中最小者rk，那么xrk为主元，作为进基变量；（上页图中x24）（2）以为xrk起点找一条闭回路，除xrk

外其余顶点必须为基变量格；（上页图中蓝色回路）（3）为闭回路的每一个顶点标号，xrk

为1，沿一个方向依次给各顶点标号；（4）求=min{xijxij对应闭回路上的偶数标号格}=xpq那么确定xpq为出基变量，为调整量；（5）对闭回路的各奇标号顶点xij+，对各偶标号顶点xij-，特别xpq-=0，变为非基变量；主元变换：由前面得到=1，于是

ij≥0，得到最优解x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余xij=0;

最优费用：f*=3*5+10*2+1*3+8*1+4*6+5*3=85

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

2、销大于产：同样假设一个产地即可，变化同上。单位运价表中的单位运价为1、产量大于销量例、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的销地运输费用为0例、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的产地运输费用为0B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5

A121134070A210359050A378120702030406040B1B2B3B4B5

A170A250A3702030406040403030203020用最小元素法求初始方案例题：20已知某运输问题的资料如下表所示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

表中没有负数，说明已经得到最优解。但有无穷多最优解。0013A312A25010A1B4B3B2B1最终的运送方案总的运费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-