利用最大元素求解最大化指派问题

李承耕 刘波

【摘要】针对指派问题中最小化问题的匈牙利解法，通过最大元素法来处理最大化指派问题.

【关键词】指派问题；匈牙利法；最小元素；最大元素

【中图分类号】0223

【文献标识码】獳オ

1.指派问题的数学模型

求解n个资源分配到n个任务的活动中，为使得总成本最小，如何完成对资源的分配.

设C﹊j为分配资源i到j任务所消耗的成本，则：

玀inz=А苙[]i=1ИА苙[]j=1c﹊j獂﹊j.其中x﹊j=0 i资源不给 j活动，

1 i资源分给 j活动，お﹊=1,2,…,n,j=1,2,…，n.

А苙[]i=1x﹊j=1(j=1,2,…，n) А苙[]j=1x﹊j=1(i=1,2,…，n)

2.匈牙利法处理指派问题的基本步骤

（1)使指派问题的系数矩阵在各行各列都出现0元素.①从系数矩阵的每行都减去该行的最小元素.②再从系数矩阵的每列减去该列的最小元素.

(2）若效率矩阵的行列数为n,想办法找到n个不同行，不同列的0元素，即n个独立的0元素，用最少的直线将所有的0元素划去，若直线数量刚好等于n个，则n个独立的0元素就找到，否则就转入下一步.

(3）在直线没有划去的元素中，选一个最小的，在没有划去的元素的各行中均减去这个最小元素，为保持原来的0元素不变，在0元素对应的列中加上该元素.

3.最大化问题的两种处理方法

（1）将最大化问题转化为最小化问题，设原来的效益矩阵为C=(C﹊j)，我们可以作一个新的效益矩阵C′=M-C﹊j，这里M比C中的最大元素要大，则C′的最小指派即为C的最大指派.

（2）直接在每行或每列中减去该行列的最大元素，然后在效益矩阵中找到n个独立的0元素，这里的0元素即是最大元素，注意n个独立的0元素所在位置是处在不同行、不同列的位置，一旦找到n个独立的0元素，也就找到对应的最大指派.

4.基本案例分析

假定有四项工作A1,A2,A3,A4要分配到四部机器B1,B2,B3,B4上，其产生的效益如下表所示.问如何分配工作效益最好.

[]B1[]B2[]B3[]B4

A1[]11[]8[]6[]9

A2[]3[]5[]2[]3

A3[]8[]7[]1[]5

A4[]4[]5[]4[]7

（1） 方法一

对于效益矩阵C=11[]8[]6[]9

3[]5[]2[]3

8[]7[]1[]5

4[]5[]4[]7

，C′=12-C=1[]4[]6[]3

9[]7[]10[]9

4[]5[]11[]7

8[]7[]8[]5

，

则C′的最小化解即为C的最大化解.通过寻求C′的最小解得到C的最大解.

最优决策方案为：X11=X23=X32=X44=1，最大收益为：玬ax玈=А4[]i=1ИА4[]j=1c﹊j獂﹊j=11+2+7+7=27.

（2） 方法二

直接利用最大元素来处理，对于效益矩阵C=11[]8[]6[]9

3[]5[]2[]3

8[]7[]1[]5

4[]5[]4[]7

，我们作如下变换：

11[]8[]6[]9

3[]5[]2[]38[]7[]1[]54[]5[]4[]7

-11-5-8-7

→0[]-3[]-5[]-2

-2[]0[]-3[]-2

0[]-1[]-7[]-3

-3[]-2[]-3[]0

オ

+30[]-3[]-2[]-2

-2[]0[]0[]-2

0[]-1[]-4[]-3

-3[]-2[]0[]0

+1おおおお+1お

→(0)[]-2[]-1[]-1

-3[]0[](0)[]-2

0[](0)[]-3[]-2

-4[]-2[]0[](0)

おお

-1

プ钣啪霾呔卣笪：1[]0[]0[]0

0[]0[]1[]00[]1[]0[]00[]0[]0[]1

.

最优决策方案为：X11=X23=X32=X44=1，最大收益为：玬ax玈=А4[]i=1ИА4[]j=1c﹊j獂﹊j=11+2+7+7=27.

5.结束语

从以上两种方法的比较我们可以看出，用最大元素来处理这类问题，就不必建立新的系数矩阵，所以在编写程序时，可以用实参代替形象的方法，用同一段代参数的程序去解决最大化、最小化两个不同的问题.

ァ静慰嘉南住开オ

［1］罗荣桂.新编运筹学题解［M］.武汉：华中科技大学出版社，2002.

［2］胡运权.运筹学基础与应用［M］.北京：高等教育出版社，2004.

［3］程丛电，唐恒永.一类资源分配与排序问题［J］.数学实践与认识，2006（1）.