吉林大学远程教育 运筹学课件4.4.

1、运 筹 学第四章 整数规划5 指派问题指派问题n 在实际问题中，常常会碰到这样的问题，要指派n个人去完成n项不同任务，每个人必须完成其中一项而且仅仅一项。但由于个人的专长不同，任务的难易程度不一样，所以完成不同任务的效率就不同，那么应该指派哪个人去完成哪项任务，能使总的效率最好呢？这就是典型的指派问题。 例6 今欲指派张王李赵四人加工A、B、C、D四种不同的零件，每人加工四种零件所需要的时间如下表所示，问应该派谁加工何种零件可使总的花费时间最少？ 零件人 A B C D张王李赵 4 6 5 8 6 10 7 8 7 8 11 9 9 3 8 4在类似问题中都必须给出一个像上表一样的矩阵C，称为

2、效率矩阵。nnnnnnCCCCCCCCCC212222111211 矩阵中的元素Cij表示指派第i个人去完成第j项任务时的效率。 求解这类问题时，通常引入01变量：njijiji, 2 , 1, ,项任务人去完成第不指派第项任务人去完成第指派第,01ijx 于是，对于极小化问题，指派问题数学模型为：m1in1jijijxcminZn ,1,2,j1,xn1iijn ,1,2,i1,xn1jij xij=1或0从模型看，指派问题是特殊的01规划，也是特殊的运输问题，可以用这两种问题的求解方法求解。但这样做是不合算的。 根据指派问题的特殊结构，我们有更为简便的方法。这就是下面将介绍的匈牙利法，这个

3、方法是由匈牙利数学家康尼格（D.Konig)给出的。 匈牙利算法是以指派问题最优解的性质为根据的。 指派问题最优解性质：指派问题最优解性质：如果将指派问题的效率矩阵的每一行（列）的各个元素都减去该行（列）的最小元素，得到一新的矩阵 C，则以C为效率矩阵的指派问题的最优解与原问题的最优解相同。 证明：设C的第i行元素都减去该行最小元素ai，第j列元素都减去该列最小元素bj ，则新矩阵C第i行第j列的元素为Cij=Cij-ai-bj，以新矩阵C为效率矩阵的指派问题的目标函数为 Z=Cijxij=（Cij-ai-bj）xij =Cijxij-ai-bj =Z-ai-bj可见新问题的最优解与原问题的最

4、优解相同，只是目标值相差一个常数。证毕。 利用这个性质，可以使原效率矩阵变换为含有多个0元素的新效率矩阵，而最优解不变。在新的效率矩阵中如果能找到n个不同行且不同列的0元素，则可以令它们对应的xij等于1，其它xij等于0，显然，该解一定是最优解。这就是匈牙利算法的基本思想。 具体步骤如下： 第一步 变换效率矩阵，使各行各列都出现 0 元素。 1效率矩阵每行元素都减去该行最小元素； 2效率矩阵每列元素都减去该列最小元素。 第二步 圈出不同行且不同列的 0 元素，进行试指派。 1（行搜索）给只有一个0 元素的行中的0 画圈，记作“”，并划去与其同列的其余0元素； 2（列搜索）给只有一个0 元素的

5、列中的0 画圈，记作“”，并划去与其同行的其余0元素； 3反复进行1、2，直至所有0元素都有标记为止。 4若行（列）的0元素均多于一个，则在0元素最少的行（列）中选定一个0元素，标“”,并划去与其同行同列的其余0元素。 5若不同行且不同列的 “”已达n个，则令它们对应的xij =1，其余xij =0，已得最优解，计算停，否则转第三步。 第三步 用最少直线覆盖效率矩阵中的0元素。 1对没有“”的行打“”； 2对打“”行中的0元素所在列打“”； 3对打“”列中“”所在行打“”； 4反复进行2、 3，直至打不出新 “”为止。 5对没 打“”的行画横线，对打“”列画竖线，则效率矩阵中所有0元素被这些直

6、线所覆盖。 第四步 调整效率矩阵，使出现新的0元素。 1找出未被划去元素中的最小元素，以其作为调整量； 2矩阵中打“”行各元素都减去，打“”列各元素都加（以保证原来的0元素不变），然后去掉所有标记，转第二步。 下面用上述算法求解例6。解：先变换效率矩阵，然后圈出不同行不同列的0元素，结果如下：040613101040302015062410214041204839911878710685640406131010403020由于不同行不同列的0元素仅有3个，所以要继续第三步及第四步。调整量=1，调整效率矩阵使之出现更多0元素。而后，再重新圈出不同行且不同列的 0 元素，进行再指派。结果如右：05

7、07030000302010由于的个数已达n=4个，所以令所对应的xij =1，其余xij =0，已得最优解。即最优指派方案为：张C；王A；李D；赵B。所需最少总时间为：5+6+9+3=23。注意，本例的最优方案不唯一，张A；王C；李B；赵D也是最优方案。 以上讨论仅限于极小化问题，对于极大化问题，不能按minZ=(-Cij)xij求解，因为匈牙利法要求效率矩阵的元素Cij0，这时可取M=maxCij,令bij=M-Cij,以B=（bij）nn为效率矩阵求解。 （M-Cij）xij=nM-Cijxij 当（M-Cij）xij取最小时，Cijxij便为最大。 另外，如果任务数与人数不相等，可以象