数学建模第五讲专用课件.ppt

数学建模讲义 参考书目 1.薛定宇，陈阳泉。高等应用数学问题的matlab求解。清华大学出版社。 2. 陈宝林。最优化理论与算法。清华大学出版社. 3. 谢金星，薛毅。优化建模与lindo/lingo优化软件.清华大学出版社. 优化模型应用的广泛性 历届数模竞赛所涉及的优化问题： 97年 A题：零件参数设计（产品参数优化设计） 目标：产品总造价最低（产品质量损失费用 零件制造成本费用） 决策：零件参数的最佳水平组合方案 98年 A题：组合投资问题（风险决策优化问题） 目标（二目标）：收益最大，风险最小 决策：组合投资方案 99年 　A题：自动化车床管理（排队-更新问题） 目标：生产工序的效益（费用最低）最大 决策：最佳检验间隔河刀具更换策略 99年 B题：钻井布局问题(生产计划优化问题) 目标：最大限度利用初步、勘探时的旧井数 决策：在规定精度的前提下确定系统勘探时的最 佳网络分布 02年 A题：车灯线光源的优化设计 目标：线光源的功率最小 决策:在满足设计规范的条件下,计算线光源的长度 B题：彩票中的数学 目标：最大限度地吸引彩民积极购买彩票 决策：在保证彩民和彩票公司的利益上如何设置最佳彩票方案 优化模型的一般形式 主要内容 线性规划(LP) 非线性规划(NLP) 整数规划(IP) 线性规划 3. 线性规划的性质 线性规划是最优化方法发展最迅速，成就最大的一个分支，线性规划发展的爆炸时期是20世纪50年代至60年代，其奠基人应是苏联数学家Cantolovch 和美国数学家G.B.Danfzig。 1947年Dantzig提出了轰动数学界的单纯形法，为求解多维线性规划问题提供了一般的有效的工具； 1950-1965年匈牙利的两位数学家H.W.Kuhn和A.W.Tucker建立了线性规划的对偶理论，为求结鞍点问题提供了数学工具，两位年轻的数学家建立了约束极值的最优形条件，称为K-T条件。为求解非线性规划奠定了理论基础； 1958年美国数学家R.E.Gomery提出整数规划的割平面法； 1960年Rantzig and P.Wolfe研究成功线性规划的分解算法，该算法为求解大规模线性规划提供了强有力的工具； 1979年-1984年苏联数学家L.G.Khachiyan和美国数学家N.A.Karmarka先后提出并完成了线性规划的多项式算法轰动了整个数学界。 线性规划的主要算法 单纯形法（1947年美国Dantzig） 修正单纯形法，对偶单纯形法。非多项式时间方法，对中小规模问题非常有效，应用广泛。 椭球方法（1979年苏联L.G.Khachiyan） 多项式时间方法，理论价值高，不常用，效果不理想。 时间复杂度为 Karmarkar方法（1984美国N.A.Karmarka ） 内点方法，多项式时间方法，理论价值高，有效，时间复杂度为 ， 对大规模问题也十分有效. 单纯形法算法思想 Karmarkar内点方法算法思想 5. 求解线性规划问题的算法软件 Matlab 可以求解任意规模的线性规划问题。 Lingo 可以求解任意规模的线性规划问题，特别是整数线性规划问题,但是不易得到功能强大的版本. 解: 编写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) S.t. 改写为： 例3 : 问题一的解答 编写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) 结果: x =0.0000 600.0000 0.0000 400.0000 0.0000 500.0000 fval =1.3800e+00