第二节 运输问题求解 —表上作业法.pptVIP

第二节 运输问题求解 —表上作业法 运输问题的方法——表上作业法： 1、确定一个初始基本可行解； 2、根据最优性判别准则来检查这个基本可行解是不是最优的。如果是则计算结束；如果不是，则至3 3、换基，直至求出最优解为止。 一、初始基本可行解的确定 根据上面的讨论，要求得运输问题的初始基本可行解，必须保证找到 m + n – 1 个不构成闭回路的基变量。一般的方法步骤如下： (1)在运输问题求解作业数据表中任选一个单元格 xij ，令 xij = min { ai , bj } 即从 Ai 向 Bj 运最大量(使行或列在 允许的范围内尽量饱和，即使一个约 束方程得以满足),填入 xij 的相应位 置； (2)从 ai 或 bj 中分别减去 xij 的值，即调整 Ai 的拥有量及 Bj 的需求量； (3)若 ai = 0，则划去对应的行（把拥有的量全部运走），若 bj = 0 则划去对应的列（把需要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）； (4)若运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。否则在剩下的运输平衡表中选下一个变量，转(4)。 上述计算过程可用流程图描述如下 按照上述方法所产生的一组变量的 取值将满足下面条件： (1)所得的变量均为非负，且变量总 数恰好为 m + n – 1 个； (2)所有的约束条件均得到满足； (3)所得的变量不构成闭回路。 因此，根据定理3.1及其推论，所得的解一定是运输问题的基本可行解。? 在上面的方法中，xij 的选取方法并没有给予限制，若采取不同的规则来选取 xij ，则得到不同的方法，较常用的方法有西北角法、最小元素法和Vogel法。 1、西北角法： 从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 2、最小元素法： 从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 3、Vogel法： 从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤。 应用西北角法、最小元素法和Vogel法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0。 最优性检验就是检查所得到的方案是不是最优方案。 检查的方法----计算检验数 由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。 1、闭回路法 以最小元素法给出的初始基本可行解方案为例，考察初始方案的一个非基变量x24。 根据初始方案，产地 A2 的产品是不运往销地 B4 的。如果现在改变初始方案，把 A2 的产品运送1 个单位给 B4 ，那么为了保持产销平衡，就必须使 x14 或 x34 减少 1 个单位；而如果 x14 减少 1 个单位，第 1 行的运输量就必须增加 1 个单位，例如 x13 增加 1 个单位，那么为了保持产销平衡，就必须使 x23 减少 1 个单位。 这个过程就是寻找一个以非基变量 x24 为起始顶点的闭回路—— {x24 ，x14 ，x13 ，x23 }，这个闭回路的其他顶点均为基变量(对应着填上数字的格)。 上述调整使总的运输费用发生的变化为 8 – 10 + 3 – 2 ＝ -1 ，即总的运费减少 1 个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。 可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基变量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。 表4-10中用虚线画出以非基变量 x22 为起始顶点的闭回路。 表4-10 以非基变量 x22 为起始顶点的闭回路 可以