基于MATLAB GUI最优指派问题综合计算平台设计(第十届科技作品)

宝鸡文理学院 物理与信息技术系 陕西 宝鸡

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

关键词 最优指派问题 匈牙利算法 MATLAB GUI

1.引言

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

2.问题分析

2.1标准形式最优指派问题及匈牙利算法

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

nnijminzci1j1xij

nj1,2,n,xij1i1n s.t.xij1i1,2,n,j1xij0或1i,j1,2,n,cij表示第i个人完成第j项任务的费用，cij

所组成的矩阵为C，C为最优指派问

题的系数矩阵。上式给出了求解标准形式最优指派问题的数学模型，那么如何求解此模型呢！最容易想到的是穷举法，例如，当遇到问题的维数为5时，需要列出5！个方案进行比较，从挑选出问题的最优解。但是问题的维数为12时，需

1

要列出12！个方案进行比较，随着问题规模的增大，这种方法显然是没有办法实现的，故寻求另一种方法。用匈牙利算法来求解此模型，匈牙利算法的基本思想是寻找系数矩阵中的独立0元素组，步骤如下：

step1：变换系数矩阵。使系数矩阵中每行及每列至少有一个零元素，同时

不出现负元素。转step2；

step2：在变换后的系数矩阵中确定独立的零元素。作覆盖所有零元素的最

少直线，若直线条数等于n，则已得出最优解。若直线的条数小于n，则转step3；

step3：继续变换系数矩阵。使未被直线覆盖的元素中出现零元素，同时消

除负元素。转step2。

利用此算法既可求出标准形式最优指派问题的最优解。 2.2对比五类最优指派问题

在现实生活中，标准形式的最优指派问题是很少见的，而非标准形式却是常见的。在求解非标准形式问题的过程中，要将其系数矩阵转化成标准形式，然后用匈牙利算法求解。下面给出求解最优指派问题的流程图，如图1：

开始输入系数矩阵CN16Y 判断：问题是否为标准形式14根据问题的类型，将其转化为相应的标准形式令B=（m-cij)n*n(m为C中的最大元素) 添加一些虚拟的“人”或“事”某人的费用系数取作足够大的数M 12化作相同的“几个人”接受指派108匈牙利算法6输出最优指派问题的最优解4结束2 图1

对图1进行分析：在求解最优指派问题时，如果问题是标准形式的，直接用匈牙

2

利算求出最优解，如果问题是非标准形式的，要根据不同的问题，将其系数矩阵转化为不同的标准形式，然后用匈牙利算法求解；可见在求解最优指派问题的过程中，都用到了匈牙利算法，而且匈牙利算法处理的对象都是矩阵。为了给用户提供解决最优指派问题的便捷工具，通过人机界面交互操作就可以求出问题的最优解，并将结果可视化。无疑MATLAB 强大的矩阵运算功能，及友好的人机交互界面GUI是最佳的。

3.总体方案设计

通过问题分析可知，利用MATLAB 强大的矩阵运算功能及友好的人机交互界面GUI，来设计解决最优指派问题的工具，此工具要把求解标准和非标准形式指派问题的功能集合于一身。在借助此工具求解问题时，要尽量减少人工的干预，并将所得到结果可视化，因此该工具是一种解决最优指派问题的综合计算平台。设计应遵循简单性、一致性、习常性原则。总的设计方案如下：

step1：在M文件中用MATLAB语言实现匈牙利算法，并能正确运行； step2：分析界面要实现的主要功能，明确设计任务；

step3：在稿纸上给出界面草图，从使用者的角度来审视草图； step4：按照构思的草图，上机制作（静态）界面，并进行检查； step5：编写界面动态功能的程序，对功能进行逐项检查。

在求解标准和非标准形式最优指派问题的过程中，都要调用匈牙利算法子函数，匈牙利算的MATLAB语言实现又占有很大的篇幅，因此把匈牙利算的MATLAB语言实现放在了总体设计方案的第一步，此算法的实现对后面的界面设计打下了基础，也为界面的实现提供了前提条件。

4.平台的具体实现

在总体设计方案中给出了最优指派问题综合计算平台实现的5个步骤，即给出了平台实现的框架，但并不能用这些步骤来求解最优指派问题。要实现此平台，就要逐步对这5个步骤加以解决。 4.1匈牙利算法的MATLAB语言实现

匈牙利算法的MATLAB语言实现，在最优指派问题综合计算平台设计中占有的重要地位，可以在总体设计方案中看到。把此算法分成三个模块来实现，前两模块实现的目标：找出独立零元素组。最后一个模块实现的目标：得出问题的

3

最优解。按照“自顶向下，逐步求精”的思想分别加以实现。在这三个模块的实现中，第二个模块的设计和实现是最为关键和困难的。

第一个模块的实现：用all函数判断系数矩阵每行每列中是否含零元素,用c(:,jj)= c(:,jj)-min(c(:,jj))或c(ii,:)= c(ii,:)-min(c(ii,:))语句变换不含零元素的行或列,使不含零元素的行或列中含有零元素。这样就实现了系数矩阵的每行每列中至少含有一个零元素。

第二个模块的实现：在每行每列都含有零元素的矩阵上，用最少的“直线”数覆盖所有的零元素，在用“直线”覆盖零元素时，要标记每行每列，为继续变换矩阵做前提。判断直线的数目是否等于系数矩阵的维数，如果不是，继续变换矩阵，使未被直线覆盖的元素中出现零元素，同时消除负元素，重新判断。若直线的数目等于系数矩阵的维数，则最优解存在，跳出循环，在最后所得到矩阵中寻找独立的零元素。部分程序如下

for ii=1:rows %标记每行每列%

labelrows_c(ii,cols+1)=ii;labelcols_c(rows+1,ii)=ii;

end

[m site2]=max(num0(:));

if site2<=cols3 %用最少“直线”数覆盖所有零元素% c(:,site2)=[];

else

c(site2-cols3,:)=[];

end

theminnumber=min(c1(1:rows2*cols2-rows2)); %继续变换矩阵% for ii=1:rows2

c(c1(ii,cols2),:)=c(c1(ii,cols2),:)- theminnumber;

end

[minimum site3]=min(thesiteofzero(:,3)); %寻找独立零元素% copy_c(thesiteofzero(site3,1),:)=inf; copy_c(:,thesiteofzero(site3,2))=inf;

therealsiteofthejob(n2)=(thesiteofzero(site3,2)-1)*rows+thesiteofzero(site3,1);

第三个模块的实现：前两个模块的实现，已经找出了独立零元素组，并把它们放在了therealsiteofthejob数组中，接下来就要实现问题最优解的输出。

for ii=1:rows %指派方案的实现%

zhipaifangan_c(therealsiteofthejob02(ii))=1; end

4

feiyongdexishujuzhen=c.*original_c; %计算所需要的费用% thechargeofthejob=sum(feiyongdexishujuzhen (:));

4.2界面要实现的主要功能

通过问题分析，该界面是集合标准和非标准形式最优指派问题的综合计算平台，其要实现的主要功能有：能读入要解决问题的数据，将该数据显示到界面中；将数据的路径和名字显示到界面中；根据问题的类型和要求做相应的操作，能得到满意的结果，并将问题的结果显示到界面中；能够清除界面中已显示过的数据； 能够切换界面中提示文字的语言；对于非法输入和超本计算平台求解的数据能够做出提示；能安全退出。 4.3界面草图

制作草图是界面设计的前期工作，根据界面要实现的主要功能，从使用者的角度画出界面的草图，并审视草图。 4.4上机制作（静态）界面

根据绘制的草图，在用户图形界面区内合理的摆放所需要的组件，并在按钮的标签上对其所要实现的功能进行描述。根据界面要实现的主要功能，该组件包括：六个按钮；两个单选按钮；一个框架；一个开关按钮；五个文本域；两个编辑框；两个列表框。该平台的（静态）界面如图2

1 2 7 8 3 9 4 5 6 11 10

图2

图2给出了最优指派问题综合计算平台的（静态）界面，在此将按照从上往下，从左往右的顺序介绍各个组件的功能：

5

按钮1：用于求解人数等于事数或人数不等于事数的最小化问题； 按钮2：用于求解人数等于事数或人数不等于事数的最大化问题； 按钮3：用于求解一个人做多件事的问题，其中有两个单选按钮，根据问题的要求选择单选按钮，默认的情况下，求解的是一个人做多件事的最大化问题；

按钮4：用于读取所要解决问题的系数矩阵；

开关按钮5：用于切换界面中提示文字的语言，在中英文之间切换； 按钮6：用于清除所显示过的数据； 按钮7：用于安全退出此界面；

编辑框8：用于显示所要解决问题的费用； 列表框9：用于显示问题的系数矩阵； 列表框10：用于显示问题的指派方案；

编辑框11：用于显示存放系数矩阵文件的路径和名字。 4.5编写界面动态功能程序

静态界面制作好之后，并不能使之运行，为了使鼠标单击某个按钮，并能做出预期的反应，就要对各个按钮编写驱动程序，这个驱动程序被称为该按钮的回调函数（Callback），回调函数的编写是界面设计中最关键的一步，直接关系到界面能否运行。由于篇幅有限，在此只给出该计算平台部分按钮回调函数的实现。

“读取数据”按钮回调函数实现：

%读取所要解决问题系数矩阵的数据%

[FileName PathName]=uigetfile(('*.xls'),'chose a file'); str=[PathName FileName]; set(handles.edit2,'string',str);

handles.orignal_c=xlsread(str)； str04=[num2str(handles.orignal_c)]; set(handles.listbox2,'string',str04); guidata(hObject,handles);

其中uigetfile((„*.xls‟),„chose a file‟)语句，用于打开一个将数据存放在execel中的文件，即在求解问题之前，将所要解决问题的系数矩阵存放在一个execel表格中。将该execel文件的储存路径和名字分别放在PathName和FileName中。set(handles.edit2,'string',str)语句将execel的储存路径和名字输入到编辑框11。xlsread函数命令用于读取execel文件中的数据。

6

实现数据的输出：

%输出最优指派问题的结果%

str02=[num2str(theminimumchargeofthejob)]; str03=[num2str(copy_c)]; set(handles.edit1,'string',str02); set(handles.listbox1,'string',str03);

num2str函数用于把数字转化成字符。set(handles.listbox1,'string',str03)语句将指派方案显示到列表框10中。

在用此平台求解问题时，需要知道此平台的适用范围，这样才能为用户提供更好的服务。首先此界面是用于求解最优指派问题的综合计算平台，可用此平台求解标准形式的指派问题、最大化的指派问题、人数不等于事数的指派问题、一个人做多件事的指派问题和某项任务一定不能由某人来完成的指派问题，需要在次说明，在用此平台求解某项任务一定不能由某人来完成的指派问题时，由于问题的类型复杂，随机性太强,所以在求解之前要对问题的系数矩阵按照问题的要求做一定的处理，然后再借助此平台求解。其次在读取数据时，应该把所要求解的数据存放在execel表格中。最后该平台在用于求解最优指派问题时，并不是实用于所有的问题，对于有些苛刻的数据，它不能给出结果。

5.平台的具体应用

在总体设计方案中给出了最优指派问题综合计算平台实现的5个步骤，在具

体实现中逐步对这5个步骤加以解决，最终实现了最优指派问题综合计算平台的设计。再借助此平台求解最优指派问题时，到底得到的结果是不是我们所满意的，能否对一些非法输入做出处理，能否在运行的过程中正确、稳定、健康、友好的运行。这就需要接受实践的检验，下面把此平台用于求解最优指派问题，在求解此类问题时，由于应用程序处理的对象是问题的系数矩阵，所以在求解的过程中，省略了对问题建立模型的这一步，而是直接用平台处理系数矩阵，并给出了问题的最优解。

例1，设有12名工作人员要完成12项工作，cij表示第i名工作人员去完成第j项工作所需要的时间，问如何指派，使完成任务最快。假设每人完成各项工作的时间矩阵为

7

 15 8 16 24 5 23 4 20 22 14 16 7 19 5 13 10 1 11 10 18 15 19 24 20 1 9 22 2 8 8 21 4 17 6 12 17 2 24 19 10 14 5 15 13 23 21 10 24 21 17 8 2 3 4 1 13 11 17 20 1 4 16 18 7 21 20 10 22 4 20 2 1C 7 19 10 16 8 16 7 11 15 22 14 18 7 11 14 24 12 8 3 1 12 9 5 20 20 5 2 9 10 8 7 24 9 11 9 6 5 7 7 20 6 8 12 5 19 2 7 17 14 19 15 3 24 18 10 13 20 23 15 7 23 15 22 21 24 7 16 23 7 16 23 2

对问题的分析，这是一个系数矩阵较大的最小化标准指派问题，在MATLAB命令窗口中输入xylsf命令，并执行此命令，就可以打开最优指派问题综合计算平台的界面。打开后我们针对此问题进行求解，在求解之前将该问题的系数矩阵存放在一个 execel表格中。求解步骤：第一步：读取数据，当按下“读取数据”按钮后会弹出如图3所示的界面；

图3

第二步：通过chose a file窗口找到存放数据得execel表格，然后打开该表格，就可以将数据显示到界面中，如图4

8

图4

从图4中可以看到该问题的系数矩阵被显示在了“系数矩阵”栏里面；第三步根据问题的要求做相应的操作，由于这是一个最小化的指派问题，故按最小化按钮，所得结果如图5。

图5

对所得的结果进行分析：“费用最大（或最小）”显示框中的40表示完成此任务所用的最少时间，“指派方案”显示框中的矩阵表示指派方案，“系数矩阵”显示框中的矩阵为该问题的系数矩阵。

例2分配甲、乙、丙、丁四个人去完成任务.由于任务数多于人数,故规定其中一个人可兼完成两项任务,其余三人每人完成一项。确定总花费时间为最少的

9

指派方案。每人完成各项任务的时间矩阵为

2539C342429382742312628364220402337333245

此问题属于一个人可以做几件事的最小化非标准指派问题，在借助平台求解时，不像求解前面的问题，这时要对该问题的系数矩阵作相应的转化，然后才能用程序求解。对此系数矩阵转化有两种方法：1）由题意知，在四个人中只能有一个人担任两项任务，不知道那个人会承担两项，故转化之后的系数矩阵共有四种：第一种，只将甲化作相同的两个“人”来接受任务。第二种，只将乙化作相同的两个“人”来接受任务。第三种，只将丙化作相同的两个“人”来接受任务。第四种，只将丁化作相同的两个“人”来接受任务。2）添加一个虚拟的“人”戊，他完成各项任务时间取甲、乙、丙、丁中最小者。

将问题的系数矩阵转化之后，就用此平台来来求解。按照1）中的转化后，会得到四个系数矩阵，分别将这四个矩阵借助平台求解，会得到四种结果，比较着四种结果，取其中费用最小的，那么最小费用和其所对应指派方案就是该问题的最优解，此解将会在附录2中给出。在此将着重用2）中的转化方法来求解此问题。所得到得结果如图6

图6

分析所得到的结果：因为该问题是一个人可以做几件事的最小化非标准指派问题，在求解的过程中要添加一些虚拟的“人”，但是在execel表格中输入该系数

10

矩阵时，不需要手动去添加，因为程序在运行的过程中会自动识别标准与非标准形式并把非标准转化成标准形式，以提高解决问题的效率。

由结果得得问题的最优指派方案为甲-B，乙-B和C，丙-E，丁-A，总计需要131h。 例3某地区从电网中分配得到的电力共有6万千瓦，可用于工业，而该地区有机械、化工、轻纺、建材四大部类，各部类获得电力以后，可以为该地区提供的利润如表3所示，问应该如何分配电力该地区的电力可使获得的利润得到最大？其费用的系数矩阵为

368C101213579101112468910115810111213

此问题既属于最大化指派问题，也属于人数和事数不等的指派问题。我们可以将1，2，…，6万千瓦的电力看作是六种不同的资源，则问题就可以看成是将六种资源用于四种生活活动的资源分派问题。对于此问题也借助此平台来求解，但是在输入系数矩阵时，不需要手动将系数矩阵化为标准指派问题的系数矩阵。所得到的结果如图7

图7

由结果可得问题的解为：分配3、4、5、6万千万的电力分别给这化工、轻纺、机械、建材生活区供电，可获得最大利润为43（万元）。

11

6.总结

本文介绍了最优指派问题和匈牙利算法的理论，但核心在于，基于匈牙利算法，如何利用MATLAB函数及图形用户界面GUI，设计实现最优指派问题的综合计算平台。文章用了较大的篇幅介绍了平台的设计思想及实现的方法和步骤，最后把平台用于求解最优指派问题，以接受实践的检验。结果表明：最优指派问题综合计算平台能够较好的用于求解最优指派问题；方便用户操作；减少了人工的干预；提高了解决问题的效率；具有可推广性；。但其中的部分功能还不够完善或有待改进。有不当之处，望专家不吝赐教。

12

参考文献

【1】 姜起源，谢金星，叶俊，数学模型（第三版），北京：高等教育出版社，

2008，107-108

【2】 胡运权，郭耀煌，运筹学教程，北京：清华大学出版社，1998，129-134 【3】 邓成梁，运筹学的原理和方法（第二版），武汉：华中理工大学出版社，

1998，242-247

【4】 胡运权，运筹学习题集（第三版），北京：清华大学出版社，2002，62-63 【5】 郑阿奇，曹戈，MATLAB实用教程（第二版），北京：电子工业出版社，2007 【6】 张旭辉，朱宏辉，郑启忠，最优指派问题匈牙利算法的探讨与C++实现，

物流技术，第5期：2004

【7】罗华飞，MATLAB GUI设计学习手记，北京：北京航天航空大学出版社，

2009，8

13