运筹学第三章：运输问题

运筹学张铭鑫

机汽学院工业工程

2006年4月前两章讨论了一般线性规划的解法，但在实际工作中，往往碰到有些线性规划问题，它们的约束方程组的系数矩阵具有很特殊的结构，这就有可能找到比单纯形法更为简便的求解方法，本章讨论的运输问题就是这样一类特殊的线性规划问题。§3运输问题

（3.1运输问题的提出）§3运输问题

3.1运输问题在经济活动中，经常碰到大宗物资的调运问题。如煤、钢铁、木材、粮食等物资，在全国有若干生产基地，根据已有的交通网，制定调运方案，将这些物资运到各消费地点，而总运费最省。

这类问题的一般提法是：设某物资有m个产地A1,A2,…,Am,其产量分别为a1,a2,…,am,有n个销地B1,B2,…,Bn,其销量分别是b1,b2,…,bn，已知产地Ai到销地Bj的单位运费是Cij，这些数据可用产销平衡表和单位运价表表示如下：若总产量等于总销量(产销平衡),试确定总运费最省的调运方案.建模:设xij表示从产地Ai到销地Bj的运量(i=1,2,…m;j=1,2,…n),则运输问题的数学模型如下：

运输数学模型销地产地

B1B2…Bn

产量

A1A2┇Am

a1a2┇am销量b1，b2，…，bn销地产地B1B2…Bn

A1A2┇Am

C11C12…C1nC21C22…C2n………………Cm1Cm2…Cmn产销平衡表

单位运价表

X11X12…X1nX21X22…X2n………………Xm1Xm2…Xmn运输数学模型系数矩阵1记

则

显然，模型是具有m×n个变量，m+n个约束的线性规划，可以用一般的单纯形法求解，但是当m与n较大时，模型的规模比较大，计算比较困难。为了进一步研究针对运输问题的特殊解法，下面考察它的约束系数矩阵。系数矩阵2记

则

A是m+n行，m×n列的矩阵，它比较稀疏，除有2m×n个1以外，其余元素皆为0，变量xij对应的系数列向量Pij中，除第i个和第m+j个为1外，其余全是0，即Pij=(0...1...1...0)T=ei+em+j系数矩阵2A是m+n行，m×n列的矩阵，它比较稀疏，除有2m×n个1以外，其余元素皆为0，变量xij对应的系数列向量Pij中，除第i个和第m+j个为1外，其余全是0，即Pij=(0...1...1...0)T=ei+em+j销地产地

B1B2B3产量

A1A2a1a2销量b1，b2，b3X11X12X13X21X22X23系数矩阵的秩记

则

运输方程的总数是m+n个，它的系数矩阵A的秩是m+n-1。可见，运输问题的基可行解中，基变量的个数应为m+n-1个。由于运输问题的数学模型具有以上特点，所以求解运输问题时，可以采用比较简单的计算方法―表上作业法。3.2表上作业法表上作业法的思想和单纯形法类似，即首先确定一个初始方案，找出一个基可行解，然后根据判别准则来检查这个初始方案是不是最优的，如果不是最优的，那么对该方案进行调整，直到求出最优方案为止。下面介绍它的计算步骤。3.2.1确定初始基可解确定初始基可行解的方法很多，我们介绍两种：最小元素法和伏格尔法。

1.最小元素法基本思想就是就近供应，即从运价表中最小运价开始确定调运量，然后次小，一直到找出初始调运方案为止。3.2表上作业法例1某公司经销甲产品。它下设三个工厂。每日的产量分别是A1为7吨，A2为4吨，A3为9吨，该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为表3－3所示，试确定总运费最省的调运方案。1.最小元素法（1）表3－3单位运价表

销地产地B1B2B3B4A1A2A3317119432101085销地产地B1B2B3B4产量A1A2A3749销量3656表3－4产销平衡表

3114633运费Z＝1×3＋4×6＋3×4＋1×2＋3×10＋3×5＝86314633

用最小元素法确定初始可行解：x13=4,x14=3x21=3,x23=1x32=6,x33=3z=3*4+10*3+1*3+2*1+4*6+5*3=861.最小元素法（复件1）1.最小元素法（2）表3－3单位运价表

销地产地

B1B2B3B4A1A2A3317119432101085销地产地

B1B2B3B4产量A1A2A3749销量3656表3－4产销平衡表

314633

用最小元素法所得初始调运方案如表3－4黄字所示。称产销平衡表中填有数字的格为数字格，没填数字的格称为空格。由最小元素法可知，在产销平衡表上每填一个数字，就划去一行或一列，表中共有m行n列，用m+n-1条线就可划去运价表所有元素，相应地在产销平衡表上就形成m+n-1个数字格。前面已经说明了运输问题的约束系数矩阵A的秩恰为m+n-1，理论上可以证明，这些数字所对应的变量相当于基变量，而空格对应的变量相当于非基变量，用最小元素法得到的初始调运方案构成一个初始基可行解。1.最小元素法（特别注意）表3－3单位运价表

销地产地

B1B2B3B4A1A2A3317119432101085销地产地

B1B2B3B4产量A1A2A3749销量3656表3－4产销平衡表

314633特别注意：数02.伏格尔法

2.伏格尔法

最小元素法的缺点是：为了节省一处的运费，有时可能造成在其它的地方多化几倍的运费。伏格尔法考虑到，一个产地的产品如果不能按最小运费就近供应，就考虑次小的运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费来调运。

伏格尔法的计算步骤：

第一步：计算单位运价表上各行和各列的最小运费和次小运费的差额，填入表的最右列和最下行。

第二步：从行或列差额中选出最大值，选择它所在行或列中的最小元素.满足最小运费调运,划去已得到满足的行或列的运价。

第三步：然后计算未被划去的行或列，重新计算差额，重复第一步和第二步，直到给出一个初始的基可行解为止。3.2表上作业法用伏格尔法确定初始解601125130122

13201

2

12376

12531z=3*1+6*4+5*3+2*10+1*8+3*5=85返回3.2.2最优性检验3.2.2最优性检验在求出问题的一个可行方案后，就应该判断这个方案是不是最优的。为了进行最优性判别，下面先给出检验树的概念。对于空格(i,j)，调整其它有关数字格的运量，则称这一系列的变化导致的总运费变化值为该空格的检验数，记作σij。当一个空格的检验数大于零，说明将该空格变为数字格会使总运费增加；反之，如果该空格检验数为负值，说明将该空格变为数字格会使总运费降低。因此有以下判别准则：

定理：如果一个可行方案的所有空格检验数都大于或等于零，则方案是最优方案。对于一个可行方案，只要求出所有空格的检验数，就可以判别该方案是否为最优方案，那么如何求得一个空格的检验数呢？下面给出两种计算检验数的方法。

3.2表上作业法＋1

1.闭回路法1.闭回路法

为了确定空格(i,j)的检验数，可以先找出以该空格为一个顶点,其余顶点全是数字格的闭回路。所谓闭回路，就是从该空格出发，沿水平或垂直方向前进，遇到合适的数字格后转90˙，继续前进，如果能够回到出发点，则称这个封闭折线为闭回路。然后假定给(i,j)格一个单位运量，调整闭回路上其余数字格的运量，使产销平衡，则闭回路上总费用的变化值就等于(i,j)格的检验数。

可以证明，在任何可行方案中，以空格(i,j)为一个顶点，其余顶点全是数字格的闭回路存在而且唯一。数

数

数

数

数

－1

＋1

－1

＋1

－1

用闭回路法求检验数(空格11)3111310销地产地

B1B2B3B4产量A17A24A39销量365692874105364133闭回路法求检验数＋1

－1

＋1

－1

σ11＝(+1)×3+(-1)×3+(+1)×2+(-1)×1=1用闭回路法求检验数(空格12－错)3111310销地产地

B1B2B3B4产量A17A24A39销量365692874105364133闭回路法求检验数用闭回路法求检验数(空格12－对)3111310销地产地

B1B2B3B4产量A17A24A39销量365692874105364133闭回路法求检验数＋1

－1

＋1

－1

σ12＝(+1)×11+(-1)×10+(+1)×5+(-1)×4=2用闭回路法求检验数(空格12－对)3111310销地产地

B1B2B3B4产量A17A24A39销量365692874105364133闭回路法求检验数＋1

－1

＋1

－1

σ22＝(+1)×9+(-1)×2+(+1)×3+(-1)×10+(+1)×5+(-1)×4=1－1

＋1

用闭回路法求检验数(空格12－对)3111310销地产地

B1B2B3B4产量A17A24A39销量365692874105364133闭回路法求检验数＋1

－1

＋1

－1

σ24＝(+1)×8+(-1)×2+(+1)×3+(-1)×10=-1用闭回路法求检验数(空格12－对)3111310销地产地

B1B2B3B4产量A17A24A39销量365692874105364133闭回路法求检验数＋1

－1

＋1

－1

σ31＝(+1)×7+(-1)×5+(+1)×10+(-1)×3+(+1)×2+(-1)×1=10－1

＋1

用闭回路法求检验数(空格12－对)3111310销地产地

B1B2B3B4产量A17A24A39销量365692874105364133闭回路法求检验数＋1

－1

＋1

－1

σ33＝(+1)×10+(-1)×5+(+1)×10+(-1)×3=12表3－15空格闭回路检验数(11)(12)(22)(24)(31)(33)(11)－(13)－(23)－(21)－(11)(12)－(14)－(34)－(32)－(12)(22)－(23)－(13)－(14)－(34)－(32)－(22)(24)－(23)－(13)－(14)－(24)(31)－(34)－(14)－(13)－(23)－(21)－(31)(33)－(34)－(14)－(13)－(33)121-11012表3－15用闭回路法求检验数(空格24)3111310销地产地

B1B2B3B4产量A17A24A39销量365692874105364133＋1

－1

＋1

－1

空格闭回路检验数(24)(24)－(23)－(13)－(14)－(24)-1σ24＝(+1)×8+(-1)×2+(+1)×3+(-1)×10=－12.位势法

用闭回路法求检验数时，需要找出每个空格所在的闭回路，产销点很多时，计算量非常大。下面介绍一种求检验数简便的方法－位势法。设Y=(u1,u2,…,um,v1,v2,…,vn)是运输问题的m+n个约束条件对应的对偶变量,决策变量xij(数字格)对应的列向量Pij=ei+em+j，对于一个基可行解，由单纯形法得知所有基变量xij(数字格)的检验数等于0，即0=Cij-CBB-1Pij=Cij-YPij=Cij-(ui+vj)，所以由m+n-1个数字格对应的Cij=(ui+vj)及u1＝0，即可确定所有ui,vj的值。

称u1,u2,…,um,v1,v2,…,vn分别为产销平衡表各行与各列的位势。因为非基变量的（空格）检验数σij=Cij-YPij=Cij-(ui+vj)，所以，只要计算出所有的位势值，就能求出各空格的检验数。可以证明，在任何可行方案中，以空格(i,j)为一个顶点，其余顶点全是数字格的闭回路存在而且唯一。2.位势法用位势法求检验数3146330103-1-5921--2--1-1----1012----Cij=(ui+vj),确定所有ui,vj的值.令u1=0,由(1,3)数字格运价3=u1+v3，可得v3=3；先由m+n-1个数字格对应的再按公式σij=Cij-(ui+vj)计算空格的检验数,结果见表格中红色数字,例σ11=C11-(u1+v1)=3-(0+2)=13.位势法方案的调整―闭回路法

当空格的检验数出现负值时，说明当前平衡表给出的调运方案不是最优的，可以进行调整，使总运输费用减少。调整方法如下：1°为了使方案有较大改进，先确定最小检验数，即min{σij|σij<0}=σLK2°找出以空格(L,K)为一个顶点，其余顶点全是数字格的闭回路,规定空格(L,K)为闭回路的第一个顶点，闭回路上其它顶点依次为第二个顶点，第三个顶点，…(顺时针或逆时针均可)。取闭回路上偶数序号顶点的最小运量为调整运量θ.

3.方案的调整－闭回路法＋1

数

数

数

－1

＋1

－1

(L,K)

3

2

θ=min{2,3}=2

3

0

-1

3.位势法方案的调整―闭回路法

当空格的检验数出现负值时，说明当前平衡表给出的调运方案不是最优的，可以进行调整，使总运输费用减少。调整方法如下：1°为了使方案有较大改进，先确定最小检验数，即min{σij|σij<0}=σLK2°找出以空格(L,K)为一个顶点，其余顶点全是数字格的闭回路,规定空格(L,K)为闭回路的第一个顶点，闭回路上其它顶点依次为第二个顶点，第三个顶点，…(顺时针或逆时针均可)。取闭回路上偶数序号顶点的最小运量为调整运量θ.

闭回路法(步骤1)＋1

数

数

数

－1

＋1

－1

(L,K)

2

2

θ=min{2,2}=2

2

0

0

3.位势法方案的调整―闭回路法

当空格的检验数出现负值时，说明当前平衡表给出的调运方案不是最优的，可以进行调整，使总运输费用减少。调整方法如下：1°为了使方案有较大改进，先确定最小检验数，即min{σij|σij<0}=σLK2°找出以空格(L,K)为一个顶点，其余顶点全是数字格的闭回路,规定空格(L,K)为闭回路的第一个顶点，闭回路上其它顶点依次为第二个顶点，第三个顶点，…(顺时针或逆时针均可)。取闭回路上偶数序号顶点的最小运量为调整运量θ.

闭回路法(步骤2)＋1

数

数

数

－1

＋1

－1

(L,K)

2

2

θ=min{2,2}=2

2

0

0

3.位势法方案的调整―闭回路法

当空格的检验数出现负值时，说明当前平衡表给出的调运方案不是最优的，可以进行调整，使总运输费用减少。调整方法如下：1°为了使方案有较大改进，先确定最小检验数，即min{σij|σij<0}=σLK2°找出以空格(L,K)为一个顶点，其余顶点全是数字格的闭回路,规定空格(L,K)为闭回路的第一个顶点，闭回路上其它顶点依次为第二个顶点，第三个顶点，…(顺时针或逆时针均可)。取闭回路上偶数序号顶点的最小运量为调整运量θ.3°闭回路上偶数序号顶点的运量均减θ，奇数序号顶点运量均加θ，不在闭回路上的运量不变。调整中，如果偶数序号顶点中仅有一个数字格的运量等于θ，则调整后，该格变为空格；如果偶数序号顶点中有两个以上的数字格运量等于调整量θ，则调整后，仅让其中一个数字格变为空格，其它调整后要记“0”，表示该格为数字格。经过这样调整，就可以得到一个含有m+n-1个数字格的新的调运方案。闭回路法(步骤3)如例1的初始方案经检验，存在一个负检验数σ24＝－1，该方案不是最优方案,在平衡表上找出闭回路。闭回路法调整例1方案－1销地产地B1B2B3B4产量A1437A2314A3639销量3656＋1

－1

＋1

－1

θ=min{1,3}=1如例1的初始方案经检验，存在一个负检验数σ24＝－1，该方案不是最优方案,在平衡表上找出闭回路。闭回路法调整例1方案－2销地产地

B1B2B3B4产量A1527A2314A3639销量3656z=5*3+2*10+3*1+1*8+6*4+3*5=85用位势法求检验数356320103-2-5930--2--21----912----对数字格，用式Cij

=（Ui+Vj）计算Ui和Vj

；对空格，用式ij=Cij

-（Ui+Vj），计算其检验数。1z=5*3+2*10+3*1+1*8+6*4+3*5=853.3产销不平衡的运输问题（产大于销）前面讨论的运输问题的理论和方法，都是以产销平衡,即：为前提的。但是在实际问题中产销往往是不平衡的。对于产销不平衡的运输问题，可以把它们转化成产销平衡问题，然后再用表上作业法求解。

1.产大于销的情况，即由于总产量大于总销量，就要考虑多余的物资在哪些产地就地贮存的问题。将各产地的仓库设成一个假想销地Bn+1，该地总需求量为再令运价表中各地到虚设销地Bn+1的单位运Ci,n+1=0,i=1,2...m,则该问题就转化成一个产销平衡问题，可以用表上作业法求解了.在最优解中，产地Ai到虚拟销地Bn+1的运量,实际上就是产地Ai就地贮存的多余物资数量。3.3产销不平衡的运输问题3.3产销不平衡的运输问题（销大于产）

2.供不应求的情况，即与产大于销类似，当销大于产时，可以在产销平衡表中虚设一个产地Am+1，该产地的产量为

再今虚拟产地Am+1到各销地的单位运价Cm+1,j=0,j=1,2,…n,则问题可以转化为一个产销平衡运输问题。在最优解中，虚拟产地Am+1到销地Bj的运量实际上就是最后分配方案中销地Bj的缺货量。在产销不平衡问题中，如果某产地不允许将多余物资就地贮存，或不允许缺货，则今相应运价Ci,n+1或Cm+1,j=M(M是相当大的正数)。3.3产销不平衡的运输问题

例2设有三个化肥厂供应四个地区的农用化肥，各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送化肥的单位运价表如表3－25所示，试求总运费最省的花费调运方案。例2-1需求地区化肥厂IIIIIIIV产量ABC1614191313202219231725－506050最低需求最高需求3050707003010不限解：化肥厂总产量是50+60+50=160万吨；如果满足其最低需求，需求总量是30+70+10=110万吨；这时情况属于产大于销；如果满足其最高需求，因为第四个地区的最高需求是“不限”的，所以这种情况是属于销大于产。

例2例2-2需求地区化肥厂IIIIIIIV产量ABC1614191313202219231725－506050最低需求最高需求3050707003010不限解：既满足其最低需求，又同时尽可能满足其最高需求。确定“不限量”。前三个销售地最低需求的总和30+70+0=100,总产量现在是160万吨，

第四个销售地最多销售160-100=60，所以,“不限量”＝60。最高需求量50+70+30+60=210,化肥厂总产量是50+60+50=160,销量大于产量。为了求得平衡,假想增加一个化肥厂D,其年产量为210-160=50.产销不平衡问题，就转化为一个产销平衡的问题。例2-3需求地区化肥厂IIIIIIIV产量ABC1614191313202219231715－506050最低需求最高需求305070700301060需求地区化肥厂产量ABCD50605050销量I′I″3020II70III30IV′

IV″1050

1613221717

14141319151519192023MMM0M0M0例2(最优解)需求地区化肥厂产量ABCD3020502003010302050605050销量I′I″3020II70III30IV′

IV″1050

根据表上作法求解，得到最优方案如表3-28所示。

我们注意，产销平衡表中m=4,n=6,m+n-1=4+6-1=9，正好表中最优解也有9个基变量。由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多，所以在解决实际问题时，人们常常尽可能把某些线性规划问题化为运输问题的数学模型，下面来介绍几个典型的例子。

例3某厂按合同规定须于当年每个季度末分别提供10,1525,20台同一规格的柴油机，已知该厂各季度的生产能力及生产每台柴油机的成本如下表，又知如果生产出来的柴油机当季度不交货，每台每季度的存储维护费用为0.15万元，试安排全年生产计划，使总费用最低。3.4应用举例3.4应用举例季度生产能力单位成本IIIIIIIV25台35台30台10台10.8万元11.1万元11.0万元11.3万元例3某厂按合同规定须于当年每个季度末分别提供10,1525,20台同一规格的柴油机，已知该厂各季度的生产能力及生产每台柴油机的成本如下表，又知如果生产出来的柴油机当季度不交货，每台每季度的存储维护费用为0.15万元，试安排全年生产计划，使总费用最低。例3（解）季度生产能力单位成本IIIIIIIV25台35台30台10台10.8万元11.1万元11.0万元11.3万元解：产量25+35+30+10=100台；需求量10+15+25+20=70台。由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的用于第j季度交货的柴油机数。例3需求量10+15+25+20=70台，

每台每季度的存储维护费用为0.15万元。例3（分析产量）季度生产能力单位成本IIIIIIIV25台35台30台10台10.8万元11.1万元11.0万元11.3万元解：设第一个季度生产X1台，X1包括X11用于当季度交货，也可以供给第二季度X12，然后还可以用于第三季度交货X13，最后供给第四个季度X14。X1=X11+X12+X13+X14≤25X2=X22+X23+X24≤35

X3=X33+X34≤30X4=X44≤10例3需求量10+15+25+20=70台，

每台每季度的存储维护费用为0.15万元。例3（分析销量）季度生产能力单位成本IIIIIIIV25台35台30台10台10.8万元11.1万元11.0万元11.3万元解：X11是为满足第一季度销量而生产的，第二个季度的销量由两部分供应X12和X22。X12是第一个季度为第二个季度生产的，X22是第二个季度本身为满足销量生产的，所以X11=10X12+X22=15X13+X23+X33=25X14+X24+X34+X44=20例3建立产销平衡表

各季度都生产产品，都可看作是产地；各季度都有销售，都可看作是销地。又因为这是一个产大于销的运输问题，需增加虚拟销地D，销售D的销量=总产量－总销量＝100－70=30。所以产销平衡表如下：

例3（产销平衡表）销地产地IIIIIIIVD产量IIIIIIIV25353010销量1015252030例3建立单位运价表

已知每台生产成本如下表，每台每季度的存储维护费用为0.15万元。例3（单位运价表）季度生产能力单位成本IIIIIIIV25台35台30台10台10.8万元11.1万元11.0万元11.3万元销地产地IIIIIIIVDIIIIIIIV10.8MMM10.9511.10MM11.1011.2511.00M11.2511.4011.1511.300000例3最优解决方案

用最小元素法写出初始调运方案，然后再进行最优性检验，接着进行方案的调整，最后得出最优解，例3（最优解决方案）销地产地IIIIIIIVD产量IIIIIIIV101552010103025353010销量1015252030例4某航运公司承担六个港口城市A、B、C、D、E、F间四条航线的货物运输任务。各航线的起点、终点、日航班数如下：表3-33

例4（表3-33，3-34）航线起点终点日航班数1234EBADDCFB3211

假定各航线使用的船只相同，各城市间的航程天数如下：表3-34

到从ABCDEFABCDEF0121477103138823015551413150172078517037852030又知每条船每次装卸货时间各需1天，问该公司至少应配备多少船？例4某航运公司承担六个港口城市A、B、C、D、E、F间四条航线的货物运输任务。各航线的起点、终点、日航班数如下：表3-33

例4（分析港口）航线起点终点日航班数1234EBADDCFB3211起点可以认为是需要船只的，终点可以提供船只的。

需要船只的港口是A、B、E；可以提供船的是C、D、F。

例4某航运公司承担六个港口城市A、B、C、D、E、F间四条航线的货物运输任务。各航线的起点、终点、日航班数如下：表3-33

例4（分析