线性规划模型的MATLAB实现及应用.pdf
- 文档编号:3432578
- 上传时间:2023-05-05
- 格式:PDF
- 页数:5
- 大小:244.41KB
线性规划模型的MATLAB实现及应用.pdf
《线性规划模型的MATLAB实现及应用.pdf》由会员分享,可在线阅读,更多相关《线性规划模型的MATLAB实现及应用.pdf(5页珍藏版)》请在冰点文库上搜索。
第22卷第12期V0122No12徐州工程学院学报JournalofXuzhouInstituteofTechnology2007年12月DEC2007O一1线性规划模型的MATLAB实现及应用管志忠1,吕楠2(1池州职业技术学院,安徽澎州247100)2徐州工程学院,江苏徐州221008)【摘要】用MATLAB程序实现了0-1线性规划问题数学模型的求解方法,并进一步通过实例模型求解方法的分析比较,证明所采用的程序方法有效快捷文中的程序简单明了且具有通用性,只需输入规划模型中对应的相关矩阵,立即得到最优解和最优值【关键词】O一1线性规划;数学模型)MATLAB)最优解;最优值【中图分类号】02211【文献标识码】A【文章编号】16730704(2007)1200640401线性规划是一种特殊形式的整数规划01规划在工厂选址问题、运输问题、投资问题、JJn-r问题、开发新产品问题等方面有着广泛的应用,随着一些数学计算软件包如MATLAB、LINDO等的开发与应用,0-1规划方法在为管理人员作决策时提供了科学的依据,是实现管理现代化的有力工具本文利用MATLAB软件对0-I线性规划模型实施了程序化,通过程序的应用以及与其它求解方法的分析对比可以看出,用0-I线性规划程序来解01线性规划问题比现有的隐枚举法、排序法、穷举法等方法求解要简单快捷得多1Ol线性规划的基本模型在实际管理中,很多问题无法归结为线性规划的数学模型,但却可以通过设置逻辑变量建立起整数规划的数学模型例如选址决策问题:
随着业务发展,某制造公司必须在甲地或乙地建立1至2个新工厂,此外还考虑建一个仓库若仓库与工厂设在同一地点,就可以节省运输费用(若不准备建工厂,也就不需要建任何仓库)问题的关键是新厂建在甲地还是乙地,或同时在两地建厂,建厂同时还必须考虑建一个仓库,仓库必须建在新厂所在地当不考虑财务因素时,这两个地点的优劣不相上下,管理层认为应该在财务分析的基础上做出决策对于这样的问题事实上就是“是一否”或“有一无”问题,可借助整数规划中的O一1整数变量,确定目标函数,建立数学模型0一I线性规划模型的基本形式是:
minZ=叩鲁1。
faqXibji=I2,m【z,=0或1一1,2,n0-1线性规划模型的解,其实质是各变量间0或1的组合随着变量数目的增加,组合方案数目将会很多目前隐枚举法和排序法求0-1线性规划模型的解,除了对特殊结构的0-1线性规划模型有较高的效率外,一般收效较慢,特别对于大规模系统,求解工作量非常大以下程序很好地解决了此问题2模型求解的Matlab程序实现收稿日期:
20070921作者简介:
管志忠(1965一),男,安徽池州人,副教授,硕士,主要从事应用数学研究64万方数据管志忠,等:
0-1线性规划模型的MATLAB实现及应用根据以上0-1线性规划数学模型,运用Matlab软件编写的程序(不妨取文件名:
LOlnm)Jt口下;functionI-xmin,f3=L01n(c,A,b,N,pre)求。
一1整数规划minf=c,*,StA*誓b,其中N表示前N个约束是等式,Pre是等式约束的精度输出最优解xmin和最优值fifnargin5,pre=0;ifnargin4,N一0;end;end;c=c(:
);b=b(;);m,n=size(A);f=sum(abs(e);x=zeros(1,n);ft-0;while1JJ一0;ft=dot(e,x);tl=ftf;while(t1=O)&(jjNiftl0JJ=0lendselseifabs(t1)preJJ=O;breaksend;endsendifjj=一mfft;xmin=x;JJO;endsk=1;whilex(k)一=1x(k)一O;ifk=一nreturnsendk=k+1;endx(k)一1;end在本程序中,整数变量的个数不受限制,并且充分利用已经得到的计算结果来推出下一步的结果,使得程序中只使用了加减运算,从而大大地减少了目标函数和约束条件的计算量运用此程序解答0-1线性规划问题时,根据实际问题的模型写出矩阵c、A、b,确定模型中的约束等式数N和等式约束的精度pre,然后在Matlab命令窗口中分别输入c、A、b,再输Axmin,f=L01n(e,Ab,N,pre),立即得到该模型的最优解X。
和最优值Xo_-f3模型程序的应用与比较通常解0-1整数规划问题所采用的是人们所熟悉的隐枚举法、排序法等,隐枚举法简单地说就是每次只检查。
一1变量组合的一部分就能确定其是否可能成为最优解的一种方法排序法是按目标函数巾各变量系数的大小按从大到小(或从小到大)重新排列,使最优解有较早出现的可能它们通过列表、确定初始过滤条件、过滤、再依次计算过滤,最后找到最优解和最优值与此相比,本文中运用Matlab编写的程序求。
一1整数规划模型的解就显得简单明了、方便快捷实例1求0-1线性规划模型:
minz=3xl+7x2一Of3+甄2xlz2+z3一毛1zlz2+6x3+4x48txl+3x2+丑5=0或1,J=1,2,3,4分析一(隐枚举法):
将上述模型变为规范形式maxf=一z=一3Xl一7X2一z3一zt65万方数据徐州工程学院学报2007年第12期5t一2xI+z2一z3+z4一1一zl+z26x34x4一85x,一3xzz4一5一0或1,歹=1,2,3,4根据。
一1整数规划模型设计隐枚举法计算表,并将0-1变量的所有组合填写在点(x-,xz,X3,)列中(如表1所示)裹1隐枚举法计算表Table1Implicitenumerationcalculationtable点(x1,x2,x3,】【)条件过滤条件函数约束l函敷约束2函数约束3目标函数f判断过滤条件值(O,0,0,0)T(O,o,0,1)7(O,0,l,0)T(O,0,1。
1)T(O,1,0,0)T(0,1,0,1)T(0,1,1,0)T(O,1,1,1)T(1,0,0,0)T(1,0,0,1)T(1,o。
1,0)r(1,0,1,1)T(1,1,0,0)T(1,1,0,I)T(1,1,1,0)T一33通过上述的列表、计算、过滤,本例中最优解X。
=(1,0,l,1)T,最优值z一-f。
一3分析二(排序法):
我们将目标函数中各变量系数的大小按从大到小重新排列,使最优解有较早出现的可能于是将模型变为minz=7x2+3xl+z4一z3计算过程见表2:
St一z2+2xlz4+z31一z2+z1+4x4+6x383x2+5x1+z45xj一0或1,J=1,2,3,4表2排序法计算表Table2Thelistofresultbyrankingmethod点(x2,xl。
】【4,x3)条件目标函数z过滤条件约束1约束2,约束3(0。
0。
0。
0)T0(0,0,0。
1)1一1(O,O。
1,0)r1(O,0。
1,I)T0(O,1,0,0)T3(0,l,0,1)72(o,1,1,0)T4(O,1,1,1)T3Z3(1,0,0。
0)T7(1,0,0,I)T6(1,0,1。
0)T8(1,0。
1。
1)T7(1。
1,0,0)T10(1,1,0。
1)79(1,l。
1。
0)T11一、(1,1,1。
1)T10ob5XXVVVVVVVVVV万方数据管志忠,等:
0-1线性规划模型的MATLAB实现及应用通过上述列表可得本例所求的最优解为(x2,xl,x4,X3)T=(o,1,1,1)T,即X。
;(xl,X2,x3,&)T=(1,0,1,1)一,最优值z。
一3如果是最大化问题,则将变量按其在目标函数中的大小由小到大排列即可。
分析三(MATLAB程序法):
在MATLAB命令窗口中,输入c一3,7,-1,1#A=一2,l,一1,1;-1,1,一6,一4;-5,一3,0,-1;b=一1,一8,-5;(回车)xmin,f=L01n(e,A,b,0,o)(回车)立即得到xmin=(1,0,1,1)T和f=3,于是原题的最优解X一(1,0,1,1)T和最优值g。
=3最后该说明一下将。
一1线性规划模型程序化的必要性了在当今企业的生产经营活动中,最高层管理者主要关心的是企业的目标、方针和基本战略等全面性决策问题,这些问题的解决为在变化环境中指导企业提供一个骨架中下层管理的很多决策活动是处于操作层次的,可以编写程序,让计算机来为管理阶层提供最优解答一旦问题被编成程序,则可以把它们移交给一个管理信息系统这种运筹模型的程序化可以把管理者从日常繁琐的计算分析工作中解脱出来,以便他们能集中精力解决更为困难的战略性问题这种模型程序化的优越性从以上实例模型的分析比较中已经完全表现出来所以,本文中的规划模型程序化做法是非常必要的,值得应用和推广参考文献、1牛映武运筹学M西安;西安交通大学出版社,2006:
118123z仉志佘运筹学基础M北京:
中国科学技术出版社,2003:
84903徐玖平,胡知能运筹学一数据模型决策l-M北京;科学出版社,2006:
42704李映红线性。
一1规划模型的排序解法J西安交通大学学报,2001,(10):
46847L5李南南等MATLAB7简明教程M北京:
清华大学出版社,2006:
289342。
MATLABRealizationofthe01LinearProgrammingModelandItsApplicationGUAN-Zhizhon91。
LnNan2(1ChizhouProfessionalandTechnicalCollege。
Chizhou247100,China2XuzhouInstituteofTechnonogy,Xuzhou221008,China)AbstractMATLABisemployedtorealizethesolutionof0-1linearprogrammingmodelAnditisfurtherprovedthroughexamplemodelcomparisonthatthenewmethodisbotheffectiveandefficientTheprogramintroducedinthepaperisSOsimpleandgeneralthattheoptimalsolutionandvaluecanbeohtainedbysimplyimputingrelativematrixintheprogrammingmodelKeywords0-1linearprogramming;mathmodel;MATLAB;optimalanswer!
optimalvalue(责任编辑燕善俊)67万方数据0-1线性规划模型的MATLAB实现及应用0-1线性规划模型的MATLAB实现及应用作者:
管志忠,吕楠,GUAN-Zhizhong,LNan作者单位:
管志忠,GUAN-Zhizhong(池州职业技术学院,安徽,池州,247100),吕楠,LNan(徐州工程学院,江苏,徐州,221008)刊名:
徐州工程学院学报英文刊名:
XUZHOUINSTITUTEOFTECHNOLOGY年,卷(期):
2007,22(12)被引用次数:
1次参考文献(5条)参考文献(5条)1.牛映武运筹学20062.仉志余运筹学基础20033.徐玖平;胡知能运筹学-数据*模型*决策20064.李映红线性0-1规划模型的排序解法期刊论文-西安交通大学学报2001(10)5.李南南MATLAB7简明教程2006本文读者也读过(9条)本文读者也读过(9条)1.晏林.YANLin线性规划及其程序设计期刊论文-文山师范高等专科学校学报2002,14
(1)2.张颖线性规划模型中MATLAB的求解实现期刊论文-通化师范学院学报2009,30(12)3.林显宁利用规划的方法求解一个最优问题期刊论文-湖北广播电视大学学报2010,30(3)4.戴建平.DAIJian-ping基于MATLAB的运输问题求解方法期刊论文-宁波职业技术学院学报2009,13
(2)5.柯善军.冀小明.KEShan-jun.JIXiao-ming用MATLAB解决优化问题期刊论文-西南民族大学学报(自然科学版)2005,31
(2)6.李映红线性0-1规划模型的排序解法期刊论文-西南交通大学学报2001,36(5)7.王聚.WANGJuMATLAB在优化方案选择中的应用期刊论文-轻工机械2006,24(4)8.毕春丽.曾强.王荣文线性规划问题中单纯形法的计算机求解期刊论文-焦作工学院学报(自然科学版)2002,21(6)9.王乐.王世卿.张静乐.WANGLe.WANGShi-qing.ZHANGJing-le基于Matlab的0-1背包问题的动态规划方法求解期刊论文-计算机技术与发展2006,16(4)引证文献(1条)引证文献(1条)1.陈武.刘慧敏.陈宾智能电网背景下电压暂降监测装置的最优布点方法期刊论文-电力建设2011(6)本文链接:
http:
/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 模型 MATLAB 实现 应用