第四章运输问题(TransportationProblem)

1、2022-6-261运输问题运输问题(Transportation Problem)p运输规划的数学模型运输规划的数学模型p表上作业法表上作业法p产销不平衡的运输问题产销不平衡的运输问题p有转运的运输问题有转运的运输问题2022-6-262一、运输问题的数学模型一、运输问题的数学模型p例：某运输问题的资料如下：例：某运输问题的资料如下：单位单位 销地销地 运价运价产地产地B1B2B3B4产量产量A1291029A213425A384257销量销量38462022-6-263 )4 . 3 . 2 . 1, 3 . 2 . 1(06483759524824371092min34241433231

2、3322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij 约约束束条条件件：目目标标函函数数：为为运运量量设设2022-6-264运输问题数学模型的一般形式p 已知某产品有已知某产品有m个生产地点个生产地点Ai（i=1,2,，m），其供应量），其供应量(产量产量)分别为分别为ai（i=1，2，m），有），有n个销地个销地Bj（j=1,2,n），其需要量），其需要量分别为分别为bj（j=1,2,n），从），从Ai到到Bj运输单位物运输单位物资

3、的运价资的运价(单价单价)为为cij，这些数据可汇总于产销平，这些数据可汇总于产销平衡表和单位运价表中，见表衡表和单位运价表中，见表4-1，表，表4-2。有时。有时可把这两表合二为一。可把这两表合二为一。 2022-6-265表4-1 产销平衡表 销地产地B1 B2 Bn产量 A1A2Am a1a2am销量b1 b2 bn2022-6-266表4-2 单位运价表2022-6-267运输问题数学模型的一般形式p若用若用x xijij表示从表示从A Ai i到到B Bj j的运量，那么在产销平衡的条件下，要求得总的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，其数学模型为运费最小的调运

4、方案，其数学模型为 ) ( 0min11ijjijijiijminjijijxbabxaxxcZ2022-6-268运输问题数学模型的特点p1.运输问题有有限个最优解p2.运输问题约束条件的特点：运输问题的数学模型包含mn个变量，(m+n)个约束方程，其系数矩阵的结构比较松散且特殊。 行行nmvvvuuuxxxxxxxxxnmmnmmnn11111111111111111121212122221112112022-6-269运输问题数学模型的特点 该系数矩阵中对应于某一变量的系数向量，该系数矩阵中对应于某一变量的系数向量，其分量中除第其分量中除第i i个和第个和第m+jm+j个为个为1 1以外

5、，其余的都为零，以外，其余的都为零，在约束条件中，前在约束条件中，前m m个约束条件的含义是：由某一产地运个约束条件的含义是：由某一产地运往各销地的产品数量之和等于该产地的产量；后往各销地的产品数量之和等于该产地的产量；后n n个约个约束条件的含义是：由各产地运往某一销地的产品数量束条件的含义是：由各产地运往某一销地的产品数量之和等于该销地的销量。之和等于该销地的销量。2022-6-2610运输问题的对偶问题p运输问题的对偶问题可按照前面写线性规划问题的对偶问题的方法给出（略）2022-6-2611运输问题的解运输问题也是一个线性规划问题，其求解时仍然可以先找一个基可行解，进行解的最优性检验，

6、若不是最优，就进行迭代，继续检验和调整直到最优，因此要求每步得到的解都是基可行解，需满足(1)满足所有约束条件；(2)基变量对应的系数列向量线性无关；(3)解中非零变量的个数不能大于m+n-1个，原因是运输问题中虽有m+n个约束条件，但由于总产量等于总销量，故只有m+n-1个约束条件是线性独立的；(4)保持基变量的个数在迭代过程中为m+n-1个。2022-6-2612第2节 表上作业法p表上作业法是单纯形法在求解运输问题时的一种简化方法，表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法其实质是单纯形法, ,但具体计算和术语有所不同，其步骤但具体计算和术语有所不同，其步骤可归

7、纳为：可归纳为：(1) (1) 找出初始基可行解：即在找出初始基可行解：即在(m(mn)n)产销平衡表上产销平衡表上用西北角用西北角法或最小元素法、法或最小元素法、Vogel法给出法给出m+n-1个数字，称为数个数字，称为数字格，它们就是初始基变量的取值。字格，它们就是初始基变量的取值。(2) (2) 求各非基变量的检验数，即在表上计算空格的检验数，求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。转到下一步。(3) (3) 确定换入变量和换出变量，找出新的基可行解。在表上确定换入变量

8、和换出变量，找出新的基可行解。在表上用闭回路法调整。用闭回路法调整。(4) 重复重复(2)，(3)直到得到最优解为止。直到得到最优解为止。2022-6-2613例题单位单位 销地销地 运价运价 产地产地产量产量311310719284741059销量销量3656产销平衡321AAA例：某食品公司下属的A1、A2、A3 ，3个厂生产方便食品，要运输到B1、B2、B3、B4 ，4个销售点，数据如下：求最优运输方案。4321 BBBB2022-6-2614一 初始基可行解的确定 确定初始基可行解的方法很多，有西北角法，最小元素法和沃格尔(Vogel)法等，一般希望的方法是既简便，又尽可能接近最优解。

9、下面分别予以介绍：1.1. 最小元素法最小元素法 此方法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止。以上例进行讨论得下表：2022-6-2615B1B2B3B4产量产量A17A2 4A39销量销量3656311310192741058341633总的运输费用（总的运输费用（3 31 1）（）（6 64 4） （4 43 3）（）（1 12 2）（）（3 31010）（）（3 35 5）8686元元2022-6-2616 2. 2.西北角法（或左上角法）：西北角法（或左上角法）： 此法是纯粹的人为规定，没有理论依据和实际背景，此法是纯粹

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

11、(33)3)(4(411)11)(2(29)9)(2(22)2)(3(310)10)(6(65)5)135135元元2022-6-26173. 沃格尔法 最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。沃格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。 沃格尔法的步骤是： 第一步第一步：在原表中分别计算出各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行，见表4-12022-6-2618表4-1第二步第二步：从行或列差额中选出

12、最大者，选择它所在行或列中的最小元素。在表4-1中B2列是最大差额所在列。B2列中最小元素为4，可确定A3的产品先供应B2的需要。得表4-2：2022-6-2619同时将运价表中的B2列数字划去。如表4-3所示（表4-3）：表4-2销 地 加工厂 B1 B2 B3 B4 行差额 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 0 1 2 列差额 2 1 3 2022-6-2620销 地 加工厂 B1 B2 B3 B4 产量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销量 3 6 5 6 第三步第三步：对表4-3中未划去的元素再分别计算出各行、各列的最小运费和

13、次小运费的差额，并填入该表的最右列和最下行，重复第一、二步，直到给出初始解为止。用此法给出上例的初始解列于表4-4（下表）。2022-6-2621说明p由以上可见：沃格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。沃格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。p本例用沃格尔法给出的初始解就是最优解。2022-6-2622二 最优解的判别p最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法

14、： 1.闭回路法； 2.位势法2022-6-26231 闭回路法在给出调运方案的计算表上，如上例表，从每一空格出发找一条闭回路。它是以某空格为起点，用水平或垂直线向前划，当碰到一数字格时可以转90后，继续前进，直到回到起始空格为止。闭回路如图(a),(b),(c)等所示。 销 地 加工厂 B1 B2 B3 B4 产量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销量 3 6 5 6 2022-6-2624p闭回路法计算检验数的经济解释为：在已给出初始解的表中，闭回路法计算检验数的经济解释为：在已给出初始解的表中， 可从任一空格出发，可从任一空格出发，如如(A1，B1)，若让，若让A1

15、的产品调运的产品调运1吨给吨给B1。为了保持产销平衡，就要依次作调。为了保持产销平衡，就要依次作调整：整： 在在(A1，B3)处减少处减少1吨，吨，(A2，B3)处增加处增加1吨，吨，(A2，B1)处减少处减少1吨，即吨，即构成了以构成了以(A1，B1)空格为起点，其他为数字格的闭空格为起点，其他为数字格的闭回路，如下表虚线所示。在回路，如下表虚线所示。在这表中闭回路各顶点所在格的右上角数字是单位运价这表中闭回路各顶点所在格的右上角数字是单位运价销 地 加工厂 B1 B2 B3 B4 产量 A1 3 (+1) 11 3 4(-1) 10 3 7 A2 1 3(-1) 9 2 1(+1) 8 4

16、 A3 7 4 6 10 5 3 9 销量 3 6 5 6 2022-6-2625p可见这调整的方案使运费增加可见这调整的方案使运费增加(+1)(+1)3+(-1)3+(-1)3+(+1)3+(+1)2+(-1)2+(-1)=1(=1(元元) )将将“1”这个数填入这个数填入(A1，B1)格，这就是检验数。按以上所述，可找出所有格，这就是检验数。按以上所述，可找出所有空格的检验数，见下表。空格的检验数，见下表。空格 闭 回 路 检验数 (11) (12) (22) (24) (31) (33) (11)-(13)-(23)-(21)-(11) (12)-(14)-(34)-(32)-(12)

17、(22)-(23)-(13)-(14)-(34)-(32)-(22) (24)-(23)-(13)-(14)-(24) (31)-(34)-(14)-(13)-(23)-(21)-(31) (33)-(34)-(14)-(13)-(33) 1 2 1 -1 10 12 2022-6-2626B1B2B3B4产量产量A17A24A39销量销量365600000121-112100当检验数还存在负数时，说明原方案不是最优解，要继续改进。当检验数还存在负数时，说明原方案不是最优解，要继续改进。 闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计闭回路法的主要缺点是：当变量个数较多时，寻找闭回路

18、以及计算两方面都会产生困难。算两方面都会产生困难。 运输问题的约束条件共有运输问题的约束条件共有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可以求出。可以求出。. .位势法位势法2022-6-2628仍以上面的例子说明。第一步第一步：按最小元素法给

19、出表的初始解，然后做下表：即在对应表的数字格处填入单位运价：销 地 加工厂 B1 B2 B3 B4 A1 A2 A3 1 4 3 2 10 5 2022-6-2629第二步第二步：在上表中增加一行一列，在列中填入ui，在行中填入vj，得下表：销 地 加工厂 B1 B2 B3 B4 ui A1 A2 A3 1 4 3 2 10 5 0 -1 -5 vj 2 9 3 10 先令u1=0，然后按ui+vj=cij， i，jB相继地确定ui，vj。由上表可见，当u1=0时，由u1+v3=3可得v3=3，由u1+v4=10可得v4=10；在v4=10时，由u3+v4=5可得u3=-5，以此类推可确定所有

20、的ui，vj的数值。 2022-6-2630第三步第三步：按ij=cij-(ui+vj), i,jN计算所有空格的检验数。如11=c11-(u1+v1)=3-(0+2)=1， 12=c12-(u1+v2)=11-(0+9)=2这些计算可直接在上表中进行。为了方便，特设计计算表，如下表所示在此表中还有负检验数，说明未得最优解，还可以改进。2022-6-2631亦即：亦即：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表成本表B1B2B3B4A1293100A218291A33425529310 u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10

21、u1+v3=3 u3+ v4 =5 令：令： u10u10 v12u2 1 v2 9u3 5 v3 3 v4 10 (ui+vj)2022-6-2632 按按ij=cij(ui+vj) 计算检验数，并以计算检验数，并以ij0 检验，检验，或用或用(ui+vj) cij 0 检验。检验。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A334-25(ui+vj)B1B2B3B4A11200A20101A3100120表中还有负数，表中还有负数，说明还未得到最说明还未得到最优解，应继续调优解，应继续调整。整。ij2022-6-2633三 解

22、的改进 闭回路调整法当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，具体步骤为：（1 1）选负检验数中最小者 rk，那么 xrk 为主元，作为进基变量（上页图中 x24 ）;（2 2）以 xrk 为起点找一条闭回路，除 xrk 外其余顶点必须为基变量格（上页图中的回路）;2022-6-2634解的改进 闭回路调整法（3 3）为闭回路的每一个顶点标号， xrk 为 1，沿一个方向（顺时针或逆时针）依次给各顶点标号；（4 4）求=Minxijxij对应闭回路上的偶数标号格= xpq，那么确定xpq为出

23、基变量，为调整量； （5 5）对闭回路的各奇标号顶点调整为：xij + ，对各偶标号顶点 调整为：xij - ，特别 xpq - = 0， xpq变为非基变量。 重复(2)、(3)步，直到所有检验数均非负，得到最优解。接上例：接上例：B1B2B3B4产量产量A17A24A39销量销量3656313463（1）（1）（1）（1）2022-6-2636B1B2B3B4产量产量A1527A2314A3639销量销量36566563销量销量9A34A27A1产量产量B4B3B2B1313463（1）（1）（1）（1）2022-6-2637B1B2B3B4A10200A20210A390120经检验经检

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

25、调入为调入格，作闭回路格，作闭回路 (1(1，1)1)+ +-(1-(1，4)4)- -(2-(2，4)4)+ +-(2-(2，1)1)- -(1-(1，1)1)+ +确定确定=min(2,3)=2=min(2,3)=2。经调整后得到另一最优解，见。经调整后得到另一最优解，见下表：下表： 四、需要说明的几个问题四、需要说明的几个问题2022-6-2639销 地 加工厂 B1 B2 B3 B4 产量 A1 A2 A3 2 1 6 5 3 3 7 4 9 销量 3 6 5 6 2022-6-2640 退化：表格中一般要有退化：表格中一般要有(m+n-1)个数字格。但有时，个数字格。但有时，在分配运

26、量时则需要同时划去一行和一列，这时需要补一在分配运量时则需要同时划去一行和一列，这时需要补一个个0，以保证有，以保证有(m+n-1)个数字格。一般可在划去的行和个数字格。一般可在划去的行和列的任意空格处加一个列的任意空格处加一个 0 即可。即可。 在用闭回路法调整时，在闭回路上出现两个和两个以在用闭回路法调整时，在闭回路上出现两个和两个以上的具有上的具有(-1)标记的相等的最小值。这时只能选择其中标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后，得到退化解。这时另一个一个作为调入格。而经调整后，得到退化解。这时另一个数字格必须填入一个数字格必须填入一个0，表明它是基变量。当出现退

27、化解，表明它是基变量。当出现退化解后，并作改进调整时，可能在某闭回路上有标记为后，并作改进调整时，可能在某闭回路上有标记为(-1)的取值为的取值为0的数字格，这时应取调整量的数字格，这时应取调整量=0。2022-6-2641第三节 产销不平衡的运输问题 前面所讲表上作业法，都是以产销平衡为前提条件的，但是实际问题中产销往往是不平衡的，这就需要设法把产销不平衡的问题化成产销平衡的问题。一、总产量大于总销量一、总产量大于总销量即此时，运输问题的数学模型可写为minjjiba112022-6-2642 ) ( 0min11ijjijijiijminjijijxbabxaxxcZ要求解此问题，需要先将

28、原问题变成平衡问题，可要求解此问题，需要先将原问题变成平衡问题，可以假设一个销地以假设一个销地Bn+1( (即实际问题中考虑产地的存量即实际问题中考虑产地的存量) )，即：即：2022-6-2643 0)min1111111ijminjnjjnjijijnjiijijijxbbbabxaxxcZm1i( 01,nic单位运价表中的单位运价单位运价表中的单位运价二、销大于产二、销大于产：同样假设一个产地即可，变化同同样假设一个产地即可，变化同上。上。B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5 A121134070A210359050A

29、378120702030406040B1B2B3B4B5 A170A250A370203040604040303020302020用最小元素法用最小元素法求初始方案求初始方案例题：例题：然后用表上作业法然后用表上作业法求解即可（略）求解即可（略） 已知某运输问题的资料如下表所示已知某运输问题的资料如下表所示B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125 表中的发量、收量单位为：吨，运价单位为：元表中的发量、收量单位为：吨，运价单位为：元/ /吨吨 试求出最优运输方案试求出最优运输方案. . 练习：练习：2022-6-2646解：用最小元素法求初始方案解：用最小元素法求初始方案B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4A153A211A324运费为运费为108108元元/ /吨吨2 2、用位势法判断：、用位势法判断：B1B2B3B4ui A153u1A211u2A324u3vj v1v2v3v4成本表成本表2022-6-2647B1B2B3B4ui A153u1A211u2A324u3vj v1v2v3v4 u1+v3=5 u2+v4 =1 u1+v4 =3 u3+v2=2 u2+v1=1 u3+v