文档介绍：基于MATLAB GUI最优指派问题综合计算平台设计

摘要:针对手工计算五类最优指派问题难的问题,设计和实现求解此类问题的便捷工具。本文介绍了标准形式指派问题数学模型的建立过程,并对求解此模型的匈牙利算法做了说明。通过分析五类最优指派问题的求解过程,并基于匈牙利算的理论,提出了此工具的总体设计方案,把此方案利用MATLAB强大的矩阵运算功能,及友好的人机交互界面GUI逐步加以实现,推出了最优指派问题的综合计算平台。把此平台用于求解最优指派问题,不仅得到了满意的结果,而且提高了解决此类问题的效率。
关键词最优指派问题匈牙利算法 MATLAB GUI

现实生活中,匈牙利算法在炮兵火力单位分配、多车型车辆调度、二次分配等最优指派问题中有许多重要的应用。最优指派问题包括标准和费标准形式,其中非标准形式又分为四类:最大化指派问题、人数和任务数不等的指派问题、一个人可以完成几项任务的指派问题、某项任务一定不能由某人来完成的指派问题。在用匈牙利算法求解最优指派问题时,根据不同的问题,要对其系数矩阵行进一系列不同的复杂变换。若用手工计算很繁琐、费时、效率低。因此,为了给用户提供求解此类问题的便捷工具,确保及时、正确地得到问题的最佳指派方案,具有着重要的意义。本文对求解五类最优指派问题的过程进行了分析比较,并基于匈牙利算法的理论,借助MATLAB软件,设计实现了最优指派问题的综合计算平台,并给出了平台使用的范围。在借助此平台求解最优指派问题问题时,即使用户不懂该工具的实现原理,也可以方便的使用应用程序,不需要了解该平台怎样执行,只需要了解该平台的使用方法,通过人机界面交互操作就可以得出问题的最优解。

在解决最优指派问题时,如果遇到的问题是标准形式,即人数和事数相等,每人只能完成一项,不同的事由不同的人做的指派问题,对于求解此问题,可建立如下数学模型

表示第个人完成第项任务的费用,所组成的矩阵为,为最优指派问题的系数矩阵。上式给出了求解标准形式最优指派问题的数学模型,那么如何求解此模型呢!最容易想到的是穷举法,例如,当遇到问题的维数为5时,需要列出5!个方案进行比较,从挑选出问题的最优解。但是问题的维数为12
时,需要列出12!个方案进行比较,随着问题规模的增大,这种方法显然是没有办法实现的,故寻求另一种方法。用匈牙利算法来求解此模型,匈牙利算法的基本思想是寻找系数矩阵中的独立0元素组,步骤如下:
1:变换系数矩阵。使系数矩阵中每行及每列至少有一个零元素,同时不出现负元素。转2;
2:在变换后的系数矩阵中确定独立的零元素。作覆盖所有零元素的最少直线,若直线条数等于,则已得出最优解。若直线的条数小于,则转3;
3:继续变换系数矩阵。使未被直线覆盖的元素中出现零元素,同时消除负元素。转2。
利用此算法既可求出标准形式最优指派问题的最优解。

在现实生活中,标准形式的最优指派问题是很少见的,而非标准形式却是常见的。在求解非标准形式问题的过程中,要将其系数矩阵转化成标准形式,然后用匈牙利算法求解。下面给出求解最优指派问题的流程图,如图1:
图1
对图1进行分析:在求解最优指派问题时,如果问题是标准形式的,直接用匈牙
利算求出最优解,如果问题是非标准形式的,要根据不同的问题,将其系数矩阵转化为不同的标准形式,然后用匈牙利算法求解;可见在求解最优指派问题的过程中,都用到了匈牙利算法,而且匈牙利算法处理的对象都是矩阵。为了给用户提供解决最优指派问题的便捷工具,通过人机界面交互操作就可以求出问题的最优解,并将结果可视化。无疑MATLAB 强大的矩阵运算功能,及友好的人机交互界面GUI是最佳的。

通过问题分析可知,利用MATLAB 强大的矩阵运算功能及友好的人机交互界面GUI,来设计解决最优指派问题的工具,此工具要把求解标准和非标准形式指派问题的功能集合于一身。在借助此工具求解问题时,要尽量减少人工的干预,并将所得到结果可视化,因此该工具是一种解决最优指派问题的综合计算平台。设计应遵循简单性、一致性、习常性原则。总的设计方案如下:
1:在M文件中用MATLAB语言实现匈牙利算法,并能正确运行;
2:分析界面要实现的主要功能,明确设计任务;
3:在稿纸上给出界面草图,从使用者的角度来审视草图;
4:按照构思的草图,上机制作(静态)界面,并进行检查;
5:编写界面动态功能的程序,对功能进行逐项检查。
在求解标准和非标准形式最优指派问题的过程中,都要调用匈牙利算法子函数,匈牙利算的MATLAB语言实现又占有很大的篇幅,因此把匈牙利算的MATLAB语言实现放在了总体设计方案的第一步,此算法的实现对后面