第三章运输问题

第三章运输问题第一页，共四十一页，2022年，8月28日第三章运输问题

3.1运输问题的数学模型已知有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，这些数据可汇总于产销平衡表和单位运价表中，见下表。（）第二页，共四十一页，2022年，8月28日

若用xij表示从Ai到Bj的运量，那么在产销平衡条件下，要求得总运费最小的调运方案，可求解以下数学模型：第三章运输问题项目销地产量

12…n产地12…m

c11c12…c1nc21c22…c2n…cm1cm2…cmna1a2…am销量

b1b2…bn第三页，共四十一页，2022年，8月28日第三章运输问题这就是运输问题的数学模型。它包括m×n个变量，（m+n）个约束方程，其系数矩阵结构比较松散，且特殊：第四页，共四十一页，2022年，8月28日第三章运输问题第五页，共四十一页，2022年，8月28日系数矩阵中对应于变量xij的系数向量Pij，其分量除第i个和第m+j个为1外，其余的均为零。即

Pij=（0…1…1…0）T=ei+em+j对于产销平衡的运输问题由于存在：可以证明：只有m+n-1个独立约束方程。即系数矩阵的秩=m+n-1。由于以上特征，所以求解运输问题时，可用比较简便的计算方法，习惯上称为表上作业法。

3.2

表上作业法表上作业法是单纯形法在求解运输问题的一种简化方法。其实质是单纯形法。但具体计算术语有所不同，可归纳为：（1）找出初始基本可行解，即在（m×n）产销平衡表上给出m+n-1个独立的数字格。第三章运输问题第六页，共四十一页，2022年，8月28日（2）求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。（3）确定调入变量和调出变量，找出新的基本可行解。在表上用闭合回路法调整。（4）重复（2）（3），直到得到最优解。以上算法都可以在表上完成。下面通过例子说明表上作业法的计算步骤。

例3.1

某公司经销一种产品，公司有三个加工厂A1、A2、A3，其产量分别为7t、4t、9t。公司有四个经销点B1、B2、B3、B4，其销量分别为3t、6t、5t、6t。已知各加工厂到各销售点的单位产品运费如下表所示，问公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费最小。第三章运输问题第七页，共四十一页，2022年，8月28日解先画出该问题的单位运价表和产销平衡表，如下：第三章运输问题B1B2B3B4A1A2A3317119432101085销地产量B1B2B3B4产地A1A2A3749销量3656

确定初始基本可行解与一般线性规划问题不同。产销平衡的运输问题总是存在可行解。第八页，共四十一页，2022年，8月28日设第三章运输问题令这就是一个可行解，又因变量有界，即由线性方程组理论，运输问题最多有Cn×nm+n-1个基解，在这有限个基本解中必存在最优解。确定初始基本可行解的方法有很多，一般希望的方法既简便又尽可能接近最优解，最常用的方法有两种：最小元素法和伏格尔（Vogel）法。第九页，共四十一页，2022年，8月28日

1.最小元素法基本思想：就近供应，即从单位单价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基本可行解为止。第三章运输问题项目销地产量B1B2B3B4A1437A2314A3639销量3656项目B1B2B3B4A1311310A21928A374105该方案的总费用为86元。①②③④⑤⑥第十页，共四十一页，2022年，8月28日

2.伏格尔法最小元素法的缺点：为了节省一处的费用，有时造成其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小费用，这就有一个差额，差额越大，说明不能按最小运费调运时运费增加越多。因而对差额最大处，就应当采用最小运费调运。基于此，伏格尔法的步骤是：

第一步：分别计算出各行和各列的最小运费和次小运费之间的差额，并填入最右列和最下行。

第二步：从行和列差额中选择最大者，选择它所在的行或列的最小元素。

第三步：对未划的行和列再分别计算各行、各列的最小运费和次小运费的差额，重复一、二步。第三章运输问题第十一页，共四十一页，2022年，8月28日第三章运输问题B1B2B3B4行差额A13113100A219281A3741051列差额2513项目销地产量B1B2B3B4A1527A23

14A3639销量36562276①②③④⑤⑥第十二页，共四十一页，2022年，8月28日由上可见：伏格尔法与最小元素法除在确定供求关系的原则上不同外，其余步骤均相同。伏格尔法得出的初始解比最小元素法给出的初始解更接近最优解。本例用伏格尔法给出的初始解即为最优解，最优值是85元。

3.2.2最优解的判别判别的方法是计算空格（非基变量）的检验数cij-CBB-1Pij都大于等于零（为什么？）。下面介绍两种求空格检验数的方法。

1.闭回路法从每个空格出发找一条闭回路，它是以某空格为起点，用水平或垂直线向前划，每碰到一个数字时可以转90°后继续前进，直到回到起始空格为止。第三章运输问题第十三页，共四十一页，2022年，8月28日可以证明：如果不区分闭回路的方向，每一个非基变量空格都存在唯一一个闭回路。闭回路法是用来检查一个非基变量从零增加到大于零时能不能改变目标函数值的一种方法。以上例采用最小元素法得出的调运表为例。第三章运输问题第十四页，共四十一页，2022年，8月28日第三章运输问题项目销地产量B1B2B3B4A1437A2314A3639销量3656项目B1B2B3B4A1311310A21928A374105第十五页，共四十一页，2022年，8月28日例如在上表中，如果x22增加一个单位，那么要保持解的可行性，就要把x22回路中每个转角点的数字加以调整：减少一个x32，增加一个x34，减少一个x14，增加一个x13，减少一个x23。这样的改变可以继续保持供求的平衡假如C22’表示增加一个单位x22后运费的增加数，那么由运费表可知：

c22’=c22-c32-+c34-c14+c13-c23=

9-4+5-10+3-2=1

说明如果把x22增加一个单位，那么总运费要增加1元。

我们计算x24的检验数：

c24’=?第三章运输问题第十六页，共四十一页，2022年，8月28日已知运输问题的产销平衡和单位运价表，试用伏格尔法求出一个调运方案，并判断该方案是否是最优的。作业项目销地产量B1B2B3B4A184127A2694725A3534326销量10102015第十七页，共四十一页，2022年，8月28日作业项目销地产量B1B2B3B4A198121318A21010121424A38911126A41010111212销量614355第十八页，共四十一页，2022年，8月28日

2.位势法用闭回路法求检验数时，需要给每一空格找一条闭回路。当产销点多时，这种计算很繁琐。下面介绍一种更为简便的方法—位势法（乘数法）。位势法的原理是线性规划的对偶理论。下面通过一个简单的例子来说明。设有一个两个产地、三个销地的运输问题，其线性规划模型如下：第三章运输问题第十九页，共四十一页，2022年，8月28日

共有6个决策变量，在基本解中，应有四个基变量（为什么？），2个非基变量。设u1，u2为对应于产地的对偶变量，v1，v2，v3为对应于销地的对偶变量，则其对偶问题是：第三章运输问题第二十页，共四十一页，2022年，8月28日

如果原始问题得到一个调运方案（基本可行解），则对偶问题的约束条件是相应各变量的最优条件。对应于基变量的约束条件等式成立，对应于非基变量的约束条件，将不等号两边相减，即得到它的检验数。第三章运输问题第二十一页，共四十一页，2022年，8月28日例如，在这个调运方案中，x11，x12，x13，x21是基变量，则对偶约束条件中，前4个约束条件等式成立，即：这是一个有5个变量、4个方程的方程组，令任一变量等于零（不妨令u1=0），则可解出其他ui、vj变量的值。将求出的ui、vj代入到非基变量对应的约束条件，两边相减，即得到它们的检验数：第三章运输问题第二十二页，共四十一页，2022年，8月28日

由于运输模型的特殊性，上述计算过程相对比较简单。在例3.1由最小元素法的得到的初始解中x23，x34，x21，x32，x13，x14是基变量，这时对应的检验数是：第三章运输问题项目销地产量B1B2B3B4A1437A2314A3639销量3656第二十三页，共四十一页，2022年，8月28日基变量检验数如果设u1=0，则可以求得：

u1=0，u2=-1，u3=-5，v1=2，v2=9，v3=3，v4=10，因此非基变量的检验数：

σij=cij-(ui+vj)这样就可以从已知的ui，vj中求得。这些计算可以在表格中进行，以例3.1说明。第三章运输问题第二十四页，共四十一页，2022年，8月28日第一步，按最小元素法给出初始解，制成表格。

第二步，在上表中增加一行、一列，在列中填入ui，在行中填入vj。令u1=0，然后依据ui+vj=cij，相继确定ui，vj，依次求出所有的ui、vi的值。例如由u1+v3=3可得出v3=3；由u1+v4=10得出v4=10；由u3+v4=5得出u3=-5以此类推。第三章运输问题项目销地B1B2B3B4A143A231A363第二十五页，共四十一页，2022年，8月28日

第三章运输问题项目销地uiB1B2B3B4A112430A2311-1-1A3106123-5vj29310B1B2B3B4A1A2A3317119432101085第二十六页，共四十一页，2022年，8月28日第三步，按σij=cij-(ui+vj)计算所有空格的检验数。如：

σ11=c11-(u1+v1)=3-(0+2)=1

σ12=c12-(u1+v2)=11-(0+9)=2

这些计算可直接在表上进行。这和前面的计算结果是一样的。在上表中还有负的检验数，说明未得最优解，还可以改进。

第三章运输问题第二十七页，共四十一页，2022年，8月28日

3.2.3改进的计算方法在所有为负值的检验数中选最小的负检验数，以它对应的非基变量为调入变量，如在例3.1中σ24=-1，选非基变量x24为调入变量，并以x24所在的表格为出发点作出一个闭回路，如下表：第三章运输问题项目销地产量B1B2B3B4A1437A2314A3639销量3656第二十八页，共四十一页，2022年，8月28日由于σ24=-1，表明增加一个单位的x24的运输量，就可以使总运输量减少1。我们应尽量多地增加x24的运输量，但为了保证运输方案的可行性（即所有调运量必须大于等于零），所以以出发点x24所在空格为1的闭回路顶点的序号序号中，找到所有偶数的顶点的调运量：x14=3，x23=1，取其最小的值为x24的值，即x24=min(3,1)=1。为例使产销平衡，把所有闭回路上为偶数顶点的运输量都减少这个值，而其他顶点运输量增加这个值，即得到调整后的运输方案，如下表：第三章运输问题第二十九页，共四十一页，2022年，8月28日

对此表格出的运输方案，我们用位势法进行检验：第三章运输问题项目销地产量B1B2B3B4A1527A2314A3639销量3656第三十页，共四十一页，2022年，8月28日

可知所有检验数都大于等于零，此解是最优解，这时最小总费用为85元。第三章运输问题项目销地uiB1B2B3B4A102520A23211-1A396123-5vj29310第三十一页，共四十一页，2022年，8月28日

3.3产销不平衡的运输问题及其求解方法前面讲的表上作业法，都是以产销平衡为前提的。但实际问题中往往是产销不平衡的，就需要把产销不平衡问题转化成产销平衡问题。当产大于销时，运输问题的数学模型可写成：第三章运输问题第三十二页，共四十一页，2022年，8月28日

由于总的产量大于销量，就要考虑多余的物资在哪一地贮存问题。设xi,n+1是产地Ai的贮存量，于是有：第三章运输问题第三十三页，共四十一页，2022年，8月28日

令c’ij=cij，当i=1，…，m，j=1，…n时；

c’ij=0，当i=1，…，m，j=n+1时将其分别代入，得到：第三章运输问题第三十四页，共四十一页，2022年，8月28日

由于这模型中所以这是一个产销平衡的运输问题。第三章运输问题第三十五页，共四十一页，2022年，8月28日当产大于销时，只要增加一个假想的销地j=n+1（实际上是存储地），该销地总需求量为。而在单位运价表中从各地到假想销地的单位运价为c’i,n+1=0，就转化为一个产销平衡的运输问题。类似地，当销大于产时，可以从产销平衡表中增加一个假想的产地i=m+1，该产地的产量为。在单位运价表上令该假想产地到各销地的单位运价c’m+1,j=0，同样可以转化为一个产销平衡的运输问题。第三章运输问题第三十六页，共四十一页，2022年，8月28日例3.2设有三个化肥厂供应四个地区的农田化肥。各化肥厂年产量，各地区年需求量及从化肥厂到各地区运送化肥的运价表如下，试求总运费最节省的化肥调拨方案。第三章运输问题项目销地产量IIIIIIIV产地ABC1614191313202219231715506050最低需求3070010最高需求507030不限第三十七页，共四十一页，2022年，8月28日解：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨。最高需求无限制。根据现有产量，第IV个地区每年最多能分配到60万吨。这样最高需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂D，其产量为50吨。由于各地区的需求包括两部分，如地区I，其中30万吨是最低需求，故不能由D供给，令相应的运价为M（任意大正数），而另一部分20万吨或满足，或不满足均可以，因此可由D供给，且令相应的运价为0。对凡是需求分两种情况的地区，实际上可按两个地区看待。这样可以写出这个问题的产销平衡表和单位运价表，如下：第三章运输问题第三十八页，共四十一页，2022年，8月28日

第三章运输问题项目销地产量I’I”IIIIIIV’IV”产地ABCD50605050销量3020703010