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

韩曙亮

发布于 2023-03-28 20:51:38

1.4K0

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、指派问题求解步骤

指派问题求解步骤 :

1 . 使行列出现

元素 : 指派问题系数矩阵

(c_{ij})

变换为

(b_{ij})

系数矩阵 , 在

(b_{ij})

矩阵中每行每列都出现

元素 ;

每行都出现

元素 :

(c_{ij})

系数矩阵中 , 每行都减去该行最小元素 ;

每列都出现

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

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

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

在

(b_{ij})

系数矩阵中找到尽可能多的独立

元素 , 如果能找到

个独立

元素 , 以这

个独立

元素对应解矩阵

(x_{ij})

中的元素为

, 其余元素为

, 这样就得到最优解 ;

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

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

元素的系数矩阵 :

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

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

元素 , 独立

元素就是位于不同行不同列的

元素 ;

第

行只有

个

, 选第

个 ; 每行每列只能选择

个 , 第

行第

列的

元素就不能再用了 ;

第

行只有

个

, 选第

个 ;

第

行有

个

, 都可以选择 , 这里选择第

个 ;

最终试指派结果 :

上面只找到了

个独立的

元素 , 应该找出

个独立

元素 ;

调整上述系数矩阵

(b_{ij})

, 每行每列同时增加或减去一个数 , 且不能出现负数 ;

第

行都减去

, 得到如下矩阵 :

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

第

行第

列出现了

-1

, 这里在将第

列都加上

, 得到如下矩阵 :

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

第一行此时没有独立的

了 , 第一行再减去

, 得到如下矩阵 :

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

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

元素 ;

在上述没有找到

个独立

元素后 , 由于在第

行没有找到

元素 , 开始从第

行进行调整 ,

调整时将非

的最小值转为

, 这样本行就多出一个

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-01-14，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

基础

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

博客

基础

登录后参与评论

0 条评论

热度