设为首页 - 加入收藏
广告 1000x90
您的当前位置:2019年全年最准资料 > 布达佩斯 > 正文

匈牙利解法

来源:未知 编辑:admin 时间:2019-07-14

  是求解指派问题的一种新颖而又简便的解法,它是美国数学家库恩Kuhn)于1955年提出的.库恩引用了匈牙利数学家康尼格(Konig)一个关于矩阵中0元素的定理:系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最小直线数,这种解法称为匈牙利法.

  指派问题的最优解有这样一个性质,若从系数矩阵的一行(列)各元素中分别减去该行(列)的最小元素,得到新矩阵,那么以新矩阵为系数矩阵求得的最优解和用原矩阵求得的最优解相同.利用这个性质,可使原系数矩阵变换为含有很多0元素的新矩阵,而最优解保持不变.

  具体操作为第一步:使指派问题的系数矩阵经变换,在各行各列中都出现0元素.(1)从系数矩阵的每行元素减去该行的最小元素;(2)再从所得系数矩阵的每列元素中减去该列的最小元素.第二步:进行试指派.若此时得到的mPn,应回到第一步,重新对系数矩阵进行变换。但要把第一步的过程改为(1)从系数矩阵的每列元素减去该列的最小元素;(2)再从所得系数矩阵的每行元素中减去该行的最小元素.这样做就使得新矩阵的0元素比较多些.再进入第二步进行试指派就可以得到最优解.利用前面的性质可以证明这个最优解就是我们所要求的原问题的最优解,从而使得求解变得更为简捷。

  中找出n个独立的0元素,则令解矩阵(Xij)中对应这n个独立0元素的取值为1,其他元素取值为0。将其代入目标函数中得到

  ,B叫C的缩减矩阵。符合匈牙利法的条件。由定理1可知:所得的最小解就是原问题的最大解。

  其特点是:m个人分派做n项工作,系数矩阵(Cij)为m×n矩阵,m≠n。

  步骤一:将这系数矩阵进行变换,使各行各列都出现0元素.从系数矩阵的每行元素减去该行的最小元素即得每行每列都有有0元素的系数矩阵.

  步骤二:进行试指派,找出独立的0元素.独立0元素用表示,其它0用表示得到

  这里的个数m=4,而n=5;问题没有得到求解,运用步骤三继续求解.

  步骤三:作最少的直线元素,以确定该系数矩阵中能找到最多的独立元素数.为此按以下步骤进行.

  令直线数为l.若ln,说明必须再变换当前的系数矩阵,才能找到n个独立的0元素,为此转换步骤四;若l=n,而mn,应回到步骤二,另行试探.

  先在第五行旁打√,接着可判断应在第一列下打√,接着在第3行旁打√,经检查不能再打√了.对没有打√行画一直线元素,对打√的列画一直线元素,得:

  为此在没有被直线覆盖的部分中找出最小元素.然后在打√行各元素中都减去这个最小元素,而在打√列的各元素上都加上这个最小元素,以保证原来0元素不变.这样得到新系数矩阵(它的最优解和原问题相同).若得到n个独立的0元素,则已得最优解,否则回到步骤三重复进行.

  在矩阵(2)中,在没有被覆盖部分(第3、5行)中找到最小元素为2,然后在第3、5行各元素分别减去2。给第l列各元素加2,得到新矩阵(3)

  匈牙利解法的示例第一个矩阵中 b_55 应该是 9 而非 0,第二个矩阵改过来了,所以结果没有影响。

本文链接:http://dicaspace.com/budapeisi/2742.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top