.

.

目录

TOC \o "1-3" \h \z \u 一 问题重述 3

二 模型假设 3

三 匈牙利法陈述 3

四 问题分析 4

五 问题实现 6

1问题重述 6

2 问题求解 6

2.1由匈牙利法构造目标函数 6

2.2模型建立 7

3 模型解析 7

4 程序实现 8

六 结果显示及min求解 27

七 模型深入 27

1 模型建立 28

2 进行求解 28

3程序分析 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四项工作，要求每人只能做一项工作，每项工作只由一人完成，问如何指派总时间最短？

每个人的对每项工作的代价如下：