[第4章指派问题.pptVIP

中华管理学习网 Page * 指派问题 中华管理学习网 Page * 指派问题 中华管理学习网 中华管理学习网 中华管理学习网 中华管理学习网 运筹学Operations Research * 烟台大学文经学院 科研与素质教育部gaoqian_yt@163.com 高 谦 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 指派问题 assignment problem * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 指派问题 assignment problem 【例1】人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人．经考核四人在不同岗位的成绩（百分制）如下表所示，如何安排他们的工作使总成绩最好。 表5-34 工作 人员 甲 乙 丙 丁 A 85 95 82 86 B 92 87 83 90 C 73 78 79 80 D 90 95 90 88 【解】设 数学模型 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 数学模型为： 甲 乙 丙 丁 A B C D 图5. 3 指派问题 assignment problem * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 假设m个人恰好做m项工作，第i个人做第j项工作的效率为cij≥0，效率矩阵为[cij] ，如何分配工作使效率最佳（min或max）的数学模型为 指派问题 assignment problem * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 解指派问题的匈牙利算法 匈牙利法的条件是：问题求最小值、人数与工作数相等及效率非负 【定理1】如果从分配问题效率矩阵[cij]的每一行元素中分别减去（或加上）一个常数ui（被称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的位势），得到一个新的效率矩阵[bij]，其中bij=cij－ui－vj,则[bij]的最优解等价于[cij]的最优解，这里cij、bij均非负． 指派问题 assignment problem 【证】 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 【定理2】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（称为独立元素）的最大个数． 如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，这时目标函数值等于零，得到最优解． 两个目标函数相差一个常数 u+v,约束条件不变,因此最优解不变。 指派问题 assignment problem * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 【例2】某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如下表所示．求最优生产配置方案． 工厂1 工厂2 工厂3 工厂4 产品1 58 75 65 82 产品2 69 50 70 55 产品3 180 150 170 200 产品4 260 230 250 280 指派问题 assignment problem * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-20