ch2第二节-表上作业法.ppt

1、3.2 运输问题求解表上作业法,表上作业法: 建立在运输表上的求解运输问题的方法。,由于运输问题系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。,一、表上作业法求解思路（单纯形法完全类似）,2,为了表上求解方便，我们往往把单位运价表、产销平衡表合 在一起列一个表：,表3-3 运输问题求解作业数据表（运输表）,运输问题解的每一个分量都惟一对应其运输表中一 个格。表示作业时得出运输问题的一个基可行解后， 就将基变量的值xij填入表中相应的格（Ai,Bj)内，这 种格叫做填有数字的格含0数字）或数字

2、格；非基变 量对应的格不填数字称为空格。,3,产销平衡运输问题基变量（数字格） (1) 个数:运输问题的基变量共有m+n-1个 （因为此时问题系数矩阵A的秩为m+n-1)。 (2)条件：运输问题的 m+n-1 个变量构成基 变量的充分必要条件是不构成闭回路。,二、几点说明,闭回路及其顶点 在表3-3的决策变量格中，凡是能够排列成下列形式的 xab ,xac ,xdc ,xde ,xst ,xsb (3.3) 或 xab ,xcb ,xcd ,xed ,xst ,xat (3.4) 其中，a,d,s 各不相同；b,c,t 各不相同，我们称之为 变量集合的一个闭回路，并将式（3.3）、式（3.4）

3、中的 变量称为这个闭回路的顶点。,4,例如，x13, x16, x36, x34, x24, x23 ；x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是闭回路。若把闭回路的各变量格看作节 点，在表中可以画出如下形式 的闭回路：,根据定义可以看出闭回路的一些明显特点： (1)闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的； (2)闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。,5,关于闭回路有如下的一些重要结论： (1) 设 xab , xac , xdc , xde , xst , xsb是一个闭回

4、路，那么该闭回路中变量所对应的系数列向量pab , pac , pdc , pde , pst , psb 线性相关； (2) 若变量组 xab , xcd , xef , xst 中包含一个部分 组构成闭回路，那么该变量组所对应的系数列向量pab , pcd, pef , pst 线性相关。 根据上述结论以及线性规划基变量的特点，可以得到下 面重要定理及其推论。,定理3.1 变量组 xab , xcd , xef , xst 所对应的 系数列向量 pab , pcd , pef , pst 线性无关的充分 必要条件是这个变量组中不包含闭回路。 推论 产销平衡运输问题的 m+n -1 个变量构

5、 成基变量的充分必要条件是它不含闭回路。 这个推论给出了运输问题基本解的重要性质， 也为寻求基本可行解提供了依据。,7,三、表上作业法的计算步骤,(1) 找出初始基可行解（初始调运方案）。即在(mn)产销平衡表上给出m+n-1个数字格。(最小元素法、西北角法或伏格尔法）,(2) 求检验数。（闭回路法或位势法） 判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。,(3) 对方案进行改善，找出新的调运方案。（表上闭回路法调整）,确定m+n-1个基变量,(4) 重复（2）、（3），直到求得最优调运方案。,空格,（一）初始调运方案的确定 根据上面的讨论，要求得运输问题的初始基本可行解， 必

6、须保证找到m+n1个不构成闭回路的基变量。 一般步骤如下： (1)在运输问题求解作业数据表中任选一个单元格xij (Ai行 Bj列交叉位置上的格),令 xij = min ai , bj 即从 Ai 向 Bj 运最大量(使行或列在允许的范围内尽量饱和，即使一个约 束方程得以满足),填入 xij 的相应位置；,8,(2) 从ai和bj中分别减去xij 的值，修正为新的ai 和 bj 即 调整 Ai 的拥有量及 Bj 的需求量； (3) 若 ai = 0，则划去对应的行（已经把拥有的量全部运 走），若 bj = 0 则划去对应的列（已经把需要的量全部运 来），且每次只划去一行或一列（即每次要去掉且

7、只去掉一 个约束）； 否则在剩下的运输平衡表中选下一个变量，返回(1)。,按照上述方法所产生的一组变量的取值将满足下 面条件： (1)所得的变量均为非负，且变量总数恰好为 m+n1 个； (2)所有的约束条件均得到满足； (3)所得的变量不构成闭回路。 因此，根据定理4.1及其推论，所得的解一定是运 输问题的基本可行解。 在上面的方法中，xij 的选取方法并没有给予限制， 若采取不同的规则来选取 xij ，则得到不同的方法， 较常用的方法有最小元素法和Vogel法。,9,10,例3.2 某运输资料如下表所示：,问：应如何调运可使总运输费用最小？,1、求初始方案：最小元素法、西北角法、伏格尔法,

8、基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,4,10,总的运输费(31)+(64) +(43) +(12)+(310)+(35)=86元,1.最小元素法,方法：按运价由小到大顺序从运价最小的格开始， 在格内的右下角标上允许取得的最大数。若某行 （列）的产量（销量）已满足，则把该行（列）的 其他格划去。然后次小运价填数。从如此进行下去， 直至得到一个基本可行解。,12,练习,12,13,13,19,1,2,2.西北角法（或左上角法）,此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下：,3 6 5

9、 6,7 4 9,3,4 4 9,0 6 5 6,4,0 4 9,0 2 5 6,2,0 2 9,0 0 5 6,2,0 0 9,0 0 3 6,3 6,0 0 0 0,0 0 0,3 4 0 0 0 2 2 0 0 0 3 6,在满足约束条件下尽可能的给最左上角的变量最大值.,8,8,6,4,8,14,所以，初始基可行解为：(8,8,4,8,14)目标函数值Z372,例3.3 某运输资料如下表所示：,练习,8,13,13,14,6,6,3Vogel 法（元素差额法） 最小元素法的缺点：按某一最小单位运价优先调运，为 了节省一处的费用，有时造成在其他处要多花几倍的运费，从 而使整个运费增加。

10、Vogel 法的思想：一产地的产品假如不能按最小运费就近 供应，就考虑次小运费，这就会有一个差额。最小和次小单位 运价之间的差额（称为罚数）。若罚数的值不大，当不能按最 小单位运价调运时造成的损失就不大；反之，如果罚数的值很 大，不按最小单位运价组织调运就会运费增加很多。故应对罚 数最大处，采用最小运费调运。,17,Vogel 法的步骤： （1）计算每行和每列的最小单位运价和次小单位运价（相 同的元素重复算）之间的差值 ，并称之为行罚数和列罚数。 将算出的行罚数填入运输表右侧行罚数栏左边第一列相应格 子中，列罚数填入运输表下边列罚数栏的第一行的相应格子 中。,18,用Vogel 法重解上例，见

11、下表。,(2) 从所有罚数中选出最大者，选择他所在行或列中的最 小元素格填数，满足最大的需要量。如出现几个相同的最 大差额，可任取一行或一列。若某行（或某列）的产量 （销量）已用尽，则把这一行（列）划去。,19,（3）对表中尚未划 去 的元素重复以上步 骤，直到给出初始调 运方案为止。,20,总运费=85元,21,练习,1,2,13,12,13,19,注:应用最小元素法和Vogel 法，每次填完数， 都只划去一行或一列，只有最后一个元例外（同 时划去一行和一列）。当填上一个数后行、列同 时饱和时，也应任意划去一行（列），在保留的 列（行）中没被划去的格内标一个0，以示数字格 （与空格区别）。,

12、22,23,二、 最优解的判别（检验数的求法）,求检验数的方法有两种： 闭回路法 对偶变量法（位势法）,（1）闭合回路法： ij0 （因为目标函数要求最小化） 表格中有调运量的地方即数字格为基变量，空格处为非基变量。基变量的检验数ij0，非基变量的检验数ij0。,ij 0 表示运费增加。,24,闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转90，然后继续前进，直到到达出发的空格所形成的闭合回路。,调运方案的任意空格存在唯一闭回路。,注：1.每一空格有且仅有一条闭回路； 2.如果某数字格有闭回路，则此解不是可行解。,1、闭回路法,为了方便，我们以（表3-4）最小

13、元素法给出的初始 调运方案为例，考察初始方案的任意一个非基变量即空格，比如 x24。,根据初始方案，产地 A2 的产品是不运往销地 B4 的。如果现在改变初始方案，把 A2 的产品运送1 个单位给 B4 ，那么为了保持产销平衡，就必须使 x14 或 x34 减少 1 个单位；而如果 x14 减少 1 个单位，第 1 行的运输量就必须增加 1 个单 位，例如 x13 增加 1 个单位，那么为了保持产销 平衡，就必须使 x23 减少 1 个单位。,25,这个过程就是寻找一个以非基变量 x24 为起 始顶点的闭回路 x24 ，x14 ，x13 ，x23 ， 这个闭回路的其他顶点均为基变量(对应着填上

14、数 字的格)。容易计算出上述调整使总的运输费用发 生的变化为 c24-c14+c13-c23= 8 10 + 3 2 -1 ，即总的运费减少 1 个单位，这就说明原 始方案不是最优方案，可以进行调整以得到更好 的方案。,26,表3-5中用虚线画出以非基变量 x22 为起始顶点的闭回路.,表3-5 以非基变量 x22 为起始顶点的闭回路,27,A1,A2,A3,可以计算出以空格（非基变量） x22 为起始顶点的闭回路调整使总的运输费用 发生的变化为 c22-c23+c13-c14+c34-c32 = 9 2 + 3 10 + 5 4 1 即总的运费增加 1 个单位，这就说明这 个调整不能改善目标

15、值。 从上面的讨论可以看出，当某个空格 （非基变量）增加一个单位时，有若干个 数字格（基变量）的取值受其影响。,28,这样，利用单位产品变化（运输的单位费 用）可计算出它们对目标函数的综合影响，其作 用与线性规划单纯形方法中的检验数完全相同。 故也称这个综合影响为该非基变量对应的检验数。 上面计算的两个非基变量的检验数为 24 = -1， 22 = 1。闭回路方法原理就是通过寻找闭回路来 找到非基变量的检验数。 如果规定作为起始顶点的非基变量为第 1 个 顶点，闭回路的其他顶点依次为第 2 个顶点、 第 3 个顶点，那么就有 ij = (闭回路上的奇数次顶点单位运费之和) -(闭回路上的偶数次

16、顶点单位运费之和) 其中 ij 为非基变量的下角指标。,29,按上述做法计算出表3-4所有空格的检验数 22=1 ， 24=-1 11 =c11-c13+c23-c21=1 12 =c12-c14+c34-c32 =2 31 =c31-c34+c14-c13 +c23-c21 =10 33 =c33-c34+c14-c13=12,30,显然，当所有非基变量的检验数均大于或等于零时，现 行的调运方案就是最优方案，因为此时对现行方案作任 何调整都将导致总的运输费用增加。 24=-10,此方案 不最优。 闭回路法的主要缺点是：当变量个数较多时，寻找 闭回路以及计算两方面都会产生困难。,31,练习,5

17、,5,7,9,-3,-11,32,m个,n个,2.对偶变量法（位势法）,设其对偶变量为：,33,uivj无约束 （i=1,2, ,m;j=1,2, ,n),标准型运输问题的对偶问题模型为：,则运输问题变量xij的检验数为：,34,由于对应基变量xij 的检验数ij =0，即对于基变量ui ,vj 满足 ui+vj=cij ，i=1,2 ,m ; j=1,2 ,n . 对产销平衡问题，这是一个包含有m+n个变量 （ ui , vj ），m+n-1 个方程（基变量个数）的 方程组，故有一个自由变量，求解即得。 称这些 ui , vj 为该基本可行解对应的位势，这种方法叫位势法。 位势不唯一。,35

18、,用位势法对初始方案进行最优性检验的步骤：,1）在给定初始解的表上增加一行和一列，在列中填入ui，在行中填入vj。,2）令u10(或其他值），再按cij-(ui+vj)=0（基变量的cij求出其余的ui与vj）,3）由i j=Ci j -（ui+vj），求出非基变量的检验数。,4) 判别,下面用位势法求表3-4的空格检验数 由 u1+v4=c14=1 0 u1=0 u1+v3=3 u2=-1 u2+v1=1 u3=-5 u2 +v4=8 并令 u1=0 得 v1=2 u3 +v4=5 v2=9 u3 +v2 =4 v3 =3 v4=10 计算非基变量(空格）的检验数 11=c11-(u1+v1

19、)=3-(0+2)=1, 12=c12-(u1+v2）=11-（0+9）=2， 22=1 ， 24=-1 ， 31=10 ， 33=12.,36,以上计算可直接在表上进行,37,A1,A2,A3,位势,u1=0,v4=10,v3=3,u2=-1,u3=-5,v1=2,v2=9,当非基变量的检验数出现负值时，则表明当前 的基本可行解不是最优解。在这种情况下，应该对 基本可行解进行调整，即找到一个新的基本可行解 使目标函数值下降，这一过程即通常的换基(或主 元变换)过程。 闭回路调整法： （1）选负检验数中最小者 rk，以它对应的空格为 调入格。即以非基变量 xrk 为换入变量（上页图中 x24 ）;,38,三、解的改进闭回路调整法,（2）以 xrk 为起点找闭回路，除 xrk 外其余顶点必 须为基变量格; （3）给闭回路的每一个顶点标号,xrk 为1，沿闭 回路顺 (或逆）时针方向依次给各顶点标号； （4）求 =minxijxij对应闭回路上的偶数格 = xpq 那么确定 xpq为出基变量，为调整量； （5）对闭回路的各奇标号顶点调整为：xij + ， 对各偶标号顶点 调整为：xij - ，特