管理优化之指派问题.ppt

《管理优化之指派问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、管理优化之—指派问题【例1】指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位只能一个人。经考核四人在不同工作岗位完成的时间如下表所示，如何安排他们的工作使总时间最少。工作人员ABCD甲85927390乙95877895丙82837990丁869080881指派问题及其数学模型数学模型如下：工作人员ABCD甲85927390乙95877895丙82837990丁86908088●求解指派问题的方法：匈牙利算法匈牙利算法是匈牙利数学家克尼格（Konig）证明了下面两个基本定理，为计算分配问题奠定了基础。

2、因此，基于两个定理基础上建立起来的解分配问题的计算方法被称为匈牙利法。【定理4.2】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（称为独立元素）的最大个数。如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，得到最优解。定理4.1告诉我们如何将效率表中的元素转换为有零元素，定理4.2告诉我们效率表中有多少个独立的“0”元素。【定理4.1】如果从分配问题效率矩阵[cij]的每一行元素中分别减去（或加上）一个常数ui

3、（被称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的位势），得到一个新的效率矩阵[bij]，若其中bij=cij－ui－vj,则[bij]的最优解等价于[cij]的最优解。这里cij、bij均非负。【例4.8】已知四人分别完成四项工作所需时间如下表，求最优分配方案。工作人员ABCD甲85927390乙95877895丙82837990丁86908088甲→C乙→B丙→A丁→D最优分配●不平衡的指派问题1．当人数m小于工作数n时，加上n－m个人，例如Min94100×××●求最大值的指派问题匈牙利法

4、的条件是：模型求最小值、效率cij≥0令则与的最优解相同。设C=(cij)m×m对应的模型是求最大值将其变换为求最小值【例4.9】某人事部门拟招聘4人任职4项工作，对他们综合考评的得分如下表（满分100分），如何安排工作使总分最高。【解】M＝95，令用匈牙利法求解：最优解：即甲安排做第二项工作、乙做第一项、丙做第四项、丁做第三项。总分为：Z＝92＋95＋90＋80＝357××●其它位置机器一二三四A13101211B15--1320C57106某工厂订购了3台机器(A、B、C），有4个位置可供机器安装，但B机器不能安

5、装在第二号位置。由于这4个安装位置离工厂中心的远近不同，所需要的运送费用也就不同，见下表。问这些机器安装在哪几个位置合适，可使总的运送费用达到最小。解：1）在（B，二）处添上一个很大的数M，以排除机器B安装在二号位置的可能。2）在第四行虚设一行。