运输问题与指派问题第5.pptVIP

OR课件 匈牙利算法 TP AP -1 -2 -3 -2 -2 (0) (0) (0) (0) Z=1+2+5+2=1+2+3+2+2=10 【例1】 OR课件 匈牙利算法 TP AP -7 -5 -4 -2 -1 【例2】 (0) ? ? ? (0) (0) -1 -1 ＋1 (0) (0) (0) (0) (0) (0) (0) (0) 或： 关键：能覆盖所有0元素的最少直线数？如何画 ？？ OR课件 匈牙利算法 TP AP Z=20 【例2】 或： OR课件 匈牙利算法 TP AP 【例2】 定理：能覆盖所有0元素的最少直线数等于在0元素处作出标号（0）的最多个数。 画法： 在没有（0）的行打?号 对打?号的行上的所有 有0元素的列打?号 再对打?号的列上 有（0）的行打?号 有新的打?号 的行列吗？ Y N 对没有打?号的行 画横线 对所有打?号的列 画纵线 OR课件 指派问题 TP AP 特殊指派问题的求解 目标为MaxZ： 令：C’ij =M- Cij ，转化为MinS. “人多于事”（mn）： 处理：加（m-n）件虚事，Ci虚＝0 “事多于人”（mn）： 处理：加（n - m ）个虚人，C虚j＝0 OR课件 本章小结 TP AP 本章重点介绍了一类特殊线性规划问题（运输问题和指派问题）的模型与求解； 应注意到： 两问题都有最优解； 两算法思想基本相同，均从目标函数系数入手，并且直接求得整数最优解； 思考：两算法的区别？ OR课件 回 顾 到目前为止，针对规划问题所建立的算法有一个共同的特征： 但是： 在决策的实践中，有些问题约束条件存在一定的特殊性，按常规办法有可能出现严重退化而导致问题无法顺利求解。如：运输问题、指派问题等。 从约束条件入手 OR课件 运 筹 帷 幄 之 中 决 胜 千 里 之 外 运输问题与指派问题 第五章 Transportation Problem—IP Assignment Problem—AP OR课件 运输问题与指派问题 运输问题和指派问题是一种特殊的LP问题，要求了解两问题的基本特征；掌握两问题的求解算法原理及计算过程；学会对它们的特殊形式的处理。 本章的要求 TP AP OR课件 运输问题与指派问题 重点 本章重点与难点 难点 TP AP 运输与指派问题模型及其特征 算法原理 特殊问题的处理 两算法的思想及其实现 OR课件 运输问题与指派问题 运输问题 主要内容 指派问题 TP AP 运输问题及其数学模型 求解方法－－表上作业法 特殊运输问题的求解 指派问题及其数学模型 求解方法－－匈牙利法 特殊指派问题的求解 OR课件 运输问题 运输问题及其数学模型 TP AP 设某种物资有 m个产地：A1,A2,…,Am； 产量分别为：a1,a2,…,am个单位； n个销地：B1,B2,…,Bn； 销量分别为：b1,b2,…,bn个单位； 假设产销总量是平衡的，即 单位运价：Ai ? Bj：cij 问：如何调运这种物资才能使总的运费最小？ OR课件 运输问题 单位运价表与平衡表（合表） TP AP 单位运价 产销量（平衡） OR课件 运输问题 模型 TP AP 设：xij为Ai?Bj的运量 OR课件 运输问题 表上作业法 TP AP 【简例】已知有关资料如下表 算法的提出：观测模型的特征 要求建立总运费最小的模型。 OR课件 运输问题 模型 TP AP 约束条件个数为 m+n，但只有m+n-1 个是线性无关 元素只有0和1，每列只有两个1 OR课件 表上作业法 算法思想 TP AP 与单纯形法一样，最优解在基本可行解中产生。但基于模型的特征，初始基本可行解是通过分析单位运价表，首先满足局部最优，然后通过调整（迭代）使整体达到最优。 平衡表 OR课件 表上作业法 步骤 算法步骤及要点 TP AP 初始调运方案 检验数?ij?0 ? Y 最优解 N 调整：找到新的调运方案 特征：解变量（基变量）个数为 m+n-1；以解变量为顶点不构成折现闭回路。 方法：最小元素法、差值法 方法：闭回路法、位势法 方法：闭回路法 OR课件 表上作业法?初始方案 折现闭回路： TP AP 顶点: x11,x12,x32,x31 顶点：x12,x13,x33,x34,x24,x22 定理：以m+n-1个变量构成的基本可行解的充要条件是它不含折现闭回路。 OR课件 表上作业法?初始方案 最小元素法 TP AP 基本思想：“就近供应”或称“就廉供应” 3 ? ? ? ? ? 4 2 ? 3 4 5 Z=1×3＋9×5＋4×3＋2×4＋7×4＋2×2＝100 OR课件 表上作业法?