《2023年运筹学指派问题的匈牙利法实验报告.docx》由会员分享，可在线阅读，更多相关《2023年运筹学指派问题的匈牙利法实验报告.docx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学筹课程设计报告 运 业级号名 专班学姓20 2 3年6月20日T2442362345戊2427262032由表412可得到系数矩阵C25293141373938262033C =342728403224423623452427262()321、将系数矩阵C输入程序。 E: 学习c+作业、匈/JiMDebugJlE去.exe 菜单 12 3 412 3 4阵露 矩变变 数为出请选择必能键1请输入索薮矩阵第1行元素:25 293141善输入系数矩阵第2行元素:39382620修输入系数矩阵第3行元素:3427284032请输入系数矩阵第4行元素:24423623卷输入系数矩阵第5行元素:2427
2、262032系数矩阵为：252931413739382620333427284032244236234524272620322、对系数矩阵各行各列减去最小元素，即程序中的初始变换。 菜单 1 .系数矩阵输入2.3.4.0 19714418019701216 013 007801773、进行行变换单输 一一 菜阵螯一一 矩变变Z ”数为出一一 系初喝一一单输 一一 菜阵螯一一 矩变变Z ”数为出一一 系初喝一一12 3 445167130-530013019120177507r青选择功能键3快行行变换输入。，进行列变换输入其他任意键： 上别输入要变换的行及该行未覆盖元素中最小元素:2度换后的矩阵
3、：514 菜单 系数矩阵输入2.3.4.进行行爰。，进行列变换输入其他任意键:5分别输入要变换的行及该行未覆盖元素中最小元素: 4变换后的矩阵:14 ?413 01875001116-5 13-1 073016712 3 4单输菜阵翳 矩变变 数45出 四年麴耦龌入明进行列变换输入其他任意键： 办别输入要变换的行及该行未覆盖元素中最小元素:4变换后的矩阵:04516714130-5370013001811-116031-434、进行列变换 菜单 阵卷 矩变变 数出 系初基阵卷 矩变变 数出 系初基懿耦盛第,进行列变换输入其他任意键:1分别输入要变换的列及该列的最小元素：4I换后的矩阵：5147
4、13 01830 0 11121 018417301636、再次进行行变换入 单输入 单输菜阵翳 又变 数出 ,现强12 3 4谓选择功能键3强行行变换输入。，进行列变换输入其他任意键：0分别输入要变换的行及该行未覆盖元素中最小元素:1变换后的矩阵:-414700013 01831 00 11117 01841330163 菜单 1 .系超更隹输入2包藤建逾.卷列变接3 .痕出京得裂喘入。，进行列变换输入其他任意键:5分别输入要变换的行及该行未覆盖元素中最小元素: 4全换后的矩阵：-4147-40 1301431007117 018 0133012312 3 4输 阵簧 矩变变出 系现范谓选择
5、功能键3省行行变换输入。，进行列变换输入其他任意键：0分别输入要变换的行及该行未覆盖元素中最小元素:5变换后的矩阵:-4147-4-1013 01421 007 017 018 003301227、再次进行列变换 菜单 -4此时,12 3 4输 阵, 矩变变 数翁出 系现范3染又 圣亍 4Jy01 选行 主 nt#:-01301421 007 017 018 00330122已经不能用少于五根直线覆盖零元素,故此时为最优指派方案。25 29 31 41 37一-0 0 1 17 339 38 26 20 3318 13 O 0 3c =34 27 28 40 3211 0 0 18 ()24
6、42 36 23 45O 14 7 0 1224 27 26 20 32320 () 2最优指派方案是:甲做B,乙做C,丙做E,丁做A ,戊做D,由于戊（虚拟的人） 完毕D的时间与乙相同，事实上最优指派方案是:乙完毕C和D,甲、丙、丁分别 完毕B, E,A,总计时间为1 31。六、结论和总结。匈牙利法解指派问题，其环节简朴易懂，操作起来也不难，可是由于计算量实 在太大很容易犯错，故运用程序来完毕对系数矩阵的化简变换是再好但是的。只 要拟定输入，以及找出的覆盖集合无误，则计算结果就不会犯错。由于时间仓促， 我编的程序尚有许多局限性之处，比如说：在输入系数矩阵之前，需要事先定义 二维数组的行及列。
7、针对这个问题我尝试了好几次，也没有解决。查了一些资料， 仿佛可以通过动态分派二维数组的空间大小来实现二维数组行和列的输入。 本来我想实现程序对系数矩阵零元素的直线覆盖功能的，可操作起来实在太难, 故改为手动操作。通过这次课程设计，我不仅对运筹学的知识进行了巩固，也发现到了编程 对数学的强大辅助功能。运用它可以解决好多数学问题，大大节省了时间及精力。 学好数学和计算机是此后就业的重要筹码。目录一、 题目。二、算法思想。三、算法环节。四、算法源程序。五、算例和结果。 六、结论与总结。一、题目:匈牙利法求解指派问题。二、算法思想。匈牙利解法的指派问题最优解的以下性质：设指派问题的系数矩阵为C = （
8、cJ ,若将C的一行（或列）各元素分别减去一个常数k（如该行或列的最小元素），则得到一个新的矩阵0那么, 以C位系数矩阵的指派问题和以C位系数矩阵的原指派问题有相同最优解。由于系数矩阵的这种变化不影响约束方程组，只是使目的函数值减少了常 数k,所以，最优解并不改变。必须指出，虽然不比规定指派问题系数矩阵中无负 元素，但在匈牙利法求解指派问题时，为了从以变换后的系数矩阵中判别能否得 到最优指派方案，规定此时的系数矩阵中无负元素。由于只有这样，才干从总费 用为零这一特性鉴定此时的指派方案为最优指派方案。三、算法环节。(1)变换系数矩阵，使各行和各列皆出现零元素。各行及各列分别减去本行及本列最小元素
9、，这样可保证每行及每列中都有 零元素，同时，也避免了出现负元素。做能覆盖所有零元素的最少数目的直线集合。因此，若直线数等于n,则以可得出最优解。否则，转第(3)步。对于系数矩阵非负的指派问题来说，总费用为零的指派方案一定是最优指 派方案。在第(1)步的基础上，若能找到n个不同行、不同列的零元素，则相应 的指派方案总费用为零，从而是最优的。当同一行(或列)上有几个零元素时， 如选择其一，则其与的零元素就不能再被选择，从而成为多余的。因此，重要的 是零元素能恰本地分布在不同行和不同列上，而并在与它们的多少。但第(1)步 并不能保证这一规定。若覆盖所有零元素的最少数目的直线集合中的直线数目是 n,则
10、表白能做到这一点。此时，可以从零元素的最少的行或列开始圈“ 0 ”，每圈一个“0”，同时把位 于同行协议列的其他零元素划去(标记为)，如此逐步进行，最终可得n个位于不同 行、不同列的零元素，他们就相应了最优解;若覆盖所有零元素的最少数目的直线 集合中的元素个数少于n,则表白无法实现这一点。需要对零元素的分布做适当 调整，这就是第步。(3)变换系数矩阵，是未被直线覆盖的元素中出现零元素。回到第(2)步。在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的 行(或列)中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必会出 现零元素，但同时却又是以被直线覆盖的元素中出现负元素
11、。为了消除负元素, 只要对它们所在的列(或行)中个元素都加上这一最小元素(可以看作减去这一 最小元素的相反数)即可。四、算法源程序。# inc 1 u d e i ncl u de# defin e m 5i nt in p u t (int Mmm)。int i, j；for(i=0;im; i +)。c out”请输入系数矩阵第”行元素：nendl;for ( j =0;jm；j+)cinMij；)ocoutV V系数矩阵为： e ndl;o f or (i= 0 ; i m； i+)。卜fo r (j= 0 ;jm;j+)c o utM i j tM;cout e ndl;)r et u
12、 r n M mm；)int c onvert (in t Mm m)“int xm, y m;in t ij;o r( i =0;im； i+) x i =Mi0；for( j =1 ； jm； j +)。 if(M ijx i )-xi = M i j：。afor(i=0;im;i + + )for ( j =0; j m;j+)。 M ij=x i ；f or(j= 0 ;jm;j+) o.yUJ=M0 j;of o r (i=0;im;i+)- j y UI)。y J 1=M i j； )for (i= 0 ； im; i +)ofor(j= 0 ;jm； j + +)。Mi j -=
13、y j;you t 对系数矩阵各行各列进行变换得：H endl；f o r(i= 0 ;im； i +) f o r(j=O;jm;j+)c o utM i j t；o c o utendl;oret urn Mm m；)i nt exch a nge(int Mmm) int i,j,n;C o u t”进行行变换输入0,进行列变换输入其他任意键:“ Vendl;c i nn;if(n= 0 )。c ou tb;for(j=0; j vm;j+ + )8 i f (n=0)Ma-1 j=b;o els e0M j a-1 -=b;c OU t 变换后的矩阵:vV e n dl；for ( i
14、 = 0 ； iVm; i +)。 for( j =0; j m;j + + )utMij, to c outcndl;6(r e tur n(0v o id main() i nt M mm;oc o utVVVVVVV end 1 ;whil e (true) c ou t , 菜单c out 菜单 uend !endl;c o uto c o u tncoutno c o u t1 .系数矩阵输入.初始变换2 .行列变换.退出en d 1；, e n d 1 ;end 1 ;uen d 1 ;cout* * * * * * * * * * * * * * *n;*sw i t c h(n
15、)(ca s e 1:gin p ut(M); b rcak;c a se 2：c o nve r t (M)； b r eak;c a se 3:o e x cha n g e (M);bre a k ;*case 4：co u t ” 谢谢使用！ en d 1 ;wex i t( 0 );br e a k;defa u It：you t V输入有误！请重新输入！ endl;0)五、算例和结果。例4一12 今有甲、乙、丙、丁 4个人去完毕5项任务。每人完毕各项 任务所需的时间如表4-1 1所示。由于任务数多于人数，故规定其中有一人可 兼完毕两项任务,其余三人各完毕一项任务。是拟定总花费时间为最小的指派方 案。（课本P113）表 4 1 1ABCDE甲252 9314 13 7乙39382 62033丙3427284032T2442362345假设第5个人是戊，他完毕各项任务的时间取甲、乙、丙、丁中的最小者，构 造表412o表 412ABCDE甲2 529314137乙3938262033丙3427284032