数学建模最优化

nullnull12几类典型优化问题及其软件解法3举例4最优化概论MATLAB优化工具箱简介最优化概论最优化概论当今，“优化”无疑是一个热门词。做宏观经济 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 要优化资源配置，搞企业经营管理要优化生产计划，作新产品 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 要优化性能成本比。就是在人们的日常生活中，优化的要求也比比皆是，消费时，如何花尽可能少的钱办尽可能多的事，出行时，如何走最短的路程到达目的地，等等。总而言之，在经济如此发展，竞争如此剧烈，资源日渐紧张的今天，人们做任何事，无不望求事半功倍之术，以求或提效、或增收、或节约等等之目标。一、最优化概念一、最优化概念所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法 另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。 比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。 数学建模竞赛中的优化问题数学建模竞赛中的优化问题2000B 钢管订购和运输问题—二次规划 2001B 公交车优化调度 2001C 基金使用的最优策略-----线性规划 2002B 彩票中的数学 2003B 露天矿生产的车辆安排问题 2004A 奥运会临时超市网点设计问题 2004D 公务员招聘工作中录用 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 —多目标规划 2005B DVD在线租赁 2006A 出版社的资源配置问题 2007A 乘公交，看奥运 2008B 高等教育学费探讨 2009B 眼科病床的合理安排 数学建模竞赛中的优化问题数学建模竞赛中的优化问题2002B，彩票中的数学—约束非线性规划 null从数学上来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：X∈D。 求目标函数F(X)在约束条件X∈D下的最小值或最大值问题，就是一般最优问题的数学模型．二、最优化问题的一般形式二、最优化问题的一般形式无约束最优化问题目标函数 约束最优化问题约束函数 最优解；最优值三、最优化问题分类三、最优化问题分类分类1：　　无约束最优化 　　　　　 约束最优化 非线性规划：目标函数与约束函数中至少有一个是变量x的非线性函数； 线性规划：目标函数与约束函数均为线性函数；分类2：　　线性规划 　　　　　 非线性规划三、最优化问题分类(续）三、最优化问题分类(续） 分类3 （根据决策变量、目标函数和要求不同）整数规划 动态规划 网络规划 随机规划 几何规划 多目标规划三、最优化问题分类(续）三、最优化问题分类(续）函数最优化 组合最优化分类４函数最优化：决策变量是一定区间内的连续变量． 组合最优化：决策变量是离散状态，同时可行域是由有限个点组成的集合 典型组合优化问题：旅行商问题；加工调度问题； 0-1背包问题；图着色问题四、求解最优化问题的方法四、求解最优化问题的方法（1）传统优化方法-----基于导数的优化方法 无约束规划：梯度法、共轭梯度法、拟牛顿法 约束规划：序列二次规划法，罚函数法 线性规划：单纯形方法等 （2）现代优化方法-----智能优化方法 遗传算法，模拟退火法，蚁群算法，粒子群算法 神经网络算法，禁忌搜索算法等 　　为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。五、构造数值优化算法的一般过程五、构造数值优化算法的一般过程最优化方法通常采用迭代法求最优解，过程是：迭代公式　六、最优化方法的基本结构　六、最优化方法的基本结构七、搜索算法结构框图七、搜索算法结构框图八、最优化方法解决问题的步骤八、最优化方法解决问题的步骤（1）确定变量，写出目标函数和有关约束条件，建立数学模型。 （2）分析模型，搞清它属于运筹学哪一分枝，选择合适的最优化方法； （3）编程求解；尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica， Lindo， Lingo等，来计算。 （4）最优解的验证和实施。九、MATLAB优化工具箱简介九、MATLAB优化工具箱简介 1 . 功能 （1）求解无约束条件非线性极小值； （2）求解约束条件下非线性极小值，包括目标逼近问题、极大-极小值问题和半无限极小值问题； （3）求解二次规划和线性规划问题； （4）非线性最小二乘逼近和曲线拟合； （5）非线性系统的方程求解； （6）约束条件下的线性最小二乘优化； （7）求解复杂结构的大规模优化问题。2. 常用函数： 2. 常用函数： 3. Options选项说明3. Options选项说明输入参数中可以用options，用于所有函数，其中包括有一下参数。 （1）Display：结果显示方式，off不显示，iter显示每次迭代的信息，final为最终结果，notify只有当求解不收敛的时候才显示结果。 （2）MaxFunEvals：允许函数计算的最大次数，取值为正整数。 （3）MaxIter：允许迭代的最大次数，正整数。 （4）TolFun：函数值（计算结果）精度，正整数。 （5）TolX：自变量的精度，正整数。 而且可以用函数optimset创建和修改。null4. 输出变量说明null2010数模竞赛培训几类典型最优化问题 及软件解法线性规划问题及其MATLAB解法线性规划问题及其MATLAB解法1. 线性规划的一般形式或线性规划问题及其MATLAB解法线性规划问题及其MATLAB解法2. 线性规划的matlab解法问题形式1： min z = CTx S.t. Ax ≤ b指令：（x，z）=linprog(f, A, b)问题形式2： min z = CTx S.t. Ax ≤ b Aeqx =beq指令：（x，z）=linprog(f, A, b, Aeq, beq)线性规划问题及其MATLAB解法线性规划问题及其MATLAB解法问题形式3： min z = CTx S.t. Ax ≤ b Aeqx =beq lb ≤ x ≤ ub指令：（x，z）=linprog(f, A, b, Aeq, beq,lb,ub) 注： 若没有不等式约束,可用[ ]替代A和b, 若没有等式约束,可用[ ]替代Aeq和beq, 若某个xi下无界或上无界,可设定-inf或 inf；null例:min Z= 4x1 +3x2s.t.解：程序如下c=[4,3];a=[1,1];b=[5]; vlb=[-6;-1]; %lower bound of vector x % vub=[10;4]; % upper bound of vector x % [X,z]=linprog(c,a,b,[],[],vlb,vub)整数线性规划(ILP)及其lindo解法整数线性规划(ILP)及其lindo解法1. 整数线性规划一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划、混合整数规划、0－1整数规划。部分或者全部为整数2、整数规划的计算机求解方法2、整数规划的计算机求解方法 目前，求解整数规划模型的现成数学软件有：Lindo, Lingo和Matlab,其中Lindo和Lingo是专业的优化软件. LINDO 公司软件产品是美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）。 网址：http://www.lindo.com LP问题的Lindo输入范例LP问题的Lindo输入范例MAX 3x1+2x2 ST 2) X1<4 3) X2<3 4) 2x1+3x2<12 END注：Lindo中已规定所有决策变量均非负，故非负约束不用 输入；乘号省略，式中不能有括号，右边不能有数学符号； <=，>=与<，>等效；2），3），4）是为了便于从结果中 查找信息和进行灵敏性分析；程序以end结束。ILP问题的Lindo输入范例之一ILP问题的Lindo输入范例之一MAX 3x1+2x2 ST 2) X1<4 3) X2<3 4) 2x1+3x2<12 END GIN2 (!表示前两个变量为一般整数) ILP问题的Lindo输入范例之二ILP问题的Lindo输入范例之二MAX 3x1+2x2 ST 2) X1<4 3) X2<3 4) 2x1+3x2<12 END INT2 (!表示前两个变量为0-1整数) ILP问题的Lingo输入范例一ILP问题的Lingo输入范例一MAX= 3*x1+2*x2; ST X1<4; X2<3; 2*x1+3*x2<12; @GIN(X1);@GIN(X2); ILP问题的Lingo输入范例之二ILP问题的Lingo输入范例之二max 3x1+2x2 s.t. X1<4 X2<3 2x1+3x2<12 @bin(x1);@bin(x2); (!x1,x2为0-1变量)使用LINDO的一些注意事项使用LINDO的一些注意事项“>”（或“<”）号与“>=”（或“<=”）功能相同 变量与系数间可有空格(甚至回车), 但无运算符 变量名以字母开头，不能超过8个字符 变量名不区分大小写（包括LINDO中的关键字） 目标函数所在行是第一行，第二行起为约束条件 行号(行名)自动产生或人为定义。行名以“）”结束 行中注有“!”符号的后面部分为注释。如: ! It’s Comment. 在模型的任何地方都可以用“TITLE” 对模型命名（最多72个字符），如： TITLE This Model is only an Example使用LINDO的一些注意事项使用LINDO的一些注意事项变量不能出现在一个约束条件的右端 表达式中不接受括号“( )”和逗号“,”等任何符号, 例: 400(X1+X2)需写为400X1+400X2 表达式应化简，如2X1+3X2- 4X1应写成 -2X1+3X2 缺省假定所有变量非负；可在模型的“END”语句后用“FREE name”将变量name的非负假定取消 可在 “END”后用“SUB” 或“SLB” 设定变量上下界 例如： “sub x1 10”的作用等价于“x1<=10” 但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。 14. “END”后对0-1变量说明：INT n 或 INT name 15. “END”后对整数变量说明：GIN n 或 GIN name二次规划及其MATLAB求解方法二次规划及其MATLAB求解方法二次规划形如当A为半正定矩阵时，（QP）为凸二次规划；当A为正定矩阵时，（QP）为严格凸二次规划。（QP）null用MATLAB优化工具包求解二次规划时必须先化为如下形式： (QP) 求解二次规划的MATLAB指令求解程序名为quadprog。 最简单的调用格式为： x = quadprog(H,c,A1,b1)    （用于不含有等式约束和上下解约束的问题）；最复杂的调用格式为： [x,fval,exitflag,output,lambda] = quadprog(H,c,A1,b1,A2,b2,v1,v2,x0,options) 多目标规划及其求解方法 多目标规划及其求解方法多目标规划的一般形式则称为线性多目标规划。其中x=(x1 ,x2 , … ,xn)为一个n维向量；fi(x)为目标函数， hj (x) g i (x)为约束函数。求解多目标规划的方法求解多目标规划的方法1、降维法 ， 即把多目标 化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、极大极小法、理想点法等； 2、分层序列法，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。 3、层次分析法，是由美国运筹学家沙旦于70年代提出的，这是一种定性与定量相结合的多目标决策与分析方法，对于目标结构复杂且缺乏必要的数据的情况更为实用。主要目标法 主要目标法 其基本思想是：在多目标问题中，根据问题的实际情况，确定一个目标为主要目标，而把其余目标作为次要目标，并且根据经验，选取一定的界限值。这样就可以把次要目标作为约束来处理，于是就将原来的多目标问题转化为一个在新的约束下的单目标最优化问题。 线性加权法 线性加权法 其基本思想是：按照多目标fi(x) (i=1, 2, … ,m)的重要程度，分别乘以一组权系数λj(j=1, 2, … ,m)然后相加作为目标函数而构成单目标规划问题。即 其中极大极小法 极大极小法 其基本思想是：对于极小化的多目标规划，让其中最大的目标函数值尽可能地小.为此，对每个 x∈R，我们先求诸目标函数值fi(x)的最大值，然后再求这些最大值中的最小值。即构造单目标规划： 理想点法 为权值系数向量。于是多目标规划问题化为： 理想点法 对于多目标规划： s.t gj (x) ≤0 j=1, 2, … ,n 先设计与目标函数相应的一组目标值理想化向量 再设γ为一松弛因子标量。设 null 在Matlab的优化工具箱中，fgoalattain函数用于解决此类问题。其数学模型形式为： min γ F(x)-weight ·γ≤goal c(x) ≤0 非线性不等式约束 ceq(x)=0 非线性等式约束 A x≤b 线性不等式约束 Aeq x=beq 线性等式约束 lb≤x≤ub 其中，x,weight,goal,b,beq,lb和ub为向量，A和Aeq为矩阵，c(x),ceq(x)和F(x)为函数null调用格式： x=fgoalattain(F,x0,goal,weight) [x,fval,attainfactor,exitflag,output,lambda] =fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options) 说明：F为目标函数；x0为初值；goal为F达到的指定目标；weight为参数指定权重；A、b为线性不等式约束的矩阵与向量；Aeq、beq为等式约束的矩阵与向量；lb、ub为变量x的上、下界向量；nonlcon为定义非线性不等式约束函数c(x)和等式约束函数ceq(x)；options中设置优化参数。 x返回最优解；fval返回解x处的目标函数值；attainfactor返回解x处的目标达到因子；exitflag描述计算的退出条件；output返回包含优化信息的输出参数；lambda返回包含拉格朗日乘子的参数。例1： 投资组合模型例1： 投资组合模型 市场上有n种资产Si (i=1,2,…,n)可以选择，现用数额为M的相当大的资金作一个时期的投资。财务人员分析估算出这一时期内购买Si的平均收益率为ri ,风险损失率为qi , 在多项投资组合中，总体风险可用投资的Si中最大的一个风险来度量。 购买Si时要付交易费，费率pi(不买无须付费).当购买额不超过给定值ui时，交易费按购买ui计算.另外，假定同期银行存款利率是r0 ,既无交易费又无风险。( r0=5%) null 试给该公司设计一种投资组合方案，即用给定达到资金M,有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。已知n=4时的相关数据如下:基本假设基本假设1.投资数额M相当大,为了便于计算，假设M=1; 2.投资越分散，总的风险越小； 3.总体风险Si用投资项目中最大的一个风险来度量； 4.n种资产Si之间是相互独立的； 5.在投资的这一时期内,ri, pi, qi, r0为定值，不受意外因素影响； 6.净收益和总体风险只受ri, pi, qi影响，不受其他因素干扰。 符号规定符号规定Si ——第i种投资项目，如股票，债券 ri ,pi ,qi ——分别为Si的平均收益率,风险损失率，交易费率 ui ——Si的交易定额, r0 ——同期银行利率 xi ——投资项目Si的资金, a ——投资风险度 Q——总体收益, ∆Q——总体收益的增量 模型的建立与分析 模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max{ qixi|i=1，2,…n} 2．购买Si所付交易费是一个分段函数,即 pixi xi>ui 交易费 = piui xi≤ui 而题目所给定的定值ui(单位:元)相对总投资M很小, piui更小,可以忽略不计,这样购买Si的净收益为(ri-pi)xi null净收益尽可能大建立模型总体风险尽可能小多目标规划问题采用主要目标法化为单目标规划采用主要目标法化为单目标规划 方法一. 固定风险水平，优化收益 在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险qixi/M≤a，可找到相应的投资方案。 模型一 线性规划模型方法二：固定盈利水平，极小化风险方法二：固定盈利水平，极小化风险 若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。 模型二 线性规划模型采用线性加权法化为单目标规划采用线性加权法化为单目标规划 投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重s（0＜s≤1)，s称为投资偏好系数. 模型三 线性规划模型模型一的求解模型一的求解 将具体数据代入,模型一如下: 由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长△a=0.001进行循环搜索，编制程序如下：nulla=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')null风险大，收益也大。 曲线上的任一点表示该风险水平的最大可能收益。 对于不同风险的承受能力，选择该风险水平下的最优投资组合。 null 在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是： a*=0.6%，Q*=20% 。 此时所对应投资方案为: 风险度= 0.0060；收益= 0.2019 ； x0 =0 ， x1 =0.2400 ，x2 =0.4000 ， x3 =0.1091， x4=0.2212null约束非线性规划一般形式： 其中，f(x)为多元实值函数;g(x)，ceq(x)为向量函数,并且f(x),g(x), ceq(x)中至少有一个函数是非线性函数（否则成为线性规划问题）。nullx=fmincon(‘fun’,x0,A,b) x=fmincon(‘fun’,x0,A,b,Aeq,beq) x=fmincon(‘fun’,x0,A,b,Aeq,beq,lb,ub) x=fmincon(‘fun’,x0,A,b,Aeq,beq,lb,ub,nonlcon) x=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON, OPTIONS)在Matlab优化工具箱中，fmincon函数是用SQP算法来解决一般的约束非线性规划的函数，它的命令格式为：上式中x为最优点；若将左端的x换为[x,f],则返回最优点x和最优值f。null【例1 】求解约束非线性规划： (初值为[1;1])解:首先建立一个m文件fun1.m function y=fun1(x) y=-exp(x(1))*x(2)^2*(3-exp(x(1))-x(2)^2); 存储为fun1.m首先将问题转化为matlab要求的格式;即求出fun,A,b,Aeq,Beq,X0,Lb,Ubnullfunction [g,cep]=fun2(x) g=[]; % g为非线性不等式,且为g<=0 ceq=exp(x(1))+x(2)^2-3; % ceq为非线性等式 然后存储为fun2.m建立主程序： A=[];b=[];Aeq=[];Beq=[];Lb=[];Ub=[]; [x,f]=fmincon(‘fun1’,[1;1],[],[],[],[],[],[],’fun2’) -f建立非线性约束m-文件 fun2.m运行结果为:x = 0.8852 0.7592 f = 6.2043e-016最优点最优值null【例 2】求解约束非线性规划： 解：首先建立一个m文件 fun5.m function y=fun5(x) y=(x(1)-1)^2+(x(2)-2)^2+(x(3)-3)^2+(x(4)-4)^2; 存储为fun5.m文件.nullx0=[1;1;1;1];A=[1 1 1 1;3 3 2 1]; B=[5;10];Aeq=[];Beq=[]; Lb=[0;0;0;0]; [x,g]=fmincon(‘fun5’,x0,A,B,Aeq,Beq,Lb)运行结果为: x = 0.0000 0.6667 1.6665 2.6668 g = 6.3333建立主程序null小结：用Matlab求解非线性规划问题，基本步骤：1. 首先建立M文件fun.m,定义目标函数 f（x）: function f=fun(x); f= f（x）;2.若约束条件中有非线性约束:g(x)或Ceq(x)=0,则建立M文件nonlcon.m定义函数g(x)与Ceq(x): function [g,Ceq]=nonlcon(X) g=... Ceq=...3. 建立主程序.并运行。最大最小化问题例如：在对策论中：在最不利的条件下，寻求最有利的策略； 在投资规划中要确定最大风险的最低限度； 在城市规划中，要确定急救中心的位置，使其到所有地点最大距离为最小。最大最小化问题null求解最大最小化问题的Matlab函数为fminimax.其调用格式如下： x=fminimax(F,x0,,A,b,Aeq,beq,lb,ub,nonlcon,options)或 [x,fval,maxfval,exitflag,output]=fminimax(…)其中：x返回最优解；fval返回解x处的目标函数值；maxfval返回解x处的最大函数值；exitflag描述计算的退出条件；output返回包含优化信息的输出参数。 null例：求解下列最大最小化问题： 首先编写一个M文件ff2.m，计算4个函数值。 function f=ff2(x) f(1)=3*x(1)^2+2*x(2)^2-12*x(1)+35; f(2)=5*x(1)*x(2)-4*x(2)+7; f(3)=x(1)^2+6*x(2); f(4)=4*x(1)^2+9*x(2)^2-12*x(1)*x(2)+20;null然后，输入初值x0=(1,1)，并调用优化函数进行计算 x0=[0 0]; [x,fval]=fminimax(@ff2,x0) 运行结果如下： x = 1.7637 0.5317 fval = 23.7331 9.5622 6.3010 23.7331null练习题： 设某城市有某种物品的10个需求点，第i个需求点Pi的坐标为(ai,bi),道路网与坐标轴平行，彼此正交。现打算建一个该物品的供应中心，且由于受到城市某些条件的限制，该供应中心只能设在x界于[5,8]，y界于[5,8]的范围之内。问该中心应建在何处为好?（即供应中心的位置到最远需求点的距离最小 ） Pi点的坐标为： 无约束最优化问题无约束最优化问题求一元函数fun在区间(x1,x2)上的最小值 X=fminbnd(fun,x1,x2) 或[x,fval]= fminbnd(fun,x1,x2)求多元无约束函数fun的最小值 [x,fval]= =fminunc(fun,x0) 　　x0为初值 [x,fval]= fminsearch(fun,x0) 注意：fminunc不是解决平方相加函数优化问 题的最好方法 null函数lsqnonlin专门解决非线性最小二乘问题：调用格式： x = lsqnonlin(fun,x0) x = lsqnonlin(fun,x0,lb,ub) x = lsqnonlin(fun,x0,lb,ub,options)线性最小二乘问题线性最小二乘问题lsqlin函数：用于解决线性最小二乘问题：调用格式： x = lsqlin(C,d,A,b) x = lsqlin(C,d,A,b,Aeq,beq) x = lsqlin(C,d,A,b,Aeq,beq,lb,ub) x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0) x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options)例. 求解下面非线性最小二乘问题例. 求解下面非线性最小二乘问题初始解向量为 解：(1) 建立函数文件example5.mfunction F = example5 (x) k = 1:10; F = 2 + 2*k-exp(k*x(1))-exp(k*x(2));x0 = [0.3 0.4]; [x,resnorm, residual] = lsqnonlin(@example5, x0)(2) 调用优化程序：null(3) 运行结果为 x = 0.2578 0.2578 resnorm = 124.3622 residual = Columns 1 through 7 1.4118 2.6505 3.6654 4.3906 4.7408 4.6057 3.8428 Columns 8 through 10 2.2672 -0.3600 -4.3482residual为解x处向量f(x)的值最优解最优值null无约束优化问题1、一元函数极小问题Min F（x） s.t. x1