§2分配问题与匈牙利法 解：1) 变换系数矩阵，增加0元素。 21513 4]-2 0 13 11 2 0 137 0 10414 15-4 6 0 10 11 6 0 6 9 914 16 13 -9 0 5 7 4 0 5 3 2 78 11 9 -7 0 4 2 0 1 0 0 2) -4 试指派 (找独立0元素) -2 06 10 ) 独立0元素的个数为4，指派问题的最优指 派方案即为甲负责D工作，乙负责B工作， 丙负责A工作，丁负责C工作。这样安排 3 能使总的工作时间最少，为4+4+9+11 2014-12 0 0 =28。 16
2014-12-15 16 §2 分配问题与匈牙利法 解：1）变换系数矩阵，增加0元素。 7 9 4 2 7 8 11 9 9 14 16 13 10 4 14 15 2 15 13 4 4 2 0 1 4 2 0 5 7 4 6 0 10 11 0 13 11 2 0 1 0 0 0 5 3 2 6 0 6 9 0 13 7 0 0 1 0 0 0 5 3 2 6 0 6 9 0 13 7 0 (0) (0) (0) (0) 2）试指派（找独立0元素） 独立0元素的个数为4 , 指派问题的最优指 派方案即为甲负责D工作，乙负责B工作， 丙负责A工作，丁负责C工作。这样安排 能使总的工作时间最少，为4＋4＋9＋11 ＝28
§2分配问题与匈牙利法 例4已知五人分别完成五项工作耗费如下表，求最优分配 方案。 任务 A B C D E 人员 甲 7 5 9 8 11 乙 9 12 7 11 9 丙 8 5 4 6 8 丁 7 3 6 9 6 戊 4 6 1 5 11 2014-12-15 17
2014-12-15 17 §2 分配问题与匈牙利法 例4 已知五人分别完成五项工作耗费如下表，求最优分配 方案。 任务 人员 A B C D E 甲 7 5 9 8 11 乙 9 12 7 11 9 丙 8 5 4 6 8 丁 7 3 6 9 6 戊 4 6 7 5 11
§2分配问题与匈牙利法 解：1)变换系数矩阵，增加0元素。 7 5 98 11 -5 2 0 43 6 9 12 7 11 9 -7 2 5 0 4 2 85 4 6 9 -4 → 4 1 0 2 5 7 3 9 6 -3 4 0 3 6 3 4 6 75 11-4 0 2 3 1 -1 75 2014-12-15 18
2014-12-15 18 §2 分配问题与匈牙利法 4 3 4 7 5 4 6 7 5 11 7 3 6 9 6 8 5 4 6 9 9 12 7 11 9 7 5 9 8 11 0 2 3 1 7 4 0 3 6 3 4 1 0 2 5 2 5 0 4 2 2 0 4 3 6 -1 -2 解：1）变换系数矩阵，增加0元素
§2分配问题与匈牙利法 2)试指派（找独立0元素） 2 2 42 4 2 5 0 0 25-030 4 1 0 1 3 4 3 4 0 5 1 40 2 3 0 5 8-3-0-5 独立0元素的个数1=4<5，故调整矩阵。 2014-12-15 19
2014-12-15 19 §2 分配问题与匈牙利法 0 2 3 0 5 4 0 3 5 1 4 1 0 1 3 2 5 0 3 0 2 0 4 2 4 0 2 3 0 5 4 0 3 5 1 4 1 0 1 3 2 5 0 3 0 2 (0) 0 4 2 4 (0) 2）试指派（找独立0元素） 独立0元素的个数l＝4<5，故调整矩阵。 (0) (0)
§2分配问题与匈牙利法 选择直线外的最小元素为1；直线外元素减1，直线交点 元素加1，其他保持不变。 2014-12-15 20
2014-12-15 20 §2 分配问题与匈牙利法 选择直线外的最小元素为1；直线外元素减1，直线交点 元素加1，其他保持不变