练习题--匈牙利法

练习题--匈牙利法 五、有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下所示。 工A B C D 作 工人 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 解:用匈牙利法求解过程如下: 15182124，， ,,19232218,, 行列变化后得 C,,,26171619 ,,19212317，， 0269，， ,,14401,,C, 画出最少覆盖 0 的直线 r, 由于r=3<阶数, 调,,10003 ,,2360，， 整 0元素的分布后得 02610，， ,,03302,,C, 画出最少覆盖 0 的直线 r, 由于r=3<阶数, ,,10004 ,,1250，， 调整 0元素的分布后得 00410，， ,,01103,,C, 画出最少覆盖 0 的直线 r, 由于r=4=阶数 ,,12006 ,,1030，， 得最优指派: 01001000,,,,,,,,10000001,,,,,,XX12,,,,00100010,,,,,,,,00010100,,,, 最少的耗时数z=15+18+16+21=70。