当前位置:首页 >> 数学 >>

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


运 筹 学
课 程 设 计 报 告

专业: 班级: 学号: 姓名:

2012 年 6 月 20 日

目录

一、 题目。 二、 算法思想。 三、 算法步骤。 四、 算法源程序。 五、 算例和结果。 六、 结论与总结。

一、 题目:匈牙利法求解指派问题。

二、 算法思想。

匈牙利解法的指派问题最优解的以下性质: 设指派问题的系数矩阵为 C=

?c ij ?

n? n

,若将 C 的一行(或列)各元素分别

减去一个常数 k(如该行或列的最小元素) ,则得到一个新的矩阵 C’=

?c 'ij ?



n? n

那么,以 C’位系数矩阵的指派问题和以 C 位系数矩阵的原指派问题有相同最优 解。 由于系数矩阵的这种变化不影响约束方程组,只是使目标函数值减少了常 数 k,所以,最优解并不改变。必须指出,虽然不比要求指派问题系数矩阵中无 负元素, 但在匈牙利法求解指派问题时,为了从以变换后的系数矩阵中判别能否 得到最优指派方案,要求此时的系数矩阵中无负元素。因为只有这样,才能从总 费用为零这一特征判定此时的指派方案为最优指派方案。

三、 算法步骤。

(1)变换系数矩阵,使各行和各列皆出现零元素。 各行及各列分别减去本行及本列最小元素,这样可保证每行及每列中都有 零元素,同时,也避免了出现负元素。

(2)做能覆盖所有零元素的最少数目的直线集合。 因此,若直线数等于 n,则以可得出最优解。否则,转第(3)步。 对于系数矩阵非负的指派问题来说,总费用为零的指派方案一定是最优指 派方案。在第(1)步的基础上,若能找到 n 个不同行、不同列的零元素,则对 应的指派方案总费用为零, 从而是最优的。 当同一行 (或列) 上有几个零元素时, 如选择其一,则其与的零元素就不能再被选择,从而成为多余的。因此,重要的 是零元素能恰当地分布在不同行和不同列上,而并在与它们的多少。但第(1) 步并不能保证这一要求。 若覆盖所有零元素的最少数目的直线集合中的直线数目 是 n,则表明能做到这一点。 此时,可以从零元素的最少的行或列开始圈“0” ,每圈一个“0” ,同时把 位于同行合同列的其他零元素划去(标记为) ,如此逐步进行,最终可得 n 个位 于不同行、不同列的零元素,他们就对应了最优解;若覆盖所有零元素的最少数 目的直线集合中的元素个数少于 n,则表明无法实现这一点。需要对零元素的分 布做适当调整,这就是第(3)步。

(3) 变换系数矩阵,是未被直线覆盖的元素中出现零元素。回到第(2)步。 在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的 行(或列)中各元素都减去这一最小元素,这样,在未被直线覆盖的元素中势必 会出现零元素, 但同时却又是以被直线覆盖的元素中出现负元素。为了消除负元 素,只要对它们所在的列(或行)中个元素都加上这一最小元素(可以看作减去 这一最小元素的相反数)即可。

四、 算法源程序。

#include<iostream.h> #include<stdlib.h> #define m 5 int input(int M[m][m]) { int i,j; for(i=0;i<m;i++) { cout<<"请输入系数矩阵第"<<i+1<<"行元素:"<<endl; 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++) { for(j=0;j<m;j++) cout<<M[i][j]<<"\t"; cout<<endl; } return M[m][m]; } int exchange(int M[m][m]) { int i,j,n; cout<<"进行行变换输入 0,进行列变换输入其他任意键:"<<endl; cin>>n; if(n==0) cout<<"分别输入要变换的行及该行未覆盖元素中最小元素:"<<endl; else cout<<"分别输入要变换的列及该列的最小元素:"<<endl; int a,b; cin>>a>>b; for(j=0;j<m;j++) if(n==0) M[a-1][j]-=b; else M[j][a-1]-=b; 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]; } void main() { int M[m][m]; cout<<"<<<<<<<<<<<<<<<<<<<匈牙利法解指派问 题>>>>>>>>>>>>>>>>>>>> "<<endl; while(true) { cout<<""<<endl; cout<<">>>>>>>>>>>>>>>> 菜单 <<<<<<<<<<<<<<<<"<<endl<<endl; cout<<" 1.系数矩阵输入 "<<endl; cout<<" 2.初始变换 "<<endl; cout<<" 3.行列变换 "<<endl; cout<<" 4.退出 "<<endl; cout<<"************************************"<<endl<<endl; int n; cout<<"请选择功能键"; cin>>n; 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; } } }

五、 算例和结果。
例 4—12 今有甲、乙、丙、丁 4 个人去完成 5 项任务。每人完成各项任

务所需的时间如表 4—11 所示。由于任务数多于人数,故规定其中有一人可兼完 成两项任务,其余三人各完成一项任务。是确定总花费时间为最小的指派方案。 (课本 P113) 表 4—11 任务 人 甲 乙 丙 丁 25 39 34 24 29 38 27 42 31 26 28 36 41 20 40 23 37 33 32 45 A B C D E

假设第 5 个人是戊,他完成各项任务的时间取甲、乙、丙、丁中的最小者, 构造表 4—12。

表 4—12 任务 人 甲 乙 丙 丁 戊 25 39 34 24 24 29 38 27 42 27 31 26 28 36 26 41 20 40 23 20 37 33 32 45 32 A B C D E

由表 4—12 可得到系数矩阵 C
? 25 ? 39 ? ? 34 ? ? 24 ? 24 ? 29 38 27 42 27 31 26 28 36 26 41 20 40 23 20 37 ? ? 33 ? 32 ? ? 45 ? 32 ? ?

C ?

1、将系数矩阵 C 输入程序。

2、对系数矩阵各行各列减去最小元素,即程序中的初始变换。

3、进行行变换

4、进行列变换

6、再次进行行变换

7、再次进行列变换

此时,已经不能用少于五根直线覆盖零元素,故此时为最优指派方案。
? 25 ? 39 ? ? 34 ? ? 24 ? 24 ? 29 38 27 42 27 31 26 28 36 26 41 20 40 23 20 37 ? ? 33 ? 32 ? ? ? 45 ? 32 ? ? ? 0 ? 18 ? ? 11 ? ? ?0 ? ? 3 ?

?0 ?
13 0 14 2

1

17 0 18 0

?0 ?
0 7 0

C ?

?0 ?

3 ? ? 3 ? ?0 ?? ? 12 ? 2 ? ?

最优指派方案是:甲做 B,乙做 C,丙做 E,丁做 A,戊做 D,由于戊(虚 拟的人)完成 D 的时间与乙相同,实际上最优指派方案是:乙完成 C 和 D,甲、 丙、丁分别完成 B,E,A,总计时间为 131。

六、 结论和总结。
匈牙利法解指派问题,其步骤简单易懂,操作起来也不难,可是由于计算 量实在太大很容易出错, 故利用程序来完成对系数矩阵的化简变换是再好不过的。 只要确定输入,以及找出的覆盖集合无误,则计算结果就不会出错。由于时间仓 促,我编的程序还有许多不足之处,比如说:在输入系数矩阵之前,需要事先定 义二维数组的行及列。针对这个问题我尝试了好几次,也没有解决。查了一些资 料,好像可以通过动态分配二维数组的空间大小来实现二维数组行和列的输入。 本来我想实现程序对系数矩阵零元素的直线覆盖功能的,可操作起来实在太难, 故改为手动操作。 通过这次课程设计,我不仅对运筹学的知识进行了巩固,也发觉到了编程 对数学的强大辅助功能。 利用它可以解决好多数学问题, 大大节省了时间及精力。 学好数学和计算机是今后就业的重要筹码。


相关文章:
指派问题的匈牙利解法
指派问题的匈牙利解法 1、 把各行元素分别减去本行元素的最小值;然后在此基础...指派问题的匈牙利法 21页 2下载券 运筹学指派问题的匈牙利... 15页 2下载...
浅析指派问题的匈牙利解法成稿
关键词:指派问题;匈牙利解法;最小零元素消耗法;对角...试验中,发现了一个较小阶不收敛的系数矩阵,下面用...5 结束语 指派问题运筹学中的经典问题,它的主要...
求解指派问题的匈牙利算法.doc
3.2 求解指派问题的匈牙利算法 由于指派问题的特殊性,又存在着由匈牙利数学家 ...运筹学指派问题的匈牙利... 15页 2下载券 最优指派问题匈牙利算法... 3...
匈牙利算法在企业员工指派问题的应用(最终版)
匈牙利算法在企业员工指派问题的应用(最终版) - 闽江学院 本科毕业论文 题目 匈牙利算法在企业员工指派问题的应用 张雯 学生姓名 学系年专号别级业 120080901139 ...
匈牙利算法在企业员工指派问题的应用(最终版)
关键词:匈牙利算法;员工指派问题;运筹学;效益矩阵 Abstract In modern society, ...经过我反复的 实验、观察效率矩阵的特殊性,现对效率矩阵进行改进,改进之后,就能...
更多相关标签: