表上作业法（经典实用）

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

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

3、个约束方程得以满范围内尽量饱和，即使一个约束方程得以满 足足),填入填入 xij 的相应位置；的相应位置； 精品课程运筹学 表上作业法 (2)(2)从从 ai 和和 bj 中分别减去中分别减去 xij 的值，修正的值，修正 为新的为新的ai 和和 bj ， ，即调整 即调整 Ai 的拥有量及的拥有量及 Bj 的需求量；的需求量； (3)(3)若若 ai = 0，则划去对应的行（已经把拥有，则划去对应的行（已经把拥有 的量全部运走），若的量全部运走），若 bj = 0 则划去对应的则划去对应的 列（已经把需要的量全部运来），且每次列（已经把需要的量全部运来），且每次 只划去一行或一列（即每次要去

4、掉且只去只划去一行或一列（即每次要去掉且只去 掉一个约束）；掉一个约束）； 精品课程运筹学 表上作业法 (4)(4)当最终的运输量选定时，其所在行、列当最终的运输量选定时，其所在行、列 同时满足，此时要同时划去一行和一列。同时满足，此时要同时划去一行和一列。 这样，运输平衡表中所有的行与列均被划这样，运输平衡表中所有的行与列均被划 去，则得到了一个初始基本可行解。去，则得到了一个初始基本可行解。 否则在剩下的运输平衡表中选下一个变否则在剩下的运输平衡表中选下一个变 量，返回量，返回(1)(1)。 精品课程运筹学 表上作业法 上述计算过程可用流程图描述如下上述计算过程可用流程图描述如下 取未划去

5、的单元格取未划去的单元格xij ,令令 xij = min ai , bj ai = ai - xij bj = bj - xij ai = 0?划去第划去第i行行 划去第划去第j列列 是是 否否 bj = 0 否否 所有行列是所有行列是 否均被划去否均被划去 是是 找到初始基找到初始基 本可行解本可行解 求运输问题的初始基本可行解过程求运输问题的初始基本可行解过程 注：为了方便，这注：为了方便，这 里总记剩余的产量里总记剩余的产量 和销量为和销量为ai, bj 精品课程运筹学 表上作业法 按照上述方法所产生的一组变量的按照上述方法所产生的一组变量的 取值将满足下面条件：取值将满足下面条件：

6、(1)所得的变量均为非负，且变量总所得的变量均为非负，且变量总 数恰好为数恰好为 m + n 1 个；个； (2)所有的约束条件均得到满足；所有的约束条件均得到满足； (3)所得的变量不构成闭回路。所得的变量不构成闭回路。 精品课程运筹学 表上作业法 因此，根据定理及其推论，所得的因此，根据定理及其推论，所得的 解一定是运输问题的基本可行解。解一定是运输问题的基本可行解。 在上面的方法中，在上面的方法中，xij 的选取方法并的选取方法并 没有给予限制，若采取不同的规则来选没有给予限制，若采取不同的规则来选 取取 xij ，则得到不同的方法，较常用的，则得到不同的方法，较常用的 方法有西北角法和

7、最小元素法。下面分方法有西北角法和最小元素法。下面分 别举例予以说明。别举例予以说明。 精品课程运筹学 表上作业法 1 1、初始基本可行解的确定、初始基本可行解的确定 （1 1）西北角法：西北角法：从西北角（左上角）从西北角（左上角） 格开始，在格内的右下角标上允许取得的格开始，在格内的右下角标上允许取得的 最大数。然后按行（列）标下一格的数。最大数。然后按行（列）标下一格的数。 若某行（列）的产量（销量）已满足，则若某行（列）的产量（销量）已满足，则 把该行（列）的其他格划去。如此进行下把该行（列）的其他格划去。如此进行下 去，直至得到一个基本可行解去，直至得到一个基本可行解。 精品课程运筹

8、学 表上作业法 （2 2）最小元素法：最小元素法：从运价最小的格开从运价最小的格开 始，在格内的右下角标上允许取得的最大始，在格内的右下角标上允许取得的最大 数。然后按运价从小到大顺序填数。若某数。然后按运价从小到大顺序填数。若某 行（列）的产量（销量）已满足，则把该行（列）的产量（销量）已满足，则把该 行（列）的其他格划去。如此进行下去，行（列）的其他格划去。如此进行下去， 直至得到一个基本可行解。直至得到一个基本可行解。 精品课程运筹学 表上作业法 注注: :应用西北角法和最小元素法，每应用西北角法和最小元素法，每 次填完数，都只划去一行或一列，只有次填完数，都只划去一行或一列，只有 最后

9、一个元例外（同时划去一行和一最后一个元例外（同时划去一行和一 列）。当填上一个数后行、列同时饱和列）。当填上一个数后行、列同时饱和 时，也应任意划去一行（列），在保留时，也应任意划去一行（列），在保留 的列（行）中没被划去的格内标一个的列（行）中没被划去的格内标一个0 0。 精品课程运筹学 表上作业法 例：某食品公司下属的 A1、A2、A3 ，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（产销平衡）

10、求最优运输方案。 精品课程运筹学 表上作业法 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 精品课程运筹学 表上作业法 （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 精品课程运筹学 表上作业法 最优性检验就是检查所得到的方案是最优性检验就是检查所得到的方

11、案是 不是最优方案。检查的方法与单纯形方法不是最优方案。检查的方法与单纯形方法 中的原理相同，即计算检验数。由于目标中的原理相同，即计算检验数。由于目标 要求极小，因此，当所有的检验数都大于要求极小，因此，当所有的检验数都大于 或等于零时该调运方案就是最优方案；否或等于零时该调运方案就是最优方案；否 则就不是最优，需要进行调整。下面介绍则就不是最优，需要进行调整。下面介绍 两种求检验数的方法。两种求检验数的方法。 二、基本可行解的最优性检验二、基本可行解的最优性检验 精品课程运筹学 表上作业法 1、闭回路法、闭回路法 为了方便，我们以上表给出的初始基本可行解为了方便，我们以上表给出的初始基本可

12、行解 方案为例，考察初始方案的任意一个非基变量，方案为例，考察初始方案的任意一个非基变量， 比如比如 x24。根据初始方案，产地。根据初始方案，产地 A2 的产品是不的产品是不 运往销地运往销地 B4 的。如果现在改变初始方案，把的。如果现在改变初始方案，把 A2 的产品运送的产品运送1 个单位给个单位给 B4 ，那么为了保持产销，那么为了保持产销 平衡，就必须使平衡，就必须使 x14 或或 x34 减少减少 1 个单位；而如个单位；而如 果果 x14 减少减少 1 个单位，第个单位，第 1 行的运输量就必须行的运输量就必须 增加增加 1 个单位，例如个单位，例如 x13 增加增加 1 个单位

13、，那么个单位，那么 为了保持产销平衡，就必须使为了保持产销平衡，就必须使 x23 减少减少 1 个单个单 位。位。 精品课程运筹学 表上作业法 这个过程就是寻找一个以非基变量这个过程就是寻找一个以非基变量 x24 为起为起 始顶点的闭回路始顶点的闭回路 x24 ，x14 ，x13 ，x23 ， 这个闭回路的其他顶点均为基变量这个闭回路的其他顶点均为基变量(对应着填对应着填 上数字的格上数字的格)。容易计算出上述调整使总的运。容易计算出上述调整使总的运 输费用发生的变化为输费用发生的变化为 8 10 + 3 2 -1 ， 即总的运费减少即总的运费减少 1 个单位，这就说明原始方个单位，这就说明原

14、始方 案不是最优方案，可以进行调整以得到更好案不是最优方案，可以进行调整以得到更好 的方案。的方案。 精品课程运筹学 表上作业法 可以证明，如果对闭回路的方向不加区别可以证明，如果对闭回路的方向不加区别 （即只要起点及其他所有顶点完全相同，而（即只要起点及其他所有顶点完全相同，而 不区别行进方向），那么以每一个非基量为不区别行进方向），那么以每一个非基量为 起始顶点的闭回路就存在而且唯一。因此，起始顶点的闭回路就存在而且唯一。因此， 对每一个非基变量可以找到而且只能找到唯对每一个非基变量可以找到而且只能找到唯 一的一个闭回路。一的一个闭回路。 下表中用虚线画出以非基变量下表中用虚线画出以非基变

15、量 x22 为起始顶为起始顶 点的闭回路。点的闭回路。 精品课程运筹学 表上作业法 销地 产地 B1B2B3B4产量 3 11 3 4 10 3 7 1 3 9 2 1 8 4 7 4 6 10 5 3 9 销量3656 20(产销平衡) A1 A2 A3 精品课程运筹学 表上作业法 可以计算出以非基变量可以计算出以非基变量 x22 为起始顶点的闭为起始顶点的闭 回路调整使总的运输费用发生的变化为回路调整使总的运输费用发生的变化为 9 2 + 3 10 + 5 4 1 即总的运费增加即总的运费增加 1 个单位，这就说明这个调个单位，这就说明这个调 整不能改善目标值。整不能改善目标值。 从上面的

16、讨论可以看出，当某个非基变量从上面的讨论可以看出，当某个非基变量 增加一个单位时，有若干个基变量的取值受增加一个单位时，有若干个基变量的取值受 其影响。其影响。 精品课程运筹学 表上作业法 这样，利用单位产品变化（运输的单位费用）这样，利用单位产品变化（运输的单位费用） 可计算出它们对目标函数的综合影响，其作用可计算出它们对目标函数的综合影响，其作用 与线性规划单纯形方法中的检验数完全相同。与线性规划单纯形方法中的检验数完全相同。 故也称这个综合影响为该非基变量对应的检验故也称这个综合影响为该非基变量对应的检验 数。上面计算的两个非基变量的检验数为数。上面计算的两个非基变量的检验数为 24 =

17、 -1， 22 = 1。闭回路方法原理就是通过寻找。闭回路方法原理就是通过寻找 闭回路来找到非基变量的检验数。闭回路来找到非基变量的检验数。 精品课程运筹学 表上作业法 如果规定作为起始顶点的非基变量为第如果规定作为起始顶点的非基变量为第 1 个个 顶点，闭回路的其他顶点依次为第顶点，闭回路的其他顶点依次为第 2 个顶点、个顶点、 第第 3 个顶点个顶点，那么就有，那么就有 ij = (闭回路上的奇数次顶点单位运费之和闭回路上的奇数次顶点单位运费之和) - (闭回路上的偶数次顶点单位运费之和闭回路上的偶数次顶点单位运费之和) 其中其中 ij 为非基变量的下角指标。为非基变量的下角指标。 精品课

18、程运筹学 表上作业法 按上述作法，可计算出表中的所有非基变量的检按上述作法，可计算出表中的所有非基变量的检 验数，把它们填入相应位置的方括号内，如下图所示。验数，把它们填入相应位置的方括号内，如下图所示。 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量产量 A A1 13 3 1 1 1111 2 2 3 3 4 4 1010 3 3 7 7 A A2 21 1 3 3 9 9 1 1 2 2 1 1 8 8 -1-1 4 4 A A3 37 7 10 10 4 4 6 6 1010 1212 5 5 3 3 9 9 销量销量3 36 65 56 6 20(20(产销

19、平衡产销平衡) ) 初始基本可行解及检验数初始基本可行解及检验数 精品课程运筹学 表上作业法 显然，当所有非基变量的检验数均大于显然，当所有非基变量的检验数均大于 或等于零时，现行的调运方案就是最优方案，或等于零时，现行的调运方案就是最优方案， 因为此时对现行方案作任何调整都将导致总因为此时对现行方案作任何调整都将导致总 的运输费用增加。的运输费用增加。 闭回路法的主要缺点是：当变量个数较闭回路法的主要缺点是：当变量个数较 多时，寻找闭回路以及计算两方面都会产生多时，寻找闭回路以及计算两方面都会产生 困难。困难。 精品课程运筹学 表上作业法 当非基变量的检验数出现负值时，当非基变量的检验数出现

20、负值时， 则表明当前的基本可行解不是最优解。则表明当前的基本可行解不是最优解。 在这种情况下，应该对基本可行解进行在这种情况下，应该对基本可行解进行 调整，即找到一个新的基本可行解使目调整，即找到一个新的基本可行解使目 标函数值下降，这一过程通常称为换基标函数值下降，这一过程通常称为换基 ( (或主元变换或主元变换) )过程。过程。 三、求新的基本可行解三、求新的基本可行解 精品课程运筹学 表上作业法 （1 1）选负检验数中最小者）选负检验数中最小者 rk，那么，那么 xrk 为主元，作为进基变量（上图中为主元，作为进基变量（上图中 x24 ）; （2 2）以）以 xrk 为起点找一条闭回路，

21、除为起点找一条闭回路，除 xrk 外其余外其余顶点必须为基变量格（上页图中顶点必须为基变量格（上页图中 的回路）的回路）; ; 在运输问题的表上作业法中，换基的过在运输问题的表上作业法中，换基的过 程是如下进行：程是如下进行： 精品课程运筹学 表上作业法 （3）为闭回路的每一个顶点标号，）为闭回路的每一个顶点标号， xrk 为为 1，沿一个方向（顺时针或逆时针）依次给，沿一个方向（顺时针或逆时针）依次给 各顶点标号；各顶点标号； （4）求）求 =minxij xij对应闭回路上的偶对应闭回路上的偶 数标号格数标号格= xpq 那么确定那么确定 xpq为出基变量，为出基变量， 为调整量；为调整量

22、； 精品课程运筹学 表上作业法 （5 5）对闭回路的各奇标号顶点调整为：）对闭回路的各奇标号顶点调整为： xij + ，对各偶标号顶点，对各偶标号顶点 调整为：调整为：xij - ， 特别特别 xpq - = 0， xpq变为非变为非基变量。基变量。 重复重复(2)(2)、(3)(3)步，直到所有检验数均步，直到所有检验数均 非负，得到最优解。非负，得到最优解。 精品课程运筹学 表上作业法 ij 0，得到最优解，得到最优解 x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3, 其余其余 xij = 0 ; 最优值：最优值： f* = 35+

23、102+13+81+46+53 = 85 精品课程运筹学 表上作业法 四、产销不平衡问题的处理四、产销不平衡问题的处理 在实际中遇到的运输问题常常不是产销在实际中遇到的运输问题常常不是产销 平衡的，而是下列的一般运输问题模型平衡的，而是下列的一般运输问题模型 m n min f = cij xij （1） i=1 j=1 n s.t. 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） 精品课程运筹学 表上作业法 我们可以通过增加虚设产地或销地 （加、减松弛变量）把问题转换成产

24、销 平衡问题，下面分别来讨论。 1.产量大于销量的情况 m n 考虑 si dj 的运输问题，得到的数学模 i=1 j=1 型为 精品课程运筹学 表上作业法 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) 精品课程运筹学 表上作业法 只要在模型中的产量限制约束（前只要在模型中的产量限制约束（前m 个不等式约束）中引入个不等式约束）中引入m个松弛变量个松弛变量 xi,n+1 i= 1, 2, , m 即可，变为：即可，变为： n xij+xi

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

26、小？ B1 B2 B3 产产量量 A1 6 4 6 300 A2 6 5 5 300 销销量量 150 150 200 精品课程运筹学 表上作业法 解：增加一个虚设的销地运输费用为解：增加一个虚设的销地运输费用为0 0 B1 B2 B3 B4 产量 A1 6 4 6 0 300 A2 6 5 5 0 300 销量 150 150 200 100 精品课程运筹学 表上作业法 2.销量大于产量的情况销量大于产量的情况 m n 考虑考虑 si dj 的运输问题，得到的数学模型为的运输问题，得到的数学模型为 i=1 j=1 m n Min f = cij xij i=1 j=1 n s.t. xij =si i = 1,2,m