1优化模型.ppt

1、最优化理论在建模中的应用,如投资的成本最小、利润最大问题，邮递员的投递路线最短问题，货物的运输调度问题，风险证券投资中的收益最大，风险最小问题.,（一）优化模型的数学描述,一 优化模型的一般意义,“受约束于”之意,（二）优化模型的分类,1.根据是否存在约束条件 有约束问题和无约束问题。 2.根据设计变量的性质 静态问题和动态问题。,3.根据目标函数和约束条件表达式的性质 线性规划，非线性规划，二次规划，多目标规划等。,（1）非线性规划 目标函数和约束条件中，至少有一个非线性函数。,（2）线性规划（LP） 目标函数和所有的约束条件都是设计变量 的线性函数。,（3）二次规划问题 目标函数为二次函数

2、，约束条件为线性约束,5. 根据变量具有确定值还是随机值 确定规划和随机规划。,4. 根据设计变量的允许值,整数规划（0-1规划）和实数规划。,（三）建立优化模型的一般步骤,(1) 确定目标函数（按照模型所需要解决的问题，用数学函数来描述目标） （2） 确定决策变量（目标的实现与那些变量有关，这里有主要变量和次要变量，在建模的初期可以进考虑主要变量对目标的影响，随后可以逐步增加变量的个数） （3） 确定约束条件（这是优化模型建模过程中最重要，也是最难的，在很多情况下，是否能够得到最优解，最优解是否合理，都是取决于约束条件的建立） （4） 模型求解（使用数学工具或数学软件求解） （5） 结果分析

3、（分析结果的合理性、稳定性、敏感程度等）,最优化理论,最优化理论与算法是数学的一个重要分支，它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优方案，这类问题很普遍，比如，工程设计中怎样选择设计参数，使设计方案既满足设计要求又能降低成本；在资源配置中，怎样分配有限资源使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产计划安排中，选择怎样的计划方案才能提高产值和利润；城建规划中，怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各个行业的发展；在人类生活的各个领域，诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题的解决，提供

4、理论基础和求解方法。,20世纪40年代以来，由于生产和科学研究的突飞猛进，特别是电子计算机日益广泛应用，使最优化问题的研究不仅成为一种迫切需要，而且有了求解的有力工具，例如lingo和lindo软件。最优化理论迅速发展成为一个新的学科，至今已经出现了线性规划、整数规划、非线性规划、几何规划、动态规划、网络流等许多分支，最优化理论与方法在实际应用中的作用越来越大。 下面我们就分成几块了解一下数学建模中经常用到的最优化理论的基础知识 -规划论中的线性规划、非线性规划问题。,1.线性规划的标准形式：,线性规划,问题一 ： 任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用

5、台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,两个引例,解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：,解答,问题二： 某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计

6、时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？,解 设需要一级和二级检验员的人数分别为x1、x2人, 则应付检验员的工资为：,因检验员错检而造成的损失为：,故目标函数为：,约束条件为：,线性规划模型：,解答,返 回,用MATLAB优化工具箱解线性规划,命令：x=linprog（c，A，b）,2、模型：min z=cX,命令：x=linprog（c，A，b，Aeq,beq）,注意：若没有不等式： 存在，则令A= ，b= .,命令：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，

7、Aeq,beq, VLB，VUB, X0）,注意：1 若没有等式约束: , 则令Aeq= , beq= . 2其中X0表示初始点,4、命令：x,fval=linprog() 返回最优解及处的目标函数值fval.,解 编写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=

8、; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To Matlab (xxgh1),解: 编写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),To Matlab (xxgh2),例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; A

9、eq=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),To Matlab (xxgh3),结果: x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000 fval =1.3800e+004 即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800。,例2 问题二的解答,问题,改写为：,编写M文件

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

11、不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解。,返 回,投资的收益和风险,二、基本假设和符号规定,三、模型的建立与分析,1.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n,4. 模型简化：,四、模型1的求解,由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：,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

12、=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）,计算结果：,五、 结果分析,返 回,4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长 很快。在这一点右

13、边，风险增加很大时，利润增长很缓慢，所以对于风险和 收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合， 大约是a*=0.6%，Q*=20% ，所对应投资方案为: 风险度 收益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212,3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。,2.当投资越分散时，投资者承担的风险越小，这与题意一致。即: 冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。,1.风险大，收益也大。,*非线性规

14、划的基本解法,*非线性规划的基本概念,非线性规划,返回,定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,非线性规划的基本概念,一般形式: （1） 其中 ， 是定义在 En 上的实值函数，简记:,其它情况: 求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式,用MATLAB软件求解,其输入格式如下: 1.x=quadprog(H,C,A,b); 2.x=quadprog(H,C,A,b,Aeq,beq); 3.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4.x=quadprog(H,C,A,b,

15、 Aeq,beq ,VLB,VUB,X0); 5.x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6.x,fval=quaprog(.); 7.x,fval,exitflag=quaprog(.); 8.x,fval,exitflag,output=quaprog(.);,1、二次规划,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20,MATLAB（youh1）,1、写成标准形式：,2、 输入命令： H=1 -1; -1 2; c=-2 ;-6;A=1

16、1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),3、运算结果为： x =0.6667 1.3333 z = -8.2222,s.t.,1. 首先建立M文件fun.m,定义目标函数F（X）: function f=fun(X); f=F(X);,2、一般非线性规划,其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：,3. 建立主程序.非线性规划求解的函数是fmincon,命令的基本格式

17、如下： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon) (5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options) (6) x,fval= fmincon(.) (7) x,fval,exitflag= fmincon(.) (8)x,fval,exitflag,output= fmin

18、con(.),输出极值点,M文件,迭代的初值,参数说明,变量上下限,注意： 1 fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。 2 fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。 3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关。,1、写成标准形式： s.t.,2x1+3x2 6 s.t x1

19、+4x2 5 x1,x2 0,例2,2、先建立M-文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,MATLAB(youh2),3、再建立主程序youh2.m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB),4、运算结果为： x = 0.7647 1.0588 fval = -2.0294,1先建立M文件 fun4.m,定义目标函数: function f=f

20、un4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0,例3,2再建立M文件mycon.m定义非线性约束： function g,ceq=mycon(x) g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;,3主程序youh3.m为: x0=-1;1; A=;b=; Aeq=1 1;beq=0; vlb=;vub=; x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb

21、,vub,mycon),MATLAB(youh3),3. 运算结果为： x = -1.2250 1.2250 fval = 1.8951,例4,1先建立M-文件fun.m定义目标函数: function f=fun(x); f=-2*x(1)-x(2);,2再建立M文件mycon2.m定义非线性约束： function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;,3. 主程序fxx.m为: x0=3;2.5; VLB=0 0;VUB=5 10; x,fval,exitflag,output =fmincon(fun,x0,VLB,VUB,my

22、con2),MATLAB(fxx(fun),4. 运算结果为: x = 4.0000 3.0000 fval =-11.0000 exitflag = 1 output = iterations: 4 funcCount: 17 stepsize: 1 algorithm: 1x44 char firstorderopt: cgiterations: ,返回主要内容,多目标规划问题及其数学模型,例5.1 某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。,问该企业应如何安排计划，使得计划期内的总利润收入为最大？,解：设甲、乙产品的产量分别

23、为x1，x2，建立线性规划模型：,其最优解为x14，x22，z14元,但企业的经营目标不仅仅是利润，而且要考虑多个方面，如： 力求使利润指标不低于12元； 考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例； C和D为贵重设备，严格禁止超时使用； 设备B必要时可以加班，但加班时间要控制；设备A即要求充分利用，又尽可能不加班。,要考虑上述多方面的目标，需要借助目标规划的方法。,线性规划模型存在的局限性： 1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。 2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。 3）线性规划中各个约束条件都处于同等重要地

24、位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。 4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。,目标规划怎样解决上述线性规划模型建模中的局限性？,1. 设置偏差变量，用来表明实际值同目标值之间的差异。,偏差变量用下列符号表示：,d+超出目标的偏差，称正偏差变量 d-未达到目标的偏差，称负偏差变量,正负偏差变量两者必有一个为0。 当实际值超出目标值时： d+0, d-=0; 当实际值未达到目标值时： d+=0, d-0; 当实际值同目标值恰好一致时： d+=0, d-=0; 故恒有d+d-=0,2. 统一处理目标和约束。,对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如C和D设备的使用限制。,对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。,1）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为： x1=x2。由于这个比例允许有偏差， 当x1x2时，出现正偏差d+，即： x1-d+ =x2或x1x2-d+ =0,正负偏差不可能同时出现，故总有： x1x2+d-d+ =0,若希望甲的产量不低于乙的产量，即不希望d-0,用目标约束可表为:,若希望甲的产量低于乙的产量，即不希望d0,用目标约束可表为:,若希望甲的产量恰好等于乙的产量，即不希望d0,也不希望d-0用目标约束可表为:,3）