第4章 线性整数规划-指派问题

1§4.5指派问题及其应用

在实际工作中，我们经常会遇到这样的问题：有n项工作要由n个人去完成，要求每人刚好承担一项工作。由于任务性质和各个人的专长不同，不同的人完成同一项工作所需的资源（或工作效率）不同。那么，到底应分配哪一个人去完成哪一项工作才能使所需的资源总量最少（或总的效率最高）？这类问题就称为指派问题或分配问题。指派问题不仅仅是指人力资源的分配，也可以是其他资源（如物力资源）的分配问题。2一、指派问题的数学模型

例：某一单位，有4个工作人员，有4项任务。如果每个工作人员都有能力去完成n项任务中的任一项，只是完成任务所需时间cij不同(见下表)，问应如何合理分配人力，才能使完成任务所需的总工时最少？

任务人员B1B2B3B4A15886A24658A361074A499733指派问题的数学模型这是一个有4个人和4项任务的完整指派问题，上表中的数据反映了每个人完成各项任务的效率（或效应），通常称为效率（或效应）矩阵。指派问题的所有原始数据均包含在其效率（或效应）矩阵中。

这个指派问题的特点是：每一项任务必须且只能由一个工作人员去完成，每一个工作人员也只能分配一项任务。引入0-1变量xij

4指派问题的数学模型S表示完成所有任务所需的总工时，则该问题的数学模型为：5对于将n项资源分配给n项任务的完整指派问题，设资源i分配给任务j所产生的效应为cij，S表示总效应，引入0-1变量

指派问题的数学模型6指派问题的数学模型则数学模型为：7讨论：

1、问题中的效应系数cij可以有多种不同的实际意义，例如可以为时间、价值、资源消耗量或工作效率等。根据效应系数的具体含义，指派问题的目标函数可以取最小值，也可以取最大值，但最大化问题可以转化为最小化问题求解。2、指派问题的数学模型是一个线性规划数学模型，约束系数矩阵的元素不是1就是0，且约束方程的右端常数均为1，其基本可行解必满足0-1变量的取值要求，故可以直接用单纯形法求解，但求解工作量较大。指派问题的数学模型83、指派问题的数学模型是一个特殊的运输问题数学模型，各个产地的产量和各个销地的销量均为1，可以采用运输问题的表上作业法求解。但由于该问题的特殊性，用表上作业法求解时效率很低。4、指派问题的数学模型是一个0-1线性规划问题，可以用上一节介绍的隐枚举法求解。但由于指派问题的变量和约束条件都较多，采用隐枚举法求解计算量很大。5、指派问题可以推广到资源数和任务数不等的情况。为了把这类推广的指派问题转化为常规指派问题，只需对问题增加若干个虚拟的资源或若干个虚拟的任务即可。指派问题的数学模型9⑴资源数多于任务数的情况。这时可引入若干个虚拟任务，并令效应矩阵中虚拟任务对应的列全为0元素。这种情况下，实际上将有某些资源分配不出去（某些人分配不到工作）。⑵任务数多于资源数。这时可引入若干个虚拟的资源，并令效应矩阵中虚拟资源对应的行全为0元素。这种情况下，实际上将有某些任务分配不到资源（某些任务无人承担）。指派问题的数学模型10匈牙利法是求解指派问题的有效算法。它是匈牙利数学家柯尼格(Konig)根据指派问题的独特性质而提出的一种巧妙而有效的算法，故称匈牙利法。指派问题的数学模型11二、用匈牙利法求解指派问题1、匈牙利法的基本思路

与大多数整数规划算法不同，求解指派问题的匈牙利法不是采用解迭代方式而采用了问题迭代的方式，其基本思路是：根据指派问题的性质对原问题做一系列同解变换，从而得到一系列等价(同解)的指派问题，最后可得到一个只需直接观察其效率矩阵就可得到最优解的派生指派问题，该问题的最优解即为原指派问题的最优解（但目标函数值不同）。12匈牙利法在介绍匈牙利法之前，我们先介绍指派问题的几个重要性质。定理1：如果效率矩阵[cij]n×n中的所有元素非负，且其中存在n个位于不同列、不同行的零元素，则只要令对应于这些零元素位置的xij=1，其余的xij＝0，这样得到的解即为指派问题的最优解。

这是因为，在目标函数表达式中xij=1的系数为0，可使目标函数达到最小；另外，还可以保证在约束方程组的每个方程中只有一个变量为1，故可满足约束条件的要求。因此，这样得到的解就是指派问题的最优解。13定理2：如果从效率矩阵的每一行元素中分别减去一个常数ui，从每一列元素中分别减去一个常数vj，由此得到一个新的效率矩阵，匈牙利法证：由于由确定的指派问题的目标函数为：则的最优解等价于的最优解。14匈牙利法由于上式后面两项均为常数，且指派问题的约束条件与效率矩阵无关，故由确定的指派问题与的指派问题有相同的最优解。证毕。15匈牙利法该定理是对指派问题进行同解变换的依据。

定理3：若矩阵A的元素可分成0与非0两部分，则覆盖0元素的最少直线数等于位于不同行、不同列的0元素的最大个数。

所谓用直线覆盖是指用一条横线划去矩阵的一行元素或用一条竖线划去一列元素，划去的元素就称为被覆盖。这个定理实际上回答了这样一个问题：至少要多少条直线(横线和竖线)才能覆盖矩阵A中的所有0元素?16匈牙利法根据定理3，可以采用最少直线覆盖所有0元素的方法确定效率矩阵中位于不同行、不同列的0元素的最大数目。如果刚好有n个0元素位于不同行、不同列，则由定理1即可得到指派问题的最优解。否则应按定理2继续对效率矩阵作同解变换。以上3个定理是匈牙利法的基础，但要实施这个算法还要解决以下两个问题：①对于给定的效率矩阵，如何用最少的直线覆盖所有0元素？

②若效率矩阵中位于不同行、不同列的0元素的最大数目小于n，如何对效率矩阵进一步作同解变换？

17匈牙利法例：数学教研室有四名教师讲四门不同的课，由于各位教师的专长、教学水平和教学经验不同，所需备课时间也分别不同，问教研室主任应如何分配这些教学任务，才能使总的备课时间最省。各教师备各门课所需时间见下表。

课程教师B1微积分B2数理方程B3线性代数B4概率论A121097A2154148A313141611A441513918匈牙利法匈牙利法的变换方法如下：(1)第一步：变换效应矩阵C(即备课时间阵)，使每行每列至少有一个元素为零，以期从这些对应的零元素能得到完整的分配方案，使总的备课时间为最省。为此，可先在每行中减去各行的最小元素，根据表中数据，第一、二、三、四行分别减去2、4、11、4，可得新一矩阵为：19匈牙利法加减常数的代数和为：S1＝2+4+11+4＝21因第三列中无零元素，因而再在第三列中减去其最小元素5，加减常数的代数和为：S1+S2＝21+5＝2620匈牙利法(2)第二步：为了给每个教师分配一个任务，以实现完整的任务分配，希望每行每列只有一个零元素，现在有的行或列多于一个零元素，如何分配呢？这需要用检验的办法决定取舍。先进行行检验，如图l所示。碰到每行只有一个0元素的先打△，有两个0元素不作记号，例如第一行只有一个0，就在0处打△，这就表示把第一门课(微积分)分配给教师Al，因此，对第一列其它的0元素打×；同理第二行打一个△；第三行有两个0，不作记号。21匈牙利法然后进行列检验，如图2所示，第一、二列已没有未作记号的0；第三列有一个0，打△，表示教师A3已接受第三门课，因此对同一行的0打×。(3)第三步，从检验出的矩阵可以看出，第四门课还未分配出去，教师A4也未分到任务。可见这不是最优方案。22匈牙利法为过渡到最优方案，需对以上的矩阵再进行变换，如图3所示。变换规则如下：(a)对所有没有分配任务的行打√。如第四行。(b)在已打√的行中，找出打×的列打√。如第一列。(c)在已打√的列中找出打△的行，打√，如第一行。(d)再进行上述(b)、(c)项检验，直至无法打√为止。并用以下调整办法找最优解。23匈牙利法(e)对所有打√的列和未打√的行划线，这些线至少可以把所有0覆盖一次。一般讲，如果是n×n阵，又要使最优分配均在0上，最少线数就应等于n。而此例中现只有三根直线，因此，这不是最优解。还需进一步进行变换。24(f)在变换后的检验矩阵中，从未经划线的元素中可以找出一个最小元素c13=2，从未全部划线的第一行和第四行中各减去2，可得一新矩阵：S1+S2+S3＝26+2+2=30加减常数的代数和为：25匈牙利法由于此矩阵中第一列有负数，因此再在第一列上加2，于是得一个所有元素均≥0的矩阵。S1+S2+S3+S4＝30-2=28

加减常数的代数和为：

26对新得的矩阵进行行检验和列检验，如图4所示。第二、四行和第四列均只有一个0，很快打上△，并对同列或同行的0打×，剩下一个c13处为0，打△。于是得一完整分配方案，也即最优分配方案。得最优解为：x13=1，x22=1，x34=1，x41=1，而其余的xij均等于0。27匈牙利法对于这个完整分配方案，可得：再看一下打△处原效应矩阵的元素值，得由此可见，最优分配方案所对应的原效应矩阵中元素值之和，等于进行变换过程中行和列所加减数字的代数和(加为负，减为正)。此例中目标函数S的最小值即为：28匈牙利法2、匈牙利法的算法步骤如有m个资源(如人力、机车或设备均为一种资源)分配到n个活动领域(如生产任务、运输路线或地区等均为一种活动对象或领域)上去。若对应的效应cij均已知，那么，分配问题就是要确定各个资源如何分配到各个活动对象上去，才能使全局的效应最优。29匈牙利法若资源的个数m大于分配对象的个数n，则在n个活动对象的列向量后加上m-n个虚构的列向量，而且这些列向量的所有元素cij均为0，这样效应矩阵C就是一个包含0列向量的m×m阶方阵。m-n列m>n30匈牙利法同理，若资源个数m小于分配对象个数n，则在m个资源的行向量下面加上n-m个虚构的行向量，这些行向量的元素也均为0，使效应矩阵C成为包含0行向量的n×n方阵。n-m行m<n31匈牙利法我们用方阵进行匈牙利算法的运算，找出完整分配方案的最优解。若所得的结果中某一1元素在虚行或虚列上，这个结果可以不考虑，而其他行和列的结果就是最优解。具体算法步骤如下：

第1步：如果是求目标函数S＝f(X)的极大值，则应将所有效应矩阵的元素改为负值，然后进行第2步。如果求目标函数S＝f(X)的极小值，则直接进行第2步。第2步：若第i行的最小元素不是0，则从该行的每个元素中减去此最小元素。(i＝1～m)。32匈牙利法第3步：若第j列的最小元素不是0，则从该列的每个元素中减去此最小元素。(j=1～n)。第4步：逐个检查每一行，看是否每一行只有一个未标注的0，如只有一个0存在，则在此元素上注以符号△，表示一种分配，同时，对同一列的0元素打×，以便下一个分配不落在此列上。重复这一过程，直到所有行上没有未标注△的0或至少有两个0。第5步：逐个检查每一列，查出单一的未标注的0，打上△，对同一行的0元素打×。重复这一过程，直到所有列上没有未标注△的0或至少有两个0。33匈牙利法第6步：反复进行第4、5步，直到下面三种情况之一发生为止：(a)每行均标注有△；(b)至少有两个未标注的0在各行或各列中；(c)没有剩下未标注的0，但还未形成一完整的分配。

第7步：如果上述(a)发生，则得一完整的分配方案；且是一最优分配方案，可停机。如果是(b)发生，可任意作一分配记号△到一个0上，而将同行或同列的另一个0打×，然后转到第4步。如果是(c)发生，则转到第8步。34匈牙利法第8步：对所有没有标注△的行打√。第9步：在打√的行中如包含一个0元素，则给该元素所对应的(没有打√的)列打上√。第10步：在打√的列上，如有△记号，则这些△记号的对应的行均打√。第11步：重复第9、10步；直到所有能打√的行和列都打完。第12步：对所有未打√的行和已打√的列划线，这些线至少有一次盖过每一个0元素，这是覆盖0元素所需的最少线数。35匈牙利法第13步：检查所有没有线通过的元素，选择出其中最小者。在未完全划线的行中，对每一元素减去此最小数，再在有线通过的列上，对每一元素加上此最小数，得一新矩阵，再回到第4步。36三、匈牙利法的FORTRAN程序

该程序用于解n个资源、n个活动对象的分配问题，要求使目标函数f(X)为最优。可用以求目标函数的极大值；也可用以求目标函数的极小值。但要求其效应矩阵C的各元素cij必须是整数。该程序由主程序和子程序组成。主程序包括数据输入、输出。子程序即为匈牙利算法，称为HUNGRY。使用下面所列程序至多可解决15个资源、15个对象的问题。若所要求解的问题中资源的个数、对象的个数大于15，即n＞15，只需改变主程序中DIMENSION语句中的维数即可。37匈牙利法的FORTRAN程序使用该程序时，应输入下列数据：

N──资源、对象的个数。KODE──对于最小化问题，KODE=0；对于最大化问题，KODE=1。MATRIX(I,J)──初始效应矩阵。该程序将计算并打印出：IASMAT──分配矩阵(ASSIGNMENTMATRIX)。NCOST──目标函数的最优值。38匈牙利法的FORTRAN程序具体程序如下：CCCC用于求解资源分配问题的匈牙利算法程序CCCC需要输入的数据为：CCCCN──资源、对象的个数。CCCCKODE──对于极小值问题，KODE=0；对于极大值问题，KODE=1。CCCCMATRIX(I,J)──初始效应矩阵，按行输入。

DIMENSIONMATRIX(15,15),IASMAT(15) OPEN(21,FILE='HUN.IN') OPEN(22,FILE='HUN.OUT') READ(21,*)N,KODE DO2I=1,N2 READ(21,*)(MATRIX(I,J),J=1,N) CLOSE(21) WRITE(22,*)'初始效应矩阵为：' DO6I=1,N6 WRITE(22,5)(MATRIX(I,J),J=1,N)395 FORMAT(1X,10I8)

CALLHUNGRY(N,MATRIX,IASMAT,NCOST,KODE) WRITE(22,120)NCOST120 FORMAT(/1X,'最优目标函数值为：',I8) WRITE(22,*)'最优分配方案为:' DO130I=1,N130 WRITE(22,135)I,IASMAT(I)135 FORMAT(1X,'资源',I2,'分配给对象',I2) CLOSE(22) STOP END匈牙利法的FORTRAN程序40匈牙利法的FORTRAN程序 SUBROUTINEHUNGRY(N,IIF,IROW,TOTAL,KODE) DIMENSIONIIF(15,15),IEFF(15,15),IROW(15),ICOL(15) DIMENSIONICHECK(15),JCHECK(15) INTEGERTOTAL IF(KODE.EQ.1)GOTO100 DO110I=1,N DO110J=1,N110 IEFF(I,J)=IIF(I,J) GOTO200100 DO120I=1,N DO120J=1,N120 IEFF(I,J)=-IIF(I,J)200 DO210I=1,N MINROW=IEFF(I,1) DO220J=1,N IF(IEFF(I,J).LE.MINROW)MINROW=IEFF(I,J)220 CONTINUE41匈牙利法的FORTRAN程序 DO210J1=1,N IEFF(I,J1)=IEFF(I,J1)-MINROW210 CONTINUE DO300J=1,N MINCOL=IEFF(1,J) DO310I=1,N IF(IEFF(I,J).LE.MINCOL)MINCOL=IEFF(I,J)310 CONTINUE DO300I1=1,N IEFF(I1,J)=IEFF(I1,J)-MINCOL300 CONTINUE400 DO410I=1,N IROW(I)=0410 ICOL(I)=0 NOMADE=0420 LOOP=0 NZEROS=0 DO430I=1,N NOZR=0 IF(IROW(I).NE.0)GOTO43042匈牙利法的FORTRAN程序 DO440J=1,N IF(ICOL(J).NE.0)GOTO440 IF(IEFF(I,J).NE.0)GOTO440 NOZR=NOZR+1 NZEROS=NZEROS+1 NRPT=J NREFF=I440 CONTINUE IF(NOZR.NE.1)GOTO430 IROW(I)=NRPT ICOL(NRPT)=1 NOMADE=NOMADE+1 LOOP=LOOP+1430 CONTINUE DO500I=1,N NOZC=043匈牙利法的FORTRAN程序 IF(ICOL(I).NE.0)GOTO500 DO510J=1,N IF(IROW(J).NE.0)GOTO510 IF(IEFF(J,I).NE.0)GOTO510 NOZC=NOZC+1 NZEROS=NZEROS+1 IRPT=J510 CONTINUE IF(NOZC.NE.1)GOTO500 ICOL(I)=1 IROW(IRPT)=I NOMADE=NOMADE+1 LOOP=LOOP+1500 CONTINUE IF(NOMADE.EQ.N)GOTO1500 IF(LOOP.NE.0)GOTO420 IF(NZEROS.EQ.0)GOTO800700 IROW(NREFF)=NRPT NOMADE=NOMADE+1 ICOL(NRPT)=1 GOTO42044匈牙利法的FORTRAN程序800 DO810I=1,N ICHECK(I)=0 JCHECK(I)=0 IF(IROW(I).NE.0)GOTO810 ICHECK(I)=I810 CONTINUE900 NCHECK=0 DO910I=1,N IF(ICHECK(I).EQ.0)GOTO910 DO920J=1,N IF(JCHECK(J).NE.0)GOTO920 IF(IEFF(I,J).NE.0)GOTO920 JCHECK(J)=J NCHECK=NCHECK+1920 CONTINUE910 CONTINUE

IF(NCHECK.EQ.0)GOTO1300

45匈牙利法的FORTRAN程序 DO1010I=1,N IF(JCHECK(I).LE.0)GOTO1010 DO1020J=1,N IF(JCHECK(I).NE.IROW(J))GOTO1020 ICHECK(J)=J NCHECK=NCHECK+11020 CONTINUE1010 CONTINUE IF(NCHECK.NE.0)GOTO9001300 MINELM=99999999 DO1310I=1,N IF(ICHECK(I).EQ.0)GOTO1310 DO1320J=1,N IF(JCHECK(J).NE.0)GOTO1320 IF(IEFF(I,J).GE.MINELM)GOTO1320 MINELM=IEFF(I,J)1320 CONTINUE1310 CONTINUE46匈牙利法的FORTRAN程序 DO1400I=1,N DO1400J=1,N IF(ICHECK(I).LT.0)GOTO1400 IF(ICHECK(I).EQ.0)GOTO1410 IF(JCHECK(J).NE.0)GOTO1400 IEFF(I,J)=IEFF(I,J)-MINELM GOTO14001410 IF(JCHECK(J).LE.0)GOTO1400 IEFF(I,J)=IEFF(I,J)+MINELM1400 CONTINUE GOTO4001500 TOTAL=0 DO1510I=1,N K=IROW(I)1510 TOTAL=TOTAL+IIF(I,K) RETURN END47匈牙利法的FORTRAN程序

数据输入文件hun.in：

4,02,10,9,715,4,14,813,14,16,114,15,13,9结果输出文件hun.out：初始效应矩阵为：

2109715414813141611415139给教师分配教学任务例题计算结果48匈牙利法的FORTRAN程序最优目标函数值为：28最优分配方案为:

x(1,3)=1

x(2,2)=1

x(3,4)=1

x(4,1)=149四、指派问题的推广应用指派问题的一种很有意义的推广是：设有m个人和n项任务，其中每个人可承担的任务总数是给定的，应如何给每个人分配任务才能既保证完成n项任务，又使总体效率最高？这里没有限定一个人必须而且只能承担一项任务，但要求一项任务只能由一人完成，而且m个人必须完成n项任务。设第i个人完成第j项任务所需的时间为cij，则以上推广指派问题的数学模型为：50指派问题的推广应用51显然该问题有解的充要条件是指派问题的推广应用经以下两步转换后，该问题可化成常规的指派问题。①增加项虚设任务，并令每个人完成虚设任务所需的时间均为0；②如果第i个人最多可承担ai项任务，则将其等价为ai个人，其中每个人刚好承担一项任务，且每个人完成各项任务（包括虚设任务）所需的时间与第i个人相同。52指派问题的推广应用转换后得到的常规指派问题将包括个人和项任务。下面以油气集输系统中油井与计量站的最优连接问题为例说明以上推广的指派问题的应用。该问题已在运输问题的拓广应用中讨论过，其数学模型与上面列出的推广的指派问题的数学模型完全相同。53指派问题的推广应用例：某油田在调整一个区块的开发计划时，决定在这个区块打5口调整井，井的位置及计划产量已定。考虑到这个区块原有的3个计量站尚有富裕的处理能力，故决定不再新建计量站，而是将调整井分配给原有的计量站管理。