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

精选资料，欢迎下载
运筹学
课
程
设
计
报
告
专业：
班级：
学号：
姓名：
2012年6月20日
目录
、 题目。
.二、
算法思想。
算法步骤。
四、
算法源程序
五、
算例和结果
、°
八、
结论与总结
精选资料，欢迎下载
题目：匈牙利法求解指派问题
二、 算法思想。
匈牙利解法的指派问题最优解的以下性质：
设指派问题的系数矩阵为C=cij ，若将C的一行（或列）各元素分别减 去一个常数k （如该行或列的最小元素），则得到一个新的矩阵C'「冷 。那
IJ n n
么，以C'位系数矩阵的指派问题和以C位系数矩阵的原指派问题有相同最优解。
由于系数矩阵的这种变化不影响约束方程组，只是使目标函数值减少了常 数k，所以，最优解并不改变。必须指出，虽然不比要求指派问题系数矩阵中无 负元素，但在匈牙利法求解指派问题时，为了从以变换后的系数矩阵中判别能否 得到最优指派方案，要求此时的系数矩阵中无负元素。因为只有这样，才能从总 费用为零这一特征判定此时的指派方案为最优指派方案。
三、 算法步骤。
（1） 变换系数矩阵，使各行和各列皆出现零元素。
各行及各列分别减去本行及本列最小元素，这样可保证每行及每列中都有 零元素，同时，也避免了出现负元素。
精选资料，欢迎下载
（2） 做能覆盖所有零元素的最少数目的直线集合。
因此，若直线数等于n,则以可得出最优解。否则，转第（3）步。
对于系数矩阵非负的指派问题来说，总费用为零的指派方案一定是最优指 派方案。在第（ 1）步的基础上，若能找到 n 个不同行、不同列的零元素，则对 应的指派方案总费用为零， 从而是最优的。当同一行（或列）上有几个零元素时， 如选择其一，则其与的零元素就不能再被选择，从而成为多余的。因此，重要的 是零元素能恰当地分布在不同行和不同列上，而并在与它们的多少。但第（ 1）
步并不能保证这一要求。 若覆盖所有零元素的最少数目的直线集合中的直线数目 是n，则表明能做到这一点。
此时，可以从零元素的最少的行或列开始圈“ 0”，每圈一个“ 0”，同时把 位于同行合同列的其他零元素划去（标记为） ，如此逐步进行，最终可得 n 个位 于不同行、 不同列的零元素， 他们就对应了最优解； 若覆盖所有零元素的最少数 目的直线集合中的元素个数少于 n,则表明无法实现这一点。需要对零元素的分 布做适当调整，这就是第（ 3）步。
（3） 变换系数矩阵，是未被直线覆盖的元素中出现零元素。回到第（ 2）步。 在未被直线覆盖的元素中总有一个最小元素。 对未被直线覆盖的元素所在的 行（或列）中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必 会出现零元素， 但同时却又是以被直线覆盖的元素中出现负元素。 为了消除负元 素，只要对它们所在的列（或行）中个元素都加上这一最小元素（可以看作减去 这一最小元素的相反数）即可。
精选资料，欢迎下载
四、 算法源程序。
#include<>
#include<>
#define m 5 int input(int M[m][m])
{
int i,j;
for(i=0;i<m;i++)
"<<endl;
{ cout<<" 请输入系数矩阵第 "<<i+1<<" 行元素： for(j=0;j<m;j++) cin>>M[i][j];
}
cout<<" 系数矩阵为： "<<endl;
for(i=0;i<m;i++)
{ for(j=0;j<m;j++) cout<<M[i][j]<<"\t"; cout<<endl;
}
return M[m][m];
}
int convert(int M[m][m])
{ int x[m],y[m];
int i,j;
for(i=0;i<m;i++)
{ x[i]=M[i][0];
for(j=1;j<m;j++)
{ if(M[i][j]<x[i]) x[i]=M[i][j];
}
}
for(i=0;i<m;i++)
for(j=0;j<m;j++)
M[i][j]-=x[i];
for(j=0;j<m;j++)
{ y[j]=M[0][j];
for(i=0;i<m;i++)
{ if(M[i][j]<y[j]) y[j]=M[i][j];
}
}
for(i=0;i<m;i++)
for(j=0;j<m;j++) M[i][j]-=y[j];
精选资料，欢迎下载
cout<<" 对系数矩阵各行各列进行变换得： "<<endl;
for(i=0;i<m;i++