第四章-运输问题(Transportation-Problem)培训讲学课件

运输问题(TransportationProblem)运输规划的数学模型表上作业法产销不平衡的运输问题有转运的运输问题7/22/20231一、运输问题的数学模型例：某运输问题的资料如下：单位销地运价产地B1B2B3B4产量A1291029A213425A384257销量38467/22/202327/22/20233运输问题数学模型的一般形式

已知某产品有m个生产地点Ai（i=1,2,…，m），其供应量(产量)分别为ai（i=1，2，…，m），有n个销地Bj（j=1,2,…,n），其需要量分别为bj（j=1,2,…,n），从Ai到Bj运输单位物资的运价(单价)为cij，这些数据可汇总于产销平衡表和单位运价表中，见表4-1，表4-2。有时可把这两表合二为一。7/22/20234表4-1产销平衡表销地产地B1

B2┉Bn产量

A1A2┆Am

a1a2┆am销量b1b2┈bn

7/22/20235表4-2单位运价表7/22/20236运输问题数学模型的一般形式若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，其数学模型为7/22/20237运输问题数学模型的特点1.运输问题有有限个最优解2.运输问题约束条件的特点：运输问题的数学模型包含m×n个变量，(m+n)个约束方程，其系数矩阵的结构比较松散且特殊。7/22/20238运输问题数学模型的特点

该系数矩阵中对应于某一变量的系数向量，其分量中除第i个和第m+j个为1以外，其余的都为零，在约束条件中，前m个约束条件的含义是：由某一产地运往各销地的产品数量之和等于该产地的产量；后n个约束条件的含义是：由各产地运往某一销地的产品数量之和等于该销地的销量。7/22/20239运输问题的对偶问题运输问题的对偶问题可按照前面写线性规划问题的对偶问题的方法给出（略）7/22/202310运输问题的解运输问题也是一个线性规划问题，其求解时仍然可以先找一个基可行解，进行解的最优性检验，若不是最优，就进行迭代，继续检验和调整直到最优，因此要求每步得到的解都是基可行解，需满足(1)满足所有约束条件；(2)基变量对应的系数列向量线性无关；(3)解中非零变量的个数不能大于m+n-1个，原因是运输问题中虽有m+n个约束条件，但由于总产量等于总销量，故只有m+n-1个约束条件是线性独立的；(4)保持基变量的个数在迭代过程中为m+n-1个。7/22/202311第2节表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法,但具体计算和术语有所不同，其步骤可归纳为：(1)找出初始基可行解：即在(m×n)产销平衡表上用西北角法或最小元素法、Vogel法给出m+n-1个数字，称为数字格，它们就是初始基变量的取值。(2)求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。(3)确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。(4)重复(2)，(3)直到得到最优解为止。7/22/202312例题单位销地运价产地产量311310719284741059销量3656产销平衡例：某食品公司下属的A1、A2、A3，3个厂生产方便食品，要运输到B1、B2、B3、B4，4个销售点，数据如下：求最优运输方案。7/22/202313一初始基可行解的确定确定初始基可行解的方法很多，有西北角法，最小元素法和沃格尔(Vogel)法等，一般希望的方法是既简便，又尽可能接近最优解。下面分别予以介绍：1.

最小元素法此方法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，…，一直到给出初始基可行解为止。以上例进行讨论得下表：7/22/202314B1B2B3B4产量A17A2

4A39销量3656311310192741058341633总的运输费用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元7/22/2023152.西北角法（或左上角法）：此法是纯粹的人为规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下：365674934490656404902562029005620090036360000000340002200036总的运费＝(3×3)＋(4×11)＋(2×9)＋(2×2)＋(3×10)＋(6×5)＝135元7/22/2023163.沃格尔法最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。沃格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。

沃格尔法的步骤是：

第一步：在原表中分别计算出各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行，见表4-17/22/202317表4-1第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表4-1中B2列是最大差额所在列。B2列中最小元素为4，可确定A3的产品先供应B2的需要。得表4-2：7/22/202318同时将运价表中的B2列数字划去。如表4-3所示（表4-3）：表4-27/22/202319第三步：对表4-3中未划去的元素再分别计算出各行、各列的最小运费和次小运费的差额，并填入该表的最右列和最下行，重复第一、二步，直到给出初始解为止。用此法给出上例的初始解列于表4-4（下表）。

7/22/202320说明由以上可见：沃格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。沃格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。本例用沃格尔法给出的初始解就是最优解。7/22/202321二最优解的判别最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法：1.闭回路法；2.位势法7/22/2023221闭回路法在给出调运方案的计算表上，如上例表，从每一空格出发找一条闭回路。它是以某空格为起点，用水平或垂直线向前划，当碰到一数字格时可以转90°后，继续前进，直到回到起始空格为止。闭回路如图(a),(b),(c)等所示。

7/22/202323闭回路法计算检验数的经济解释为：在已给出初始解的表中，可从任一空格出发，如(A1，B1)，若让A1的产品调运1吨给B1。为了保持产销平衡，就要依次作调整：

在(A1，B3)处减少1吨，(A2，B3)处增加1吨，(A2，B1)处减少1吨，即构成了以(A1，B1)空格为起点，其他为数字格的闭回路，如下表虚线所示。在这表中闭回路各顶点所在格的右上角数字是单位运价7/22/202324可见这调整的方案使运费增加

(+1)×3+(-1)×3+(+1)×2+(-1)×１=1(元)

将“1”这个数填入(A1，B1)格，这就是检验数。按以上所述，可找出所有空格的检验数，见下表。7/22/202325B1B2B3B4产量A17A24A39销量365600000121-112100当检验数还存在负数时，说明原方案不是最优解，要继续改进。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。7/22/202326

运输问题的约束条件共有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可以求出。⑵.位势法7/22/202327仍以上面的例子说明。

第一步：按最小元素法给出表的初始解，然后做下表：即在对应表的数字格处填入单位运价：7/22/202328第二步：在上表中增加一行一列，在列中填入ui，在行中填入vj，得下表：先令u1=0，然后按ui+vj=cij，i，j∈B相继地确定ui，vj。由上表可见，当u1=0时，由u1+v3=3可得v3=3，由u1+v4=10可得v4=10；在v4=10时，由u3+v4=5可得u3=-5，以此类推可确定所有的ui，vj的数值。

7/22/202329第三步：按σij=cij-(ui+vj),i,j∈N计算所有空格的检验数。如

σ11=c11-(u1+v1)=3-(0+2)=1，σ12=c12-(u1+v2)=11-(0+9)=2

这些计算可直接在上表中进行。

为了方便，特设计计算表，如下表所示在此表中还有负检验数，说明未得最优解，还可以改进。7/22/202330亦即：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表B1B2B3B4A1293100A21829－1A3－34－25－529310u2+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)7/22/202331按σij=cij－(ui+vj)计算检验数，并以σij≥0检验，或用(ui+vj)

－cij

≤0检验。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A3－34-25(ui+vj)－B1B2B3B4A11200A2010－1A3100120＝表中还有负数，说明还未得到最优解，应继续调整。σij7/22/202332三解的改进闭回路调整法当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，具体步骤为：（1）选负检验数中最小者rk，那么xrk

为主元，作为进基变量（上页图中x24）;（2）以xrk

为起点找一条闭回路，除xrk外其余顶点必须为基变量格（上页图中的回路）;7/22/202333解的改进闭回路调整法（3）为闭回路的每一个顶点标号，xrk为1，沿一个方向（顺时针或逆时针）依次给各顶点标号；（4）求=Min{xijxij对应闭回路上的偶数标号格}=xpq，那么确定xpq为出基变量，为调整量；（5）对闭回路的各奇标号顶点调整为：xij+，对各偶标号顶点调整为：xij-，特别xpq-=0，xpq变为非基变量。重复(2)、(3)步，直到所有检验数均非负，得到最优解。7/22/202334接上例：B1B2B3B4产量A17A24A39销量3656313463（＋1）（＋1）（－1）（－1）7/22/202335B1B2B3B4产量A1527A2314A3639销量36566563销量9A34A27A1产量B4B3B2B1313463（＋1）（＋1）（－1）（－1）7/22/202336B1B2B3B4A10200A20210A390120经检验所有σij≥0得到最优解，最小运费为85元。v4v3v2v1u354A3u281A2u1103A1B4B3B2B1成本表10393－55－24－2A3－28171A2010393A1B4B3B2B1(ui+vj)7/22/202337⑴.无穷多最优解：产销平衡的运输问题必定存最优解。如果非基变量的σij＝0，则该问题有无穷多最优解。如上例：（1.1）中的检验数是0，经过调整，可得到另一个最优解：可在最优表中以(1，1)为调入格，作闭回路(1，1)+-(1，4)--(2，4)+-(2，1)--(1，1)+确定θ=min(2,3)=2。经调整后得到另一最优解，见下表：

四、需要说明的几个问题7/22/2023387/22/202339

⑵退化：表格中一般要有(m+n-1)个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格。一般可在划去的行和列的任意空格处加一个0即可。在用闭回路法调整时，在闭回路上出现两个和两个以上的具有(-1)标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后，得到退化解。这时另一个数字格必须填入一个0，表明它是基变量。当出现退化解后，并作改进调整时，可能在某闭回路上有标记为(-1)的取值为0的数字格，这时应取调整量θ=0。7/22/202340第三节产销不平衡的运输问题

前面所讲表上作业法，都是以产销平衡为前提条件的，但是实际问题中产销往往是不平衡的，这就需要设法把产销不平衡的问题化成产销平衡的问题。一、总产量大于总销量即此时，运输问题的数学模型可写为7/22/202341要求解此问题，需要先将原问题变成平衡问题，可以假设一个销地Bn+1(即实际问题中考虑产地的存量)，即：7/22/202342单位运价表中的单位运价二、销大于产：同样假设一个产地即可，变化同上。7/22/202343B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5

A121134070A210359050A378120702030406040B1B2B3B4B5

A170A250A370203040604040303020302020用最小元素法求初始方案例题：然后用表上作业法求解即可（略）7/22/202344已知某运输问题的资料如下表所示B1B2B3B4发量A1265315A2132112A3327413收量1013125表中的发量、收量单位为：吨，运价单位为：元/吨试求出最优运输方案.练习：7/22/202345解：用最小元素法求初始方案B1B2B3B4发量A112315A210212A313013收量1013125B1B2B3B4A153A211A324运费为108元/吨2、用位势法判断：B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4成本表7/22/202346B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4u1+v3=5u2+v4=1u1+v4=3u3+v2=2u2+v1=1u3+v4=4令：u1＝0u1＝0v1＝3u2＝－2v2＝1u3＝1v3＝5v4＝37/22/202347B1B2B3B4ui

A1530A211－2A3241vj

3153B1B2B3B4ui

A131530A21－131－2A342641vj

3153(ui+vj)7/22/202348B1B2B3B4A12653A21321A33274B1B2B3B4A13153A21－131A34264cij－B1B2B3B4A1－1500A204－10A3－1010＝表中还有负数，说明没有得到最优解，调整运输方案。σij(ui+vj)7/22/202349B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A3130＋2＋2－2－2新的运送方案B1B2B3B4A153A212A