文档介绍：理学院
最优化理论与应用
课程设计
学 号：XXXXXXX
专 业：应用数学
学生姓名：XXXXXX
任课教师：XXXXXX教授
2015年10月
第一部分
在最优化理论与应用这门课中，我对求指派问题及指派问题的一个很N 、
I ”可 引
1
■
2
3
11
6
14
19
10
5
13
4
0
0
0
0
0
7
q
0
0
即当甲分派C任务，乙分派A任务， 时间最短，最短时间为24小时。
丙分派B任务，戊分派D任务时，工作
此‘1数加上尬 >
4 0 4 12 5
6 13 0 5 7
0 0 2 1 2
4 0 « 12 3
4 (
6 1
-12 5
1 5 7
H Tfl 1. >
0 (
4 (
「：
! 1 2
:12 3
H 卜
0 -(J
1 0 1 9 ~T
6 16 0’ 5 7
M
由 3 "1 T
1 (T 5 厂 0*
0 4 1 0 —(T
匈牙利算法的缺点
“匈牙利算法”在各种已发表的教材，专注和研究成果中，通常求解中小 型分派问题，效能矩阵的阶数不超过20，故很难发现匈牙利算法”的缺点，匈 牙利算法在处理一些特殊数据时并不有效，算法不收敛，无法找出最优解。
在匈牙利算法的求解步骤中，效率矩阵即可以先进行行减约也可以先进行 列减约，但是，有时候先进行行减约比先进行列减约复杂，增加了许多步，有时 却相反。
匈牙利算法的改进
现对效率矩阵进行改进，这样就能知道先行减约还是先进行列减约，改进如 下：
第一步，简化效率矩阵。(1)统计效率矩阵每行的最小元素的个数总和R (sum)和每列的最小元素的个数总和C (sum)。(2)若R (sum)和C (sum)均 大于n，且当R (sum) >C (sum)时，则先对效率矩阵的没咧减去该列的最小元 素，在对所得效率矩阵的每行减去该行的最小元素。反之当R (sum) <C (sum) 时，则先对效率矩阵的每行减去该行的最小元素，在对所得效率矩阵的每列减去 该列的最小元素。(3)若R (sum)和C (sum)均不满足均大于n，且当R (sum) <C (sum)时，则先对效率矩阵的每列减去该行列的最小元素，在对所得效率矩 阵的每行减去该行的最小元素。反之，当R (sum) >C (sum)时，则先对效率矩 阵的每行减去该行的最小元素，在对所得效率矩阵的每列减去该列的最小元素；
第二步，检查矩阵C,若矩阵C的各行各列均有“0”，则跳过吃步，否则进 行列（或行）约减。得到新的矩阵
C；
第三步，画盖“0”线，即画最少的线讲矩阵C中的0全覆盖住，得新的矩 阵C；
第四步，数据转换。若“盖0”线的数目等于矩阵的维数则直接跳到第六步，
若“盖0”线的数目小于矩阵的维数则进行数据转换，步奏如下：
（1） 找到未被“盖0”线覆盖的数中的最小值人
（2） 将未被“盖0”线覆盖住的数减去人
（3） 将“盖0”线交叉的数加上人
第五部，重复第三步和第四步，直到“盖0”的数目等于矩阵的维数；
第六步，求最优解对n维矩阵，找到不同行，不同列的n个“0”，每个“0” 的位置代表一对配置关系，具体步骤如下：
（1） 先找只含有一个“0”的行（或列），将该行（或列）中的“0”
打“/ ”
（2） 将带“/”的“0”所在列（或行）中的“0”打“X”
（3） 重复（1）步和（2）步结束，若所有行列均含有多个“0”，
则从“0”的数目最少的行或列中任选一个“0”打“/”；
第七步，打“/”即为员工所对应的指派任务。
第三部分
匈牙利算法的C语言实现如下：
#include<>
#include<>
//#define M 5
//#define N 5
#define MAXSIZE 10
int M,N;
int arrangement[999][999];
int bestcost=999;
int x[999];
int bestx[999];
void backtrackarrage(int i,int cost);
void outputresult();
void swap(int i,int j);
main()
(
int i,j;
printf("请输入行(人数):M=");
scanf(〃％d〃，&M);
printf("请输入列(人数):N=");
scanf("%d",&N);
printf("**************输入方式 **********