数学建模讲义6

《数学建模讲义6》由会员分享，可在线阅读，更多相关《数学建模讲义6（51页珍藏版）》请在金锄头文库上搜索。

1、主讲人:穆学文西安电子科技大学数学系 Email:数学建模讲义最优化模型-线性规划 参考书目1.薛定宇，陈阳泉。高等应用数学问题的matlab 求解。清华大学出版社。2. 陈宝林。最优化理论与算法。清华大学出版社.3. 谢金星，薛毅。优化建模与lindo/lingo优化软 件.清华大学出版社.优化模型应用的广泛性（1） 系统分析，即生产计划和经营决策中的优 化问题。例如：合理计划生产:运输，分配，布局，选址，指派， 下料、配料等优化问题（linear programming）;合理开发（或配置）资源:可再生资源的持续开 发,不可再生资源的优化配置（linear programming）合理运行

2、设备:设备的最有运行（维修）方案.合理组合投资:追求最大受益、最小风险的投资组 合方案（Multiobjective programming） （2）工程设计和控制中的非线性分析（Non- linear programming and optimal control） 例如：结构系统最优设计（人字架设计）机械零件或部件的最优化设计(轮轴颈,凸轮设计)化工设备最优设计（单件或连锁设备优化设计）电力网络和水力网络的优化设计（平衡条件）历届数模竞赛所涉及的优化问题：94年 A题 逢山开路（工程设计优化问题） 目标：工程造价最低 决策：在若干约束下选择一条最佳线路 95年 B题：天车调度问题（生产操作

3、优化问题） 目标：年钢产量最大 决策：天车调度的最优方案设计l96年 A题：最优捕鱼策略（开发资源优化问题） 目标：可持续捕捞的努力量及最大捕捞量 决策：在平衡条件下确定五年内最佳捕捞方案l97年 A题：零件参数设计（产品参数优化设计）目标：产品总造价最低（产品质量损失费用零件制造成本费用） 决策：零件参数的最佳水平组合方案l98年 A题：组合投资问题（风险决策优化问题）目标（二目标）：收益最大，风险最小决策：组合投资方案l99年 A题：自动化车床管理（排队-更新问题）目标：生产工序的效益（费用最低）最大决策：最佳检验间隔河刀具更换策略l99年 B题：钻井布局问题(生产计划优化问题)目标：最大

4、限度利用初步、勘探时的旧井数决策：在规定精度的前提下确定系统勘探时的最 佳网络分布l02年 A题：车灯线光源的优化设计目标：线光源的功率最小决策:在满足设计规范的条件下,计算线光源的长度B题：彩票中的数学目标：最大限度地吸引彩民积极购买彩票决策：在保证彩民和彩票公司的利益上如何设置 最佳彩票方案优化模型的一般形式x:决策变量 f(x):目标函数gi(x)0:约束条件可行解：满足约束条件的解最优解：取得最值的可行解次优解：一个较满意的可行解可行集（域）：所有可行解组成的集合，l线性规划(LP)l非线性规划(NLP)l整数规划(IP)主要内容线性规划1、两个引例。2、线性规划模型3、线性规划的性质

5、。4、线性规划的主要算法。5、用数学软件包求解线性规划问题6、建模案例选讲：投资的收益与风险例1：某厂每日8小时的产量不低于1800件。为了进行质量控制 ，计划聘请两种不同水平的检验员。一级检验员的标准为：速 度25件/小时，正确率98%，计时工资4元/小时；二级检验员的 标准为：速度15小时/件，正确率95%，计时工资3元/小时。检 验员每错检一次，工厂要损失2元。为使总检验费用最省，该 工厂应聘一级、二级检验员各几名？解： 设需要一级和二级检验员的人数分别为x1、x2人, 则应付检验员的工资为：因检验员错检而造成的损失为：故目标函数为：约束条件为：线性规划模型：某车间有甲、乙两台机床，可用

6、于加工三种工件。假定这两 台车床的可用台时数分别为800和900，三种工件的数量分别 为400、600和500，且已知用三种不同车床加工单位数量不同 工件所需的台时数和加工费用如下表。问怎样分配车床的加 工任务，才能既满足加工工件的要求，又使加工费用最低？例2 ：任务分配问题解：设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：线性规划的标准形式：2. 线性规划的模型 线性规划的模型结构：目标函数 ： 约束变量 ： 变量符号 ：目标函数 ： 约束变量 ： 变量符号 ：3. 线性规划的性质线性规划是最优化

7、方法发展最迅速，成就 最大的一个分支，线性规划发展的爆炸时期是 20世纪50年代至60年代，其奠基人应是苏联数 学家Cantolovch 和美国数学家G.B.Danfzig。1947年Dantzig提出了轰动数学界的单纯形 法，为求解多维线性规划问题提供了一般的有 效的工具；1950-1965年匈牙利的两位数学家H.W.Kuhn 和A.W.Tucker建立了线性规划的对偶理论，为 求结鞍点问题提供了数学工具，两位年轻的数 学家建立了约束极值的最优形条件，称为K-T条 件。为求解非线性规划奠定了理论基础；4. 线性规划的算法1958年美国数学家R.E.Gomery提出整数规划的 割平面法；196

8、0年Rantzig and P.Wolfe研究成功线性规 划的分解算法，该算法为求解大规模线性规划提 供了强有力的工具；1979年-1984年苏联数学家L.G.Khachiyan和 美国数学家N.A.Karmarka先后提出并完成了线性 规划的多项式算法轰动了整个数学界。线性规划的主要算法l单纯形法（1947年美国Dantzig）修正单纯形法，对偶单纯形法。非多项式时间方法， 对中小规模问题非常有效，应用广泛。l椭球方法（1979年苏联L.G.Khachiyan）多项式时间方法，理论价值高，不常用，效果不理想。时间复杂度为lKarmarkar方法（1984美国N.A.Karmarka ）内点方

9、法，多项式时间方法，理论价值高，有效，时间复杂度为 ， 对大规模问题也十分有效.单纯形法算法思想从一个可行域的某个顶点出发（基本可行 解）出发，转换到另一个更好的顶点（使目 标函数值有所改善的基本可行解，通过不断 改进基本可行解），最终达到目标函数最优 的顶点(求得问题的最优解)。Karmarkar内点方法算法思想通过射影变换把原问题转化为在球域上 极小化另一个线性函数。求出问题在球域 上的最优解后，再用逆变换将该解返回到 原决策空间里去，从而得到原问题的近似 解。重复以上过程，得到的点列在多项式 时间内收敛于原问题的最优解.5. 求解线性规划问题的算法软件lMatlab可以求解任意规模的线性

10、规划问题。lLingo可以求解任意规模的线性规划问题，特 别是整数线性规划问题,但是不易得到功 能强大的版本.用MATLAB优化工具箱解线性规划1、模型：命令：x=linprog(c，A，b) 2、模型 ：命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式： 存在，则令A= ，b= .3、模型：命令：1 x=linprog(c，A，b，Aeq,beq, VLB，VUB)2 x=linprog(c，A，b，Aeq,beq, VLB，VUB, x0)注意：1 若没有等式约束: , 则令Aeq= , beq= .2 其中x0表示初始点 4、命令：x,fval=linprog()

11、返回最优解x及x处的目标函数值fval.注意：在linprog函数中，其中有一选择“largescale”，如 果命令为“on”，则表示利用大规模的线性规划算法求解， 如果命令为“off”，则表示利用中小规模的线性规划算法求 解。求解大规模的线性规划利用的是Karmarkar内点方法 ，求解中小规模的线性规划利用的是一种修正的单纯形法解 :编写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.

12、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)解: 编写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 00 0 0 0.5 1

13、.2 1.3; b = 800; 900; Aeq=1 0 0 1 0 00 1 0 0 1 00 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.0000600.00000.0000400.00000.0000500.0000fval =1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个 工件1、500个工件3，可在满足条件的情况下使总加工 费最小为13800。例4: 问题二的解答改写为：编写M文件xxgh4.m如下

14、：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)结果为：x =9.00000.0000fval =360 即只需聘用9个一级检验员。注： 本问题应还有一个约束条件：x1、x2取整数。故它是一 个整数线性规划问题。这里把它当成一个线性规划来解 ，求得其最优解刚好是整数：x1=9，x2=0，故它就是该 整数规划的最优解。若用线性规划解法求得的最优解不 是整数，将其取整后不一定是相应整数规划的最优解， 这样的整数规划应用专

15、门的方法求解。投资的收益和风险二、基本假设和符号规定二、基本假设和符号规定三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n三、模型的建立与分析4. 模型简化：四、模型1的求解 由于a是任意给定的风险度，到底怎样给定没有一个准 则，不同的投资者有不同的风险度。我们从a=0开始，以 步长a=0.001进行循环搜索，编制程序如下：a=0; while(1.1-a)1c=-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);ax=xQ=-valplot(a,Q,.)，axis(0 0.1 0 0.5)，hold ona=a+0.001; end xlabel(a),ylabel(Q