表上作业法课件.ppt

《表上作业法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2.1表上作业法表上作业法:建立在运输费用矩阵的求解运输问题的方法。表上作业法求解运输问题的思想和单纯形法完全类似：确定一个初始基本可行解——根据最优性判别准则来检查这个基本可行解是不是最优的？如果是，则计算结束；如果不是，则进行换基。——直至求出最优解为止。一、初始基本可行解的确定根据上面的讨论，要求得运输问题的初始基本可行解，必须保证找到m+n–1个不构成闭回路的基变量。一般的方法步骤如下：(1)在运输问题求解作业数据表中任选一个单元格xij(Ai行Bj列交叉位置上的格),令xij=min{ai,bj}即从Ai向Bj运最大量(使行或列在允许的范围内尽量饱和，即

2、使一个约束方程得以满足),填入xij的相应位置；精品课程《运筹学》(2)从ai和bj中分别减去xij的值，修正为新的ai和bj，即调整Ai的拥有量及Bj的需求量；(3)若ai=0，则划去对应的行（已经把拥有的量全部运走），若bj=0则划去对应的列（已经把需要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）；(4)当最终的运输量选定时，其所在行、列同时满足，此时要同时划去一行和一列。这样，运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。否则在剩下的运输平衡表中选下一个变量，返回(1)。上述计算过程可用流程图描述如下取未划去的单元格x

3、ij,令xij=min{ai,bj}ai’=ai-xijbj’=bj-xijai’=0?划去第i行划去第j列是否bj’=0否所有行列是否均被划去是找到初始基本可行解求运输问题的初始基本可行解过程注：为了方便，这里总记剩余的产量和销量为ai,bj按照上述方法所产生的一组变量的取值将满足下面条件：(1)所得的变量均为非负，且变量总数恰好为m+n–1个；(2)所有的约束条件均得到满足；(3)所得的变量不构成闭回路。因此，根据定理及其推论，所得的解一定是运输问题的基本可行解。在上面的方法中，xij的选取方法并没有给予限制，若采取不同的规则来选取xij，则得到不同的方法，较常

4、用的方法有西北角法和最小元素法。下面分别举例予以说明。1、初始基本可行解的确定（1）西北角法：从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。（2）最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。注:应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时

5、划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0。最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法。二、基本可行解的最优性检验1、闭回路法为了方便，我们以上表给出的初始基本可行解方案为例，考察初始方案的任意一个非基变量，比如x24。根据初始方案，产地A2的产品是不运往销地B4的。如果现在改变初始方案，把A2的产品运送1个单

6、位给B4，那么为了保持产销平衡，就必须使x14或x34减少1个单位；而如果x14减少1个单位，第1行的运输量就必须增加1个单位，例如x13增加1个单位，那么为了保持产销平衡，就必须使x23减少1个单位。这个过程就是寻找一个以非基变量x24为起始顶点的闭回路——{x24，x14，x13，x23}，这个闭回路的其他顶点均为基变量(对应着填上数字的格)。容易计算出上述调整使总的运输费用发生的变化为8–10+3–2＝-1，即总的运费减少1个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同

7、，而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。下表中用虚线画出以非基变量x22为起始顶点的闭回路。销地产地B1B2B3B4产量3[]11[]341037139[]218[]47[]4610[]539销量365620(产销平衡)A1A2A3可以计算出以非基变量x22为起始顶点的闭回路调整使总的运输费用发生的变化为9–2+3–10+5–4＝1即总的运费增加1个单位，这就说明这个调整不能改善目标值。从上面的讨论可以看出，当某个非基变量增加一个单位时，有若干个基变量的取值受其影响。这