第二节运输问题求解表上作业法.ppt
《第二节运输问题求解表上作业法.ppt》由会员分享,可在线阅读,更多相关《第二节运输问题求解表上作业法.ppt(51页珍藏版)》请在三一文库上搜索。
1、1,第二节 运输问题求解 表上作业法,运输问题的方法表上作业法: 1、确定一个初始基本可行解; 2、根据最优性判别准则来检查这个基本可行解是不是最优的。如果是则计算结束;如果不是,则至3 3、换基,直至求出最优解为止。,2,一、初始基本可行解的确定 根据上面的讨论,要求得运输问题的初始基本可行解,必须保证找到 m + n 1 个不构成闭回路的基变量。一般的方法步骤如下: (1)在运输问题求解作业数据表中任选一个单元格 xij ,令 xij = min ai , bj ,3,即从 Ai 向 Bj 运最大量(使行或列在 允许的范围内尽量饱和,即使一个约 束方程得以满足),填入 xij 的相应位 置
2、; (2)从 ai 或 bj 中分别减去 xij 的值,即调整 Ai 的拥有量及 Bj 的需求量;,4,(3)若 ai = 0,则划去对应的行(把拥有的量全部运走),若 bj = 0 则划去对应的列(把需要的量全部运来),且每次只划去一行或一列(即每次要去掉且只去掉一个约束); (4)若运输平衡表中所有的行与列均被划去,则得到了一个初始基本可行解。否则在剩下的运输平衡表中选下一个变量,转(4)。,5,上述计算过程可用流程图描述如下,6,按照上述方法所产生的一组变量的 取值将满足下面条件: (1)所得的变量均为非负,且变量总 数恰好为 m + n 1 个; (2)所有的约束条件均得到满足; (3
3、)所得的变量不构成闭回路。,7,因此,根据定理3.1及其推论,所得的解一定是运输问题的基本可行解。 在上面的方法中,xij 的选取方法并没有给予限制,若采取不同的规则来选取 xij ,则得到不同的方法,较常用的方法有西北角法、最小元素法和Vogel法。,8,1、西北角法: 从西北角(左上角)格开始,在格内的右下角标上允许取得的最大数。然后按行(列)标下一格的数。若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去。如此进行下去,直至得到一个基本可行解。,9,2、最小元素法: 从运价最小的格开始,在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行(列)的产量(销量)已
4、满足,则把该行(列)的其他格划去。如此进行下去,直至得到一个基本可行解。,10,3、Vogel法: 从运价表上分别找出每行与每列的最小的两个元素之差,再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量上供应完毕或得到满足时,划去运价表中对应的行或列,再重复上述步骤。,11,应用西北角法、最小元素法和Vogel法,每次填完数,都只划去一行或一列,只有最后一个元例外(同时划去一行和一列)。当填上一个数后行、列同时饱和时,也应任意划去一行(列),在保留的列(行)中没被划去的格内标一个0。,12,表1,13,14,15,16,17,最优性检验就是检查所得到的方案是不是最
5、优方案。 检查的方法-计算检验数 由于目标要求极小,因此,当所有的检验数都大于或等于零时该调运方案就是最优方案;否则就不是最优,需要进行调整。,二、基本可行解的最优性检验,18,1、闭回路法 以最小元素法给出的初始基本可行解方案为例,考察初始方案的一个非基变量x24。 根据初始方案,产地 A2 的产品是不运往销地 B4 的。如果现在改变初始方案,把 A2 的产品运送1 个单位给 B4 ,那么为了保持产销平衡,就必须使 x14 或 x34 减少 1 个单位;而如果 x14 减少 1 个单位,第 1 行的运输量就必须增加 1 个单位,例如 x13 增加 1 个单位,那么为了保持产销平衡,就必须使
6、x23 减少 1 个单位。,19,这个过程就是寻找一个以非基变量 x24 为起始顶点的闭回路 x24 ,x14 ,x13 ,x23 ,这个闭回路的其他顶点均为基变量(对应着填上数字的格)。 上述调整使总的运输费用发生的变化为 8 10 + 3 2 -1 ,即总的运费减少 1 个单位,这就说明原始方案不是最优方案,可以进行调整以得到更好的方案。,20,可以证明,如果对闭回路的方向不加区别(即只要起点及其他所有顶点完全相同,而不区别行进方向),那么以每一个非基变量为起始顶点的闭回路就存在而且唯一。因此,对每一个非基变量可以找到而且只能找到唯一的一个闭回路。 表4-10中用虚线画出以非基变量 x22
7、 为起始顶点的闭回路。,21,表4-10 以非基变量 x22 为起始顶点的闭回路,22,可以计算出以非基变量 x22 为起始顶点的闭回路调整使总的运输费用发生的变化为 9 2 + 3 10 + 5 4 1 即总的运费增加 1 个单位,这就说明这个调整不能改善目标值。 从上面的讨论可以看出,当某个非基变量增加一个单位时,有若干个基变量的取值受其影响。,23,这样,利用单位产品变化(运输的单位费用)可计算出它们对目标函数的综合影响,称这个综合影响为该非基变量对应的检验数。 上面计算的两个非基变量的检验数为 24 = -1,22 = 1。 闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数。,2
8、4,如果规定作为起始顶点的非基变量为第 1 个顶点,闭回路的其他顶点依次为第 2 个顶点、第 3 个顶点,那么就有 ij = (闭回路上的奇数次顶点单位运费之和) - (闭回路上的偶数次顶点单位运费之和) 其中 ij 为非基变量的下角指标。,25,按上述作法,可计算出表1的所有非基变量的检验数,把它们填入相应位置的方括号内,如图4-11所示。,26,显然,当所有非基变量的检验数均大于或等于零时,现行的调运方案就是最优方案,因为此时对现行方案作任何调整都将导致总的运输费用增加。 闭回路法的主要缺点是:当变量个数较多时,寻找闭回路以及计算两方面都会产生困难。,27,2.位势法 位势:设对应基变量x
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 运输 问题 解表 作业
链接地址:https://www.31doc.com/p-2560221.html