【运筹学】匈牙利法 ( 匈牙利法步骤 | 试指派调整矩阵原理分析 | 打 √ | 直线覆盖 )

韩曙亮

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

8480

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

文章目录

一、指派问题求解步骤

指派问题求解步骤 :

1 . 使行列出现

元素 : 指派问题系数矩阵

(c_{ij})

变换为

(b_{ij})

系数矩阵 , 在

(b_{ij})

矩阵中每行每列都出现

元素 ;

每行都出现

元素 :

(c_{ij})

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

每列都出现

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

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

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

在

(b_{ij})

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

元素 , 如果能找到

个独立

元素 , 以这

个独立

元素对应解矩阵

(x_{ij})

中的元素为

, 其余元素为

, 这样就得到最优解 ;

二、打 √

分析【运筹学】匈牙利法 ( 匈牙利法步骤 | 第二步 : 试指派操作示例 ) 博客中试指派调整矩阵的原理 ;

下面的矩阵是完成第一步操作后 , 得到的行列都有

的元素的系数矩阵

(b_{ij})

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

试指派后的结果如下 :

定位一个没有独立

元素的行 : 先对没有

元素的行打钩 √ : 第

行没有独立

元素 , 第

行打 √ ;

讨论第

行 : 第

行没有独立的

元素 , 但是有废弃的

元素 , 因为在第一步已经保证了每行每列都有

元素 ;

在第

行

元素所在列 , 即第

列 , 打 √ ;

讨论第

列 : 上述打钩的列中 , 查看是否有独立的

元素 , 如果有对应的行就打 √ ;

第

行有独立的

元素 , 在第

行位置打 √ ;

讨论第

行 : 查看第

行是否有废弃的

元素 , 如果有就继续打 √ , 如果没有就停止 ;

第

行没有废弃的

元素 , 直接停止 ;

讨论行的时候讨论的是废弃的

元素 ,

讨论列的时候讨论的是独立的

元素 ;

三、直线覆盖

打 √ 完毕 , 开始讨论覆盖 ,

没有打 √ 的行划线 , 打 √ 的列划线 , 三条线就将所有的

元素覆盖了 ,

在没有被覆盖的元素中 , 找最小的元素

, 将该元素所在的没有覆盖的行

-1

, 覆盖的列

;

最终得到如下矩阵 :

(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 条评论

热度