表上作业法教程.ppt

* * 5 * * 5 * 运输问题的灵敏度分析 * * * * * * * * Min问题的非基变量检验数σij是对偶问题的最优解，也是资源的影子价格 ，故是非基变量每增加一个单位运量而成为进基变量时引起目标函数值(总运费）的增量 * Min问题的非基变量检验数σij是对偶问题的最优解，也是资源的影子价格 ，故是非基变量每增加一个单位运量而成为进基变量时引起目标函数值(总运费）的增量 * 从任一空格出发，如(A1,B1)，若让A1的产品调运1吨给B1，为了保持产销平衡，就要依次作调整：在(A2,B1)处减少1吨，在(A2,B3)处增加1吨，在(A1,B3)处减少1吨，即构成了以空格(A1,B1)为起点的闭环回路。 调整后的方案使运费变成 (+1)×3＋(－1)×1＋ (+1)×2＋(－1)×3＝1（元） 这就是(A1,B1)的检验数。 * * * * * * * * * * 材一直放在第84页 括号中的数是位势加起来所得 下表中的是对应的检验数 * 为满足互补松弛条件，原问题中xij被选为基变量，即xij0，则要求对偶问题中ui+vj=cij ，该行的松弛变量为0 令 zij= ui + vj ，其相当原问题xij的机会费用 * * 若有两个或两个以上的负检验数时，一般选其中最小的负检验数，和其它数字格构成闭回路。可证，此闭回路存在且唯一。在闭回路上进行运量调整，使选定空格处的运量尽可能地增加。 * 若有两个或两个以上的负检验数时，一般选其中最小的负检验数，和其它数字格构成闭回路。可证，此闭回路存在且唯一。在闭回路上进行运量调整，使选定空格处的运量尽可能地增加。 * * * 第一张表是最小元素法得到的运量表 * 必须补足基变量的个数，否则不能正常解出m+n个ui和 vj 2)补充后不能有某个基变量独占一行一列 * * * * M+n个决策变量，mn个约束条件 （b）闭回路调整中： 闭回路中，在需要减少运量的地方，基变量同时有多个达到最小, 调整后原先空格处填上这个最小数，而有多个 原基变量变为 0，就要把其中之一变为空格. 原则是选运费最大者变为空格，即为出基变量， 其余均保留在新的基解中，即均补添0，并看 作数字格，使数字格数=m+n-1 2、无穷解：运输问题必有最优解，当某个非基变量（空格）的检验数为0时，该问题有无穷最优解. (max)初始单纯形表：通过加入松驰变量，确定初始基可行解 最优性检验：当表中所有检验数?j ?0，则表中的基可行解就是问题的最优解 从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表 (1)确定进基变量 (2)确定出基变量 一定是min问题,应用最小元素法或Vogel法，确定m+n-1个基元，并做初表 最优性检验：当表中所有检验数?j ≥0，则表中的基可行解就是问题的最优解(闭回路法,位势法) 闭回路调整法：从一个基可行解转换到另一个目标函数值更小的基可行解，列出新的运输表 (1)确定进基变量 (2)确定出基变量 单 纯 形 法 表 上 作 业 法 (3)迭代运算：生成新单纯形表，并再求检验数，以得最优解 (3)迭代:空格加入调整量θ，闭回路上奇点加θ，偶点减θ，得新表 四、表上作业法与单纯形法 　　表上作业法计算步骤、过程与单纯形法相同，只是由于系数矩阵形式固定，具体计算时不必画出单纯形表，而只需在产销平衡表上进行. 1、最小元素法得到的一定是基可行解吗？ 　 由于用最小元素法所得的基变量都非负，且满足产销平衡约束条件，所以必为可行解 又由所选m+n-1个变量对应的列向量线性无关，所以为基可行 证明： 　选中一个变量xij 选中它对应的列向量Pij＝ei+em+j　 划掉一行 　或 划掉一列 去掉一个产量约束，ei所在行中含1的列向量对应的变量取为0　 去掉一个销量约束， em+j 所在行中含1的列向量对应的变量取为0 xij必为基变量 Pij 无法被其它列向量线性表出 五、几点说明 2、位势法何以还称之为对偶检验法？ 位势无正负约束 对基变量而言，(ui +vj)＝cij 　　 对非基变量而言，?ij+ (ui +vj) =cij ，即ui +vj＜cij 行位势ui为前m个约束条件对应的对偶变量的解 列位势vj为后n个约束条件对应的对偶变量的解 练习 ： 1、用表上作业法求出最优解。 这是一个产销平衡的问题 40 15 20 25 10 25 2）最优解的判别（闭回路法） 1）初始调运方案（最小元素） 初始调运方案的总运费为420元。 40 15 20 25 10 25 空格 闭回路 检验数 (13) (13)－(23)－(21)－(11)－(13) 9 (14) (14)－(24)－(2