精华内容
下载资源
问答
  • 匈牙利法
    2021-01-13 10:10:39





    一、克尼格定理



    匈牙利法 主要用于解决指派问题 , 其主要依据是 克尼格定理 ;

    指派问题 参考 【运筹学】整数规划 ( 整数规划求解方法 | 指派问题 ) 博客 ;


    克尼格定理 :

    分配问题 效率矩阵 [ a i j ] [a_{ij}] [aij] 中 ,

    每一行元素 中加上或减去一个常数 u i u_i ui ,

    每一列元素 中加上或减去一个常数 v j v_j vj ,

    得到新的效率矩阵 [ b i j ] [b_{ij}] [bij] ,

    两个效率矩阵 [ a i j ] [a_{ij}] [aij] [ b i j ] [b_{ij}] [bij] 分配问题的 最优解相同 ;


    克尼格定理示例 : 指派问题 , 给 4 4 4 个人指派 4 4 4 个岗位 , 每个人在不同的岗位产生的利润不同 , 如何安排使得利润最高 ;

    A A A B B B C C C D D D
    85 85 85 92 92 92 73 73 73 90 90 90
    95 95 95 87 87 87 78 78 78 95 95 95
    82 82 82 83 83 83 79 79 79 90 90 90
    86 86 86 90 90 90 80 80 80 88 88 88

    给 甲 对应的行加上所有表格都加上 5 5 5 , 变为如下表格 ,

    A A A B B B C C C D D D
    90 90 90 97 97 97 78 78 78 95 95 95
    95 95 95 87 87 87 78 78 78 95 95 95
    82 82 82 83 83 83 79 79 79 90 90 90
    86 86 86 90 90 90 80 80 80 88 88 88

    甲 今天状态好 , 不管四个工作 , 哪个分配给 甲 , 其产生的利润都会增加 ;

    最终计算出来的指派问题的最优解是不变的 ;





    二、匈牙利法引入



    给 甲乙丙丁 四人分配 A B C D ABCD ABCD 四项工作 , 每人做每项工作的耗时如下 , 如何指派问题使得耗时最小 ;

    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

    分派任务时 , 给每个人分配其所用时间最小的工作 ,

    • 给 甲 分配 D D D 任务 , 其只用 2 时间即可完成该任务 , 耗时最小 ;
    • 给 乙 分配 A A A 任务 , 其只用 4 时间即可完成该任务 , 耗时最小 ;
    • 给 丙 分配 B B B 任务 , 其只用 1 时间即可完成该任务 , 耗时最小 ;
    • 给 丁 分配 C C C 任务 , A B D ABD ABD 任务已经分配给了其它人 , 只能给 丁 分配 C C C 任务 ;

    如果 为每个人选择了耗时最小的任务 , 正好位于不同行 , 不同列 , 那么当前的指派 , 就是该问题的 最优解 ;

    但是上述示例中 , 给 丁 分配任务时 , 合适的任务都分配给了甲乙丙 , 只能分配 C C C 任务 ;

    这时就需要讨论给 丁 指派 C C C 任务是否是最优的 ;


    这里就需要 引入 匈牙利法 解决上述问题 ;

    更多相关内容
  • 一、使用匈牙利法求解下面的指派问题、 二、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )、 三、第二步 : 试指派 ( 找独立 0 元素 )





    一、使用匈牙利法求解下面的指派问题



    四人分别完成四项工作所用时间 :

    A A A B B B C C C D D D
    2 2 2 15 15 15 13 13 13 4 4 4
    10 10 10 4 4 4 14 14 14 15 15 15
    9 9 9 14 14 14 16 16 16 13 13 13
    7 7 7 8 8 8 11 11 11 9 9 9




    二、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )



    先写出指派问题的系数矩阵 :

    ( c i j ) = [ 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 ] (c_{ij}) =\begin{bmatrix} & 2 & 15 & 13 & 4 & \\\\ & 10 & 4 & 14 & 15 & \\\\ & 9 & 14 & 16 & 13 & \\\\ & 7 & 8 & 11 & 9 & \\ \end{bmatrix} (cij)=2109715414813141611415139


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

    • 1 1 1 行减去最小值 2 2 2 ;
    • 2 2 2 行减去最小值 4 4 4 ;
    • 3 3 3 行减去最小值 9 9 9 ;
    • 4 4 4 行减去最小值 7 7 7 ;

    ( c i j ′ ) = [ 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2 ] (c_{ij}') =\begin{bmatrix} & 0 & 13 & 11 & 2 & \\\\ & 6 & 0 & 10 & 11 & \\\\ & 0 & 5 & 7 & 4 & \\\\ & 0 & 1 & 4 & 2 & \\ \end{bmatrix} (cij)=06001305111107421142


    此时发现有两列 , 第 4 4 4 列 , 第 5 5 5 列 , 没有 0 0 0 元素 , 这两列每列都减去最小值 :

    • 3 3 3 列减去最小值 4 4 4 ;
    • 4 4 4 列减去最小值 2 2 2 ;

    最终得到行列都有 0 0 0 元素的系数矩阵 ( b i j ) (b_{ij}) (bij) :

    ( b i j ) = [ 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 ] (b_{ij}) =\begin{bmatrix} & 0 & 13 & 7 & 0 & \\\\ & 6 & 0 & 6 & 9 & \\\\ & 0 & 5 & 3 & 2 & \\\\ & 0 & 1 & 0 & 0 & \\ \end{bmatrix} (bij)=06001305176300920





    三、第二步 : 试指派 ( 找独立 0 元素 )



    基于上一步的行列都有 0 0 0 元素的系数矩阵 ,

    ( b i j ) = [ 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 ] (b_{ij}) =\begin{bmatrix} & 0 & 13 & 7 & 0 & \\\\ & 6 & 0 & 6 & 9 & \\\\ & 0 & 5 & 3 & 2 & \\\\ & 0 & 1 & 0 & 0 & \\ \end{bmatrix} (bij)=06001305176300920

    进行试指派 ;


    找出每行的独立 0 0 0 元素 ,

    优先从唯一选择开始 ,

    2 2 2 行只有 1 1 1 0 0 0 元素 , 该元素是独立 0 0 0 元素 ;

    在这里插入图片描述

    3 3 3 行只有 1 1 1 0 0 0 元素 , 该元素是独立 0 0 0 元素 ( 红色矩形框 ) , 位于第 1 1 1 列 ; 同时第 1 1 1 列中的其它 0 0 0 元素标记为 废弃 0 0 0 元素 ( 绿色矩形框 );

    在这里插入图片描述

    1 1 1 行和第 4 4 4 行都有多个 0 0 0 元素 ;

    然后从列里面找独立 0 0 0 元素 , 第 1 1 1 列 和 第 2 2 2 列都已经找到了 0 0 0 元素 , 这里看 第 3 3 3 列 和 第 4 4 4 列 ;

    3 3 3 列有 独立 0 0 0 元素 ( 红色矩形框 ) ; 位于第 4 4 4 行 , 将第 4 4 4 行的其它 0 0 0 元素标记为 废弃 0 0 0 元素 ( 绿色矩形框 ) ;

    在这里插入图片描述

    4 4 4 列有 独立 0 0 0 元素 ( 红色矩形框 ) ; 位于第 1 1 1 行 , 将第 1 1 1 行的其它 0 0 0 元素标记为 废弃 0 0 0 元素 ( 绿色矩形框 ) , 已经标记过了 , 不用再进行标记 ;

    在这里插入图片描述

    这里第一次指派就找到了最优解 ;

    展开全文
  • 二、第二步 : 试指派操作示例 在 【运筹学】匈牙利法 ( 匈牙利法步骤 | 第一步 : 使行列出现 0 元素示例 ) 博客示例基础上 , 已经得到了行列都有 000 元素的系数矩阵 : (bij)=[4540010420433720](b_{ij}) = \begin{...





    一、指派问题求解步骤



    指派问题求解步骤 :

    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 0 元素的系数矩阵 :

    ( 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)=4023510740410430

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

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

    在这里插入图片描述

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

    在这里插入图片描述

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

    最终试指派结果 :
    在这里插入图片描述

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

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

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

    ( b i j ) = [ 4 5 4 0 0 1 0 4 2 0 4 3 2 6 0 − 1 ] (b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 2 & 6 & 0 & -1 & \\ \end{bmatrix} (bij)=4022510640400431


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

    ( b i j ) = [ 4 5 4 1 0 1 0 5 2 0 4 4 2 6 0 0 ] (b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 1 & \\\\ & 0 & 1 & 0 & 5 & \\\\ & 2 & 0 & 4 & 4 & \\\\ & 2 & 6 & 0 & 0 & \\ \end{bmatrix} (bij)=4022510640401540


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

    ( b i j ) = [ 3 4 3 0 0 1 0 5 2 0 4 4 2 6 0 0 ] (b_{ij}) = \begin{bmatrix} & 3 & 4 & 3 & 0 & \\\\ & 0 & 1 & 0 & 5 & \\\\ & 2 & 0 & 4 & 4 & \\\\ & 2 & 6 & 0 & 0 & \\ \end{bmatrix} (bij)=3022410630400540


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

    在这里插入图片描述



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

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

    展开全文
  • 最速下降,搜索算法,匈牙利算法。等等···
  • 二、打 √ 分析 【运筹学】匈牙利法 ( 匈牙利法步骤 | 第二步 : 试指派操作示例 ) 博客中试指派调整矩阵的原理 ; 下面的矩阵是完成第一步操作后 , 得到的行列都有 000 的元素的系数矩阵 (bij)(b_{ij})(bij​) : ...





    一、指派问题求解步骤



    指派问题求解步骤 :

    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 的元素的系数矩阵 ( b i j ) (b_{ij}) (bij) :

    ( 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)=4023510740410430


    试指派后的结果如下 :

    在这里插入图片描述


    定位一个没有独立 0 0 0 元素的行 : 先对没有 0 0 0 元素的行打钩 √ : 第 4 4 4 行没有独立 0 0 0 元素 , 第 4 4 4 行打 √ ;

    在这里插入图片描述


    讨论第 4 4 4 行 : 4 4 4 行没有独立的 0 0 0 元素 , 但是有废弃的 0 0 0 元素 , 因为在第一步已经保证了每行每列都有 0 0 0 元素 ;

    在第 4 4 4 0 0 0 元素所在列 , 即第 4 4 4 列 , 打 √ ;

    在这里插入图片描述


    讨论第 4 4 4 列 : 上述打钩的列中 , 查看是否有 独立的 0 0 0 元素 , 如果有对应的行就打 √ ;

    1 1 1 行有独立的 0 0 0 元素 , 在第 1 1 1 行位置打 √ ;

    在这里插入图片描述


    讨论第 1 1 1 行 : 查看第 1 1 1 行是否有废弃的 0 0 0 元素 , 如果有就继续打 √ , 如果没有就停止 ;

    1 1 1 行没有废弃的 0 0 0 元素 , 直接停止 ;


    讨论 的时候讨论的是 废弃的 0 0 0 元素 ,

    讨论 的时候讨论的是 独立的 0 0 0 元素 ;





    三、直线覆盖



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

    没有 打 √ 的行划线 , 打 √ 的列划线 , 三条线就将所有的 0 0 0 元素覆盖了 ,

    在这里插入图片描述

    在没有被覆盖的元素中 , 找最小的元素 1 1 1 , 将该元素所在的没有覆盖的行 − 1 -1 1 , 覆盖的列 + 1 +1 +1 ;

    最终得到如下矩阵 :

    ( b i j ) = [ 3 4 3 0 0 1 0 5 2 0 4 4 2 6 0 0 ] (b_{ij}) = \begin{bmatrix} & 3 & 4 & 3 & 0 & \\\\ & 0 & 1 & 0 & 5 & \\\\ & 2 & 0 & 4 & 4 & \\\\ & 2 & 6 & 0 & 0 & \\ \end{bmatrix} (bij)=3022410630400540

    展开全文
  • 解决图论中Warshall-Floyd 算法,Kruskal 避圈法,匈牙利算法,求最佳匹配的算法,求最大流的Ford--Fulkerson 标号算法,求解最小费用流问题的matlab程序
  • 一、使用匈牙利法求解下面的指派问题、 二、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )、 三、第二步 : 试指派 ( 找独立 0 元素 )、 四、第二步 : 试指派 ( 打 √ )、 五、第二步 : 试指派 ( 直线覆盖 )、 五...
  • 二、匈牙利法引入、 三、指派问题求解步骤、 四、匈牙利法示例 1、 1、第一步 : 使行列出现 00 元素示例、 2、第二步 : 试指派操作示例、 3、打 √、 4、直线覆盖、 五、匈牙利法示例 2、 六、匈牙利法示例 3、 1、...
  • 二、第一步使行列出现 000 元素示例 上一篇博客 【运筹学】匈牙利法 ( 克尼格定理 | 匈牙利法引入 ) 中的指派问题 : AAA BBB CCC DDD 甲 666 777 111111 222 乙 444 555 999 888 丙 333 111 101010 444 丁 555 999 ...
  • 本文介绍求解指派问题的匈牙利法,并证明该算法的最优性。
  • Hungarian匈牙利法

    2017-09-04 09:52:25
    匈牙利法,在网上找来的,在Qt下编译的,标准C++写的,代码有注释,拿来就用,很是方便,欢迎下载交流............................................
  • 运筹学 匈牙利法

    千次阅读 2020-09-01 00:13:56
    FebruaryMarchAprilMayJuneJulyAugustSeptemberOctoberNovemberDecember已完成 进行中 计划中 批量导出 档案管理系统
  • 该脚本使用Perl语言编写,专门使用匈牙利法处理指派问题
  • 整数规划(分支定界、匈牙利法

    千次阅读 2021-01-12 15:53:08
    (iv)匈牙利法—解决指派问题(“0-1”规划特殊情形)。 (v)蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 本文只介绍分支定界法和匈牙利法。 分支定界法 首先不考虑变量的整数...
  • 这一点可以通过,闭回路进行最优解的判别的时候得到,因为闭回路采用矩形的形式构建回路,同时对一行或者一列进行操作,并不会影响最优解的判别。这条很强的约束,导致
  • 匈牙利法 第一步: (1)写出工作效率矩阵 先找出行最小值,并用每个数减掉,再找出列最小值,并进一步减去 (2)需要找出N个独立的“0元素”,满足 从行上看,只有1个0,从列上看,也只有1个0,此时令这些独立...
  • C++之匈牙利命名

    2020-12-22 22:31:15
    匈牙利命名是由Microsoft的开发人员、Excel的主要设计者查尔斯·西蒙尼在他的博士论文中提出来的,由于西蒙尼的国籍是匈牙利,所以这种命名匈牙利命名。  匈牙利命名为C标识符的命名定义了一种非常标准...
  • 【运筹学】指派问题匈牙利法

    千次阅读 2020-06-02 21:26:37
    运筹学指派问题——匈牙利法 期末考运筹学,线上教学真好~自学中,还是小白~ 1.系数矩阵每行减去每行的最小值,最后每列减去每列的最小组,直至每行每列都含有0元素 2.找出n个独立的零元素(每一行每一类只能有...
  • 二分图匹配 匈牙利算法和KM算法简介 二分图的概念 二分图又称作二部图,是图论中的一种特殊 模型 冷设G=(V{R})是一个无向图如顶点集V可分 割为两个互不相交的子集,并且图中每条边 依附的两个顶点都分属两个不同的子集...
  • 混合整数规划与匈牙利法的自动化立体仓库货位优化研究.pdf
  • 使用matlab运用匈牙利法解决0-1规划问题,代码可以进行参考
  • 分配问题与匈牙利法

    千次阅读 2017-12-23 21:45:26
    分配问题: 已知成本矩阵,求最优分配方案。 成本矩阵:行列分别为worker和task,元素值为对应worker完成对应task的开销。...1、蛮力:穷举。对于n*n矩阵,要计算n!个成本值,时间复杂度O(n!) 2、
  • 一、 匈牙利命名开头字母用变量类型的缩写,其余部分用变量的英文或英文的缩写,要求单词第一个字母大写。比如: long lSum = 0; //"l"是类型的缩写;二、驼峰命名camel-case骆峰式命名(Camel-Case)是电脑程式...
  • 程序实现了匈牙利算法应用于指派问题,输入指派成本矩阵C,给出最小成本及使得成本最小的最优指派
  • 二分图最大匹配 匈牙利法 原理 应用 ACM常用解题方法
  • 这个项目是我实习的一部分,它包含一个经过训练可检测20个物体的SSD检测器,但仅用于人员,以生成跟踪,对每个人执行Kalman滤波,针对每个人的ID生成,处理匈牙利方法。 用法 : python2 main.py --prototxt ...
  • 这是著名的匈牙利算法(也称为 Munkres 算法)的极快实现。 它可以在配备 Matlab 2008a 的 Core Duo (T2500 @ 2.00GHz) XP 笔记本电脑中在约 20 秒内解决 1000 x 1000 问题,比 FEX ID 6543 中的 mex 代码...
  • 在本文中,我们将匈牙利算法用于分配问题,以解决旅行商问题。 包括算法应用的树形示例。
  • 二分法和匈牙利法解决全封锁
  • 基于匈牙利算法的指派问题优化分析.zip

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,548
精华内容 8,219
关键字:

匈牙利法

友情链接: LTC2944.rar