运筹学-表上作业法

1、运输问题求解运输问题求解 表上作业法表上作业法运输问题求解之表上作业法运输问题求解之表上作业法1.运输问题模型及其求解思路运输问题模型及其求解思路2.确定初始基本可行解确定初始基本可行解3.最优性检验最优性检验4.方案调整方案调整1.运输问题模型及其求解思路运输问题模型及其求解思路v运输问题： 研究把某种商品从若干个产地运至若干个销售地而使总运费最小的一类问题。v目标：1总运费最小 1.运输问题模型及其求解思路运输问题模型及其求解思路 销地产地B1B2Bn产量A1A2 :Amc11c21:cm1c12c22:cm2:c1nc2n:cmna1a2:am销量b1b2bnv 已知有m个产地Ai（i=

2、1,2， ， m ）可供应某种物资，其供应量（产量）分别为ai ，有n个销地Bj （j=1,2， ， n）其销量（需求量）分别为bj ，从A到B的单位物资运价为cij 。若设若设 代表从第代表从第Ai个产地到第个产地到第Bj个销售地的调运量，在个销售地的调运量，在产销产销平衡平衡的条件下（的条件下（ ），要确定总运输费用最小的调运），要确定总运输费用最小的调运方案，可表示为如下的数学模型方案，可表示为如下的数学模型ijxnjjmiiba11ijmnjijxcz11mini011ijjmiijinjijxbxaxs.t.(i=1，2，m； j=1，2，n)矩阵形式：CXzmin0XAXbs.t.

3、 1.运输问题模型及其求解思路运输问题模型及其求解思路1 1 1 1 1 11 1 11 1 11 1 11 1 1 A=m 行n 行 1.运输问题模型及其求解思路运输问题模型及其求解思路系数矩阵2 1.运输问题模型及其求解思路运输问题模型及其求解思路对于产销平衡的运输问题，对于产销平衡的运输问题，若产地为若产地为m个，销地为个，销地为n个，个，则则 变量个数为变量个数为mn个，个，约束条件个数为约束条件个数为m+n，其中包含：总产量总销售其中包含：总产量总销售故线性无关的约束条件个数为故线性无关的约束条件个数为m+n-1，基本解中的基变量个数为基本解中的基变量个数为m+n-1。v运输问题求解

4、思路运输问题求解思路表上作业法表上作业法v由于运输规划系数矩阵的特殊性，如果直接使用线由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条性规划单纯形法求解计算，则无法利用这些有利条件。件。v人们在分析运输规划系数矩阵特征的基础上建立了人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的针对运输问题的表上作业法表上作业法。 1.运输问题模型及其求解思路运输问题模型及其求解思路v 表上作业法是单纯形法在求解产销平衡的运输问题时的一表上作业法是单纯形法在求解产销平衡的运输问题时的一种简化方法，其实质仍是单纯形法，所不同的只是完成各种简化方法，其实质仍是单纯

5、形法，所不同的只是完成各步采用的具体形式。步采用的具体形式。v 具体操作步骤如下：具体操作步骤如下：v （1）确定一个初始基本可行解：即在）确定一个初始基本可行解：即在mn阶产销平衡阶产销平衡表上给出表上给出m+n-1个数字格（个数字格（基变量基变量）；）；v （2）求各非基变量（空格）的检验数，即在表上）求各非基变量（空格）的检验数，即在表上计算空格的计算空格的检验数检验数。判别式否达到最优解。如果是最优解，。判别式否达到最优解。如果是最优解，则停止计算，否则进入下一步。则停止计算，否则进入下一步。v （3）确定换入变量和换出变量，找出新的基可行解。）确定换入变量和换出变量，找出新的基可行解

6、。v （4）重复）重复(2)、(3)直至得到最优解为止直至得到最优解为止。 1.运输问题模型及其求解思路运输问题模型及其求解思路2.确定初始基本可行解确定初始基本可行解1）最小元素法）最小元素法 基本思想：基本思想：就近供应就近供应，按运价最小的优先调运原则确，按运价最小的优先调运原则确定初始方案，即从单位运价表中选择运价定初始方案，即从单位运价表中选择运价最小的开始确定调运关系，然后次小。若最小的开始确定调运关系，然后次小。若某行（列）的产量（销量）已满足，则把某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，该行（列）的其他格划去。如此进行下去，一直到给出初始基可行

7、解为止一直到给出初始基可行解为止 。 v 例如，某公司经营某种产品，该公司下设例如，某公司经营某种产品，该公司下设A、B、C三个三个生产厂，有甲、乙、丙、丁四个销售点。公司每天把三个生产厂，有甲、乙、丙、丁四个销售点。公司每天把三个工厂生产的产品分别运往四个销售点，各工厂到各销售点工厂生产的产品分别运往四个销售点，各工厂到各销售点的路程不同，单位产品的运费不同。各工厂每日的产量、的路程不同，单位产品的运费不同。各工厂每日的产量、各销售点每日的销量，以及从各工厂到各销售点单位产品各销售点每日的销量，以及从各工厂到各销售点单位产品的运价如下表。问该公司如何调运产品，在满足各销售点的运价如下表。问该

8、公司如何调运产品，在满足各销售点需要的前提下，使需要的前提下，使总运费最小总运费最小。甲甲乙乙丙丙丁丁产量产量A3113107B19284C741059销量销量36562.确定初始基本可行解确定初始基本可行解34333231242322211413121151047829103113minxxxxxxxxxxxxz06563947342414332313322212312111343332312423222114131211ijxxxxxxxxxxxxxxxxxxxxxxxxxs.t2.确定初始基本可行解确定初始基本可行解ijxv 若设 代表从第i个产地到第j个销售地的运输量（i=1,2,3；

9、j=1,2,3,4)B1B2B3B4产量产量A13113107A219284A3741059销量销量36563431632.确定初始基本可行解确定初始基本可行解Z=43+310+31+12+64+35=86为保证基变量的个数有为保证基变量的个数有m+n-1个，个，v1、每次填完数，只能划去一行或一列，只、每次填完数，只能划去一行或一列，只有最后一个格子例外。有最后一个格子例外。v2、用最小元素法时，可能会出现基变量个、用最小元素法时，可能会出现基变量个数还差两个以上但只剩下一行或一列的情数还差两个以上但只剩下一行或一列的情况，此时不能将剩下行或列按空格划掉，况，此时不能将剩下行或列按空格划掉，

10、应在剩下的空格中标上应在剩下的空格中标上0。（退化的基本可。（退化的基本可行解）行解）2.确定初始基本可行解确定初始基本可行解注意：注意：B1B2B3B4产量产量A13113108A219283A3741059销量销量36563530632.确定初始基本可行解确定初始基本可行解v）伏格尔法）伏格尔法v 伏格尔法的基本思想：如果某一地的产品不能按最小运费伏格尔法的基本思想：如果某一地的产品不能按最小运费就近供应，就考虑次小运费，两者间就有一个差额。差额就近供应，就考虑次小运费，两者间就有一个差额。差额越大，说明越大，说明费用增量费用增量越大。因而对差额最大处，优先采用越大。因而对差额最大处，优先

11、采用最小运费调运。最小运费调运。v 步骤：步骤：v 分别计算表中各行和各列中分别计算表中各行和各列中最小运费和次小运费的差最小运费和次小运费的差 额额，并填入表中的最右列和最下行。，并填入表中的最右列和最下行。v 从行和列的差额中选出最大者，选择其所在行或列中的从行和列的差额中选出最大者，选择其所在行或列中的最小元素，按类似于最小元素法优先供应，划去相应的行最小元素，按类似于最小元素法优先供应，划去相应的行或列。或列。v 对表中未划去的元素，重复对表中未划去的元素，重复 ，直到所有的行和列，直到所有的行和列都划完为止。都划完为止。2.确定初始基本可行解确定初始基本可行解B1B2B3B4两最小元

12、素之差两最小元素之差A1311310A21928A374105两最小元素之差两最小元素之差2.确定初始基本可行解确定初始基本可行解0112513B1B2B3B4两最小元素之差两最小元素之差A13113100A219281A3741052两最小元素之两最小元素之差差2132.确定初始基本可行解确定初始基本可行解B1B2B3B4两最小元素之差两最小元素之差A13113100A219281A374105两最小元素之两最小元素之差差2122.确定初始基本可行解确定初始基本可行解B1B2B3B4两最小元素之差两最小元素之差A13113107A219286A374105两最小元素之两最小元素之差差122.

13、确定初始基本可行解确定初始基本可行解B1B2B3B4两最小元素之差两最小元素之差A1311310A21928A374105两最小元素之两最小元素之差差22.确定初始基本可行解确定初始基本可行解B1B2B3B4两最小元素之差两最小元素之差A1311310A21928A374105两最小元素之两最小元素之差差2.确定初始基本可行解确定初始基本可行解B1B2B3B4产量产量A1527A2314A3639销量销量36562.确定初始基本可行解确定初始基本可行解Z=53+210+31+18+64+35=853.最优性检验最优性检验v检验数的意义：非基变量增加一个单位，检验数的意义：非基变量增加一个单位，

14、使目标函数值增加的数量。使目标函数值增加的数量。v运输问题中目标函数值要求最小化，因此，运输问题中目标函数值要求最小化，因此，当所有的检验数都当所有的检验数都大于或等于零大于或等于零时该调运时该调运方案就是最优方案；否则不是。方案就是最优方案；否则不是。v下面介绍两种计算检验数的方法：下面介绍两种计算检验数的方法：v1 1、闭回路法、闭回路法v闭回路：在已给出基本解的运输表上，从一个非基闭回路：在已给出基本解的运输表上，从一个非基变量出发，沿水平或竖直方向前进，只有碰到基变变量出发，沿水平或竖直方向前进，只有碰到基变量，才能向右或向左转量，才能向右或向左转9090o o ( (当然也可以不改变

15、方向）当然也可以不改变方向）继续前进。继续前进。v这样继续下去，总能回到出发的那个非基变量，由这样继续下去，总能回到出发的那个非基变量，由此路线形成的封闭曲线，叫闭回路。此路线形成的封闭曲线，叫闭回路。3.最优性检验最优性检验3.最优性检验最优性检验B1B2B3B4产量产量A13113 410 37A21 392 184A374 6105 39销量销量3656v若让若让x111，则总运费变化：，则总运费变化：31+231 。 11 =1v若让若让x311，则总运费变化：，则总运费变化：75+103+2-110 。 31 =103.最优性检验最优性检验63 24 = -13B49 33 = 12

16、6 31 = 10A3563销量销量41 22= 13A274 12 = 2A1产量产量B3B2B1 11 = 1v最优标准：所有检验数最优标准：所有检验数 ij 0v2、位势法、位势法v 闭回路法的缺点：当变量个数较多时，寻找闭回路以及计算闭回路法的缺点：当变量个数较多时，寻找闭回路以及计算两方面都容易出错。两方面都容易出错。位势法检验步骤：位势法检验步骤：v 1）设产地）设产地Ai对应的位势量为对应的位势量为ui ，销地，销地Bj对应的位势量为对应的位势量为vj；v 2）由）由 ij=Cij-（Ui+Vj）,利用对基变量而言有利用对基变量而言有 ij=0，计算位计算位势势Ui ， Vj ，

17、即即Cij-（Ui+Vj） = 0，令，令U1=0；v 3）再由）再由 ij=Cij-（Ui+Vj）计算非基变量的检验数计算非基变量的检验数 ij3.最优性检验最优性检验B1B2B3B4uiA13 11 3 410 3A21 39 2 18A37 4 6105 3vju1 u2u3v1v2v3v40103-1-5293.最优性检验最优性检验B1B2B3B4uiA13 11 3 410 30A21 39 2 18-1A37 4 6105 3-5vj29310 ij=Cij-（Ui+Vj） 11=C11-（U1+V1）=3-(0+2)=1 12=C12-（U1+V2）=11-(0+9)=2(1)(

18、2)3.最优性检验最优性检验B1B2B3B4产量产量A1437A2314A3639销量销量36563.最优性检验最优性检验 33=12 11=1 22=1 31=10 24= -1 12=2当存在非基变量的检验数当存在非基变量的检验数 ij 0，说明现行方案为最，说明现行方案为最优方案，否则目标成本还可以进一步减小。优方案，否则目标成本还可以进一步减小。3.最优性检验最优性检验v1、闭回路法计算式：、闭回路法计算式：v ij = (闭回路上的奇数顶点运价之和闭回路上的奇数顶点运价之和) - (闭回路上闭回路上的偶数顶点运价之和的偶数顶点运价之和)v2、位势法计算式：、位势法计算式：v ij =

19、 cij - ui vj 当存在非基变量的检验数当存在非基变量的检验数 ij 0，说明现行方案为，说明现行方案为最优方案，否则目标成本还可以进一步减小。最优方案，否则目标成本还可以进一步减小。4.方案调整方案调整闭回路调整法步骤：闭回路调整法步骤：1、入基变量的确定：选负检验数中最小者、入基变量的确定：选负检验数中最小者 rk，那，那么么 xrk 作为进基变量；（使总运费尽快减少）作为进基变量；（使总运费尽快减少）2、出基变量的确定：在进基变量、出基变量的确定：在进基变量xrk 的闭回路上，的闭回路上，选取偶数顶点上调运量最小的值，将其对应的运量选取偶数顶点上调运量最小的值，将其对应的运量作为

20、出基变量。（刚好有一个基变量出基，其它基作为出基变量。（刚好有一个基变量出基，其它基变量都为正）变量都为正）4.方案调整方案调整 即求即求 =Minxij 闭回路上的偶数顶点的闭回路上的偶数顶点的xij= xpq。那么那么确定确定xpq为出基变量，为出基变量， 为调整量；为调整量； 3、换基调整：对闭回路的奇数顶点运量调整为：、换基调整：对闭回路的奇数顶点运量调整为：xij+ ，对各偶数顶点运量调整为：，对各偶数顶点运量调整为：xij- ，特别，特别 xpq- =0，xpq变为非基变量。变为非基变量。 重复以上步骤，直到所有检验数均非负，即得到最优重复以上步骤，直到所有检验数均非负，即得到最优

21、解。解。4.方案调整方案调整B1B2B3B4产量产量A13 （1）11 （2）3 410 37A21 39 （1）2 18 （-1）4A37 （10）4 610 （12）5 39销量销量3656最小检验数最小检验数原则，确定原则，确定进基变量进基变量最小偶点原则，最小偶点原则，确定出基变量和确定出基变量和调整量调整量+1-1+1-1 13 , 1minmin14,23 xx四、方案调整B1B2B3B4产量产量aiA13 11 3 5 10 2 7A21 39 2 8 14A37 4 610 5 39销量销量bj3656v得到新的基变量：得到新的基变量：x13 = 5, x14 = 2, x21

22、 = 3, x24 = 1, x32 = 6, x34 = 3。重新计算检验数。重新计算检验数。（1）（2）（2）（1）（9）（12）四、方案调整v经过一次基变换，所有经过一次基变换，所有 ij 0，已得到最优解：，已得到最优解： x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3，其它为，其它为0。v最优值：最优值：vf* =35+102+13+81+46+53 = 85表上作业法计算中的相关问题表上作业法计算中的相关问题v1.无穷多最优解v 当最优方案中存在某空格（非基变量）检验数为当最优方案中存在某空格（非基变量）检验数为0,时，则时，则该运输问题一定有多重最优解。该运输问题一定有多重最优解。v2.退化解v 当运输问题的最优表中有数格（基变量）的运量为当运输问题的最优表中有数格（基变量）的运量为0，则，则出现退化。出现退化。v 1）确定基本可行解中，出现同时需要划去一行和一列的）确定基本可行解中，出现同时需要划去一行和一列的情况，则需要