匈牙利法真题演练

匈牙利法真题演练（07年5月）：

某车间产品装配组有王成、赵云、江平、李鹏四位员工.现有A、B、C、D四项任务，在现有生产技术组织条件下，每位员工完成每项工作所需要的工时如表1所示。 问：请运用匈牙利法求出员工与任务的配置情况，以保证完成任务的总时间最短，并求出完成任务的量短时间。 表1 工 作 任 务 员工 王 成 赵 云 江 平 李 鹏 A B C D

10 13 3 18 5 18 2 9 9 6 4 10 18 12 4 16 解题步骤：

1、建立矩阵 10 13 3 18

2、行列约减 5 7 1 9 （-1） 5 18 2 9 9 6 4 10 18 12 4 16 （-5） （-6） （-2） （-9） 0 12 0 0 4 0 2 1 13 6 2 7 （-2） PS：行约减以后需要检查列是否都有“0”

1

3、盖“0” 4 6 0 8

0 12 0 0 4 0 2 1 11 4 0 5

“盖0”只有三条，需要找出剩下数字中最小约数

4、继续约减，交叉处加上约数 3 0 6 13 0 1 7 0

3

0 2 0 10 4 0 4

当我们做完第三步会发现盖0线的数目仍然小于矩阵维数，继续寻找最小约数

将未被盖0线覆盖的数字都减去最小约数，同时在盖0线交叉点上的数字加上这个最小约数

5、数据转化 0 3 0 4

6、求最优解

0√ 3 0× 4

0 13 4 0 3 0 5 0 7 1 0 1

四条盖0线，四个维度，进行求最优解，首先只有一个0的行列，打钩

0× 13 4 0√ 3 0√ 5 0× 7 1 0√ 1

得到最优解如下：王—A；赵—D；江—B；李—C。 对照工时消耗表，完成任务的总时间为10+9+6+4=29

2

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库匈牙利法真题演练在线全文阅读。