管理优化之指派问题.pptVIP

生产计划部 * 生产计划部 管理优化之指派问题 【例1 】指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位只能一个人。经考核四人在不同工作岗位完成的时间如下表所示，如何安排他们的工作使总时间最少。 工作 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 1 指派问题及其数学模型 数学模型如下： 工作 人员 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 ●求解指派问题的方法：匈牙利算法 匈牙利算法是匈牙利数学家克尼格（Konig）证明了下面两个基本定理，为计算分配问题奠定了基础。因此，基于两个定理基础上建立起来的解分配问题的计算方法被称为匈牙利法。 【定理4.2 】 若矩阵A的元素可分成“ 0”与非“ 0”两部分，则覆盖“ 0”元素的最少直线数等于位于不同行不同列的“ 0”元素（称为独立元素）的最大个数。 如果最少直线数等于m，则存在m个独立的“ 0”元素，令这些零元素对应的xij等于1，其余变量等于0，得到最优解。定理4.1告诉我们如何将效率表中的元素转换为有零元素，定理4.2告诉我们效率表中有多少个独立的“ 0”元素。 【定理4.1 】如果从分配问题效率矩阵[cij]的每一行元素中分别减去（或加上）一个常数ui（被称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的位势），得到一个新的效率矩阵[bij]，若其中bij=cij－ui－vj,则[bij]的最优解等价于[cij]的最优解。这里cij、bij均非负。 【例4.8 】已知四人分别完成四项工作所需时间如下表，求最优分配方案。 工作 人员 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 甲→C 乙→B 丙→A 丁→D 最优分配 ●　不平衡的指派问题 1．当人数m小于工作数n时，加上n－m个人，例如 Min 9 4 10 0 × × × ●　求最大值的指派问题 匈牙利法的条件是：模型求最小值、效率cij≥0 令 则 与 的最优解相同。 设C=(cij)m×m 对应的模型是求最大值 将其变换为求最小值 【例4.9】某人事部门拟招聘4人任职4项工作，对他们综合考评的 得分如下表（满分100分），如何安排工作使总分最高。 【解】M＝95，令 用匈牙利法求解： 最优解： 即甲安排做第二项工作、乙做第一项、丙做第四项、丁做第三项。 总分为：Z＝92＋95＋90＋80＝357 × × 生产计划部