指派问题(0-1规划 程序)

指派问题的算法分析与实现摘要在企业、公司的运营与管理中，管理者总是希望把人员最佳分派以发挥其最大工作效率，从而降低成本、提高效益。

然而，如果没有科学的方法是很难实现优化管理的，由此我们引入了指派问题。

指派问题多是求项目的工时最少，而很多情况下人们并不关心项目总工时的多少，而只关心项目能否在最短的时间内完成，即历时最少的指派问题。

这类问题研究的是n个人执行n项任务，执行每项任务的人数以及总的指派人项数均有限制，要求最优指派。

在运筹学中求解整数规划的指派问题通常是通过匈牙利算法来求解，但指派问题也可以归结为一个0-1整数规划问题，本文先对指派问题进行陈述，引出对实际问题的求解。

在指派问题的背景、描述中充分理解该问题，先运用匈牙利算法实现指派问题，然后再建立一个0-1整数规划模型，并运用matlab和lingo编译程序对问题进行编译，运用软件解决模型问题，最终实现指派问题在实际问题中的运用。

通过运用匈牙利算法和0-1整数规划同时对指派问题求解，我们发现用0-1整数规划的方法来求解可以更简单，也更方便程序的阅读和理解。

与此同时，我们还对0-1整数规划问题由整数数据深入研究到小数数据。

最后通过实例来说明运用matlab，lingo编译程序来解决整数规划问题的简便和有效性。

关键词：指派问题；匈牙利算法；0-1整数规划；matlab模型；lingo模型1. 问题陈述指派问题又称分配问题，其用途非常广泛，比如某公司指派n个人去做n 件事，各人做不同的事，如何安排人员使得总费用最少？若考虑每个职工对工作效率（如熟练程度等），怎样安排会使总销量达到最大？这些都是一个企业经营管理者必须考虑的问题，所以该问题有重要的应用价值。

假设有n 件工作分派给n 个人来做，每项工作只能由一人来做，每个人只能做一项工作。

若给出各人对各项工作所具有的工作效率。

问应该如何安排人选，及发挥个人特长又能使总的效率最大。

为此用0-1整数规划来实现指派问题即如何安排人选。

指派问题的C++实现一．指派问题在生活中经常遇见这样的问题，有n项任务要求n个人完成，这n个人完成各项任务的效率（或所需时间）不同，于是产生指派哪个人去完成哪项任务的问题，这类问题称为指派问题或分派问题。

1．指派问题的数学模型引入变量Xij，其取值只能是1或0，并令Xij=1表示指派第i人完成第j项任务Xij=0表示不指派第i人完成第j项任务；当问题要求极小化时，数学模型是：Min z= ①② ③④约束条件②说明第j项任务只能由1人完成；约束条件③说明第i 人只能完成1项任务。

满足约束条件②--④的解，可以用矩阵来表示，此矩阵称为解矩阵。

当问题要求极大化时，可令bij=M-Cij把问题转换成极小化模型。

二．指派问题的解法指派问题是0-1规划的特例，也是运输问题的特例，可以用整数规划、0-1规划、运输问题的解法去求解，但因忽略指派问题的特殊性，因而不能达到好的解题效率。

指派问题的最优解具有这样的性质，若从系数矩阵（bij）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（bij’），那么以（bij’）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。

库恩于1955年提出了指派问题的解法，其中引用了康尼格一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。

三．程序实现依照上述方法，编制Assignment类，以实现对任意规模的指派问题的解决。

class Assignment{public:Assignment(int n, int * eff);~Assignment();int * getAssignment(bool isMin=true);private:bool hasAssigned(int * eff);bool hasZero(int * eff);void changeMinToMax();void getRowColZero(int * eff); void assignAndGetoff(int * eff); void changeEfficiency(int * eff); void getTaskAssignment(int * eff); void assignCore(int * eff);void resetZero (int * eff);int getLineNum(int *eff);private:bool allAssigned;int * task;int * efficiency;int scale;int * rowTicked;int * colTicked;public: // 定义的几个常数const int MAXVALUE ;const bool MAXASSIGN; const bool MINASSIGN; const int ASSIGNED ;const int GETOFFED ;};Assignment类说明1.Assignment类实现任务指派；2.使用示例Assignment assignment = Assignment(n, eff);int * Task = assignment.getTaskAssignment(isMin);其中，n表示指派任务个数；eff 效率系数，以一维数组传递；isMin 是否取最小代价指派；isMin=true时，表示为最小代价指派，缺省情况下，isMin=true；Task 指派结果，若T ask[i]=j, 表示第i个人完成第j项任务(以0为第一序数)；3.应用举例：int main(){int scale, *eff, * task;int i, j;// Get Scalecout<<"\nThe Scale Of Problem: ";cin>>scale;// Construct effeff = new int[scale*scale];// Get Efficiencyfor(i=0; ifor(j=0; j{cout<<"\nThe Efficiency Of The "<<i+1<<"th " <<j+1<<"th ";cin>>eff[i*scale+j];}// Get minormaxbool isMin= true;char isY;cout<<"\nIs a min cost assignment ?(Y for yes, & others for no): ";cin>>isY;isMin= (isY=='Y' || isY=='y');// List the Efficiencycout<<"\n" <<"The Effienciency:";for(i=0; i{cout<<"\nThe " <for(j=0; jcout<}// Assignment Typeif (isMin)cout<<"\n\nMin Cost Assignment.\n";elsecout<<"\n\nMax Effect Assignment.\n";Assignment assignment = Assignment(scale, (int *)eff); task = assignment.getAssignment(isMin);// Output the resultfor(i=0; icout<<"\nThe " <<</i+1<<"th>> max)max = efficiency[i*scale+j];// Changefor(i=0; ifor(j=0; jefficiency[i*scale+j] -= max;}void Assignment::getRowColZero(int * eff){int i,j , min;// Zero in Rowfor(i=0; i{min = MAXVALUE; // Get Minfor(j=0; jif (eff[i*scale+j] < min)min = eff[i*scale+j];if (min==0) continue;for(j=0; jeff[i*scale+j] -= min;}// Zero in Colfor(j=0; j{min = MAXVALUE; // Get Minfor(i=0; iif (eff[i*scale+j] < min)min = eff[i*scale+j];if (min ==0) continue;for(i=0; ieff[i*scale+j] -= min;}}void Assignment::assignAndGetoff(int * eff) {int i,j,k, rowZero, colZero, zeroPos;bool isOver = false;while (!isOver){isOver = true;// From row which has only one zerofor(i=0; i{rowZero = 0;for(j=0; jif (eff[i*scale+j] == 0){rowZero++;zeroPos = j; // Write down the col number }// Only one zero in rowif (rowZero == 1){isOver = false;eff[i*scale+zeroPos] = ASSIGNED;for(k=0; kif (eff[k*scale+zeroPos]==0)eff[k*scale+zeroPos] = GETOFFED;}} // End for____Row// Column processfor(j=0; j{colZero = 0;for(i=0; iif (eff[i*scale+j]==0){colZero++;zeroPos = i; // Write down the row number}if (colZero==1){isOver = true;eff[zeroPos*scale+j] = ASSIGNED;for(k=0; kif (eff[zeroPos*scale+k]==0)eff[zeroPos*scale+k] = GETOFFED;} // End If} // End for____Column} // End whilereturn;}/*void Assignment::assignWithStart(int * eff, int row, int col) {int i,j;if (allAssigned)return;if (hasZero(eff)){for(i=0; i{if (allAssigned)return;for(j=0; j{if (allAssigned)return;if (eff[i*scale+j]==0){int * tempEff = new int[scale*scale]; int k,m;for(k=0; kfor(m=0; mtempEff[k*scale+m] = eff[k*scale+m];tempEff[row*scale+col] = ASSIGNED; for(k=0; kif (tempEff[k*scale+col]==0) tempEff[k*scale+col] = GETOFFED; for(k=0; kif (tempEff[row*scale+k]==0) tempEff[row*scale+k] = GETOFFED;// Get new row, col Startfor(k=0; kfor(m=0; mif (tempEff[k*scale+m]==0) assignWithStart(tempEff, k, m);delete [] tempEff;} // End if}}}else // No zero{while (getLineNum(eff) < scale){changeEfficiency(eff);if (hasAssigned(eff)) break;}if (hasAssigned(eff)){allAssigned = true; getTaskAssignment(eff);return;}} // End else}*/int Assignment::getLineNum(int * eff) {int i,j, lineNum=0;bool hasMore = true;// Initiate rowTicked & colTickedfor(i=0; i{rowTicked[i] = colTicked[i] = 0;}// Get rows that has no ASSIGNED for(i=0; i{rowTicked[i] = 1;for(j=0; jif (eff[i*scale+j]==ASSIGNED) {rowTicked[i] = 0;break;}}int time=0;while ( (hasMore)&& (time++ {hasMore = false;// Columnfor(i=0; iif (rowTicked[i]==1)for(j=0; jif ( (eff[i*scale+j]==ASSIGNED) || (eff[i*scale+j]==GETOFFED) ) {colTicked[j] = 1;hasMore = true;break;}// Rowfor(j=0; jif (colTicked[j])for(i=0; iif (eff[i*scale+j]==ASSIGNED){rowTicked[i] = 1;hasMore = true;break;}} // End whilefor(i=0; i{if (rowTicked[i]==0)lineNum++;if (colTicked[j]==1)lineNum++;}return lineNum;}void Assignment::changeEfficiency(int * eff) {int i,j, minValue = MAXVALUE;// Get minValue in where lines donot cover for(i=0; i{if (rowTicked[i]==0) continue;for(j=0; j{if (colTicked[j]==1) continue;if (eff[i*scale+j] < minValue)minValue = eff[i*scale+j];}}// To get more zerofor(i=0; iif (rowTicked[i]==1)for(j=0; jeff[i*scale+j] -= minValue;for(j=0; jif (colTicked[j]==1)for(i=0; ieff[i*scale+j] += minValue;}void Assignment::getTaskAssignment(int * eff) {for(int i=0; ifor(int j=0; jif (eff[i*scale+j]==ASSIGNED){task[i] = j; // Person i do the task jbreak;}}bool Assignment::hasZero(int * eff) {for(int i=0; ifor(int j=0; jif (eff[i*scale+j]==0) return true;return false;}bool Assignment::hasAssigned(int * eff) {int i, j;for(i=0; i{for(j=0; jif (eff[i*scale+j]==ASSIGNED) break;if (j==scale) return false;}return true;}void Assignment::assignCore(int * eff) {if (hasAssigned(eff)){getTaskAssignment(eff);allAssigned = true;return;}else{// Zero not Assigned ?if (hasZero(eff)){// Not All Assigned & has Zerofor(int i=0; i{if (allAssigned) break;for(int j=0; j{if (allAssigned) break;// Get the first zero, for getting the best zero is so difficult. if (eff[i*scale+j]==0){int m;int * tempEff = new int [scale*scale];// Keep the copyfor(m=0; mtempEff[m] = eff[m];tempEff[i*scale + j] = ASSIGNED; // Marked as Assigned for(m=0; m{// Marked Zero in the same col As GETOFFEDif (tempEff[m*scale + j]==0) tempEff[m*scale+j] = GETOFFED;// Marked Zero in the same row As GETOFFEDif (tempEff[i*scale + m]==0) tempEff[i*scale+m] = GETOFFED;} // End for___m//if (! allAssigned)assignCore(tempEff); // Nested Calldelete [] tempEff;}} // End for___j} // End for___i(To get rid of Dependent Zero} // End if____(hasZero(eff))// Not All Assigned & has No Zeroelse{if (getLineNum(eff)<n{changeEfficiency(eff); // Change Efficiency MatrixresetZero(eff);getRowColZero(eff);assignAndGetoff(eff);assignCore(eff);}else // l=nreturn;}} // End elsereturn;}void Assignment::resetZero(int * eff){for(int i=0; iif ((eff[i]==ASSIGNED)||(eff[i]==GETOFFED)) eff[i]=0;}。

公交站点的数学建模的例子0-1规划记录一个关于0-1规划问题（指派问题、分配问题）模型的建立、实现、求解的过程，并在基础模型通过添加惩罚或激励机制考虑多种情况。

记录目的在于学习交流以及日后自己对该类模型能进行较快的进行描述实现。

问题描述（基础）考虑这么一个分配问题有9个数，让他们其中分成2组每组不超过6人，每组又分成A、B两队，每队不超过3人。

目标使得每组A、B两队和之差最小。

用数学题的语言进行描述该问题，现有9人，分成2组，每组最多6人，每组内又分AB两队，如何安排才能使得每组两队分数较为平衡。

思考解的形式我们将解分成2*2个（两组每组两队）部分，每个部分需要重9个数中进行选择，用0-1来表示在该部分中是否被选中，那么它的解的个分别数为9*2*2，用矩阵形式为：将其用向量的形式进行表示：思考约束条件以及目标解的形式确定之后，思考如何针对该解的形式，然后对问题进行描述，从问题中和解的形式，我们可以总结出以下的2个约束：•每组中的A部分和B部分分别小于等于3人•每个数只能出现1次，即每一列的和为1 用公式进行表达为：∑j=113x1ja<=3∑i=13xi1a<=1∑j=113x1jb<=3∑i=13xi 1b<=1......思考目标两队分数之和比较接近，可以理解每一组中为：max(∑(xa)∗y)st.∑(xa)∗y<=1/2∗∑(x)∗y其中x表示9个数的位置（0-1表示），y表示对应位置的数的值,即使得每组A队的分数尽可能大并且接近该组之和的1/2。

将其组合起来可以该总目标表示为：max(∑(xija)∗y）st.∑j=19x1ja<=∑j=19x1jb∑j=19x2ja<=∑j=19x2jb最后将问题进行重新进行整理•目标为：A队之和最大•约束1: 每队小于等于3人•约束2: 每组A队小于B队•约束3: 每个数只能出现1次，即每一列和为1代码实现主代码，函数在附录。

lingo 指派问题Lingo作业题1、指派问题设有n个人, 计划作n项工作, 其中cij表示第i个人做第j项工作的收益,求一种指派方式，使得每个人完成一项工作，使总收益最大.现6个人做6项工作的最优指派问题，其收益矩阵如表所示，请给出合理安排. 人工作1 工作2 工作3 工作4 工作5工作6 1 20 15 16 5 4 7 2 17 15 33 12 8 6 3 9 12 18 16 30 13 4 12 8 11 27 19 14 5 0 7 10 21 10 32 6 0 0 0 6 11 13 解：一、问题分析根据第一题的题意我们可以知道，此题的最终目标是让我们建立一种数学模型来解决这个实际生活中的问题，此题意简而言之就是为了解决6个人做6项工作的指派最优问题，从而使题目中的Cij收益等达到所需要的目的。

在题目中曾提到：每个人完成一项工作。

其意思就是每人只能做一项工作且每项工作只能做一人做。

二、符号说明此题属于最优指派问题，引入如下变量：题目中说：Cij表示第i个人做第j项工作的收益。

例如C56则表示第5个人做第6项工作。

即maxz???xyijciji?1j?166s.t.：?Ci?16ij・・・，6 ?1 ，j=1,2,3，?Cj?16ij・・・，6 ?1 ，i=1,2,3，・・・，6 Cij?0或1 ，i,j=1,2,3，此题需要求出最大值最优（最大值），即需要使用max，表示最大。

在编程过程中“@bin（x）”是“限制x为0或1”。

三、建立模型此题属于最优指派问题，与常见的线性问题极为类似。

因此，使用Lingo软件。

由于“每人只能做一项工作且每项工作只能做一人做”故采用0-1规划求得优。

四、模型求解（一）常规程序求解 Lingo输入框：max=20*c11+15*c12+16*c13+5*c14+4*c15+7*c16+17*c21+15*c22+33*c23+12*c24+8*c25+6*c26+9*c31+12*c32+18*c33+16*c34+30*c35+13*c36+12*c41+8*c42+11*c43+27*c44+19*c45+14*c46+0*c51+7*c52+10*c53+21*c54+10*c55+32*c56+ 0*c61+0*c62+0*c63+6*c64+11*c65+13*c66;c11+c12+c13+c14+c15+c16=1; c21+c22+c23+c24+c25+c26=1;c31+c32+c33+c34+c35+c36=1; c41+c42+c43+c44+c45+c46=1;c51+c52+c53+c54+c55+c56=1; c61+c62+c63+c64+c65+c66=1;c11+c21+c31+c41+c51+c61=1; c12+c22+c32+c42+c52+c62=1;c13+c23+c33+c43+c53+c63=1; c14+c24+c34+c44+c54+c64=1;c15+c25+c35+c45+c55+c65=1; c16+c26+c36+c46+c56+c66=1;@bin(c11);@bin(c12);@bin(c13);@bin(c14);@bin(c15);@bin(c16);@bin(c21);@bin(c22);@bin(c23);@bin(c24);@bin(c25);@bin(c26);@bin(c31);@bin(c32);@bin(c33);@bin(c34);@bin(c35);@bin(c36);@bin(c41);@bin(c42);@bin(c43);@bin(c44);@bin(c45);@bin(c46);@bin(c51);@bin(c52);@bin(c53);@bin(c54);@bin(c55);@bin(c56);@bin(c61);@bin(c62);@bin(c63);@bin(c64);@bin(c65);@bin(c66);Lingo输出（结果）框：Global optimal solution found.Objective value: 142.0000 Extended solversteps: 0 Total solver iterations: 0Variable Value Reduced CostC11 1.000000 -20.00000 C120.000000 -15.00000 C13 0.000000-16.00000 C14 0.000000 -5.000000 C15 0.000000 -4.000000C16 0.000000 -7.000000 C210.000000 -17.00000 C22 0.000000-15.00000 C23 1.000000 -33.00000 C24 0.000000 -12.00000 C250.000000 -8.000000 C26 0.000000-6.000000 C31 0.000000 -9.000000 C32 0.000000 -12.00000 C330.000000 -18.00000 C34 0.000000-16.00000 C35 1.000000 -30.00000 C36 0.000000 -13.00000 C410.000000 -12.00000 C42 0.000000-8.000000 C43 0.000000 -11.00000 C44 1.000000 -27.00000 C450.000000 -19.00000 C46 0.000000-14.00000 C51 0.000000 0.000000 C52 0.000000 -7.000000 C530.000000 -10.00000 C54 0.000000-21.00000 C55 0.000000 -10.00000 C56 1.000000 -32.00000 C610.000000 0.000000 C62 1.0000000.000000 C63 0.000000 0.000000 C64 0.000000 -6.000000 C650.000000 -11.00000 C66 0.000000-13.00000Row Slack or Surplus Dual Price 1142.0000 1.000000 2 0.0000000.000000 3 0.000000 0.000000 4 0.000000 0.000000 50.000000 0.000000 6 0.0000000.000000 7 0.000000 0.000000 8 0.000000 0.000000 90.000000 0.000000 10 0.0000000.000000 11 0.000000 0.00000012 0.000000 0.000000 130.000000 0.000000（二）循环语句求解 Lingo输入框： model: sets:gz/A1..A6/:a; ry/B1..B6/:b; yw(gz,ry):xy,x; endsets data:a=1,1,1,1,1,1; b=1,1,1,1,1,1; xy=20 15 16 5 4 7, 17 15 33 12 8 6, 912 18 16 30 13, 12 8 11 27 19 14, 0 7 10 21 10 32, 0 0 0 6 11 13;enddatamax=@sum(yw:xy*x);@for(gz(i):@sum(ry(j):x(i,j))=1); @for(ry(j):@sum(gz(i):x(i,j))=1);@for(yw(i,j):@bin(x(i,j))); EndLingo输出（结果）框Global optimal solution found.Objective value: 142.0000 Extended solversteps: 0 Total solver iterations: 0Variable Value Reduced CostA( A1) 1.000000 0.000000 A( A2)1.000000 0.000000 A( A3) 1.0000000.000000 A( A4) 1.000000 0.000000 A( A5) 1.000000 0.000000 A( A6)1.000000 0.000000 B( B1) 1.0000000.000000 B( B2) 1.000000 0.000000B( B3) 1.000000 0.000000 B( B4)1.000000 0.000000 B( B5) 1.0000000.000000 B( B6) 1.000000 0.000000 XY( A1, B1) 20.00000 0.000000 XY( A1, B2)15.00000 0.000000 XY( A1, B3) 16.000000.000000 XY( A1, B4) 5.000000 0.000000 XY( A1, B5) 4.000000 0.000000 XY( A1, B6)7.000000 0.000000 XY( A2, B1) 17.000000.000000 XY( A2, B2) 15.00000 0.000000 XY( A2, B3) 33.00000 0.000000 XY( A2, B4)12.00000 0.000000 XY( A2, B5) 8.0000000.000000 XY( A2, B6) 6.000000 0.000000 XY( A3, B1) 9.000000 0.000000 XY( A3, B2)12.00000 0.000000 XY( A3, B3) 18.000000.000000 XY( A3, B4) 16.00000 0.000000 XY( A3, B5) 30.00000 0.000000 XY( A3, B6)13.00000 0.000000 XY( A4, B1) 12.000000.000000 XY( A4, B2) 8.000000 0.000000 XY( A4, B3) 11.00000 0.000000 XY( A4, B4)27.00000 0.000000 XY( A4, B5) 19.000000.000000 XY( A4, B6) 14.00000 0.000000 XY( A5, B1) 0.000000 0.000000 XY( A5, B2)7.000000 0.000000 XY( A5, B3) 10.000000.000000 XY( A5, B4) 21.00000 0.000000 XY( A5, B5) 10.00000 0.000000 XY( A5, B6)32.00000 0.000000 XY( A6, B1) 0.0000000.000000 XY( A6, B2) 0.000000 0.000000 XY( A6, B3) 0.000000 0.000000 XY( A6, B4)6.000000 0.000000 XY( A6, B5) 11.000000.000000 XY( A6, B6) 13.00000 0.000000 X( A1, B1) 1.000000 -20.00000 X( A1, B2)0.000000 -15.00000 X( A1, B3) 0.000000-16.00000 X( A1, B4) 0.000000 -5.000000感谢您的阅读，祝您生活愉快。

第一章绪论1、指派问题的背景及意义指派问题又称分配问题，其用途非常广泛，比如某公司指派n个人去做n 件事，各人做不同的一件事，如何安排人员使得总费用最少？若考虑每个职工对工作的效率（如熟练程度等），怎样安排会使总效率达到最大？这些都是一个企业经营管理者必须考虑的问题，所以该问题有重要的应用价值.虽然指派问题可以用0-1规划问题来解，设X(I,J)是0-1变量, 用X(I,J)=1表示第I个人做第J件事, X(I,J)=0表示第I个人不做第J件事. 设非负矩阵C（I，J）表示第I个人做第J件事的费用，则问题可以写成LINGO程序SETS:PERSON/1..N/;WORK/1..N/;WEIGHT(PERSON, WORK): C, X ;ENDSETSDATA:W=…ENDDATAMIN=@ SUM(WEIGHT: C*X);@FOR(PERSON(I): @SUM(WORK(J):X(I,J))=1);@FOR(WORK(J): @SUM(PERSONM(I):X(I,J))=1);@FOR(WEIGHT: @BIN(X));其中2*N个约束条件是线性相关的, 可以去掉任意一个而得到线性无关条件.但是由于有N^2个0-1变量, 当N很大时，用完全枚举法解题几乎是不可能的. 而已有的0-1规划都是用隐枚举法做的，计算量较大. 对于指派问题这种特殊的0-1规划，有一个有效的方法——匈牙利算法，是1955年W. W. Kuhn利用匈牙利数学家D.König的二部图G的最大匹配的大小等于G的最小顶点覆盖的大小的定理提出的一种算法，这种算法是多项式算法，计算量为O(N3).匈牙利算法的基本原理是基于以下两个定理.定理1设C=(C ij)n×n是指派问题的效益矩阵，若将C中的任一行（或任一列）减去该行（或该列）中的最小元素，得到新的效率矩阵C’，则C’对应的新的指派问题与原指派问题有相同的最优解.证明：设X’是最优解, 即@SUM(WEIGHT: C*X’)<= @SUM(WEIGHT: C*X), 则当C中任一行或任一列减去该行或该列的最小数m时,得到的阵C’还是非负矩阵, 且@SUM(WEIGHT: C’*X’)<=@SUM(WEIGHT: C*X)-m=@SUM(WEIGHT: C’*X)定理2效率矩阵C中独立的0元素的最多个数等于覆盖所有0元素的最少直线数. 当独立零元素的个数等于矩阵的阶数时就得到最优解.3、理论基础定义:图G的一个匹配M是图G中不相交的边的集合. 属于匹配M中的边的所有端点称为被该匹配M饱和, 其他的顶点称为M-未饱和的. 如果一个匹配M 饱和了图G的所有顶点，则称该匹配M是一个完全匹配. 可见顶点数是奇数的图没有完全匹配. 一个匹配M称为是极大匹配, 如果它不能再扩张成更大的一个匹配. 一个匹配称为是最大匹配, 如果不存在比它更大的匹配.定义:对于一个匹配M, 图G的一个M-交替路是图G中的边交替地在M中及不在M中的边组成. 从M-未饱和点出发到M-为饱和点结束的M-交替路称为一条M-增广路. 把M-增广路中不是M中的边改成新的匹配M’中的边, 把M-增广路中M中的边不作为M’中的边, 在M-增广路以外的M中的边仍作为M’中的边, 则M’的大小比M大1. 故名M-增广路. 因此最大匹配M不存在M-增广路.定义:若图G和图H有相同的顶点集V, 我们称G和H的对称差,记为G∆H,是一个以V为顶点集的图, 但其边集是G和H的边集的对称差: E(G∆H)=E(G) ∆E(H)=E(G)⋂E(H)-(E(G)⋃E(H))=(E(G)-E(H)) ⋂ (E(H)-E(G))定理: (Berge, 1957) 图G的一个匹配M是最大匹配,当且仅当G中没有M-增广路.证明: 我们只要证明, G中没有M-增广路时, M是最大匹配. 用反证法, 若有一个比M大的匹配M’. 令G的一个子图F, E(F)=M∆M’, 因M和M’都是匹配, F的顶点的最大度数至多是2, 从而F由不相交的路和环组成, 它们的边交替地来自M和M’, 于是F中的环的长度是偶数. 由于M’比M大, F中存在一个连通分支,其中M’中的边数大于M中的边数. 这个分支只能是起始和终止的边都在M’中. 而这就是一条G中的M-增广路. 与假设矛盾. 证毕.定理(Hall, 1935)设G是一个二部图, X和Y是其二分集, 则存在匹配M 饱和X当且仅当对于X中的任意子集S, Y 中与S中的点相邻的点组成的集合N(S)中元素的个数大于等于集合S中元素的个数.证明：必要性是显然的. 对于充分性, 假设 |N(S)|≥|S|, ∀S⊂X, 考虑G的一个最大匹配M, 我们用反证法，若M没有饱和X, 我们来找一个集合S不满足假设即可. 设u∈X是一个M-未饱和顶点, 令S⊂X和T⊂Y分别是从u出发的M-交替路上相应的点.我们来证明M中的一些边是T到S-u上的一个匹配. 因为不存在M-增广路，T中的每个点是M-饱和的. 这意味着T中的点通过M中的边到达S中的一个顶点. 另外, S-u中的每个顶点是从T中的一个顶点通过M中的一条边到达的. 因此M 中的这些边建立了T与S-u的一个双射, 即|T|=|S-u|. 这就证明了M中的这些边是T到S-u上的一个匹配，从而意味着T⊂N(S), 实际上, 我们可证明T=N(S). 这是因为连接S和Y-T中的点y的边是不属于M的, 因为不然的话, 就有一条到达y的M-增广路, 与y∉T矛盾. 故|N(S)|=|T|=|S-u|=|S|-1<|S|, 与假设矛盾.当X与Y的集合的大小相同时的Hall定理称为婚姻问题,是由Frobenius(1917)证明的.推论: k-正则的二部图（X的每一点和Y的每一点相关联的二部图）(k>0)存在完全匹配.证明: 设二分集是X,Y. 分别计算端点在X和端点在Y的边的个数, 得k|X|=k|Y|, 即|X|=|Y|.因此只要证明Hall的条件成立即可. 使X饱和的匹配就是完全匹配. 考虑∀S⊂X, 设连接S与N(S)有m条边, 由G的正则性, m=k|S|. 因这m条边是与N(S)相关联的, m≤k|N(S)|, 即k|S|≤ k|N(S)|, 即|N(S)|≥|S|. 这就是Hall的条件.用求M-增广路的方法来得到最大匹配是很费时的. 我们来给出一个对偶最优化问题.定义:图G的一个顶点覆盖是集合S⊂V(G), 使得G的每条边至少有一个端点在S中. 我们称S中的一个顶点覆盖一些边, 若这个顶点是这些边的公共端点.因为匹配的任意两条边不能被同一个顶点覆盖, 所以顶点覆盖的大小不小于匹配的大小: |S|≥|M|. 所以当|S|=|M| 时就同时得到了最大的匹配和最小的顶点覆盖.定理(König [1931],Egerváry[1931])二部图G的最大匹配的大小等于G的最小顶点覆盖的大小.证明: 设M是G的任一个匹配, 对应的二分集是X,Y. 设U是一个最小的顶点覆盖, 则|U|≥|M|, 我们只要由顶点覆盖U来构造一个大小等于|U|的匹配即完成证明. 令R=U⋃X, T=U⋃Y, 令H, H’分别是由顶点集R⋂(Y-T)及T⋂(X-R)诱导的G的子图. 我们应用Hall的定理来证明H有一个R到Y-T中的完全匹配，H’有一个从T到X-R中的完全匹配. 再因这两个子图是不相交的, 这两个匹配合起来就是G中的一个大小为|U|的匹配.因为R⋂T是G的一个覆盖, Y-T与X-R之间没有边相联接. 假设S⊂R, 考虑在H中S的邻接顶点集N(S), N(S) ⊂Y-T. 如果|N(S)|<|S|, 因为N(S)覆盖了不被T覆盖的与S相关联所有边, 我们可以把N(S) 代替S作为U中的顶点覆盖而得到一个更小的顶点覆盖. U的最小性意味着H中Hall条件成立. 对H'作类似的讨论得到余下的匹配. 证毕.最大匹配的增广路算法输入: 一个二分集为X，Y的二部图G，一个G中的匹配M， X中的M-未饱和顶点的集合U.思路: 从U出发探求M-交替路，令S⊂X，T⊂Y为这些路到达过的顶点集. 标记S中不能再扩张的顶点. 对于每个x∈(S⋂T)-U, 记录在M-增广路上位于x前的点.初始化: S=U,T=∅.叠代: 若S中没有未标记过的顶点, 结束并报告T⋂(X-S)是最小顶点覆盖而M是最大匹配.不然, 选取S中未标记的点x, 考虑每个y∈N(x)且xy∉M, 若y是M-未饱和的, 则得到一个更大的匹配，它是把xy加入原来的匹配M得到的,将x从S中去除. 不然, y是由M中的一条边wy相连接的, w∈X, 把y加入T(也有可能y本来就在T中), 把w加入S. w未标记, 记录w前的点是y. 对所有关联到x的边进行这样的探索后, 标记x. 再次叠代.定理: 增广路算法可以得到一个相同大小的匹配和顶点覆盖.证明: 考虑这个算法终止的情况, 即标记了S中所有的点. 我们要证明R=T⋂(X-S)是大小为|M|的一个顶点覆盖.从U出发的M-交替路只能通过M中的边进入X中的顶点, 所以S-U中的每个顶点通过M与T中的顶点匹配, 并且没有M中的边连接S和Y-T. 一旦一条M-交替路到达x∈S, 可以继续沿着任何未饱和的边进入T, 由于算法是对于x的所有邻域顶点进行探索才终止的,所以从S 到Y-T 没有未饱和边. 从而S 到Y-T 没有边, 证明了R 是一个顶点覆盖.因为算法是找不到M-增广路时终止, T 的每一个顶点是饱和的. 这意味着每个顶点y ∈T 是通过M 匹配与S 中的一个顶点. 由于U ⊂S, X-S 的每个顶点是饱和的, 故M 中与X-S 相关联的边不和T 中的点相连接. 即它们与是饱和T 的边不同的, 这样我们可见M 至少有|T|+|X-S|条边. 因不存在一个比顶点覆盖更大的匹配， 所以有|M|=|T|+|X-S|=|R|.设二部图G 的二分集X 和Y 都是n 个元素的点集, 在其边j i y x 上带有非负的权ij w , 对于G 的一个匹配M, M 上各边的权和记作w(M).定义: 一个n ×n 矩阵A 的一个横截(transversal)是A 中的n 个位置, 使得在每行每列中有且只有一个位置（有的文献中把横截化为独立零元素的位置来表示）.定义: 指派问题就是给定一个图G=n n K ,(完全二部图, 即每个X 中的顶点和Y 中的每个顶点有边相连接的二部图)的边的权矩阵A, 求A 的一个横截, 使得这个横截上位置的权和最大. 这是最大带权匹配问题的矩阵形式.定义: 对于图G=n n K ,，设其二分集是X ，Y ，给定G 的边j i y x 的n ×n 权矩阵W={ij w }.考虑G 的子图v u G ,, 设其二分集是U ⊂X ，V ⊂Y, 边集是E(v u G ,)， 对于子图v u G ,的带权覆盖u,v 是一组非负实数{i u },{j v },使得ij j i w v u ≥+,)(,v u j i G E y x ∈∀, v u G ,的带权覆盖的费用是∑∑+j i v u 记为C(u,v), 最小带权覆盖问题就是求一个具有最小费用C(u,v)的带权覆盖u,v.引理: 若M ⊂E(v u G ,)是一个带权二部子图v u G ,的最大匹配, 且u, v 是v u G ,的带权覆盖, 则C(u,v)≥w(M). 而且, C(u,v)=w(M)当且仅当ij j i w v u =+，M y x j i ∈∀. 这时M 是v u G ,最大带权匹配, u,v 是v u G ,的最小带权覆盖， 定义这时的v u G ,为G 的相等子图（equality subgraph ）.证明: 因为匹配M 中的边是不相交的, 由带权覆盖的定义就得C(u,v)≥w(M). 而且C(u,v)=w(M)当且仅当ij j i w v u =+，M y x j i ∈∀成立. 因一般地有C(u,v)≥w(M).所以当C(u,v)=w(M)时. 意味着没有一个匹配的权比C(u,v)大, 也没有一个覆盖的费用比w(M)小.Kuhn 得到一个指派问题的算法，命名为匈牙利算法, 为的是将荣耀归于匈牙利数学家König 和Egerv áry.指派问题的匈牙利算法(Kuhn[1955], Munkres[1957]):输入G=n n K ,的边的权矩阵A, 及G 的二分集X,Y.初始化: 任取一个可行的带权覆盖，例如)(max ij ji w u =，0=j v ，建立G 的相等子图v u G ,, 其二分集是X, Y ’⊂Y, 求v u G ,的一个最大匹配M. 这个匹配的权和w(M)=C(u,v), M 的带权覆盖是具有最小费用的.叠代: 如M 是G 的一个完全匹配, 停止叠代, 输出最大带权匹配M. 不然, 令U 是X 中的M-未饱和顶点. 令S ⊂X, T ⊂Y 是从U 中顶点出发的M-交替路到达的顶点的集合.令},:min{T Y y S x w v u j i ij j i -∈∈-+=ε.对于所有的S x i ∈, 将i u 减少ε, 对于所有的T y j ∈,将j v 增加ε,形成新的带权覆盖u ’,v ’及对应的新的相等子图v u G '',.如果这个新的相等子图含有M-增广路, 求它的最大匹配M ’, 不然不改变M 再进行叠代.定理: 匈牙利算法能找到一个最大权匹配和一个最小费用覆盖.证明: 算法由一个覆盖开始，算法的每个叠代产生一个覆盖，仅在相等子图有一个完全的匹配为止。