提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

【运筹学】匈牙利法 ( 匈牙利法步骤 | 第二步 : 试指派操作示例 )

操作 示例 步骤 运筹学 匈牙利 指派
2023-06-13 09:17:48 时间

文章目录

一、指派问题求解步骤

指派问题求解步骤 :

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_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 3 & 7 & 1 & 0 & \\ \end{bmatrix}

下面进行试指派操作 , 试指派就是找独立

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_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 2 & 6 & 0 & -1 & \\ \end{bmatrix}

第

4

行第

4

列出现了

-1

, 这里在将第

4

列都加上

1

, 得到如下矩阵 :

(b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 1 & \\\\ & 0 & 1 & 0 & 5 & \\\\ & 2 & 0 & 4 & 4 & \\\\ & 2 & 6 & 0 & 0 & \\ \end{bmatrix}

第一行此时没有独立的

0

了 , 第一行再减去

1

, 得到如下矩阵 :

(b_{ij}) = \begin{bmatrix} & 3 & 4 & 3 & 0 & \\\\ & 0 & 1 & 0 & 5 & \\\\ & 2 & 0 & 4 & 4 & \\\\ & 2 & 6 & 0 & 0 & \\ \end{bmatrix}

再次进行试指派 , 找到了如下独立

0

元素 ;

在上述没有找到

4

个独立

0

元素后 , 由于在第

4

行没有找到

0

元素 , 开始从第

4

行进行调整 ,

调整时将非

0

的最小值转为

0

, 这样本行就多出一个

0

, 以及负数 , 负数有需要再对应列加上一个值 , 保持矩阵中所有的值都是非负的 ;

相关文章