数学建模指派问题论文正稿.doc

目录一问题重述3二模型假设3三匈牙利法陈述3四问题分析4五问题实现61问题重述62 问题求解62.1由匈牙利法构造目标函数62.2模型建立73 模型解析74 程序实现8六结果显示及min求解27七模型深入271 模型建立282 进行求解283程序分析30八模型检验30九整体总结30十参考文献31一 问题重述指派问题亦称平衡指派问题仅研究人数与事数相等、一人一事及一事一人的情形现有的不平衡指派问题将研究范围扩大到人数与事数可以不等、一人一事或一人多事及一事一人的情形日常活动中也不乏人数与事数可以不等、一人多事及一事多人的情形.这类事务呈现了广义指派问题的实际背景平衡指派问题是特殊形式的平衡运输问题.可运用匈亚利法、削高排除法和缩阵分析法等特殊方法求解另一方面.正是平衡指派问题的这种特殊性.使得不平衡指派问题不能按常规技术转化为平衡指派问题因此.各种不平衡指派问题需要确立相应的有效解法１问题的提出及其数学模型广义指派问题并非奇特和抽象的构想.相反.该问题可以从司空见惯的日常事务中引出现在我们就运用匈牙利法.去实现n个人.n件工作的指派问题二 模型假设1 假设一共有n个人.n件工作.即人数与工作数相等。

2 假设每个人的都能从事某项工作.但是付出的代价不同 3 假设求解代价最小的解 4甲乙丙丁四个人.ABCD四项工作.要求每人只能做一项工作.每项工作只由一人完成.问如何指派总时间最短？ 三 匈牙利法陈述 第一步：找出矩阵每行的最小元素.分别从每行中减去这个最小元素；第二步：再找去矩阵每列的最小元素.分别从各列减去这个最小元素；第三步：经过这两步变换后.矩阵的每行每列至少都有了一个零元素.接着根据以下准则进行试指派.找出覆盖上面矩阵中所有零元素至少需要多少条直线；〔1从第一行开始.若该行只有一个零元素打上〔号对打〔号零元素所在列划一条直线若该行没有零元素或有两个以上零元素〔已划去的不计在内.则转下一行.一直到最后一行为止；〔2从第一列开始.若该列只有一个零元素就对这个零元素打上〔号〔同样不考虑已划去的零元素.对打〔号零元素所在行划一条直线若该列没有零元素或 还有两个以上零元素.则转下一列.并进行到最后一列；〔3重复〔1、〔2两个步骤.可能出现三种情况：① 矩阵每行都有一个打〔号零元素.很显然.按照上述步骤得到的打〔的零元素都位于不同行不同列.因此就找到了问题的答案；② 有多于两行或两列存在两个以上零元素.即出现了零元素的闭回路.这个时候可顺着闭回路的走向.对每个间隔的零元素打上〔号.然后对所有打〔号零元素或所有列或所在行划一条直线。

③ 矩阵中所有零元素或打上〔号.或被划去.但打〔号零元素个数小于m第四步：为了设法使每行都有一个打〔的零元素.就要继续对矩阵进行变换；〔1从矩阵未被直线覆盖的元素找出最小元素k；〔2对矩阵的每行.当该行有直线覆盖时.令=0.无直线覆盖的.令=k；〔3对矩阵的每列.当该列有直线覆盖时.令=-k.无直线覆盖的.令=0；〔4得列一个变换后的矩阵.其中每个元素=--第五步：回到第三步.反复进行.一直到矩阵中每一行都有一个打〔的零元素为止.即找到最优分配方案为止四问题分析指派问题的标准形式〔以人和事为例如下有n个人和n项任务.已知第i个人做第j件事的费用为.要求确定人和事之间的一一对应的指派方案.使完成这n项任务的费用最少 一般把目标函数的系数写为矩阵形式.称矩阵为系数矩阵〔Coefficient Matrix.也称为效益矩阵或价值矩阵矩阵的元素〔i,j=1,2,…n表示分配第i个人去完成第j项任务时的效益一般地.以表示给定的资源分配用于给定活动时的有关效益〔时间.费用.价值等.且然后我们求解最小〔最大〔这里不再讨论代价和模型.当然.作为可行解.矩阵的每列元素中都有且只有一个1.以满足约束条件式〔3。

每行元素中也有且只有一个1.以满足约束条件〔2指派问题n!个可行解如果要求解最大值时.我们将构造一个新的矩阵.使.其中是一个足够大的常数一般取中最大的元素作为.求解.所得的解就是原问题的解事实上.由可的此结论五问题实现1问题重述已知问题甲乙丙丁四个人.ABCD四项工作.要求每人只能做一项工作.每项工作只由一人完成.问如何指派总时间最短？ 每个人的对每项工作的代价如下：2 问题求解开始求解2.1由匈牙利法构造目标函数引入0-1变量xij.xij =1：第i人做第j项工作 xij =0：第i人不做第j项工作约束条件： 2.2模型建立即一项任务只由一个人完成一人只能完成一项任务求出目标函数3 模型解析根据指派问题的最优性定理.求最优解的问题可以转换为求效益矩阵的大1元素组的问题匈牙利法的一般计算步骤为：步骤1：对效益矩阵进行初等变换.使每行每列都出现0元素1.      从效益矩阵A中每一行减去该行的最小元素；2.      再在所得矩阵中每一列减去该列的最小元素.得矩阵D；步骤2：将矩阵D中0元素置为1元素.非0元素置为0元素.得矩阵E。

步骤3：确定独立1元素组1.      在矩阵E中含有1元素的各行中选择1元素最少的行.比较该行中各1元素所在的列中1元素的个数.选择1元素的个数最少的那一列中的1元素；2.      将所选的1元素所在的行和列的元素置为0；3.      重复第2步和第3步.直到没有1元素为止.即得到一个独立1元素组步骤4：判断是否为最大独立1元素组1.      如果所得独立1元素组为原效益矩阵的最大独立1元素组〔即1元素的个数等于矩阵的阶数.则已得到最优解.停止计算；2.      如果所得独立1元素组还不是原效益矩阵的最大独立1元素组.那么继续寻找可扩路的方法对其进行扩张.进行下一步；步骤5：利用寻找可扩路方法确定最大独立1元素组1.      做最少的直线覆盖矩阵D的所有0元素；2.      在没有被直线覆盖的部分找出最小元素.在没有被直线覆盖的各行减去此最小元素.在没有被直线覆盖的各列上加上此最小元素.得到一个新的矩阵.返回第二步4 程序实现这里我们运用c++语言进行编程进行求解/************************************************************************//* zhipai2.cpp Author: 路遥Date:2012-12-1 Description:需要在同样的目录下建立一个input.txt的文件夹在里面写入每个人从事不同的工作代价.首行要写入几阶方程.然后是每个人的不同工作代价.用空格隔开。

每人一行.见下面数字形式用匈牙利法.实现n个人.n件工作的指派问题Input:input.txt 格式为代价矩阵维度n.和矩阵内容.例如：43 5 8 46 8 5 42 5 8 59 2 5 2Output:控制台输出指派矩阵.例如0 0 0 10 0 1 01 0 0 00 1 0 0*//************************************************************************/#include #include using namespace std;#define MAX_N 100int nn;//输入矩阵的维度nnvoid printMatrix{ int i,j; for { for cout< { int c[MAX_N][MAX_N],b[MAX_N][MAX_N]; int quan[MAX_N][MAX_N],cha[MAX_N][MAX_N]; int rowZero[MAX_N],colZero[MAX_N]; int rowCheck[MAX_N],colCheck[MAX_N]; int i,j,k; ifstream input<"input.txt">; if { cout<<"Open input file failed."<; exit<1>; } //读取输入文件 input>>nn; for { for { input>>c[i][j]; b[i][j]=c[i][j]; } } input.close<>; //每行减去该行最小 for { int min=b[i][0]; for { if min=b[i][j]; } for b[i][j] -= min; } //每列减去该列最小 for { int min=b[0][j]; for { if min=b[i][j]; } for b[i][j] -= min; } //开始尝试进行试指派assign: //初始化标记数组和计数数组 for { rowZero[i]=colZero[i]=0; rowCheck[i]=colCheck[i]=0; for quan[i][j]=cha[i][j]=0; } //计算每行每列0元素个数 for for if { rowZero[i]++; colZero[j]++; } bool flag; //直到尽可能多的0元素都被圈出和划掉为止 do { flag=false; //寻找只有一个0元素的行.加圈划叉 for { if//该行只有一个0元素 { //cout<<"rowZero found: "< { if { quan[i][j]=1; rowZero[i]--; colZero[j]--; for { if { cha[k][j]=1; rowZero[k]--; colZero[j]--; } } break; } } /。