指派问题_匈牙利算法

最大化指派问题匈牙利算法匈牙利算法，也称为Kuhn-Munkres算法，是用于解决最大化指派问题（Maximum Bipartite Matching Problem）的经典算法。

最大化指派问题是在一个二分图中，找到一个匹配（即边的集合），使得匹配的边权重之和最大。

下面我将从多个角度全面地介绍匈牙利算法。

1. 算法原理：匈牙利算法基于增广路径的思想，通过不断寻找增广路径来逐步扩展匹配集合，直到无法找到增广路径为止。

算法的基本步骤如下：初始化，将所有顶点的标记值设为0，将匹配集合初始化为空。

寻找增广路径，从未匹配的顶点开始，依次尝试匹配与其相邻的未匹配顶点。

如果找到增广路径，则更新匹配集合；如果无法找到增广路径，则进行下一步。

修改标记值，如果无法找到增广路径，则通过修改标记值的方式，使得下次寻找增广路径时能够扩大匹配集合。

重复步骤2和步骤3，直到无法找到增广路径为止。

2. 算法优势：匈牙利算法具有以下优势：时间复杂度较低，匈牙利算法的时间复杂度为O(V^3)，其中V是顶点的数量。

相比于其他解决最大化指派问题的算法，如线性规划算法，匈牙利算法具有更低的时间复杂度。

可以处理大规模问题，由于时间复杂度较低，匈牙利算法可以处理大规模的最大化指派问题，而不会因为问题规模的增加而导致计算时间大幅增加。

3. 算法应用：匈牙利算法在实际中有广泛的应用，例如：任务分配，在人力资源管理中，可以使用匈牙利算法将任务分配给员工，使得任务与员工之间的匹配最优。

项目分配，在项目管理中，可以使用匈牙利算法将项目分配给团队成员，以最大程度地提高团队成员与项目之间的匹配度。

资源调度，在物流调度中，可以使用匈牙利算法将货物分配给合适的运输车辆，使得货物与运输车辆之间的匹配最优。

4. 算法扩展：匈牙利算法也可以扩展到解决带权的最大化指派问题，即在二分图的边上赋予权重。

在这种情况下，匈牙利算法会寻找一个最优的匹配，使得匹配边的权重之和最大。

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

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

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

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

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

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

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

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

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

关键词：指派问题；匈牙利算法；0-1整数规划；matlab模型；lingo模型AbstractIn business, the company's operations and management, managers always want the best distribution of the staff to maximize their efficiency, reduce costs and improve efficiency. However, if there is no scientific method is difficult to achieve optimal management, which we introduced the assignment problem. Multi-assignment problem is to get the project working hours at least, and in many cases people do not care about how much the total project work, but only care about whether the project can be completed within the shortest possible time, that lasted for at least the assignment problem. Such problems is the n individual execution of tasks n, the number of people to perform each task and assign the total number of items are restricted to two people, requiring the optimal assignment. Integer programming in operations research for solving the assignment problem is usually solved by Hungarian algorithm, but the assignment problem can be reduced to a 0-1 integer programming problem, this paper first to make a statement on the assignment problem, leads to the solution of practical problems. Assignment problem in the background to fully understand the problem description, the first assignment problem using Hungarian algorithm, and then a 0-1 integer programming model and compiler using matlab and the lingo of the problem to be compiled using the software solution model problem Ultimately in the assignment of the application in practical problems. By using the Hungarian algorithm and the 0-1 integer programming to solve assignment problems simultaneously, we found that 0-1 integer programming method to solve a more simple and easier to read and understand the program. At the same time, we also 0-1 integer programming problem in-depth study by the integer data to a decimal data. Finally, an example to illustrate the use of matlab, lingo compiler to solve the integer programming problem is simple and effective.Keywords:assignment problem; Hungarian algorithm; 0-1 integer programming;matlab model; lingo model目录1. 问题陈述 (1)2. 指派问题的背景 (1)3. 指派问题的描述 (1)3.1 指派问题的一般形式 (1)3.2 问题的数学模型一般形式 (2)3.3 目标函数极大化的指派问题 (2)4．指派问题实现 (3)4.1 匈牙利算法 (3)4.1.1 匈牙利算法的理论基础 (3)4.1.2 匈牙利算法的实现步骤 (3)4.1.3 匈牙利算法实现指派问题 (4)4.2 0-1整数规划 (5)4.2.1 模型假设 (6)4.2.2 模型建立 (6)4.2.3 模型求解 (7)5. 问题的深入（0-1整数规划） (10)5.1 模型建立 (10)5.2 模型求解 (11)5.2.1 用matlab求解问题 (11)5.2.2 用lingo求解问题 (12)6. 结论 (14)6.1 总结概论 (14)6.2 具体分工.................................. 错误！未定义书签。

指派问题匈牙利算法最大值
指派问题是一个优化问题，旨在确定如何将 n 个任务分配给 n 个人员，以便完成总成本最小或总利润最大。

匈牙利算法是解决指派问题的经典算法之一，通过寻找增广路径来找到最大权值的匹配。

在指派问题中，我们有一个 n x n 的成本矩阵，其中的每个元素表
示将特定任务分配给特定人员的成本或利润。

问题的目标是找到一种分配方式，使得总成本最小或总利润最大。

匈牙利算法是一种基于图论的算法，它通过构建二分图和寻找增广路径来解决指派问题。

算法的核心思想是通过不断改进当前的匹配，直到找到最优解。

具体来说，匈牙利算法的步骤如下：
1. 初始化一个空的匹配集合。

2. 对于每个任务，找到一个未被分配的人员，并将其分配给该任务。

如果该任务没有未被分配的人员，则考虑将其他任务分配给当前人员，并将当前任务分配给其它人员。

3. 如果存在一个未被匹配的任务，寻找一条从该任务出发的增广路径。

增广路径是一条交替经过匹配边和非匹配边的路径，起点和终点都是未匹配的任务。

4. 如果存在增广路径，则改进当前的匹配，即通过将增广路径上的
非匹配边变为匹配边，并将增广路径上的匹配边变为非匹配边。

5. 重复步骤3和步骤4，直到不存在增广路径为止。

匈牙利算法的运行时间复杂度为 O(n^3)，其中 n 是任务或人员的数量。

该算法可以找到指派问题的最优解，并且在实践中表现良好。

总之，指派问题是一个重要的优化问题，而匈牙利算法是一种解决指派问题的经典算法。

通过构建二分图并寻找增广路径，匈牙利算法可以找到指派问题的最优解。

3.2 求解指派问题的匈牙利算法由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig 提出的更为简便的解法—匈牙利算法。

算法主要依据以下事实：如果系数矩阵)(ij c C =一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵)(ij b B = ，则以C 或B 为系数矩阵的指派问题具有相同的最优指派。

利用上述性质，可将原系数阵C 变换为含零元素较多的新系数阵B ，而最优解不变。

若能在B 中找出n 个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为零，则所得该解是以B 为系数阵的指派问题的最优解，从而也是原问题的最优解。

由C 到B 的转换可通过先让矩阵C 的每行元素均减去其所在行的最小元素得矩阵D ，D 的每列元素再减去其所在列的最小元素得以实现。

下面通过一例子来说明该算法。

例7 求解指派问题，其系数矩阵为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=16221917171822241819211722191516C 解 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=06310157124074011B 再将第3列元素各减去1，得⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=****20531005711407301B 以2B 为系数矩阵的指派问题有最优指派⎪⎪⎭⎫ ⎝⎛43124321 由等价性，它也是例7的最优指派。

有时问题会稍复杂一些。

例8 求解系数矩阵C 的指派问题⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=61071041066141512141217766698979712C 解：先作等价变换如下∨∨∨⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡→⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡----- 2636040*08957510*00*0032202*056107104106614151214121776669897971246767 容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但5=n ，最优指派还无法看出。

运筹学课程设计指派问题的匈牙利法专业：姓名：学号：1.算法思想：匈牙利算法的基本思想是修改效益矩阵的行或列，使得每一行或列中至少有一个为零的元素，经过修正后，直至在不同行、不同列中至少有一个零元素，从而得到与这些零元素相对应的一个完全分配方案。

当它用于效益矩阵时，这个完全分配方案就是一个最优分配，它使总的效益为最小。

这种方法总是在有限步內收敛于一个最优解。

该方法的理论基础是：在效益矩阵的任何行或列中，加上或减去一个常数后不会改变最优分配。

2.算法流程或步骤：1.将原始效益矩阵C的每行、每列各元素都依次减去该行、该列的最小元素，使每行、每列都至少出现一个0元素，以构成等价的效益矩阵C’。

2.圈0元素。

在C’中未被直线通过的含0元素最少的行（或列）中圈出一个0元素，通过这个0元素作一条竖（或横）线。

重复此步，若这样能圈出不同行不同列的n个0元素，转第四步，否则转第三步。

3.调整效益矩阵。

在C’中未被直线穿过的数集D中，找出最小的数d，D中所有数都减去d，C’中两条直线相交处的数都加的d。

去掉直线，组成新的等价效益矩阵仍叫C’，返回第二步。

X=0，这就是一种最优分配。

最低总4.令被圈0元素对应位置的X ij=1,其余ij耗费是C中使X=1的各位置上各元素的和。

ij算法流程图：3.算法源程序：#include<iostream.h>typedef struct matrix{float cost[101][101];int zeroelem[101][101];float costforout[101][101];int matrixsize;int personnumber;int jobnumber;}matrix;matrix sb;int result[501][2];void twozero(matrix &sb);void judge(matrix &sb,int result[501][2]);void refresh(matrix &sb);void circlezero(matrix &sb);matrix input();void output(int result[501][2],matrix sb);void zeroout(matrix &sb);matrix input(){matrix sb;int m;int pnumber,jnumber;int i,j;float k;char w;cout<<"指派问题的匈牙利解法:"<<endl;cout<<"求最大值，请输入1;求最小值，请输入0:"<<endl;cin>>m;while(m!=1&&m!=0){cout<<"请输入1或0:"<<endl;cin>>m;}cout<<"请输入人数(人数介于1和100之间):"<<endl;cin>>pnumber;while(pnumber<1||pnumber>100){cout<<"请输入合法数据:"<<endl;cin>>pnumber;}cout<<"请输入工作数(介于1和100之间):"<<endl;cin>>jnumber;while(jnumber<1||jnumber>100){cout<<"请输入合法数据:"<<endl;cin>>jnumber;}cout<<"请输入"<<pnumber<<"行"<<jnumber<<"列的矩阵,同一行内以空格间隔,不同行间以回车分隔,以$结束输入:\n";for(i=1;i<=pnumber;i++)for(j=1;j<=jnumber;j++){cin>>sb.cost[i][j];sb.costforout[i][j]=sb.cost[i][j];}cin>>w;if(jnumber>pnumber)for(i=pnumber+1;i<=jnumber;i++)for(j=1;j<=jnumber;j++){sb.cost[i][j]=0;sb.costforout[i][j]=0;}else{if(pnumber>jnumber)for(i=1;i<=pnumber;i++)for(j=jnumber+1;j<=pnumber;j++){sb.cost[i][j]=0;sb.costforout[i][j]=0;}}sb.matrixsize=pnumber;if(pnumber<jnumber)sb.matrixsize=jnumber;sb.personnumber=pnumber;sb.jobnumber=jnumber;if(m==1){k=0;for(i=1;i<=sb.matrixsize;i++)for(j=1;j<=sb.matrixsize;j++)if(sb.cost[i][j]>k)k=sb.cost[i][j];for(i=1;i<=sb.matrixsize;i++)for(j=1;j<=sb.matrixsize;j++)sb.cost[i][j]=k-sb.cost[i][j];}return sb;}void circlezero(matrix &sb){int i,j;float k;int p;for(i=0;i<=sb.matrixsize;i++)sb.cost[i][0]=0;for(j=1;j<=sb.matrixsize;j++)sb.cost[0][j]=0;for(i=1;i<=sb.matrixsize;i++)for(j=1;j<=sb.matrixsize;j++)if(sb.cost[i][j]==0){sb.cost[i][0]++;sb.cost[0][j]++;sb.cost[0][0]++;}for(i=0;i<=sb.matrixsize;i++)for(j=0;j<=sb.matrixsize;j++)sb.zeroelem[i][j]=0;k=sb.cost[0][0]+1;while(sb.cost[0][0]<k){k=sb.cost[0][0];for(i=1;i<=sb.matrixsize;i++){if(sb.cost[i][0]==1){for(j=1;j<=sb.matrixsize;j++)if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0)break;sb.zeroelem[i][j]=1;sb.cost[i][0]--;sb.cost[0][j]--;sb.cost[0][0]--;if(sb.cost[0][j]>0)for(p=1;p<=sb.matrixsize;p++)if(sb.cost[p][j]==0&&sb.zeroelem[p][j]==0){sb.zeroelem[p][j]=2;sb.cost[p][0]--;sb.cost[0][j]--;sb.cost[0][0]--;}}}for(j=1;j<=sb.matrixsize;j++){if(sb.cost[0][j]==1){for(i=1;i<=sb.matrixsize;i++)if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0)break;sb.zeroelem[i][j]=1;sb.cost[i][0]--;sb.cost[0][j]--;sb.cost[0][0]--;if(sb.cost[i][0]>0)for(p=1;p<=sb.matrixsize;p++)if(sb.cost[i][p]==0&&sb.zeroelem[i][p]==0){sb.zeroelem[i][p]=2;sb.cost[i][0]--;sb.cost[0][p]--;sb.cost[0][0]--;}}}}if(sb.cost[0][0]>0)twozero(sb);elsejudge(sb,result);}void twozero(matrix &sb){int i,j;int p,q;int m,n;float k;matrix st;for(i=1;i<=sb.matrixsize;i++)if(sb.cost[i][0]>0)break;if(i<=sb.matrixsize){for(j=1;j<=sb.matrixsize;j++){st=sb;if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0){sb.zeroelem[i][j]=1;sb.cost[i][0]--;sb.cost[0][j]--;sb.cost[0][0]--;for(q=1;q<=sb.matrixsize;q++)if(sb.cost[i][q]==0&&sb.zeroelem[i][q]==0){sb.zeroelem[i][q]=2;sb.cost[i][0]--;sb.cost[0][q]--;sb.cost[0][0]--;}for(p=1;p<=sb.matrixsize;p++)if(sb.cost[p][j]==0&&sb.zeroelem[p][j]==0){sb.zeroelem[p][j]=2;sb.cost[p][0]--;sb.cost[0][j]--;sb.cost[0][0]--;}k=sb.cost[0][0]+1;while(sb.cost[0][0]<k){k=sb.cost[0][0];for(p=i+1;p<=sb.matrixsize;p++){if(sb.cost[p][0]==1){for(q=1;q<=sb.matrixsize;q++)if(sb.cost[p][q]==0&&sb.zeroelem[p][q]==0)break;sb.zeroelem[p][q]=1;sb.cost[p][0]--;sb.cost[0][q]--;sb.cost[0][0]--;for(m=1;m<=sb.matrixsize;m++)if(sb.cost[m][q]=0&&sb.zeroelem[m][q]==0){sb.zeroelem[m][q]=2;sb.cost[m][0]--;sb.cost[0][q]--;sb.cost[0][0]--;}}}for(q=1;q<=sb.matrixsize;q++){if(sb.cost[0][q]==1){for(p=1;p<=sb.matrixsize;p++)if(sb.cost[p][q]==0&&sb.zeroelem[p][q]==0)break;sb.zeroelem[p][q]=1;sb.cost[p][q]--;sb.cost[0][q]--;sb.cost[0][0]--;for(n=1;n<=sb.matrixsize;n++)if(sb.cost[p][n]==0&&sb.zeroelem[p][n]==0){sb.zeroelem[p][n]=2;sb.cost[p][0]--;sb.cost[0][n]--;sb.cost[0][0]--;}}}}if(sb.cost[0][0]>0)twozero(sb);elsejudge(sb,result);}sb=st;}}}void judge(matrix &sb,int result[501][2]){int i,j;int m;int n;int k;m=0;for(i=1;i<=sb.matrixsize;i++)for(j=1;j<=sb.matrixsize;j++)if(sb.zeroelem[i][j]==1)m++;if(m==sb.matrixsize){k=1;for(n=1;n<=result[0][0];n++){for(i=1;i<=sb.matrixsize;i++){for(j=1;j<=sb.matrixsize;j++)if(sb.zeroelem[i][j]==1)break;if(i<=sb.personnumber&&j<=sb.jobnumber)if(j!=result[k][1])break;k++;}if(i==sb.matrixsize+1)break;elsek=n*sb.matrixsize+1;}if(n>result[0][0]){k=result[0][0]*sb.matrixsize+1;for(i=1;i<=sb.matrixsize;i++)for(j=1;j<=sb.matrixsize;j++)if(sb.zeroelem[i][j]==1){result[k][0]=i;result[k++][1]=j;}result[0][0]++;}}else{refresh(sb);}}void refresh(matrix &sb){int i,j;float k;int p;k=0;for(i=1;i<=sb.matrixsize;i++){for(j=1;j<=sb.matrixsize;j++)if(sb.zeroelem[i][j]==1){sb.zeroelem[i][0]=1;break;}}while(k==0){k=1;for(i=1;i<=sb.matrixsize;i++)if(sb.zeroelem[i][0]==0){sb.zeroelem[i][0]=2;for(j=1;j<=sb.matrixsize;j++)if(sb.zeroelem[i][j]==2){sb.zeroelem[0][j]=1;}}for(j=1;j<=sb.matrixsize;j++){if(sb.zeroelem[0][j]==1){sb.zeroelem[0][j]=2;for(i=1;i<=sb.matrixsize;i++)if(sb.zeroelem[i][j]==1){sb.zeroelem[i][0]=0;k=0;}}}}p=0;k=0;for(i=1;i<=sb.matrixsize;i++){if(sb.zeroelem[i][0]==2){for(j=1;j<=sb.matrixsize;j++){if(sb.zeroelem[0][j]!=2)if(p==0){k=sb.cost[i][j];p=1;}else{if(sb.cost[i][j]<k)k=sb.cost[i][j];}}}}for(i=1;i<=sb.matrixsize;i++){if(sb.zeroelem[i][0]==2)for(j=1;j<=sb.matrixsize;j++)sb.cost[i][j]=sb.cost[i][j]-k;}for(j=1;j<=sb.matrixsize;j++){if(sb.zeroelem[0][j]==2)for(i=1;i<=sb.matrixsize;i++)sb.cost[i][j]=sb.cost[i][j]+k;}for(i=0;i<=sb.matrixsize;i++)for(j=0;j<=sb.matrixsize;j++)sb.zeroelem[i][j]=0;circlezero(sb);}void zeroout(matrix &sb){int i,j;float k;for(i=1;i<=sb.matrixsize;i++){k=sb.cost[i][1];for(j=2;j<=sb.matrixsize;j++)if(sb.cost[i][j]<k)k=sb.cost[i][j];for(j=1;j<=sb.matrixsize;j++)sb.cost[i][j]=sb.cost[i][j]-k;}for(j=1;j<=sb.matrixsize;j++){k=sb.cost[1][j];for(i=2;i<=sb.matrixsize;i++)if(sb.cost[i][j]<k)k=sb.cost[i][j];for(i=1;i<=sb.matrixsize;i++)sb.cost[i][j]=sb.cost[i][j]-k;}}void output(int result[501][2],matrix sb) {int k;int i;int j;int p;char w;float v;v=0;for(i=1;i<=sb.matrixsize;i++){v=v+sb.costforout[i][result[i][1]];}cout<<"最优解的目标函数值为"<<v;k=result[0][0];if(k>5){cout<<"解的个数超过了限制."<<endl;k=5;}for(i=1;i<=k;i++){cout<<"输入任意字符后输出第"<<i<<"种解."<<endl;cin>>w;p=(i-1)*sb.matrixsize+1;for(j=p;j<p+sb.matrixsize;j++)if(result[j][0]<=sb.personnumber&&result[j][1]<=sb.jobnumber)cout<<"第"<<result[j][0]<<"个人做第"<<result[j][1]<<"件工作."<<endl;}}void main(){result[0][0]=0;sb=input();zeroout(sb);circlezero(sb);output(result,sb);}4. 算例和结果：自己运算结果为：->⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡3302102512010321->⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡330110241200032034526635546967562543----⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡可以看出：第1人做第4件工作；第2人做第1件工作；第3人做第3件工作；第4人做第2件工作。

指派问题的匈牙利解法1、 把各行元素分别减去本行元素的最小值；然后在此基础上再把每列元素减去本列中的最小值。

⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⇒⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛0 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 06 10 12 9 610 6 14 7 67 8 12 9 61014 17 9 712 15 7 8 4 此时每行及每列中肯定都有0元素了。

2、 确定独立零元素，并作标记。

（1）、首先逐行判断是否有含有独立0元素的行，如果有，则按行继续处理；如没有，则要逐列判断是否有含有独立0元素的列，若有，则按列继续处理。

若既没有含有独立0元素的行，也没有含有独立0元素的列，则仍然按行继续处理。

（2）在按行处理时，若某行有独立0元素，把该0元素标记为a ，把该0所在的列中的其余0元素标记为b ；否则，暂时越过本行，处理后面的行。

把所有含有独立0元素的行处理完毕后，再回来处理含有2个以及2个以上的0元素的行：任选一个0做a 标记，再把该0所在行中的其余0元素及所在列中的其余0元素都标记为b 。

（3）在按列处理时，若某列有独立0元素，把该0元素标记为a ，把该0所在的行中的其余0元素标记为b ；否则，暂时越过本列，处理后面的列。

把所有含有独立0元素的列处理完毕后，再回来处理含有2个以及2个以上的0元素的列：任选一个0做a 标记，再把该0所在列中的其余0元素及所在行中的其余0元素都标记为b 。

（4）、重复上述过程，即得到独立零元素（标记a 的“0”）⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛a b b a b b a 04 3 2 04 05 0 01 2 3 2 037 7 1 08 11 0 3 0a b 3、 若独立零元素等于矩阵阶数，则已经得到最优解，若小于矩阵阶数，则继续以下步骤：（1）、对没有标记a 的行作标记c（2）、在已作标记c 的行中，对标记b 所在列作标记c（3）、在已作标记c 的列中，对标记a 所在的行作标记c（4）、对没有标记c 的行划线，对有标记c 的列划线4、 在未被直线覆盖的所有元素中找出一个最小元素（Xmin ），未被直线覆盖的行（或列）中所有元素都减去这个数。

指派问题与匈⽛利解法指派问题概述：实际中，会遇到这样的问题，有n项不同的任务，需要n个⼈分别完成其中的1项，每个⼈完成任务的时间不⼀样。

于是就有⼀个问题，如何分配任务使得花费时间最少。

通俗来讲，就是n*n矩阵中，选取n个元素，每⾏每列各有1个元素，使得和最⼩。

如下图：指派问题性质：指派问题的最优解有这样⼀个性质，若从矩阵的⼀⾏(列)各元素中分别减去该⾏(列)的最⼩元素，得到归约矩阵，其最优解和原矩阵的最优解相同．匈⽛利法：12797989666717121491514661041071091.⾏归约：每⾏元素减去该⾏的最⼩元素502022300001057298004063652.列归约：每列元素减去该列的最⼩元素502022300001057298004063653.试指派：(1)找到未被画线的含0元素最少的⾏列，即，遍历所有未被画线的0元素，看下该0元素所在的⾏列⼀共有多少个0，最终选取最少个数的那个0元素。

(2)找到该⾏列中未被画线的0元素，这就是⼀个独⽴0元素。

对该0元素所在⾏和列画线。

50202230000105729800406365502022300001057298004063655020223000010572980040636550202230000105729800406365(3)暂时不看被线覆盖的元素，重复(1)(2)直到没有线可以画。

(4)根据(2)找到的0元素个数判断，找到n个独⽴0元素则Success，⼩于n个则Fail.（本例⼦中，n=5，可以看到，第⼀次试指派之后，独⽴0元素有4个，不符合）4.画盖0线：⽬标：做最少的直线数覆盖所有0元素，直线数就是独⽴0元素的个数。

注意：这跟3的线不同；不能⽤贪⼼法去画线，⽐如1 0 01 1 01 0 1若先画横的，则得画3条线，实际只需2条；若先画竖的，将矩阵转置后同理。

步骤3得出的独⽴0元素的位置50202230000105729800406365(1)对没有独⽴0元素的⾏打勾、(2)对打勾的⾏所含0元素的列打勾(3)对所有打勾的列中所含独⽴0元素的⾏打勾(4)重复(2)(3)直到没有不能再打勾(5)对打勾的列和没有打勾的⾏画画线，这就是最⼩盖0线。

软考指派问题计算
软考指派问题是一种常见的组合优化问题，通常涉及到将一组任务分配给一组工人，以最小化总成本或最大化总效益。

解决指派问题的一种常见方法是使用匈牙利算法。

以下是使用匈牙利算法解决指派问题的基本步骤：
1. 创建代价矩阵：将问题抽象为一个二维矩阵，其中每个元素表示将某个任务分配给某个工人的成本或者效益。

代价矩阵的大小为n行m列，其中n
表示任务的数量，m表示工人的数量。

2. 寻找增广路径：从代价矩阵中寻找增广路径，即从某一行或某一列出发，沿着矩阵的边缘移动，直到回到起始位置。

在寻找增广路径的过程中，需要不断更新代价矩阵。

3. 构造增广矩阵：在增广路径上，将代价矩阵中对应位置的元素减去最小值，并将路径上的其他元素设置为最大值。

这样构造的增广矩阵与原代价矩阵具有相同的行和列。

4. 求解最小二等分问题：将增广矩阵分为两个子矩阵，分别代表左半部分和右半部分。

求解这两个子矩阵对应的最小二等分问题，即找到一个分割线，使得左半部分和右半部分的元素总和最小。

5. 确定最佳分配方案：根据最小二等分问题的解，确定最佳的分配方案。

如果最小二等分问题的解为0，则说明已经找到了最优解；否则，需要重复步骤2-4，直到找到最优解。

通过以上步骤，可以求解指派问题并找到最优的分配方案。

需要注意的是，指派问题的解并不一定是整数解，可能是小数或者分数。

在实际应用中，需要根据具体问题和要求来确定是否需要取整或者进行其他处理。

python的scipy（匈牙利算法）解决教学任务指派问题python的scipy（匈牙利算法）解决教学任务指派问题参考资料：匈牙利算法求解教学任务指派问题指派问题组合优化理论里的第六章_指派问题的课件问题简介在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。

由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。

于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。

这类问题称为指派问题或分派问题。

教学任务指派问题为指派问题中的一种，考虑教师对课程的擅长程度，教学任务饱满序列和学生对教师的满意度，通过匈牙利算法求得最优课程指派。

算法指派问题一般模型：匈牙利算法：教师与课程一样多把求最大值变为求最小值问题：矩阵C=20-擅长矩阵。

再进行匈牙利算法操作：如果得不到解，则：程序实现：import numpy as npfrom scipy.optimize import linear_sum_assignmentdefprintf(row_ind,col_ind):print("最优教师课程指派：")for i inrange(len(row_ind)):print("教师",row_ind[i],"->课程",col_ind[i],end='; ')print() goodAt=np.array([[18,5,7,16],[10,16,6,5],[11,6,4,7],[13,12,9 ,11]])weakAt=20-goodAtrow_ind,col_ind=linear_sum_assignment(weakAt)print(row _ind)print(col_ind)print(goodAt[row_ind,col_ind])print (goodAt[row_ind,col_ind].sum())printf(row_ind,col_ind)输出结果：教师少与课程多把求最大值变为求最小值问题：矩阵C=10-擅长矩阵。

第6章 指派问题与旅行商问题一、指派问题的匈牙利算法1、最小化指派效益矩阵（或费用矩阵）的每一行各元素分别减去该行中的最小元素；→新效益矩阵（或新费用矩阵）的每一列各元素分别减去该列中的最小元素；→判别：如果找出n 个在不同行不同列的0元素，停止运算，最优解即为这些“0”对应位置，否则→标记每一行或列只有一个“0”元素为“*0”，一旦标记，就划去“*0”所在的行或列； →在剩下的矩阵中重复前面步骤。

冲刺模拟试卷（一）第11题冲刺模拟试卷（四）第11题冲刺模拟试卷（五）第11题冲刺模拟试卷（八）第11、12题2、最大化指派在最大化的效益矩阵中，用最大的那个元素分别减去矩阵中的所有元素；→利用上面得“最小化指派”运算即可。

冲刺模拟试卷（三）第11题冲刺模拟试卷（七）第11题二、旅行商问题的匈牙利算法1、问题描述：从点0v 出发经n v v v ,....,,21点各一次，最后返回0v 的路径最短者。

2、求解：利用“最小化指派”运算→读取结果：从0v 开始，从第一行中找出“*0”对应的列i v ，得到i v v →0；从i v 开始，从第二行中找出“*0”对应的列j v ，得到j i v v →；当出现断裂时，选择小集合进行重新调整，选择最短的！冲刺模拟试卷（一）第12题冲刺模拟试卷（二）第7、14题冲刺模拟试卷（四）第12题冲刺模拟试卷（五）第12、13题冲刺模拟试卷（六）第12题冲刺模拟试卷（七）第12题三、哥尼斯堡七桥问题1、欧拉图：联通图中没有奇点存在；联通的非欧拉图：一定会有偶数个奇点。

2、从一般图到最优的欧拉图：相邻的奇点直接增加一条连线；圈上的连线长不过圈的一半；两点之间不能出现重叠（只能有1条或2条连线）。

冲刺模拟试卷（一）第10,、13题冲刺模拟试卷（二）第9、15题冲刺模拟试卷（四）第13题冲刺模拟试卷（六）第10题冲刺模拟试卷（七）第14题冲刺模拟试卷（八）第14题。

指派问题求解步骤（匈牙利法）
极小化问题
1、变换系数矩阵
（1）从系数矩阵的各行元素中减去该行中的最小元素
（2）从系数矩阵的各列元素中减去该列中的最小元素
2、试找最优解
从0元素最少的行（或列）开始，圈出一个0元素，划去该0元素所在的行和列。

已经划去的0元素不能再划圈。

如此重复。

如果圈出了n个独立的0元素，则确定了最优解；否则，转入下一步。

3、寻找最少覆盖线
（1）没有划圈的行打√，
（2）在打√的行中，有0元素的列打√
（3）在打√的列中，有划圈的行打√
（4）重复（2）和（3）
（5）没有打√的行划横线，打√的列划竖线
4、调整0元素
（1）在没有被直线覆盖的元素中找出最小元素
（2）将没有被直线覆盖的元素减去该最小元素
（3）被一条直线覆盖的元素不变
（4）被二条直线覆盖的元素加上该最小元素
5、转入第二步
极大化问题
用系数矩阵中的最大元素减去各元素，化为极小化问题.。

第四讲 指派模型及匈牙利方法§ 4.1 引言将不同的任务分派给若干人去完成，由于任务有难易，人员素质有高低，因此各人去完成不同的任务的效率就有差异。

我们的问题是：应分派何人去完成哪种任务使得总效率最高（或所花费的时间最少，或所需的费用最低）？这一类问题称为指派问题或分配问题。

指派问题的一般提法是：用最佳方法按照一对一的原则把“任务”指派给“人”。

具体地就是：设有n 个人A 1，A 2，…，A n ，被分派去完成n 项工作B 1，B 2，…，B n ，要求每项工作需且仅需一个人去完成，每个人需完成且仅需完成一项工作。

已知A i 完成B j 工作的效率（如工时、成本或价值等）为c ij 。

问应如何指派，才能使总的工作效率最好？指派问题本质上是0—1规划问题。

设X ij 表示A i 完成B j 工作，并令⎪⎩⎪⎨⎧=工作去完成当不指派工作去完成当指派j i j i ij B A B A X 0 1，则指派模型的标准形式为), ,2 ,1,( }1 ,0{ ) , ,2 ,1( 1 ), ,2 ,1( 1s.t.)0( min 1111n j i X n j X n i Xc X c Z ij n i ij nj ijij ni nj ij ij ΛΛΛ=∈====≥=∑∑∑∑====由c ij 组成的方阵C = (c ij )n ⨯n 称为效率矩阵。

只要效率矩阵C 给定，指派问题也就相应确定。

若0ij x 为指派模型的最优解，则n 阶方阵X = (0ij x ) 称为指派模型的最优解方阵。

事实上，方阵X 为一置换方阵，即该矩阵中的每一行、每一列只有一个“1”。

显然，指派问题是运输问题的特例。

§ 4.2 匈牙利方法除了求解0—1规划外，解决指派问题还有其特殊的方法，它是由匈牙利数学家柯尼格（D. Köngig ）提出的，因此得名匈牙利方法（The Hungarian Method of Assignment ）。