运筹学指派问题的匈牙利法实验报告

运筹学课程设计报告专业：班级：学号：姓名：2012年6月20日目录一、题目。二、算法思想。三、算法步骤。四、算法源程序。五、算例和结果。六、结论与总结。一、题目：匈牙利法求解指派问题。二、算法思想。匈牙利解法的指派问题最优解的以下性质：设指派问题的系数矩阵为C=cijnn，若将C的一行（或列）各元素分别减去一个常数k（如该行或列的最小元素），则得到一个新的矩阵C’='cijnn。那么，以C’位系数矩阵的指派问题和以C位系数矩阵的原指派问题有相同最优解。由于系数矩阵的这种变化不影响约束方程组，只是使目标函数值减少了常数k，所以，最优解并不改变。必须指出，虽然不比要求指派问题系数矩阵中无负元素，但在匈牙利法求解指派问题时，为了从以变换后的系数矩阵中判别能否得到最优指派方案，要求此时的系数矩阵中无负元素。因为只有这样，才能从总费用为零这一特征判定此时的指派方案为最优指派方案。三、算法步骤。（1）变换系数矩阵，使各行和各列皆出现零元素。各行及各列分别减去本行及本列最小元素，这样可保证每行及每列中都有零元素，同时，也避免了出现负元素。（2）做能覆盖所有零元素的最少数目的直线集合。因此，若直线数等于n，则以可得出最优解。否则，转第（3）步。对于系数矩阵非负的指派问题来说，总费用为零的指派方案一定是最优指派方案。在第（1）步的基础上，若能找到n个不同行、不同列的零元素，则对应的指派方案总费用为零，从而是最优的。当同一行（或列）上有几个零元素时，如选择其一，则其与的零元素就不能再被选择，从而成为多余的。因此，重要的是零元素能恰当地分布在不同行和不同列上，而并在与它们的多少。但第（1）步并不能保证这一要求。若覆盖所有零元素的最少数目的直线集合中的直线数目是n，则表明能做到这一点。此时，可以从零元素的最少的行或列开始圈“0”，每圈一个“0”，同时把位于同行合同列的其他零元素划去（标记为），如此逐步进行，最终可得n个位于不同行、不同列的零元素，他们就对应了最优解；若覆盖所有零元素的最少数目的直线集合中的元素个数少于n，则表明无法实现这一点。需要对零元素的分布做适当调整，这就是第（3）步。（3）变换系数矩阵，是未被直线覆盖的元素中出现零元素。回到第（2）步。在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的行（或列）中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必会出现零元素，但同时却又是以被直线覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）中个元素都加上这一最小元素（可以看作减去这一最小元素的相反数）即可。四、算法源程序。#includeiostream.h#includestdlib.h#definem5intinput(intM[m][m]){inti,j;for(i=0;im;i++){cout请输入系数矩阵第i+1行元素：endl;for(j=0;jm;j++)cinM[i][j];}cout系数矩阵为：endl;for(i=0;im;i++){for(j=0;jm;j++)coutM[i][j]\t;coutendl;}returnM[m][m];}intconvert(intM[m][m]){intx[m],y[m];inti,j;for(i=0;im;i++){x[i]=M[i][0];for(j=1;jm;j++){if(M[i][j]x[i])x[i]=M[i][j];}}for(i=0;im;i++)for(j=0;jm;j++)M[i][j]-=x[i];for(j=0;jm;j++){y[j]=M[0][j];for(i=0;im;i++){if(M[i][j]y[j])y[j]=M[i][j];}}for(i=0;im;i++)for(j=0;jm;j++)M[i][j]-=y[j];cout对系数矩阵各行各列进行变换得：endl;for(i=0;im;i++){for(j=0;jm;j++)coutM[i][j]\t;coutendl;}returnM[m][m];}intexchange(intM[m][m]){inti,j,n;cout进行行变换输入0，进行列变换输入其他任意键：endl;cinn;if(n==0)cout分别输入要变换的行及该行未覆盖元素中最小元素：endl;elsecout分别输入要变换的列及该列的最小元素：endl;inta,b;cinab;for(j=0;jm;j++)if(n==0)M[a-1][j]-=b;elseM[j][a-1]-=b;cout变换后的矩阵：endl;for(i=0;im;i++){for(j=0;jm;j++)coutM[i][j]\t;coutendl;}returnM[m][m];}voidmain(){intM[m][m];cout匈牙利法解指派问题endl;while(true){coutendl;cout菜单endlendl;cout1.系数矩阵输入endl;cout2.初始变换endl;cout3.行列变换endl;cout4.退出endl;cout************************************endlendl;intn;cout请选择功能键;cinn;switch(n){case1:input(M);break;case2:convert(M);break;case3:exchange(M);break;case4:cout谢谢使用！endl;exit(0);break;default:cout输入有误！请重新输入！endl;}}}五、算例和结果。例4—12今有甲、乙、丙、丁4个人去完成5项任务。每人完成各项任务所需的时间如表4—11所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人各完成一项任务。是确定总花费时间为最小的指派方案。（课本P113）表4—11任务人ABCDE甲2529314137乙3938262033丙3427284032丁2442362345假设第5个人是戊，他完成各项任务的时间取甲、乙、丙、丁中的最小者，构造表4—12。表4—12任务人ABCDE甲2529314137乙3938262033丙3427284032丁2442362345戊2427262032由表4—12可得到系数矩阵C32202627244523364224324028273433202638393741312925C1、将系数矩阵C输入程序。2、对系数矩阵各行各列减去最小元素，即程序中的初始变换。3、进行行变换4、进行列变换6、再次进行行变换7、再次进行列变换此时，已经不能用少于五根直线覆盖零元素，故此时为最优指派方案。32202627244523364224324028273433202638393741312925C20023120714001800113001318317100最优指派方案是：甲做B，乙做C，丙做E，丁做A，戊做D，由于戊（虚拟的人）完成D的时间与乙相同，实际上最优指派方案是：乙完成C和D，甲、丙、丁分别完成B，E，A，总计时间为131。六、结论和总结。匈牙利法解指派问题，其步骤简单易懂，操作起来也不难，可是由于计算量实在太大很容易出错，故利用程序来完成对系数矩阵的化简变换是再好不过的。只要确定输入，以及找出的覆盖集合无误，则计算结果就不会出错。由于时间仓促，我编的程序还有许多不足之处，比如说：在输入系数矩阵之前，需要事先定义二维数组的行及列。针对这个问题我尝试了好几次，也没有解决。查了一些资料，好像可以通过动态分配二维数组的空间大小来实现二维数组行和列的输入。本来我想实现程序对系数矩阵零元素的直线覆盖功能的，可操作起来实在太难，故改为手动操作。通过这次课程设计，我不仅对运筹学的知识进行了巩固，也发觉到了编程对数学的强大辅助功能。利用它可以解决好多数学问题，大大节省了时间及精力。学好数学和计算机是今后就业的重要筹码。