数学建模指派问题论文

《数学建模指派问题论文》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录一问题重述3二模型假设3三匈牙利法陈述3四问题分析4五问题实现61问题重述62问题求解62.1由匈牙利法构造目标函数62.2模型建立73模型解析74程序实现8六结果显示及min求解27七模型深入271模型建立282进行求解283程序分析30八模型检验30九整体总结30十参考文献31一问题重述指派问题亦称平衡指派问题仅研究人数与事数相等、一人一事及一事一人的情形。现有的不平衡指派问题将研究范围扩大到人数与事数可以不等、一人一事或一人多事及一事一人的情形。日常活动中也不乏人数与事数可以不等、一人多事及一事多人的情形，这类事务呈现了广义指派问题的

2、实际背景。平衡指派问题是特殊形式的平衡运输问题，可运用匈亚利法、削高排除法和缩阵分析法等特殊方法求解。另一方面，正是平衡指派问题的这种特殊性，使得不平衡指派问题不能按常规技术转化为平衡指派问题。因此，各种不平衡指派问题需要确立相应的有效解法１问题的提出及其数学模型广义指派问题并非奇特和抽象的构想，相反，该问题可以从司空见惯的日常事务中引出。现在我们就运用匈牙利法，去实现n个人，n件工作的指派问题。二模型假设1假设一共有n个人，n件工作，即人数与工作数相等。2假设每个人的都能从事某项工作，但是付出的代价不同。3假设求解代价最小的解。4甲乙丙丁四个

3、人，ABCD四项工作，要求每人只能做一项工作，每项工作只由一人完成，问如何指派总时间最短？三匈牙利法陈述第一步：找出矩阵每行的最小元素，分别从每行中减去这个最小元素；第二步：再找去矩阵每列的最小元素，分别从各列减去这个最小元素；第三步：经过这两步变换后，矩阵的每行每列至少都有了一个零元素，接着根据以下准则进行试指派，找出覆盖上面矩阵中所有零元素至少需要多少条直线；（1）从第一行开始，若该行只有一个零元素打上（）号。对打（）号零元素所在列划一条直线。若该行没有零元素或有两个以上零元素（已划去的不计在内），则转下一行，一直到最后一行为止；（2）从第

4、一列开始，若该列只有一个零元素就对这个零元素打上（）号（同样不考虑已划去的零元素），对打（）号零元素所在行划一条直线。若该列没有零元素或还有两个以上零元素，则转下一列，并进行到最后一列；（3）重复（1）、（2）两个步骤，可能出现三种情况：①矩阵每行都有一个打（）号零元素，很显然，按照上述步骤得到的打（）的零元素都位于不同行不同列，因此就找到了问题的答案；②有多于两行或两列存在两个以上零元素，即出现了零元素的闭回路，这个时候可顺着闭回路的走向，对每个间隔的零元素打上（）号，然后对所有打（）号零元素或所有列或所在行划一条直线。③矩阵中所有零元素或打

5、上（）号，或被划去，但打（）号零元素个数小于m。第四步：为了设法使每行都有一个打（）的零元素，就要继续对矩阵进行变换；（1）从矩阵未被直线覆盖的元素找出最小元素k；（2）对矩阵的每行，当该行有直线覆盖时，令=0，无直线覆盖的，令=k；（3）对矩阵的每列，当该列有直线覆盖时，令=-k，无直线覆盖的，令=0；（4）得列一个变换后的矩阵，其中每个元素=--。第五步：回到第三步，反复进行，一直到矩阵中每一行都有一个打（）的零元素为止，即找到最优分配方案为止。四问题分析指派问题的标准形式（以人和事为例）如下。有n个人和n项任务，已知第i个人做第j件事的费

6、用为，要求确定人和事之间的一一对应的指派方案，使完成这n项任务的费用最少。一般把目标函数的系数写为矩阵形式，称矩阵为系数矩阵（CoefficientMatrix），也称为效益矩阵或价值矩阵。矩阵的元素（i,j=1,2,…n）表示分配第i个人去完成第j项任务时的效益。一般地，以表示给定的资源分配用于给定活动时的有关效益（时间，费用，价值等），且然后我们求解最小（最大（这里不再讨论））代价和模型，当然，作为可行解，矩阵的每列元素中都有且只有一个1，以满足约束条件式（3）。每行元素中也有且只有一个1，以满足约束条件（2）。指派问题n!个可行解。如果要

7、求解最大值时，我们将构造一个新的矩阵，使，其中是一个足够大的常数。一般取中最大的元素作为，求解，所得的解就是原问题的解。事实上，由可的此结论。五问题实现1问题重述已知问题甲乙丙丁四个人，ABCD四项工作，要求每人只能做一项工作，每项工作只由一人完成，问如何指派总时间最短？每个人的对每项工作的代价如下：2问题求解开始求解2.1由匈牙利法构造目标函数引入0-1变量xij，xij=1：第i人做第j项工作xij=0：第i人不做第j项工作约束条件：(i=1,2,…,92j=1,2,…,20)2.2模型建立即一项任务只由一个人完成一人只能完成一项任务求出目

8、标函数3模型解析根据指派问题的最优性定理，求最优解的问题可以转换为求效益矩阵的大1元素组的问题。匈牙利法的一般计算步骤为：步骤1：对效益矩阵进行初等变