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

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


运 筹 学
课 程 设 计 报 告

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

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。

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


相关文章:
运筹学指派问题的匈牙利法实验报告.doc
运筹学指派问题的匈牙利法实验报告_数学_自然科学_专业资料。指派问题的匈牙利法实
运筹学指派问题实验报告.doc
运筹学指派问题实验报告 - 运筹学实践报告 指派问题 第一部分 问题背景 泰泽公
运筹学指派问题的匈牙利法.doc
运筹学指派问题的匈牙利法_数学_自然科学_专业资料。指派问题的匈牙利法运筹学课程
匈牙利解法-指派问题-运筹学游庆山_图文.ppt
匈牙利解法-指派问题-运筹学游庆山 - 相册 由 User 创建... 运筹学| 匈牙利解法-指派问题-运筹学游庆山_数学_高中教育_教育专区。相册由 User 创建 相册...
《管理运筹学》分配问题与匈牙利算法.ppt
《管理运筹学》分配问题匈牙利算法 - 第4章 整数规划与分配问题 运筹学 分配问题匈牙利法 2013-8-22 第 1页 第4章 整数规划与分配问题 运筹学 1. 分配...
运筹学指派问题_图文.ppt
运筹学指派问题 - 运筹小额 指派问题 匈牙利算法... 运筹学指派问题_生产/经营管理_经管营销_专业资料。运筹小额 指派问题 匈牙利算法 第五节 指派问题(Assignment ...
运筹学实验报告.doc
运筹学实验报告 - 运筹与优化课内实验 检测 实验一:线性规划问题与对偶问题的建模与求解 一. 线性规划: 满足以下三个条件的称之为线性规划问题: (1)决策变量的...
运筹学指派问题课件.ppt
运筹学教程 第五节 指派问题一、指派问题的标准形式及其数学模型 标准形式(以...匈牙利法条件: MIN、i=j 、Cij≥0 运筹学教程 匈牙利法的主要步骤: 步骤1:...
运筹学指派问题.doc
运筹学指派问题_计算机软件及应用_IT/计算机_专业资料。运筹学作业 ---关于指派...本次的课程设计算法编写使为求最优的指派问题的程序, 运用的方法是匈牙利方法,...
运筹学中的指派问题.pdf
运筹学中的指派问题 - Advances in Applied Mathemat
运筹学匈牙利法_图文.ppt
运筹学匈牙利法 - 0-1 整数规划的应用 整数规划是一种特殊形式的整数规划,
运筹学实验报告.pdf
运筹学实验报告_调查/报告_表格/模板_实用文档。武汉大学 XXXX 学院 武汉大学 ...运输 问题、表上作业法、指派问题匈牙利法、线性规划在管理中的应用、目标 ...
运筹学 工作指派问题_图文.pdf
运筹学 工作指派问题 - 第一章 线性规划的基本 理论及其应用 1 第九节 工作指派问题 工作指派问题是这样一类问题: 有n个人和n件事,已知第i个人做第j件事的...
匈牙利解法的步骤.doc
匈牙利解法的步骤 - 指派问题的匈牙利法求解步骤: 1) 变换指派问题的系数矩阵
运筹学匈牙利算法示例_图文.ppt
运筹学匈牙利算法示例 - 匈牙利算法示例 (二)、解题步骤: 指派问题是0-1 规划的特例,也是运输问题的特例, 当然可用整数规划,0-1 规划或运输问题的解法去求 解...
运筹学匈牙利法_图文.ppt
运筹学匈牙利法 - 0-1 整数规划的应用 0-1 整数规划是一种特殊形式的整数
运筹学匈牙利法_图文.ppt
运筹学匈牙利法 - 0-1 整数规划的应用 0-1 整数规划是一种特殊形式的整数
运筹学-指派问题_图文.ppt
运筹学-指派问题 - 指派问题 重庆移动公司基站维护外包问题的分析及对策 中,结
匈牙利法解决人数与任务数不等的指派问题1.doc
匈牙利法解决人数与任务数不等的指派问题1 - 匈牙利法解决人数与任务数不等的指派问题 于凯 重庆科技学院 经济管理学院 物流专业 重庆沙坪坝区 摘要: 本文将讨论...
指派问题的算法分析与实现.doc
运筹学中求解整数 规划的指派问题通常是通过匈牙利算法来求解,但指派问题也可以归结为一个 0-1 整数规划问题,本文先对指派问题进行陈述,引出对实际问题的求解。...
更多相关标签: