第7章运筹学运输问题试卷.ppt

* 结合例1说明这种方法。 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 行罚数 ① 0 1 1 列 罚 数 2 1 5 3 ① 14 8 0 优先安排销地 ，否则运价会更高 下次不考虑该列 第一次 * 第二次 结合例1说明这种方法。 行罚数 ② 0 1 2 列 罚 数 2 1 3 ② 优先安排销地 ，否则运价会更高 8 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 14 8 0 0 6 下次不考虑该行 * 结合例1说明这种方法。 行罚数 ③ 0 1 列 罚 数 2 1 2 ③ 8 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 14 8 0 0 6 下次不考虑该列 8 0 2 第三次 * 结合例1说明这种方法。 行罚数 ④ 7 6 列 罚 数 1 2 ④ 8 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 14 8 0 0 6 8 0 2 4 12 0 下次不考虑该列 第四次 * 结合例1说明这种方法。 行罚数 ⑤ 0 0 列 罚 数 2 ⑤ 4 2 8 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 14 8 0 0 6 8 0 2 4 12 0 0 0 0 第五次 * 例1用伏格尔法得到的初始基可行解 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 4 8 14 8 12 2 目标函数值 用最小元素法 求出的目标函数z=246 一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。 * 第二步：解的最优性检验 闭回路法 思路：计算空格（非基变量）的检验数 若令 则 如何求检验数？ 分析： ——运费的增量 即 增加1个单位 的检验数=相应的运费增量 * 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 从初始表分析： 要保证产销平衡，则 称为闭回路 +1 -1 +1 -1 * 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 2 1 * 检验数表 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 2 1 1 -1 10 12 表中的解不是最优解。 * 第三步：解的调整 从检验数为负值的格出发，做一条除该空格外其余顶点均为有数字格组成的闭回路。在这条闭回路上对空格的运量作最大可能的调整。 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 -1 （-2） （-2） （+2） （+2） * 调整后的解为： 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 12 14 4 8 2 2 0 9 1 12 此时的解为最优解。 最优解不唯一 * 运输问题练习1 求解运输问题 销地 产地 B1 B2 B3 　 B4 产量 A1 A2 A3 4 8 7 5 3 5 4 3 5 4 9 6 7 3 6 销 量 4 4 5 3 * 运输问题练习2 有甲乙丙三个商品产地，商品的运出量分别为25t、18t、5t，ABCD四个销售地，运入量分别为16t、20t、5t、7t，运输费用与各地之间的运输距离成正比，运输距离和运输量如下表所示，求合理的调运方案及最小吨公里。 * 2.位势法 所谓位势法，我们对运输表上的每一行赋予一个数值ui，对每一列赋 予一个数值vj，它们的数值是由基变量xij的检验数 所决 定的，则非基变量xij的检验数就可以用公式 求出。 。 销地 产地 B1 B2 B3 B4 ui A