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

运 筹 学课程设计报告专业：班级：学号：2012 年 6 月 20 日精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 15 页目录一、题目。二、算法思想。三、算法步骤。四、算法源程序。五、算例和结果。六、结论与总结。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 15 页一、 题目：匈牙利法求解指派问题。二、 算法思想。匈牙利解法的指派问题最优解的以下性质：设指派问题的系数矩阵为C=cijnn，假设将 C 的一行或列各元素分别减去一个常数 k 如该行或列的最小元素 ， 则得到一个新的矩阵C = cijnn。那么，以 C 位系数矩阵的指派问题和以C 位系数矩阵的原指派问题有相同最优解。由于系数矩阵的这种变化不影响约束方程组，只是使目标函数值减少了常数 k，所以，最优解并不改变。必须指出，虽然不比要求指派问题系数矩阵中无负元素，但在匈牙利法求解指派问题时， 为了从以变换后的系数矩阵中判别能否得到最优指派方案， 要求此时的系数矩阵中无负元素。因为只有这样， 才能从总费用为零这一特征判定此时的指派方案为最优指派方案。三、 算法步骤。1变换系数矩阵，使各行和各列皆出现零元素。各行及各列分别减去本行及本列最小元素，这样可保证每行及每列中都有零元素，同时，也防止了出现负元素。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 15 页2做能覆盖所有零元素的最少数目的直线集合。因此，假设直线数等于n，则以可得出最优解。否则，转第3步。对于系数矩阵非负的指派问题来说，总费用为零的指派方案一定是最优指派方案。在第 1步的基础上，假设能找到n 个不同行、不同列的零元素，则对应的指派方案总费用为零，从而是最优的。当同一行或列上有几个零元素时，如选择其一，则其与的零元素就不能再被选择，从而成为多余的。因此，重要的是零元素能恰当地分布在不同行和不同列上，而并在与它们的多少。 但第 1步并不能保证这一要求。 假设覆盖所有零元素的最少数目的直线集合中的直线数目是 n，则说明能做到这一点。此时，可以从零元素的最少的行或列开始圈“0” ，每圈一个“ 0” ，同时把位于同行合同列的其他零元素划去标记为，如此逐步进行，最终可得n 个位于不同行、 不同列的零元素， 他们就对应了最优解； 假设覆盖所有零元素的最少数目的直线集合中的元素个数少于n，则说明无法实现这一点。需要对零元素的分布做适当调整，这就是第3步。3 变换系数矩阵，是未被直线覆盖的元素中出现零元素。回到第2步。在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的行或列中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必会出现零元素， 但同时却又是以被直线覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列或行中个元素都加上这一最小元素可以看作减去这一最小元素的相反数即可。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 15 页四、 算法源程序。#include #include #define m 5 int input(int Mmm) int i,j; for(i=0;im;i+) cout请输入系数矩阵第 i+1 行元素： endl; for(j=0;jMij; cout系数矩阵为： endl; for(i=0;im;i+) for(j=0;jm;j+) coutMijt; coutendl; return Mmm; int convert(int Mmm) int xm,ym; int i,j; for(i=0;im;i+) xi=Mi0; for(j=1;jm;j+) if(Mijxi) xi=Mij; for(i=0;im;i+) for(j=0;jm;j+) Mij-=xi; for(j=0;jm;j+) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 15 页 yj=M0j; for(i=0;im;i+) if(Mijyj) yj=Mij; for(i=0;im;i+) for(j=0;jm;j+) Mij-=yj; cout对系数矩阵各行各列进行变换得：endl; for(i=0;im;i+) for(j=0;jm;j+) coutMijt; coutendl; return Mmm; int exchange(int Mmm) int i,j,n; cout进行行变换输入 0，进行列变换输入其他任意键：n; if(n=0) cout分别输入要变换的行及该行未覆盖元素中最小元素：endl; else cout分别输入要变换的列及该列的最小元素：ab; for(j=0;jm;j+) if(n=0) Ma-1j-=b; else Mja-1-=b; cout变换后的矩阵： endl; for(i=0;im;i+) for(j=0;jm;j+) coutMijt; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 15 页coutendl; return Mmm; void main() int Mmm; cout endl; while(true) coutendl; cout 菜单endlendl; cout 1.系数矩阵输入endl; cout 2.初始变换endl; cout 3.行列变换endl; cout 4.退出endl; cout*endlendl; int n; coutn; switch(n) case 1: input(M);break; case 2: convert(M);break; case 3: exchange(M);break; case 4: cout谢谢使用！ endl; exit(0);break; default: cout输入有误！请重新输入！endl; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 15 页五、 算例和结果。例 412 今有甲、乙、丙、丁4 个人去完成 5 项任务。每人完成各项任务所需的时间如表411 所示。由于任务数多于人数， 故规定其中有一人可兼完成两项任务，其余三人各完成一项任务。是确定总花费时间为最小的指派方案。课本 P113 表 411 任务人A B C D E 甲25 29 31 41 37 乙39 38 26 20 33 丙34 27 28 40 32 丁24 42 36 23 45 假设第 5 个人是戊，他完成各项任务的时间取甲、乙、丙、丁中的最小者，构造表 412。表 412 任务人A B C D E 甲25 29 31 41 37 乙39 38 26 20 33 丙34 27 28 40 32 丁24 42 36 23 45 戊24 27 26 20 32 由表 412 可得到系数矩阵 C 32202627244523364224324028273433202638393741312925C精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 15 页1、将系数矩阵 C 输入程序。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 15 页2、对系数矩阵各行各列减去最小元素，即程序中的初始变换。3、进行行变换精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 15 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 15 页4、进行列变换6、再次进行行变换精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 15 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 15 页7、再次进行列变换此时，已经不能用少于五根直线覆盖零元素，故此时为最优指派方案。32202627244523364224324028273433202638393741312925C20023120714001800113001318317100最优指派方案是：甲做B，乙做 C，丙做 E，丁做 A，戊做 D，由于戊虚拟的人完成 D 的时间与乙相同， 实际上最优指派方案是： 乙完成 C 和 D，甲、丙、丁分别完成 B，E，A，总计时间为 131。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 15 页六、 结论和总结。匈牙利法解指派问题，其步骤简单易懂，操作起来也不难，可是由于计算量实在太大很容易出错， 故利用程序来完成对系数矩阵的化简变换是再好不过的。只要确定输入， 以及找出的覆盖集合无误， 则计算结果就不会出错。 由于时间仓促，我编的程序还有许多不足之处，比方说：在输入系数矩阵之前，需要事先定义二维数组的行及列。 针对这个问题我尝试了好几次，也没有解决。 查了一些资料，好似可以通过动态分配二维数组的空间大小来实现二维数组行和列的输入。本来我想实现程序对系数矩阵零元素的直线覆盖功能的，可操作起来实在太难，故改为手动操作。通过这次课程设计，我不仅对运筹学的知识进行了稳固，也觉察到了编程对数学的强大辅助功能。 利用它可以解决好多数学问题， 大大节省了时间及精力。学好数学和电脑是今后就业的重要筹码。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 15 页