一、使用匈牙利法求解下面的指派问题

四人分别完成四项工作所用时间 :

二、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )

先写出指派问题的系数矩阵 :

( c i j ) = [ 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 ] (c_{ij}) =

使每行都出现 $0$ 元素 : $(c_{ij})$ 系数矩阵中 , 每行都 减去该行最小元素 ;

• 第 $1$ 行减去最小值 $2$ ;
• 第 $2$ 行减去最小值 $4$ ;
• 第 $3$ 行减去最小值 $9$ ;
• 第 $4$ 行减去最小值 $7$ ;

( c i j ′ ) = [ 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2 ] (c_{ij}') =

此时发现有两列 , 第 $4$ 列 , 第 $5$ 列 , 没有 $0$ 元素 , 这两列每列都减去最小值 :

• 第 $3$ 列减去最小值 $4$ ;
• 第 $4$ 列减去最小值 $2$ ;

最终得到行列都有 $0$ 元素的系数矩阵 $(b_{ij})$ :

( b i j ) = [ 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 ] (b_{ij}) =

三、第二步 : 试指派 ( 找独立 0 元素 )

基于上一步的行列都有 $0$ 元素的系数矩阵 ,

( b i j ) = [ 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 ] (b_{ij}) =

进行试指派 ;

找出每行的独立 $0$ 元素 ,

优先从唯一选择开始 ,

第 $2$ 行只有 $1$ 个 $0$ 元素 , 该元素是独立 $0$ 元素 ;

第 $3$ 行只有 $1$ 个 $0$ 元素 , 该元素是独立 $0$ 元素 ( 红色矩形框 ) , 位于第 $1$ 列 ; 同时第 $1$ 列中的其它 $0$ 元素标记为 废弃 $0$ 元素 ( 绿色矩形框 );

第 $1$ 行和第 $4$ 行都有多个 $0$ 元素 ;

然后从列里面找独立 $0$ 元素 , 第 $1$ 列 和 第 $2$ 列都已经找到了 $0$ 元素 , 这里看 第 $3$ 列 和 第 $4$ 列 ;

第 $3$ 列有 独立 $0$ 元素 ( 红色矩形框 ) ; 位于第 $4$ 行 , 将第 $4$ 行的其它 $0$ 元素标记为 废弃 $0$ 元素 ( 绿色矩形框 ) ;

第 $4$ 列有 独立 $0$ 元素 ( 红色矩形框 ) ; 位于第 $1$ 行 , 将第 $1$ 行的其它 $0$ 元素标记为 废弃 $0$ 元素 ( 绿色矩形框 ) , 已经标记过了 , 不用再进行标记 ;

这里第一次指派就找到了最优解 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/112603385