表上作业法实用教案

1、精品课程运筹学n表上作业法表上作业法: 建立在运输费用矩阵的求解运输问题的方法。建立在运输费用矩阵的求解运输问题的方法。n表上作业法求解运输问题的思想和单纯形法完全类似：表上作业法求解运输问题的思想和单纯形法完全类似：n 确定一个初始基本可行解确定一个初始基本可行解 根据根据(gnj)最优性判别准则来检查这个基本可行解是不是最优的？最优性判别准则来检查这个基本可行解是不是最优的？n 如果是，则计算结束；如果是，则计算结束；n 如果不是，则进行换基。如果不是，则进行换基。n 直至求出最优解为止。直至求出最优解为止。第1页/共42页第一页，共43页。精品课程运筹学 一、初始基本可行一、初始基本可行

2、(kxng)解的确定解的确定 根据上面的讨论，要求得运输问题的初根据上面的讨论，要求得运输问题的初始基本可行始基本可行(kxng)解，必须保证找到解，必须保证找到 m + n 1 个不构成闭回路的基变量。个不构成闭回路的基变量。 一般的方法步骤如下：一般的方法步骤如下： 第2页/共42页第二页，共43页。精品课程运筹学 (1)在运输问题求解作业数据表中任选一个单元格在运输问题求解作业数据表中任选一个单元格 xij ( Ai 行行 Bj 列交叉位置列交叉位置(wi zhi)上的格上的格),令令 xij = min ai , bj 即从即从 Ai 向向 Bj 运最大量运最大量(使行或列在允许的范围

3、使行或列在允许的范围内尽量饱和，即使一个约束方程得以满足内尽量饱和，即使一个约束方程得以满足),填入填入 xij 的相应位置的相应位置(wi zhi)； 第3页/共42页第三页，共43页。精品课程运筹学(2)(2)从从 ai ai 和和 bj bj 中分别减去中分别减去 xij xij 的值，修正的值，修正为新的为新的ai ai 和和 bj bj ，即调整，即调整 Ai Ai 的拥有量及的拥有量及 Bj Bj 的需求量；的需求量；(3)(3)若若 ai = 0 ai = 0，则划去对应的行（已经把拥有，则划去对应的行（已经把拥有的量全部的量全部(qunb)(qunb)运走），若运走），若 bj

4、 = 0 bj = 0 则划则划去对应的列（已经把需要的量全部去对应的列（已经把需要的量全部(qunb)(qunb)运来），且每次只划去一行或一列（即每次运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）；要去掉且只去掉一个约束）；第4页/共42页第四页，共43页。精品课程运筹学(4)(4)当最终的运输量选定时，其所在行、列当最终的运输量选定时，其所在行、列同时满足，此时要同时划去一行和一列同时满足，此时要同时划去一行和一列(y li)(y li)。这样，运输平衡表中所有的行。这样，运输平衡表中所有的行与列均被划去，则得到了一个初始基本可与列均被划去，则得到了一个初始基本可行解。行

5、解。 否则在剩下的运输平衡表中选下一个变否则在剩下的运输平衡表中选下一个变量，返回量，返回(1)(1)。第5页/共42页第五页，共43页。精品课程运筹学上述计算过程上述计算过程(guchng)可用流程图描述如下可用流程图描述如下取未划去的单元格xij ,令xij = min ai , bj ai = ai - xijbj = bj - xijai = 0?划去第i行划去第j列是否 bj = 0否所有行列是否均被划去是找到初始基本可行解求运输问题的初始基本可行解过程注：为了方便，这里总记剩余的产量和销量为ai, bj第6页/共42页第六页，共43页。精品课程运筹学 按照上述方法所产生的一组变量的

6、按照上述方法所产生的一组变量的取值将满足下面条件：取值将满足下面条件： (1)所得的变量均为非负，且变量总所得的变量均为非负，且变量总数恰好为数恰好为 m + n 1 个；个； (2)所有的约束条件均得到所有的约束条件均得到(d do)满足；满足； (3)所得的变量不构成闭回路。所得的变量不构成闭回路。第7页/共42页第七页，共43页。精品课程运筹学 因此，根据定理及其推论，所得的解一因此，根据定理及其推论，所得的解一定是运输问题的基本可行解。定是运输问题的基本可行解。 在上面的方法中，在上面的方法中，xij xij 的选取方法并没的选取方法并没有给予限制有给予限制(xinzh)(xinzh)

7、，若采取不同的规则，若采取不同的规则来选取来选取 xij xij ，则得到不同的方法，较常用，则得到不同的方法，较常用的方法有西北角法和最小元素法。下面分的方法有西北角法和最小元素法。下面分别举例予以说明。别举例予以说明。第8页/共42页第八页，共43页。精品课程运筹学 1 1、初始基本可行解的确定、初始基本可行解的确定 （1 1）西北角法：从西北角（左上角）西北角法：从西北角（左上角）格开始，在格内的右下角标上允许格开始，在格内的右下角标上允许(ynx)(ynx)取得的最大数。然后按行（列）标下一格取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满的数。若某行（列）的产

8、量（销量）已满足，则把该行（列）的其他格划去。如此足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。进行下去，直至得到一个基本可行解。第9页/共42页第九页，共43页。精品课程运筹学 （2 2）最小元素法：从运价最小的格开始，）最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数。在格内的右下角标上允许取得的最大数。然后然后(rnhu)(rnhu)按运价从小到大顺序填数。按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行

9、解。去，直至得到一个基本可行解。第10页/共42页第十页，共43页。精品课程运筹学 注注: :应用西北角法和最小元素法，每次应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和一个数后行、列同时饱和(boh)(boh)时，也应时，也应任意划去一行（列），在保留的列（行）中任意划去一行（列），在保留的列（行）中没被划去的格内标一个没被划去的格内标一个0 0。第11页/共42页第十一页，共43页。精品课程运筹学例：某食品公司下属的 A1、A2、A3

10、 ，3 个厂生产方便食品，要运输到 B1、B2、B3、B4 ，4 个销售点，数据如下： B1 B2 B3 B4 产量 ai A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量 bj 3 6 5 6 20（产销平衡） 求最优运输方案。 第12页/共42页第十二页，共43页。精品课程运筹学1、确 定 初 始 基 本 可 行 解： （1）西 北 角 法 B1 B2 B3 B4 产量 ai A1 3 3 11 4 3 10 7 A2 1 9 2 2 2 8 4 A3 7 4 10 3 5 6 9 销量 bj 3 6 5 6 20 第13页/共42页第十三页，共43

11、页。精品课程运筹学（2）最小元素法 B1 B2 B3 B4 产量 ai A1 3 11 3 4 10 3 7 A2 1 3 9 2 1 8 4 A3 7 4 6 10 5 3 9 销量 bj 3 6 5 6 20 第14页/共42页第十四页，共43页。精品课程运筹学 最优性检验就是检查所得到的方案是不是最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标要求极小相同，即计算检验数。由于目标要求极小(j (j xio)xio)，因此，当所有的检验数都大于或等于，因此，当所有的检验数都大于或等于零时该调运方

12、案就是最优方案；否则就不是最零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的优，需要进行调整。下面介绍两种求检验数的方法。方法。 二、基本(jbn)可行解的最优性检验 第15页/共42页第十五页，共43页。精品课程运筹学 1、闭回路法、闭回路法 为了方便，我们以上表给出的初始基本可行解为了方便，我们以上表给出的初始基本可行解方案为例，考察初始方案的任意一个非基变量方案为例，考察初始方案的任意一个非基变量(binling)，比如，比如 x24。根据初始方案，产地。根据初始方案，产地 A2 的产品是不运往销地的产品是不运往销地 B4 的。如果现在改变初始的。如果现在

13、改变初始方案，把方案，把 A2 的产品运送的产品运送1 个单位给个单位给 B4 ，那么为，那么为了保持产销平衡，就必须使了保持产销平衡，就必须使 x14 或或 x34 减少减少 1 个个单位；而如果单位；而如果 x14 减少减少 1 个单位，第个单位，第 1 行的运输行的运输量就必须增加量就必须增加 1 个单位，例如个单位，例如 x13 增加增加 1 个单位，个单位，那么为了保持产销平衡，就必须使那么为了保持产销平衡，就必须使 x23 减少减少 1 个个单位。单位。第16页/共42页第十六页，共43页。精品课程运筹学 这个过程就是寻找一个以非基变量这个过程就是寻找一个以非基变量 x24 为起始

14、为起始顶点顶点(dngdin)的闭回路的闭回路 x24 ，x14 ，x13 ，x23 ，这个闭回路的其他顶点，这个闭回路的其他顶点(dngdin)均为基变量均为基变量(对应着填上数字的格对应着填上数字的格)。容易计算出。容易计算出上述调整使总的运输费用发生的变化为上述调整使总的运输费用发生的变化为 8 10 + 3 2 -1 ，即总的运费减少，即总的运费减少 1 个单位，这就个单位，这就说明原始方案不是最优方案，可以进行调整以说明原始方案不是最优方案，可以进行调整以得到更好的方案。得到更好的方案。第17页/共42页第十七页，共43页。精品课程运筹学 可以证明，如果对闭回路的方向不加区别（即只可

15、以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进要起点及其他所有顶点完全相同，而不区别行进(xngjn)方向），那么以每一个非基量为起始顶点方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。变量可以找到而且只能找到唯一的一个闭回路。 下表中用虚线画出以非基变量下表中用虚线画出以非基变量 x22 为起始顶点的为起始顶点的闭回路。闭回路。第18页/共42页第十八页，共43页。精品课程运筹学销地产地B1B2B3B4产量3 11 3 410 371 39 2

16、 18 47 4 610 5 39销量365620(产销平衡)A1A2A3第19页/共42页第十九页，共43页。精品课程运筹学 可以计算出以非基变量可以计算出以非基变量 x22 为起始顶点的闭回为起始顶点的闭回路调整使总的运输费用发生的变化为路调整使总的运输费用发生的变化为 9 2 + 3 10 + 5 4 1 即总的运费增加即总的运费增加 1 个单位，这就说明个单位，这就说明(shumng)这个调整不能改善目标值。这个调整不能改善目标值。 从上面的讨论可以看出，当某个非基变量增加从上面的讨论可以看出，当某个非基变量增加一个单位时，有若干个基变量的取值受其影响。一个单位时，有若干个基变量的取值

17、受其影响。第20页/共42页第二十页，共43页。精品课程运筹学 这样，利用单位产品变化（运输的单位费用）这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综合影响，其作用可计算出它们对目标函数的综合影响，其作用与线性规划单纯形方法中的检验数完全相同。与线性规划单纯形方法中的检验数完全相同。故也称这个综合影响为该非基变量对应的检验故也称这个综合影响为该非基变量对应的检验数。上面计算的两个非基变量的检验数为数。上面计算的两个非基变量的检验数为 24 = -1，22 = 1。闭回路。闭回路(hul)方法原理就是通方法原理就是通过寻找闭回路过寻找闭回路(hul)来找到非基变量的检验数。来

18、找到非基变量的检验数。 第21页/共42页第二十一页，共43页。精品课程运筹学 如果规定作为如果规定作为(zuwi)起始顶点的非基变量起始顶点的非基变量为第为第 1 个顶点，闭回路的其他顶点依次为第个顶点，闭回路的其他顶点依次为第 2 个顶点、第个顶点、第 3 个顶点个顶点，那么就有，那么就有 ij = (闭回路上的奇数次顶点单位运费之闭回路上的奇数次顶点单位运费之和和) - (闭回路上的偶数次顶点单位运费之和闭回路上的偶数次顶点单位运费之和) 其中其中 ij 为非基变量的下角指标。为非基变量的下角指标。第22页/共42页第二十二页，共43页。精品课程运筹学 按上述作法，可计算出表中的所有非基

19、变量的检验按上述作法，可计算出表中的所有非基变量的检验数，把它们填入相应数，把它们填入相应(xingyng)(xingyng)位置的方括号内，如位置的方括号内，如下图所示。下图所示。 销地产地B1B2B3B4产量A13 111 23 410 37A21 39 12 18-14A37 104 610125 39销量365620(产销平衡)初始基本可行解及检验数第23页/共42页第二十三页，共43页。精品课程运筹学 显然，当所有非基变量的检验数均大于显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，或等于零时，现行的调运方案就是最优方案，因为此时因为此时(c sh)(c s

20、h)对现行方案作任何调整都对现行方案作任何调整都将导致总的运输费用增加。将导致总的运输费用增加。 闭回路法的主要缺点是：当变量个数较闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生多时，寻找闭回路以及计算两方面都会产生困难。困难。第24页/共42页第二十四页，共43页。精品课程运筹学 当非基变量的检验数出现负值时，当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目调整，即找到一个新的基本可行解使目标函数值下降，这一过程标函

21、数值下降，这一过程(guchng)(guchng)通通常 称 为 换 基常 称 为 换 基 ( ( 或 主 元 变 换或 主 元 变 换 ) ) 过 程过 程(guchng)(guchng)。 三、求新的基本(jbn)可行解第25页/共42页第二十五页，共43页。精品课程运筹学 （1 1）选负检验数中最小者）选负检验数中最小者 rkrk，那么，那么 xrk xrk 为主元，作为进基变量（上图中为主元，作为进基变量（上图中 x24 x24 ）; ; （2 2）以）以 xrk xrk 为起点找一条闭回路，除为起点找一条闭回路，除 xrk xrk 外其余外其余(qy)(qy)顶点必须为基变量格（上页

22、图中顶点必须为基变量格（上页图中的回路）的回路）; ; 在运输(ynsh)问题的表上作业法中，换基的过程是如下进行：第26页/共42页第二十六页，共43页。精品课程运筹学 （3）为闭回路的每一个顶点标号，）为闭回路的每一个顶点标号， xrk 为为 1，沿一个方向（顺时针或逆时针）依次给，沿一个方向（顺时针或逆时针）依次给各顶点标号；各顶点标号； （4）求）求 =minxijxij对应闭回路上的对应闭回路上的偶数标号格偶数标号格= xpq 那么那么(n me)确定确定 xpq为为出基变量，出基变量，为调整量；为调整量；第27页/共42页第二十七页，共43页。精品课程运筹学 （5 5）对闭回路的各

23、奇标号顶点调整为：）对闭回路的各奇标号顶点调整为：xij + xij + ，对各偶标号顶点，对各偶标号顶点 调整为：调整为：xij - xij - ，特别，特别 xpq - xpq - = 0 = 0， xpq xpq变为非基变变为非基变量。量。 重复重复(2)(2)、(3)(3)步，直到所有步，直到所有(suyu)(suyu)检检验数均非负，得到最优解。验数均非负，得到最优解。第28页/共42页第二十八页，共43页。精品课程运筹学 ij 0，得到(d do)最优解 x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3, 其余 xij = 0

24、 ; 最优值： f* = 35+102+13+81+46+53 = 85第29页/共42页第二十九页，共43页。精品课程运筹学 四、产销不平衡问题的处理 在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般(ybn)运输问题模型 m nmin f = cij xij （1） i=1 j=1 n . xij si i = 1,2,m （2） j=1 m xij (=,)dj j = 1,2,n (3） i=1 xij 0 (i=1,2,m;j=1,2,n) （4） 第30页/共42页第三十页，共43页。精品课程运筹学 我们可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题，

25、下面分别来讨论。 1.产量大于销量的情况 m n 考虑(kol) si dj 的运输问题，得到的数学模 i=1 j=1型为第31页/共42页第三十一页，共43页。精品课程运筹学 m n min f = cij xij i=1 j=1 n s.t. xij si i = 1,2,m j=1 m xij =dj j = 1,2,n i=1 xij0(i=1,2,m;j=1,2,n) 第32页/共42页第三十二页，共43页。精品课程运筹学 只要在模型中的产量限制约束（前m个不等式约束）中引入m个松弛变量(binling)xi,n+1 i= 1, 2, , m 即可，变为： n xij+xin+1=s

26、i i=1,2,m j=1然后，需设一个销地Bn+1,它的销量为： m n bn+1= si- dj i=1 j=1 第33页/共42页第三十三页，共43页。精品课程运筹学 这里(zhl)，松弛变量 xi n+1 可以视为从产地 A i 运往销地 Bn+1 的运输量，由于实际并不运送，它们的运费为 ci n+1=0 i= 1,2,m。于是，这个运输问题就转化成了一个产销平衡的问题。第34页/共42页第三十四页，共43页。精品课程运筹学 例:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运(dioy

27、n)可使总运输费用最小？ B1 B2 B3 产产量量 A1 6 4 6 300 A2 6 5 5 300 销销量量 150 150 200 第35页/共42页第三十五页，共43页。精品课程运筹学 解：增加一个虚设解：增加一个虚设(xsh)(xsh)的销地运输费用为的销地运输费用为0 0 B1 B2 B3 B4 产量 A1 6 4 6 0 300 A2 6 5 5 0 300 销量 150 150 200 100 第36页/共42页第三十六页，共43页。精品课程运筹学 2.销量大于产量的情况 m n 考虑(kol) sidj 的运输问题，得到的数学模型为 i=1 j=1 m n Min f = cij xij i=1 j=1 n . xij =si i = 1,2,m j=1 m xij dj j = 1,2,n i=1 xij0(i=1,2,m;j=1,2,n) 第37页/共42页第三十七页，共43页。精品课程运筹学 只要在模型(mxng)中的产量限制约束（后n个不等式约束）中引入n个松弛变量xm+1j j = 1,2,n即可，变为： m x