第三章-运输问题-运筹学

清华大学出版社《运筹学教程》（第三版）运筹学基础胡运权主编教材

诸如这类有多个不同的生产、消费者，如何合理不同的生产者和消费者之间的分配关系，达到最小费用的问题也运筹学最重要的问题之一。我们把这种分派问题称为运输问题。

在运筹学中，运输问题是一个广义的“运输”，即许多其它问题也可以通过适当的手段，把它们转化为运输问题加以解决。这部分也是我们这学期主要学习内容之一。运输问题某种物品先存放在两个仓库A1相A2中，再运往三个使用地B1，B2和B3，其间的距离(或单位运价)如下表小方格中的数据所示，各仓库的存量和使用地的需用量也都示于下表中，试建立控总运输量(或总运费)最小的运输问题数学模型。设：xij——

从Ai地运往Bj地的货物数量运价min

z=3x11+4x12+2x13+

3x21+5x22+3x23x11+x12+x13=10约束条件st.x21+x22+x23=4x11+x21=3x12+x22=5x13+x23=6xij

≥0运输问题的特点x11+x12+x13=10x21+x22+x23=4x11+x21=3x12+x22=5x13+x23=6111101114113115116

1）运输问题有有限最优解2）运输问题系数矩阵非常特殊3）运输问题约束都是等式约束5）一般运输问题都是产销平衡的（不平衡问题要化为平衡问题）4）一般运输问题约束有一个多余的约束6）一般产m、销n有（m*n）个变量和（m+n）个约束（没有去掉多余）7）产m、销n运输问题最多有（m+n-1）个值为非零的变量因为有一个约束多余，既R（A）=m+n-1运输问题求解方法：表上作业法例三

B1B2B3B4产量A116A210A322销量8141214484124112103985116最小元素法82101486

B1B2B3B4产量A116A210A322销量81412144841241121039851168864814西北角法运价：246运价：372例三

B1B2B3B4产量A116A210A322销量8141214484850402103985116最小元素法821486108864814运价：880运价：456

B1B2B3B4产量A116A210A322销量8141214484850402103985116西北角法有没有搞错！！！例三

B1B2B3B4产量A116A210A322销量8141214484850402103985116最小元素法8214问题就在这里！！！沃格尔提出一种新的解决问题的方法思路例三

B1B2B3B4产量A116A210A322销量814121448412411210398511614运价：244列罚数12345行罚数8124282513011213012212011276200运价：246（最小元素法）运价：372（西北角法）怎样的安排为最优呢？例三

B1B2B3B4产量A116A210A322销量8141214484124112103985116abcd

B1B2B3B4产量A116A210A322销量814121448afbcde

cbjiahgfed闭回路检验法例三

B1B2B3B4产量A116A210A322销量8141214484124112103985116最小元素法82101486运价：246b例三

B1B2B3B4产量A116A210A322销量8141214484124112103985116最小元素法82101486运价：246b0例三

B1B2B3B4产量A116A210A322销量8141214484124112103985116最小元素法82101486运价：246b2例三

B1B2B3B4产量A116A210A322销量8141214484124112103985116最小元素法82101484运价：246b2例三

B1B2B3B4产量A116A210A322销量8141214484124112103985116最小元素法82121484运价：246b2例三

B1B2B3B4产量A116A210A322销量8141214484124112103985116最小元素法80121484运价：246b2例三

B1B2B3B4产量A116A210A322销量8141214484124112103985116最小元素法8121484运价：2462244例三

B1B2B3B4产量A116A210A322销量814121448412411210398511680121484b

B1B2B3B4产量A116A210A322销量81412144841241121039851169-11+4-3=-1-11102112

我们可以通过找出所有回路的方法来确定怎样调整运输计划，逐步使总运价降低。这种逐步调整运输计划直至达到最优解为止的方法称为闭合回路法。它的难点是每次找这些回路非常复杂。有更好的办法吗？运输问题的数学模型（假定产销平衡）目标函数：nmj=1i=1minZ=∑∑Cij

xijnj=1∑xij=aii=1,2,…m产量约束：销量约束：mi=1∑xij=bjj=1,2,…nxij

≥0nmj=1i=1maxw=∑aiui＋∑bj

vjui+vj

≤cijui、vj无约束σ=C-CBB-1A=C-YAσij=cij-(u1,u2……um,v1,v2……vn)pij=cij-ui-vj运输问题的数学模型（假定产销平衡）由于基变量的检验数等于零，故对这组基变量可写出方程组：现设已得到的运输问题的一个基可行解，其基变量是：显然，这个方程组有(m+n-1)个方程。运输表中每个产地和每个销地都对应原运输问题的一个约束条件，从而也对应各自的一个对偶变量；由于运输表中每行和每列都含有基变量，可知这样构造的以上方程组中含有全部(m+n)个对偶变量。可以证明，以上方程组有解，且由于对偶变量比方程数多一个，故解不唯一。基变量对应的σ应该等于零n+m-1个等式,但有n+m个变量无穷多解解称为位势运输问题的数学模型（假定产销平衡）若由以上方程组解得的某组解满足对偶问题约束条件，这时可以证明：若由上式解得的解不满足约束条件式，即非基变量的检验数有负值存在，则上面得到的运输问题的解不是最优解，需要进行解的调整。现仍用前面的例子说明用位势法(对偶变量法)求检验数的方法和步骤。运输问题的数学模型（假定产销平衡）

(1)在上表上增加一位势列ui和位势行vi。

(2)计算位势。可先建立方程组，并据此计算出运输表各行和格列的位势。在本例中，x13，x14，x21，x23，x32，x34这六个变量为基变量，故有：

B1B2B3B4产量A116A210A322销量814121448412411210398511681014862运输问题的数学模型（假定产销平衡）在求解以上方程组时，为计算简便，常任意指定某一位势等于一个较小的整数或零。在此例求解时，任意指定u2=0，由此可算出：v1=2，v3=3，u1=1，v4=10，u3=-4，v2=9(3)计算检验数有了位势ui和vj之后，即可计算各空格的检验数。本例算出各空格的检验数如下表：

B1B2B3B4产量A116A210A322销量81412144841241121039851161121210-1运输问题的数学模型（假定产销平衡）三、解的改进对运输问题的一个解来说，若最优性检验时某非基变量xij的检验数为负，说明将这个非基变量变为基变量时运费会更小，因而这个解不是最优解，还可以进一步改进。改进的方法是在运输表中找出这个空格对应的闭回路，在满足所有约束条件前提下，使xij尽量增大并相应调整此闭回路上其他顶点的运输量，已得到另一个更好的基可行解。解改进的具体步骤为：(1)以xij为换入变量，找出它在运输表中的闭回路；(2)以空格(Ai,Bj)为第一个奇数顶点，沿闭回路的顺(或逆)时针方向前进，对闭回路上的顶点依次编号；(3)在闭回路上的所有偶数顶点中，找出运输量最小的xij的顶点，以该格中的变量为换出变量;(4)以运输量最小的xij为调整量，将该闭合回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案。该运输方案的总费用比原运输方案减少。然后再对得到的新解进行最优性检验。运输问题的数学模型（假定产销平衡）例：对上面用最小元素法得出的解进行改进。

B1B2B3B4产量A116A210A322销量81412144841241121039851161121210-1

B1B2B3B4产量A116A210A322销量814121448412411210398511682121484b2运价：246+2*（-1）=244运输问题的数学模型（假定产销平衡）再用位势法或闭回路法求这个新解各非基变量的检验数，结果列于下表。由于所有非基变量的检验数全非负，故为最优解。

B1B2B3B4产量A116A210A322销量81412144841241121039851160221291对这个解来说，因为

ij=0,若x11为换入变量可再得一解，它与上面最优解的目标函数值相等，故它也是一个最优解。几点说明

1、若运输问题的某一基可行解有多个非基变量的检验数为负，在继续进行迭代时，取它们中的任一变量为换入变量可使目标函数值得到改善，但通常取最小者对应的变量为换入变量。

2、当迭代到运输问题的最优解时，如果有某非基变量的检验数为0，则说明该运输问题有多重最优解。

3、当运输问题某部分产地的产量和与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时常发生的。为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量。使迭代过程中基变量个数恰好为(m+n-1)个。运输问题的进一步讨论一、产销不平衡的运输问题前面讲述的运输问题的算法，是以总产量等于总销量为前提的。实际上，在很多运输问题中，总产量不等于总销量。这时，为了使用前述表上作业法求解，就需将产销不平衡问题化为产销平衡运输问题。如果总产量大于总销量，即运输问题的进一步讨论为借助于产销平衡时的表上作业法求解，可增加一个假想的销地Bn+1，由于实际上它不存在，因而由产地Ai调运到这个假想销地的物品数量xi,n+1，实际上是就地存储在Ai的物品数量。就地存储的物品不经过运输，故可令其单位运价ci,n+1=0。

若令假想地的销量为bn+1，且则模型变为：运输问题的进一步讨论

？例某市有三个造纸厂A1、A2和A3，其纸的产量分别为8个单位、5个单位和9个单位，有4个集中用户B1、B2、B3和B4，其需用量分别为4个单位，3个单位，5个单位和6个单位