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

《2022年运筹学指派问题的匈牙利法实验报告.docx》由会员分享，可在线阅读，更多相关《2022年运筹学指派问题的匈牙利法实验报告.docx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 运 筹 学课 程 设 计 报 告专业：班级：学号：2022 年 6 月 20 日名师归纳总结 - - - - - - -第 1 页,共 15 页精选学习资料 - - - - - - - - - 目录一、题目；二、算法思想；三、算法步骤；四、算法源程序；五、算例和结果；六、结论与总结；名师归纳总结 - - - - - - -第 2 页,共 15 页精选学习资料 - - - - - - - - - 一、 题目：匈牙利法求解指派问题；二、 算法思想；匈牙利解法的指派问题最优解的以下性质：设指派问题的系数矩阵为 C= cij n n,假设将 C 的一行

2、或列各元素分别减去一个常数 k如该行或列的最小元素 ,就得到一个新的矩阵 C= c ij n n；那么,以 C位系数矩阵的指派问题和以 解；C 位系数矩阵的原指派问题有相同最优由于系数矩阵的这种变化不影响约束方程组,只是使目标函数值削减了常 数 k,所以,最优解并不转变；必需指出,虽然不比要求指派问题系数矩阵中无 负元素,但在匈牙利法求解指派问题时, 为了从以变换后的系数矩阵中判别能否得到最优指派方案, 要求此时的系数矩阵中无负元素；由于只有这样, 才能从总费用为零这一特点判定此时的指派方案为最优指派方案；三、 算法步骤；1变换系数矩阵,使各行和各列皆显现零元素；各行及各列分别减去本行及本列最

3、小元素,这样可保证每行及每列中都有零元素,同时,也防止了显现负元素；名师归纳总结 - - - - - - -第 3 页,共 15 页精选学习资料 - - - - - - - - - 2做能掩盖全部零元素的最少数目的直线集合；因此,假设直线数等于n,就以可得出最优解；否就,转第3步；对于系数矩阵非负的指派问题来说,总费用为零的指派方案肯定是最优指派方案；在第 1步的基础上,假设能找到n 个不同行、不同列的零元素,就对应的指派方案总费用为零,从而是最优的；当同一行或列上有几个零元素 时,如挑选其一,就其与的零元素就不能再被挑选,从而成为余外的；因此,重要的是零元素能恰当地分布在不同行和不同列上,而

4、并在与它们的多少； 但第1步并不能保证这一要求； 假设掩盖全部零元素的最少数目的直线集合中的直线数 目是 n,就说明能做到这一点；此时,可以从零元素的最少的行或列开头圈“0” ,每圈一个“0”,同时把 位于同行合同列的其他零元素划去标记为,如此逐步进行,最终可得 n 个位 于不同行、 不同列的零元素, 他们就对应了最优解； 假设掩盖全部零元素的最少数目的直线集合中的元素个数少于n,就说明无法实现这一点；需要对零元素的分布做适当调整,这就是第3步；3 变换系数矩阵,是未被直线掩盖的元素中显现零元素；回到第2步；在未被直线掩盖的元素中总有一个最小元素；对未被直线掩盖的元素所在的行或列中各元素都减去

5、这一最小元素,这样,在未被直线掩盖的元素中势必 会显现零元素, 但同时却又是以被直线掩盖的元素中显现负元素；为了排除负元 素,只要对它们所在的列或行中个元素都加上这一最小元素可以看作减去 这一最小元素的相反数即可；名师归纳总结 - - - - - - -第 4 页,共 15 页精选学习资料 - - - - - - - - - 四、 算法源程序；#include #include #define m 5 int inputint Mmm int i,j; fori=0;im;i+ cout请输入系数矩阵第 i+1 行元素： endl; forj=0;jMij; cout系数矩阵为： endl;

6、fori=0;im;i+ forj=0;jm;j+ coutMijt; coutendl; return Mmm; int convertint Mmm int xm,ym; int i,j; fori=0;im;i+ xi=Mi0; forj=1;jm;j+ ifMijxi xi=Mij; fori=0;im;i+ forj=0;jm;j+ Mij-=xi; forj=0;jm;j+ 名师归纳总结 - - - - - - -第 5 页,共 15 页精选学习资料 - - - - - - - - - yj=M0j; fori=0;im;i+ ifMijyj yj=Mij; fori=0;im;i

7、+ forj=0;jm;j+ Mij-=yj; cout对系数矩阵各行各列进行变换得：endl; fori=0;im;i+ forj=0;jm;j+ coutMijt; coutendl; return Mmm; int exchangeint Mmm int i,j,n; endl; coutn; ifn=0 cout分别输入要变换的行及该行未掩盖元素中最小元素：endl; else cout分别输入要变换的列及该列的最小元素：ab; forj=0;jm;j+ ifn=0 Ma-1j-=b; else Mja-1-=b; cout变换后的矩阵： endl; fori=0;im;i+ forj

8、=0;jm;j+ coutMijt; 名师归纳总结 - - - - - - -第 6 页,共 15 页精选学习资料 - - - - - - - - - coutendl; return Mmm; void main int Mmm; cout endl; whiletrue coutendl; cout 菜单 endlendl; cout 1.系数矩阵输入 endl; cout 2.初始变换 endl; cout 3.行列变换 endl; cout 4.退出 endl; cout*endlendl; int n; coutn; switchn case 1: inputM;break; cas

9、e 2: convertM;break; case 3: exchangeM;break; case 4: cout感谢使用！ endl; exit0;break; default: cout输入有误！请重新输入！endl; 名师归纳总结 - - - - - - -第 7 页,共 15 页精选学习资料 - - - - - - - - - 五、 算例和结果；例 412 今有甲、乙、丙、丁 4 个人去完成 5 项任务；每人完成各项任务所需的时间如表 411 所示；由于任务数多于人数, 故规定其中有一人可兼完成两项任务,其余三人各完成一项任务；是确定总花费时间为最小的指派方案；课本 P113表 41

10、1 人任务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 名师归纳总结 C2529314137第 8 页,共 15 页39382620333427284032244236234524

11、27262032- - - - - - -精选学习资料 - - - - - - - - - 1、将系数矩阵 C 输入程序；名师归纳总结 - - - - - - -第 9 页,共 15 页精选学习资料 - - - - - - - - - 2、对系数矩阵各行各列减去最小元素,即程序中的初始变换；3、进行行变换名师归纳总结 - - - - - - -第 10 页,共 15 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页,共 15 页精选学习资料 - - - - - - - - - 4、进行列变换6、再次进行行变换名师归纳总结 - - - -

12、- - -第 12 页,共 15 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页,共 15 页精选学习资料 - - - - - - - - - 7、再次进行列变换此时,已经不能用少于五根直线掩盖零元素,故此时为最优指派方案；C2529314137001173393826203318130033427284032110018024423623450147012242726203232002最优指派方案是：甲做B,乙做 C,丙做 E,丁做 A,戊做 D,由于戊虚拟的人完成 D 的时间与乙相同, 实际上最优指派方案是： 乙完成 C 和 D,甲

13、、丙、丁分别完成 B,E,A,总计时间为 131；名师归纳总结 - - - - - - -第 14 页,共 15 页精选学习资料 - - - - - - - - - 六、 结论和总结；匈牙利法解指派问题,其步骤简洁易懂,操作起来也不难,可是由于运算 量实在太大很简洁出错, 故利用程序来完成对系数矩阵的化简变换是再好不过的；只要确定输入, 以及找出的掩盖集合无误, 就运算结果就不会出错； 由于时间仓 促,我编的程序仍有很多不足之处,比方说：在输入系数矩阵之前,需要事先定义二维数组的行及列； 针对这个问题我尝试了好几次,也没有解决； 查了一些资料,好像可以通过动态安排二维数组的空间大小来实现二维数组行和列的输入；原来我想实现程序对系数矩阵零元素的直线掩盖功能的,可操作起来实在太难,故改为手动操作；通过这次课程设计,我不仅对运筹学的学问进行了稳固,也觉察到了编程 对数学的强大帮助功能； 利用它可以解决好多数学问题, 大大节约了时间及精力；学好数学和电脑是今后就业的重要筹码；名师归纳总结 - - - - - - -第 15 页,共 15 页