西安电子科技大学数学建模讲义第五讲专题省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢,主讲人:穆学文,西安电子科技大学数学系,Email:mxw1334,数学建模讲义,第1页,最优化模型,-线性规划,第2页,参考书目,1.薛定宇，陈阳泉。高等应用数学问题matlab求解。清华大学出版社,。,2,.陈宝林。最优化理论与算法。清华大学出版社,.,3,.谢金星，薛毅。优化建模与lindo/lingo优化软件.清华大学出版社.,第3页,优化模型应用广泛性,（1）系统分析，即生产计划和经营决议中优化问题。比如：,合理计划生产:运输，分配，布局，选址，指派，下料、配料等优化问题（linear programming）;,合理开发（或配置）资源:可再生资源连续开发,不可再生资源优化配置（linear programming）,合理运行设备:设备最有运行（维修）方案.,合理组合投资:追求最大受益、最小风险投资组合方案（Multiobjective programming）,第4页,（2）工程设计和控制中非线性分析（Non-linear programming and optimal control）,比如：,结构系统最优设计（人字架设计）,机械零件或部件最优化设计(轮轴颈,凸轮设计),化工设备最优设计（单件或连锁设备优化设计）,电力网络和水力网络优化设计（平衡条件,）,第5页,历届数模竞赛所包括优化问题：,94年 A题 逢山开路（工程设计优化问题）,目标：工程造价最低,决议：在若干约束下选择一条最正确线路,95年 B题：天车调度问题（生产操作优化问题）,目标：年钢产量最大,决议：天车调度最优方案设计,96年 A题：最优打鱼策略（开发资源优化问题）,目标：可连续捕捞努力量及最大捕捞量,决议：在平衡条件下确定五年内最正确捕捞方案,第6页,97年 A题：零件参数设计（产品参数优化设计）,目标：产品总造价最低（产品质量损失费用,零件制造成本费用）,决议：零件参数最正确水平组合方案,98年 A题：组合投资问题（风险决议优化问题）,目标（二目标）：收益最大，风险最小,决议：组合投资方案,99年 A题：自动化车床管理（排队-更新问题）,目标：生产工序效益（费用最低）最大,决议：最正确检验间隔河刀具更换策略,第7页,99年 B题：钻井布局问题(生产计划优化问题),目标：最大程度利用初步、勘探时旧井数,决议：在要求精度前提下确定系统勘探时最 佳网络分布,A题：车灯线光源优化设计,目标：线光源功率最小,决议:在满足设计规范条件下,计算线光源长度,B题：彩票中数学,目标：最大程度地吸引彩民主动购置彩票,决议：在确保彩民和彩票企业利益上怎样设置最正确彩票方案,第8页,优化模型普通形式,x:,决议变量,f,(,x,):目标函数,g,i,(,x,),0,:约束条件,可行解：满足约束条件解,最优解：取得最值可行解,次优解：一个较满意可行解,可行集（域）：全部可行解组成集合，,第9页,线性规划(,LP,),非线性规划(,NLP,),整数规划(,IP,),主要内容,第10页,线性规划,1、两个引例。,2、线性规划模型,3、线性规划性质。,4、线性规划主要算法。,5、用数学软件包求解线性规划问题,6、建模案例选讲：投资收益与风险,第11页,例1：,某厂每日8小时产量不低于1800件。为了进行质量控制，计划聘请两种不一样水平检验员。一级检验员标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？,解：,设需要一级和二级检验员人数分别为,x,1,、,x,2,人,则应付检验员工资为：,因检验员错检而造成损失为：,第12页,故目标函数为：,约束条件为：,第13页,线性规划模型：,第14页,某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床可用台时数分别为800和900，三种工件数量分别为400、600和500，且已知用三种不一样车床加工单位数量不一样工件所需台时数和加工费用以下表。问怎样分配车床加工任务，才能既满足加工工件要求，又使加工费用最低？,例2：任务分配问题,第15页,解：,设在甲车床上加工工件1、2、3数量分别为,x,1,、,x,2,、,x,3,，,在乙车床上加工工件1、2、3数量分别为,x,4,、,x,5,、,x,6,。,可建立以下线性规划模型,：,第16页,线性规划标准形式：,2.线性规划模型,线性规划模型结构：,目标函数：,约束变量：,变量符号：,目标函数：,约束变量：,变量符号：,第17页,3.线性规划性质,线性规划可行域是凸集,线性规划可能有解、无解或无有限最优解,线性规划最优解在极点(顶点)上,凸集：对区域D中任意两个元素,x,y,和人意非负数0,a,1,元素,ax+,(,1-a,),y,也在区域D中。,第18页,线性规划是最优化方法发展最快速，成就最大一个分支，线性规划发展爆炸时期是20世纪50年代至60年代，其奠基人应是苏联数学家Cantolovch 和美国数学家G.B.Danfzig。1947年Dantzig提出了轰动数学界单纯形法，为求解多维线性规划问题提供了普通有效工具；1950-1965年匈牙利两位数学家H.W.Kuhn和A.W.Tucker建立了线性规划对偶理论，为求结鞍点问题提供了数学工具，两位年轻数学家建立了约束极值最优形条件，称为K-T条件。为求解非线性规划奠定了理论基础；,4.线性规划算法,第19页,1958年美国数学家R.E.Gomery提出整数规划割平面法；1960年Rantzig and P.Wolfe研究成功线性规划分解算法，该算法为求解大规模线性规划提供了强有力工具；1979年-1984年苏联数学家L.G.Khachiyan和美国数学家N.A.Karmarka先后提出并完成了线性规划多项式算法轰动了整个数学界,。,第20页,线性规划主要算法,单纯形法（,1947年美国Dantzig）,修正单纯形法，对偶单纯形法。非多项式时间方法，对中小规模问题非常有效，应用广泛,。,椭球方法（1979年苏联,L.G.Khachiyan）,多项式时间方法，理论价值高，不惯用，效果不理想。,时间复杂度为,Karmarkar方法,（,1984,美国N.A.Karmarka,）,内点方法，多项式时间方法，理论价值高，有效，时间复杂度为 ，,对大规模问题也十分有效,.,第21页,单纯形法算法思想,从一个可行域某个顶点出发（,基本可行解,）出发，转换到另一个更加好顶点（,使目标函数值有所改进基本可行解，经过不停改进基本可行解,），最终到达目标函数最优顶点(,求得问题最优解,)。,第22页,Karmarkar,内点方法算法思想,经过射影变换把原问题转化为在球域上极小化另一个线性函数。求出问题在球域上最优解后，再用逆变换将该解返回到原决议空间里去，从而得到原问题近似解。重复以上过程，得到点列在多项式时间内收敛于原问题最优解.,第23页,5.求解线性规划问题算法软件,Matlab,能够求解任意规模线性规划问题。,Lingo,能够求解任意规模线性规划问题，尤其是整数线性规划问题,不过不易得到功效强大版本.,第24页,用MATLAB优化工具箱解线性规划,1、模型：,命令,：,x,=linprog(,c,，A，b),2、模型,：,命令：,x,=linprog（,c,，A，b，Aeq,beq）,注意：若没有不等式：存在，则令A=，b=.,第25页,3、模型,：,命令：,1,x,=linprog(c，A，b，Aeq,beq,VLB，VUB),2,x,=linprog(c，A，b，Aeq,beq,VLB，VUB,x,0,),注意：,1 若没有等式约束:,则令Aeq=,beq=.,2 其中,x,0,表示初始点,第26页,4、命令：,x,fval=linprog(),返回最优解,x,及,x,处目标函数值fval.,注意：在linprog函数中，其中有一选择“largescale”，假如命令为“on”，则表示利用大规模线性规划算法求解，假如命令为“off”，则表示利用中小规模线性规划算法求解。求解大规模线性规划利用是,Karmarkar内点方法,，求解中小规模线性规划利用是,一个修正单纯形法,第27页,第28页,解:编写M文件xxgh1.m以下：,c,=-0.4-0.28-0.32-0.72-0.64-0.6;,A=0.01 0.01 0.01 0.03 0.03 0.03;,0.02 0 0 0.05 0 0;,0 0.02 0 0 0.05 0;,0 0 0.03 0 0 0.08;,b=850;700;100;900;,Aeq=;beq=;,vlb=0;0;0;0;0;0;vub=;,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),第29页,第30页,解:,编写M文件xxgh2.m以下：,c=6 3 4;,A=0 1 0;,b=50;,Aeq=1 1 1;,beq=120;,vlb=30,0,20;,vub=;,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub,),第31页,S.t.,改写为：,例3:,问题一解答,第32页,编写M文件xxgh3.m以下:,f=13 9 10 11 12 8;,A=0.4 1.1 1 0 0 0,0 0 0 0.5 1.2 1.3;,b=800;900;,Aeq=1 0 0 1 0 0,0 1 0 0 1 0,0 0 1 0 0 1;,beq=400 600 500;,vlb=zeros(6,1);,vub=;,x,fval=linprog(f,A,b,Aeq,beq,vlb,vub),第33页,结果:,x,=0.0000,600.0000,0.0000,400.0000,0.0000,500.0000,fval,=1.3800e+004,即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件情况下使总加工费最小为13800。,第34页,例4:问题二解答,改写为：,第35页,编写M文件xxgh4.m以下：,c=40;36;,A=-5-3;,b=-45;,Aeq=;,beq=;,vlb=zeros(2,1);,vub=9;15;,%调用linprog函数：,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),第36页,结果为：,x,=9.0000,0.0000,fval=360,即只需聘用9个一级检验员,。,注：,本问题应还有一个约束条件：,x,1,、,x,2,取整数。故它是一个整数线性规划问题。这里把它当成一个线性规划来解，求得其最优解刚好是整数：,x,1,=9，,x,2,=0，故它就是该整数规划最优解。若用线性规划解法求得最优解不是整数，将其取整后不一定是对应整数规划最优解，这么整数规划应用专门方法求解。,第37页,投资收益和风险,第38页,二、基本假设和符号要求,第39页,二、基本假设和符号要求,第40页,三、模型建立与分析,1.总体风险用所投资S,i,中最大一个风险来衡量,即,max,q,i,x,i,|i=1，2,n,第41页,三、模型建立与分析,第42页,4.模型简化,：,第43页,第44页,第45页,四、模型1求解,因为,a,是任意给定风险度，到底怎样给定没有一个准则，不一样投资者有不一样风险度。我们从a=0开始，以步长,a,=0.001进行循环搜索，编制程序以下,：,第46页,a=0;,while(1.1-a)1,c=-0.05-0.27-0.19-0.185-0.185;,Aeq=1 1.01 1.02 1.045 1.065;beq=1;,A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026;,b=a;a;a;a;,vlb=0,0,0,0,0;vub=;,x,val=linprog(c,A,b,Aeq,beq,vlb,vub);,a,x=x,Q=-val,plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on,a=a+0.001;,end,xlabel(a),ylabel(Q),To Matlab（xxgh5）,第47页,计算结果：,第48页,五、结果分析,3.,曲线上任一点都表示该风险水平最大可能收益和该收益要求最小风险。对于不一样风险承受能力，选择该风险水平下最优投资组合。,2,.当投资越分散时，投资者负担风险越小，这与题意一致。即:冒险投资者会出现集中投资情况，保守投资者则尽可能分散投资,。,1.,风险大，收益也大。,第49页,返 回,4,.,在,a,=0.006,附近有一个转折点，在这一点左边，风险增加极少时，利润增加很快。在这一点右边，风险增加很大时，利润增加很迟缓，所以对于风险和收益没有特殊偏好投资者来说，应该选择曲线拐点作为最优投资组合，大约是,a,*,=0.6%，Q,*,=20%，所对应投资方案为:,风险度 收益,x,0,x,1,x,2,x,3,x,4,0.0060 0.0 0.2400 0.4000 0.1091 0.2212,第50页,