【运筹学】匈牙利法 ( 匈牙利法步骤 | 第一步 : 使行列出现 0 元素示例 )

一、指派问题求解步骤

指派问题求解步骤 :

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

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

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

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

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

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

二、第一步 : 使行列出现 0 0 0 元素示例

上一篇博客 【运筹学】匈牙利法 ( 克尼格定理 | 匈牙利法引入 ) 中的指派问题 :

A A A B B B C C C D D D甲 6 6 6 7 7 7 11 11 11 2 2 2乙 4 4 4 5 5 5 9 9 9 8 8 8丙 3 3 3 1 1 1 10 10 10 4 4 4丁 5 5 5 9 9 9 8 8 8 2 2 2

系数矩阵 ( c i j ) = [ 6 7 11 2 4 5 9 8 3 1 10 4 5 9 8 2 ] (c_{ij}) =\begin{bmatrix} & 6 & 7 & 11 & 2 & \\\\ & 4 & 5 & 9 & 8 & \\\\ & 3 & 1 & 10 & 4 & \\\\ & 5 & 9 & 8 & 2 & \\ \end{bmatrix} (cij​)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡​​6435​7519​119108​2842​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤​

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

第 1 1 1 行减去 2 2 2 , 第 2 2 2 行减去 4 4 4 , 第 3 3 3 行减去 1 1 1 , 第 4 4 4 行减去 2 2 2 ,

得到新的系数矩阵 系数矩阵 [ 4 5 9 0 0 1 5 4 2 0 9 3 3 7 6 0 ] \begin{bmatrix} & 4 & 5 & 9 & 0 & \\\\ & 0 & 1 & 5 & 4 & \\\\ & 2 & 0 & 9 & 3 & \\\\ & 3 & 7 & 6 & 0 & \\ \end{bmatrix} ⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡​​4023​5107​9596​0430​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤​

每列都出现 0 0 0 元素 : 在上述变换的基础上 , 每列元素中 减去该列最小元素 ; 观察矩阵后发现 , 只有第三列没有 0 0 0 元素 , 这里将第 3 3 3 列 , 都减去最小值 5 5 5 , 得到如下矩阵 :

( b i j ) = [ 4 5 4 0 0 1 0 4 2 0 4 3 3 7 1 0 ] (b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 3 & 7 & 1 & 0 & \\ \end{bmatrix} (bij​)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡​​4023​5107​4041​0430​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤​

这样就得到每行每列都有 0 0 0 元素的矩阵 ;