运筹学-运输问题的表上作业法(名校讲义)精选ppt课件.ppt

第十讲运输问题的表上作业法 1运输问题事例 2运输问题的一般形式 3表上作业法 1运输问题事例 1 已知 有4个产地 源点 生产的产品需销售到4个需求地 目的地或汇点 其源点产量和目的地需求量见表1 5 表1 5运输问题的需求量及产量 其源点到目的地的单位产品的运费价格见图1 7 1运输问题事例 2 24181236 22281723 图1 7运输费用矩阵表格旁边数字为产量和需要求量 2运输问题的一般形式 ri 源i产量 aj 目的地j的需求量 3表上作业法 1 与单纯形表格法一样 该法亦分两步进行 求出初始基础可行解 求出最优解1 用最小元素法求出满意的初始基础可解其方法是 按照费用矩阵元素Cij增长顺序逐个选择引入基本解的变量xij 非退化情况下 每选择1个 就必然排除1个源点或目的地 最后一步可一次排除1个源点和1个目的地 这样便可得到一个初始基础可行解 3表上作业法 2 以上例考察 观察图1 7 min cij c22 1 故优先分配源2和目的地2之间的产品 图1 8最小元素法第1步 3表上作业法 3 余下元素中 最小值为c32 2 图1 9最小元素法第2步 依此类推 最后获初始基础可行解示如图1 10中 3表上作业法 4 图1 10初始基础可行解 即基础解为 x11 22 x12 18 x33 12 x42 8 x43 5 x44 23 此时总费用为225 3表上作业法 5 2 求出最优解这有两种方法 闭回路法和位势法 闭回路法 其思路是令表中空格 即非基础解 对应的变量由0增加d单位 然后在保持产品供求平衡 即满足约束条件 情况下 使基础解参与变动 看其费有如何变化 若费用减少 则该非基变量可进入基 否则 加以排除 其思路与单纯形法一致 现继上图继续改进基础解 直至达优 i 参见图1 11 分析非基变量x32增加d单位以后 其它基础解及费用变化 3表上作业法 6 2 求出最优解 图1 11回路法原理 3表上作业法 7 为使供求平衡 必须符合 x32 d x42 d x43 d x33 d变动后 费用增加值为 8d 5d 4d 2d 5d 即费用增加 x32不能进基 为比较 把增加1个单位产品所引起的费用增加值填入相应的非基变量表格内 这又称检验值 注意 在用回路法求解每个非基变量检验值时 在根据供求平衡寻找闭合回路过程中 其回路转折点必须是基础解 例如 分析非基解x31 x11 x12 x42 x43 x33 x31 3表上作业法 8 对每个非基变量计算后 将其检验值填入图1 12中 图1 12回路法计算结果其中 内表示费用元素 内表示检验值表内其它值为基础解 3表上作业法 9 ii 观察表格 或检验值全部 0 已达最优胜 结束 否则 选取最负的检验值所对的非基变量 令其进基 图1 12中 x13的检验值为最负 故令x13进基 应使x13尽量大 但又必须使其它变量非负 观察x13变化规律 x13 x12 x42 x43 应取下降变量中的最小值作为x13的值 此时min x12 x43 min 2 5 2 故令x13 2则x12 0 x42 10 x43 3 将图1 12修正后 再求出当前非变量的检验值 示如图1 13 非基础解的检验数合为正 故获最成解 总费用为249 3表上作业法 10 图1 13回路法所得最优表格 3表上作业法 11 位势法 简捷法 该法对运输费用矩阵表格每次可确定一组 行值 和 列值 确定原则为使得每个基础变量之费用cij等于相应得行 列值之和 根据该原则求出行列值之后 用这些值再去求解每个非基本变量的检验数 结合本例阐述该步骤 见图1 14 3表上作业法 12 图1 14用位势法求解实例 3表上作业法 13 i 令si tj分别为行值和列值求解方程 si tj cij xij B基集 从方程知 共有m n 1个方程和m n个未知量 由于我们感兴趣的是相对值 故可令任一个行值或列值等于某个固定值 例如令t1 0 即可求出各行 列值 可见 行 列 值不是唯一的 对于本例 令t1 0后 解联立方程 3表上作业法 14 ii 根据已得的si tj值求出非基础的检验值 或成本变动值 ij ij cij si tj 例如 图1 14中 13 c13 s1 t3 5 3 5 3若 13 0 则可进入基 根据此法求出所有非基本变量对应的检验值 成本变动值 后 选取min ij ij 0 所对应的变量进入基础解 图1 14中得知 13 3为最小值 令x13进基 采用回路法找出应离开的基变量 重新调整后 仍按上述步骤反复运算 最后得出最优解 现在看位势法的对偶解释 结合本例 示如表1 6中 3表上作业法 15 表1 6位势法的对偶解释 x11 x12 x13 x14 24x21 x22 x23 x24 18x31 x32 x43 x44 12x41 x42 x43 x44 36x11 x21 x31 x41 22x12 x22 x32 x42 28x13 x23 x33 x43 17x14 x24 x34 x44 23 r1 s1 r2 s2 r3 s3 r4 s4 a1 t1 a2 t2 a3 t3 a4 t4 c11c12c13c14 c44 3表上作业法 16 表1 6列出了本例的供求关系的8个约束方程 由于 故只有7个独立约束方程 该规划的对偶约束必为 3表上作业法 17 显然 si tj即是对偶问题的对偶变量y 共8个对偶变量 每次送代时有7个基础解变量 可写出7平衡方程式 si tj cij xij B 这与上面分析完全一致 因此 位势法实质每一步都是首先求解对偶方程的