一、指派问题求解步骤

指派问题求解步骤 :

1 . 使行列出现 $0$ 元素 : 指派问题系数矩阵 $(c_{ij})$ 变换为 $(b_{ij})$ 系数矩阵 , 在 $(b_{ij})$ 矩阵中 每行 每列 都出现 $0$ 元素 ;

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

• 每列都出现 $0$ 元素 : 在上述变换的基础上 , 每列元素中 减去该列最小元素 ;

注意必须先变行 , 然后再变列 , 行列不能同时进行改变 ; 否则矩阵中会出现负数 , 该矩阵中 不能出现负数 ;

2 . 试指派 : 进行尝试指派 , 寻求最优解 ;

在 $(b_{ij})$ 系数矩阵 中找到尽可能多的 独立 $0$ 元素 , 如果能找到 $n$ 个独立 $0$ 元素 , 以这 $n$ 个独立 $0$ 元素对应解矩阵 $(x_{ij})$ 中的元素为 $1$ , 其余元素为 $0$ , 这样就得到最优解 ;

二、第二步 : 试指派操作示例

在 【运筹学】匈牙利法 ( 匈牙利法步骤 | 第一步 : 使行列出现 0 元素示例 ) 博客示例基础上 , 已经得到了行列都有 $0$ 元素的系数矩阵 :

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

下面进行试指派操作 , 试指派就是找独立 $0$ 元素 , 独立 $0$ 元素就是位于不同行不同列的 $0$ 元素 ;

第 $1$ 行只有 $1$ 个 $0$ , 选第 $4$ 个 ; 每行每列只能选择 $1$ 个 , 第 $4$ 行第 $4$ 列的 $0$ 元素就不能再用了 ;

第 $3$ 行只有 $1$ 个 $0$ , 选第 $2$ 个 ;

第 $2$ 行有 $2$ 个 $0$ , 都可以选择 , 这里选择第 $1$ 个 ;

最终试指派结果 :

上面只找到了 $3$ 个独立的 $0$ 元素 , 应该找出 $4$ 个独立 $0$ 元素 ;

调整上述系数矩阵 $(b_{ij})$ , 每行每列同时增加或减去一个数 , 且不能出现负数 ;

第 $4$ 行都减去 $1$ , 得到如下矩阵 :

( b i j ) = [ 4 5 4 0 0 1 0 4 2 0 4 3 2 6 0 − 1 ] (b_{ij}) =

第 $4$ 行第 $4$ 列出现了 $-1$ , 这里在将第 $4$ 列都加上 $1$ , 得到如下矩阵 :

( b i j ) = [ 4 5 4 1 0 1 0 5 2 0 4 4 2 6 0 0 ] (b_{ij}) =

第一行此时没有独立的 $0$ 了 , 第一行再减去 $1$ , 得到如下矩阵 :

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

再次进行试指派 , 找到了如下独立 $0$ 元素 ;

在上述没有找到 $4$ 个独立 $0$ 元素后 , 由于在第 $4$ 行没有找到 $0$ 元素 , 开始从第 $4$ 行进行调整 ,

调整时将非 $0$ 的最小值转为 $0$ , 这样本行就多出一个 $0$ , 以及负数 , 负数有需要再对应列加上一个值 , 保持矩阵中所有的值都是非负的 ;

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

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