基于MATLAB GUI最优指派问题综合计算平台设计第十届科技作品Word格式.docx
- 文档编号:6316261
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:15
- 大小:603.70KB
基于MATLAB GUI最优指派问题综合计算平台设计第十届科技作品Word格式.docx
《基于MATLAB GUI最优指派问题综合计算平台设计第十届科技作品Word格式.docx》由会员分享,可在线阅读,更多相关《基于MATLAB GUI最优指派问题综合计算平台设计第十届科技作品Word格式.docx(15页珍藏版)》请在冰点文库上搜索。
最容易想到的是穷举法,例如,当遇到问题的维数为5时,需要列出5!
个方案进行比较,从挑选出问题的最优解。
但是问题的维数为12时,需要列出12!
个方案进行比较,随着问题规模的增大,这种方法显然是没有办法实现的,故寻求另一种方法。
用匈牙利算法来求解此模型,匈牙利算法的基本思想是寻找系数矩阵中的独立0元素组,步骤如下:
1:
变换系数矩阵。
使系数矩阵中每行及每列至少有一个零元素,同时不出现负元素。
转
2;
2:
在变换后的系数矩阵中确定独立的零元素。
作覆盖所有零元素的最少直线,若直线条数等于
,则已得出最优解。
若直线的条数小于
,则转
3;
3:
继续变换系数矩阵。
使未被直线覆盖的元素中出现零元素,同时消除负元素。
2。
利用此算法既可求出标准形式最优指派问题的最优解。
2.2对比五类最优指派问题
在现实生活中,标准形式的最优指派问题是很少见的,而非标准形式却是常见的。
在求解非标准形式问题的过程中,要将其系数矩阵转化成标准形式,然后用匈牙利算法求解。
下面给出求解最优指派问题的流程图,如图1:
图1
对图1进行分析:
在求解最优指派问题时,如果问题是标准形式的,直接用匈牙
利算求出最优解,如果问题是非标准形式的,要根据不同的问题,将其系数矩阵转化为不同的标准形式,然后用匈牙利算法求解;
可见在求解最优指派问题的过程中,都用到了匈牙利算法,而且匈牙利算法处理的对象都是矩阵。
为了给用户提供解决最优指派问题的便捷工具,通过人机界面交互操作就可以求出问题的最优解,并将结果可视化。
无疑MATLAB强大的矩阵运算功能,及友好的人机交互界面GUI是最佳的。
3.总体方案设计
通过问题分析可知,利用MATLAB强大的矩阵运算功能及友好的人机交互界面GUI,来设计解决最优指派问题的工具,此工具要把求解标准和非标准形式指派问题的功能集合于一身。
在借助此工具求解问题时,要尽量减少人工的干预,并将所得到结果可视化,因此该工具是一种解决最优指派问题的综合计算平台。
设计应遵循简单性、一致性、习常性原则。
总的设计方案如下:
在M文件中用MATLAB语言实现匈牙利算法,并能正确运行;
分析界面要实现的主要功能,明确设计任务;
在稿纸上给出界面草图,从使用者的角度来审视草图;
4:
按照构思的草图,上机制作(静态)界面,并进行检查;
5:
编写界面动态功能的程序,对功能进行逐项检查。
在求解标准和非标准形式最优指派问题的过程中,都要调用匈牙利算法子函数,匈牙利算的MATLAB语言实现又占有很大的篇幅,因此把匈牙利算的MATLAB语言实现放在了总体设计方案的第一步,此算法的实现对后面的界面设计打下了基础,也为界面的实现提供了前提条件。
4.平台的具体实现
在总体设计方案中给出了最优指派问题综合计算平台实现的5个步骤,即给出了平台实现的框架,但并不能用这些步骤来求解最优指派问题。
要实现此平台,就要逐步对这5个步骤加以解决。
4.1匈牙利算法的MATLAB语言实现
匈牙利算法的MATLAB语言实现,在最优指派问题综合计算平台设计中占有的重要地位,可以在总体设计方案中看到。
把此算法分成三个模块来实现,前两模块实现的目标:
找出独立零元素组。
最后一个模块实现的目标:
得出问题的最优解。
按照“自顶向下,逐步求精”的思想分别加以实现。
在这三个模块的实现中,第二个模块的设计和实现是最为关键和困难的。
第一个模块的实现:
用all函数判断系数矩阵每行每列中是否含零元素,用c(:
jj)=c(:
jj)-min(c(:
jj))或c(ii,:
)=c(ii,:
)-min(c(ii,:
))语句变换不含零元素的行或列,使不含零元素的行或列中含有零元素。
这样就实现了系数矩阵的每行每列中至少含有一个零元素。
第二个模块的实现:
在每行每列都含有零元素的矩阵上,用最少的“直线”数覆盖所有的零元素,在用“直线”覆盖零元素时,要标记每行每列,为继续变换矩阵做前提。
判断直线的数目是否等于系数矩阵的维数,如果不是,继续变换矩阵,使未被直线覆盖的元素中出现零元素,同时消除负元素,重新判断。
若直线的数目等于系数矩阵的维数,则最优解存在,跳出循环,在最后所得到矩阵中寻找独立的零元素。
部分程序如下
forii=1:
rows%标记每行每列%
labelrows_c(ii,cols+1)=ii;
labelcols_c(rows+1,ii)=ii;
end
[msite2]=max(num0(:
));
ifsite2<
=cols3%用最少“直线”数覆盖所有零元素%
c(:
site2)=[];
else
c(site2-cols3,:
)=[];
theminnumber=min(c1(1:
rows2*cols2-rows2));
%继续变换矩阵%
rows2
c(c1(ii,cols2),:
)=c(c1(ii,cols2),:
)-theminnumber;
[minimumsite3]=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数组中,接下来就要实现问题最优解的输出。
rows%指派方案的实现%
zhipaifangan_c(therealsiteofthejob02(ii))=1;
end
feiyongdexishujuzhen=c.*original_c;
%计算所需要的费用%
thechargeofthejob=sum(feiyongdexishujuzhen(:
4.2界面要实现的主要功能
通过问题分析,该界面是集合标准和非标准形式最优指派问题的综合计算平台,其要实现的主要功能有:
能读入要解决问题的数据,将该数据显示到界面中;
将数据的路径和名字显示到界面中;
根据问题的类型和要求做相应的操作,能得到满意的结果,并将问题的结果显示到界面中;
能够清除界面中已显示过的数据;
能够切换界面中提示文字的语言;
对于非法输入和超本计算平台求解的数据能够做出提示;
能安全退出。
4.3界面草图
制作草图是界面设计的前期工作,根据界面要实现的主要功能,从使用者的角度画出界面的草图,并审视草图。
4.4上机制作(静态)界面
根据绘制的草图,在用户图形界面区内合理的摆放所需要的组件,并在按钮的标签上对其所要实现的功能进行描述。
根据界面要实现的主要功能,该组件包括:
六个按钮;
两个单选按钮;
一个框架;
一个开关按钮;
五个文本域;
两个编辑框;
两个列表框。
该平台的(静态)界面如图2
图2
图2给出了最优指派问题综合计算平台的(静态)界面,在此将按照从上往下,从左往右的顺序介绍各个组件的功能:
按钮1:
用于求解人数等于事数或人数不等于事数的最小化问题;
按钮2:
用于求解人数等于事数或人数不等于事数的最大化问题;
按钮3:
用于求解一个人做多件事的问题,其中有两个单选按钮,根据问题的要求选择单选按钮,默认的情况下,求解的是一个人做多件事的最大化问题;
按钮4:
用于读取所要解决问题的系数矩阵;
开关按钮5:
用于切换界面中提示文字的语言,在中英文之间切换;
按钮6:
用于清除所显示过的数据;
按钮7:
用于安全退出此界面;
编辑框8:
用于显示所要解决问题的费用;
列表框9:
用于显示问题的系数矩阵;
列表框10:
用于显示问题的指派方案;
编辑框11:
用于显示存放系数矩阵文件的路径和名字。
4.5编写界面动态功能程序
静态界面制作好之后,并不能使之运行,为了使鼠标单击某个按钮,并能做出预期的反应,就要对各个按钮编写驱动程序,这个驱动程序被称为该按钮的回调函数(Callback),回调函数的编写是界面设计中最关键的一步,直接关系到界面能否运行。
由于篇幅有限,在此只给出该计算平台部分按钮回调函数的实现。
“读取数据”按钮回调函数实现:
%读取所要解决问题系数矩阵的数据%
[FileNamePathName]=uigetfile(('
*.xls'
),'
choseafile'
);
str=[PathNameFileName];
set(handles.edit2,'
string'
str);
handles.orignal_c=xlsread(str);
str04=[num2str(handles.orignal_c)];
set(handles.listbox2,'
str04);
guidata(hObject,handles);
其中uigetfile((‘*.xls’),‘choseafile’)语句,用于打开一个将数据存放在execel中的文件,即在求解问题之前,将所要解决问题的系数矩阵存放在一个execel表格中。
将该execel文件的储存路径和名字分别放在PathName和FileName中。
str)语句将execel的储存路径和名字输入到编辑框11。
xlsread函数命令用于读取execel文件中的数据。
实现数据的输出:
%输出最优指派问题的结果%
str02=[num2str(theminimumchargeofthejob)];
str03=[num2str(copy_c)];
set(handles.edit1,'
str02);
set(handles.listbox1,'
str03);
num2str函数用于把数字转化成字符。
str03)语句将指派方案显示到列表框10中。
在用此平台求解问题时,需要知道此平台的适用范围,这样才能为用户提供更好的服务。
首先此界面是用于求解最优指派问题的综合计算平台,可用此平台求解标准形式的指派问题、最大化的指派问题、人数不等于事数的指派问题、一个人做多件事的指派问题和某项任务一定不能由某人来完成的指派问题,需要在次说明,在用此平台求解某项任务一定不能由某人来完成的指派问题时,由于问题的类型复杂,随机性太强,所以在求解之前要对问题的系数矩阵按照问题的要求做一定的处理,然后再借助此平台求解。
其次在读取数据时,应该把所要求解的数据存放在execel表格中。
最后该平台在用于求解最优指派问题时,并不是实用于所有的问题,对于有些苛刻的数据,它不能给出结果。
5.平台的具体应用
在总体设计方案中给出了最优指派问题综合计算平台实现的5个步骤,在具体实现中逐步对这5个步骤加以解决,最终实现了最优指派问题综合计算平台的设计。
再借助此平台求解最优指派问题时,到底得到的结果是不是我们所满意的,能否对一些非法输入做出处理,能否在运行的过程中正确、稳定、健康、友好的运行。
这就需要接受实践的检验,下面把此平台用于求解最优指派问题,在求解此类问题时,由于应用程序处理的对象是问题的系数矩阵,所以在求解的过程中,省略了对问题建立模型的这一步,而是直接用平台处理系数矩阵,并给出了问题的最优解。
例1,设有12名工作人员要完成12项工作,
名工作人员去完成第
项工作所需要的时间,问如何指派,使完成任务最快。
假设每人完成各项工作的时间矩阵为
对问题的分析,这是一个系数矩阵较大的最小化标准指派问题,在MATLAB命令窗口中输入xylsf命令,并执行此命令,就可以打开最优指派问题综合计算平台的界面。
打开后我们针对此问题进行求解,在求解之前将该问题的系数矩阵存放在一个execel表格中。
求解步骤:
第一步:
读取数据,当按下“读取数据”按钮后会弹出如图3所示的界面;
图3
第二步:
通过choseafile窗口找到存放数据得execel表格,然后打开该表格,就可以将数据显示到界面中,如图4
图4
从图4中可以看到该问题的系数矩阵被显示在了“系数矩阵”栏里面;
第三步根据问题的要求做相应的操作,由于这是一个最小化的指派问题,故按最小化按钮,所得结果如图5。
图5
对所得的结果进行分析:
“费用最大(或最小)”显示框中的40表示完成此任务所用的最少时间,“指派方案”显示框中的矩阵表示指派方案,“系数矩阵”显示框中的矩阵为该问题的系数矩阵。
例2分配甲、乙、丙、丁四个人去完成任务.由于任务数多于人数,故规定其中一个人可兼完成两项任务,其余三人每人完成一项。
确定总花费时间为最少的指派方案。
每人完成各项任务的时间矩阵为
此问题属于一个人可以做几件事的最小化非标准指派问题,在借助平台求解时,不像求解前面的问题,这时要对该问题的系数矩阵作相应的转化,然后才能用程序求解。
对此系数矩阵转化有两种方法:
1)由题意知,在四个人中只能有一个人担任两项任务,不知道那个人会承担两项,故转化之后的系数矩阵共有四种:
第一种,只将甲化作相同的两个“人”来接受任务。
第二种,只将乙化作相同的两个“人”来接受任务。
第三种,只将丙化作相同的两个“人”来接受任务。
第四种,只将丁化作相同的两个“人”来接受任务。
2)添加一个虚拟的“人”戊,他完成各项任务时间取甲、乙、丙、丁中最小者。
将问题的系数矩阵转化之后,就用此平台来来求解。
按照1)中的转化后,会得到四个系数矩阵,分别将这四个矩阵借助平台求解,会得到四种结果,比较着四种结果,取其中费用最小的,那么最小费用和其所对应指派方案就是该问题的最优解,此解将会在附录2中给出。
在此将着重用2)中的转化方法来求解此问题。
所得到得结果如图6
图6
分析所得到的结果:
因为该问题是一个人可以做几件事的最小化非标准指派问题,在求解的过程中要添加一些虚拟的“人”,但是在execel表格中输入该系数矩阵时,不需要手动去添加,因为程序在运行的过程中会自动识别标准与非标准形式并把非标准转化成标准形式,以提高解决问题的效率。
例3某地区从电网中分配得到的电力共有6万千瓦,可用于工业,而该地区有机械、化工、轻纺、建材四大部类,各部类获得电力以后,可以为该地区提供的利润如表3所示,问应该如何分配电力该地区的电力可使获得的利润得到最大?
其费用的系数矩阵为
此问题既属于最大化指派问题,也属于人数和事数不等的指派问题。
我们可以将1,2,…,6万千瓦的电力看作是六种不同的资源,则问题就可以看成是将六种资源用于四种生活活动的资源分派问题。
对于此问题也借助此平台来求解,但是在输入系数矩阵时,不需要手动将系数矩阵化为标准指派问题的系数矩阵。
所得到的结果如图7
图7
由结果可得问题的解为:
分配3、4、5、6万千万的电力分别给这化工、轻纺、机械、建材生活区供电,可获得最大利润为43(万元)。
6.总结
本文介绍了最优指派问题和匈牙利算法的理论,但核心在于,基于匈牙利算法,如何利用MATLAB函数及图形用户界面GUI,设计实现最优指派问题的综合计算平台。
文章用了较大的篇幅介绍了平台的设计思想及实现的方法和步骤,最后把平台用于求解最优指派问题,以接受实践的检验。
结果表明:
最优指派问题综合计算平台能够较好的用于求解最优指派问题;
方便用户操作;
减少了人工的干预;
提高了解决问题的效率;
具有可推广性;
。
但其中的部分功能还不够完善或有待改进。
有不当之处,望专家不吝赐教。
参考文献
【1】姜起源,谢金星,叶俊,数学模型(第三版),北京:
高等教育出版社,2008,107-108
【2】胡运权,郭耀煌,运筹学教程,北京:
清华大学出版社,1998,129-134
【3】邓成梁,运筹学的原理和方法(第二版),武汉:
华中理工大学出版社,1998,242-247
【4】胡运权,运筹学习题集(第三版),北京:
清华大学出版社,2002,62-63
【5】郑阿奇,曹戈,MATLAB实用教程(第二版),北京:
电子工业出版社,2007
【6】张旭辉,朱宏辉,郑启忠,最优指派问题匈牙利算法的探讨与C++实现,物流技术,第5期:
2004
【7】罗华飞,MATLABGUI设计学习手记,北京:
北京航天航空大学出版社,2009,8
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于MATLAB GUI最优指派问题综合计算平台设计第十届科技作品 基于 MATLAB GUI 最优 指派 问题 综合 计算 平台 设计 第十 科技 作品