运筹学指派问题的匈牙利法.docx

《运筹学指派问题的匈牙利法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学课程设计指派问题的匈牙利法专业：姓名：学号：1.算法思想：匈牙利算法的基本思想是修改效益矩阵的行或列，使得每一行或列中至少有一个为零的元素，经过修正后，直至在不同行、不同列中至少有一个零元素，从而得到与这些零元素相对应的一个完全分配方案。当它用于效益矩阵时，这个完全分配方案就是一个最优分配，它使总的效益为最小。这种方法总是在有限步內收敛于一个最优解。该方法的理论基础是：在效益矩阵的任何行或列中，加上或减去一个常数后不会改变最优分配。2.算法流程或步骤：1.将原始效益矩阵C的每行、每列各元素都依次减去该行、该列的最小元素，使每行、每列都至少出现一个0元素，以构

2、成等价的效益矩阵C’。2.圈0元素。在C’中未被直线通过的含0元素最少的行（或列）中圈出一个0元素，通过这个0元素作一条竖（或横）线。重复此步，若这样能圈出不同行不同列的n个0元素，转第四步，否则转第三步。3.调整效益矩阵。在C’中未被直线穿过的数集D中，找出最小的数d，D中所有数都减去d，C’中两条直线相交处的数都加的d。去掉直线，组成新的等价效益矩阵仍叫C’，返回第二步。4.令被圈0元素对应位置的Xij=1,其余=0，这就是一种最优分配。最低总耗费是C中使=1的各位置上各元素的和。算法流程图：圈出n个不同行不同列的0元素？还有0可圈？在C’中划直线：对新圈的0

3、元素所在的行或列划直线（只划一条）在C’中圈0元素：选圈含0元素个数最少的行或列中的0元素变换效益矩阵C为等价的效益矩阵C’，（使C’的每行每列至少含有一个0）开始调整：令未被直线穿过的数据区为D，d=min（D），D中每个元素减去d，直线相交处每个元素加上d，去掉直线和圈，构成新的C’。YNY结束作答：仅对应于所圈0元素位置（i，j）处，即指派第i个人干第j件事。N1.算法源程序：#includetypedefstructmatrix{floatcost[101][101];intzeroelem[101][101];floatcostf

4、orout[101][101];intmatrixsize;intpersonnumber;intjobnumber;}matrix;matrixsb;intresult[501][2];voidtwozero(matrix&sb);voidjudge(matrix&sb,intresult[501][2]);voidrefresh(matrix&sb);voidcirclezero(matrix&sb);matrixinput();voidoutput(intresult[501][2],matrixsb);voidzeroout(matrix&sb);matr

5、ixinput(){matrixsb;intm;intpnumber,jnumber;inti,j;floatk;charw;cout<<"指派问题的匈牙利解法:"<>m;while(m!=1&&m!=0){cout<<"请输入1或0:"<>m;}cout<<"请输入人数(人数介于1和100之间):"<>pnumber;while(pnumber<1

6、

7、pnumber>100){cout<<"请输入合法数据:"<>p

8、number;}cout<<"请输入工作数(介于1和100之间):"<>jnumber;while(jnumber<1

9、

10、jnumber>100){cout<<"请输入合法数据:"<>jnumber;}cout<<"请输入"<>sb.cost[i][j];sb.costforout[i][j]=sb.co

11、st[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

12、mber)