非线性规划数学建模.ppt

,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版副标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数学实验之,非线性规划,实验目的,引 例,基本概念,算法概述,软件求解,范 例,布置实验,结 束,课堂延伸,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,非线性规划数学建模,非线性规划数学建模,1952年美国经济学家Markowitz用概率统计的方法，将收益视作随机变量，用它的方差作为风险的指标，建立了完整的组合投资理论，于19 90年获得诺贝尔经济学奖。,引 例,组合投资,问题的描述:设有8种投资选择:5支股票,2种债券,黄金.投资者收集到这些投资项目的年收益率的历史数据(见下页,表,),投资者应如何分配他的投资资金,即需要确定这8种投资的最佳投资分配比例.,引 例,x,1,+x,2,+x,n,=1,x,i,0,问题的分析:设投资的期限是一年，不妨设投资总数为1个单位，用于第i项投资的资金比例为,x,i,X=(x,1,x,2,x,n,)称为投资组合向量.显然有,项目,年份,债券1,债券2,股票1,股票2,股票3,股票4,股票5,黄金,1973,1.075,0.942,0.852,0.815,0.698,1.023,0.851,1.677,1974,1.084,1.020,0.735,0.716,0.662,1.002,0.768,1.722,1975,1.061,1.056,1.371,1.385,1.318,1.123,1.354,0.760,1976,1.052,1.175,1.236,1.266,1.280,1.156,1.025,0.960,1977,1.055,1.002,0.926,0.974,1.093,1.030,1.181,1.200,1978,1.077,0.982,1.064,1.093,1.146,1.012,1.326,1.295,1979,1.109,0.978,1.184,1.256,1.307,1.023,1.048,2.212,1980,1.127,0.947,1.323,1.337,1.367,1.031,1.226,1.296,1981,1.156,1.003,0.949,0.963,0.990,1.073,0.977,0.688,1982,1.117,1.465,1.215,1.187,1.213,1.311,0.981,1.084,1983,1.092,0.985,1.224,1.235,1.217,1.080,1.237,0.872,1984,1.103,1.159,1.061,1.030,0.903,1.150,1.074,0.825,1985,1.080,1.366,1.316,1.326,1.333,1.213,1.562,1.006,1986,1.063,1.309,1.186,1.161,1.086,1.156,1.694,1.216,1987,1.061,0.925,1.052,1.023,0.959,1.023,1.246,1.244,1988,1.071,1.086,1.165,1.179,1.165,1.076,1.283,0.861,1989,1.087,1.212,1.316,1.292,1.204,1.142,1.105,0.977,1990,1.080,1.054,0.968,0.938,0.830,1.083,0.766,0.922,1991,1.057,1.193,1.304,1.342,1.594,1.161,1.121,0.958,1992,1.036,1.079,1.076,1.090,1.174,1.076,0.878,0.926,1993,1.031,1.217,1.100,1.113,1.162,1.110,1.326,1.146,1994,1.045,0.889,1.012,0.999,0.968,0.965,1.078,0.990,其中:,r,jk,代表第j种投资在第k年的收益率.,Markowitz,风险的定义:收益的波动程度,可用样本方差(历史方差)来度量,为,引 例,收益和风险,每个投资项目的收益率可以看成一个随机变量,其均值可以用样本均值(历史均值)来近似.因此,预计第j种投资的平均收益率为,投资组合X=(x,1,x,2,x,n,)在第 k年的收益率为:,投资组合X=(x,1,x,2,x,n,)的风险为:,投资组合X=(x,1,x,2,x,n,)的平均收益率为:,引 例,双目标:最大化利润,最小化风险,s.t.x,1,+x,2,+x,8,=1,x,i,0,i=1,2,8,组合投资,引 例,化为单目标:,模型1:控制风险最大化收益,模型2:固定赢利，最小化风险,化为单目标:,模型3:对收益和风险加权平均(0,1),组合投资,引 例,3个模型均为非线性规划模型。,投资选择问题,某公司在一个时期内可用于投资的总资本为b万元,可供选择的项目有n个。假定对第i个项目的投资总额为,a,i,万元，收益总额为,c,i,万元。,问如何确定投资方案，使总的投资利润率(,收益占总投资的比例,),达最高？,设决策变量为：,引 例,对第i项目进行投资,不对第i项目投资,数学模型,非线性整数规划问题。,收益占总投资的比例,引 例,b:总资本,a,i:,第i个项目的投资额,c,i,:,第i个项目的收益,基本概念,例如：,非线性规划模型的一般形式,特殊情形,1）无约束,2）二次规划,基本概念,多峰函数，,存在,局部最大(小)和整体最大(小),函数曲面图形,图形解释,基本概念,fgoalattain 多目标规划,fminbnd 有界标量非线性优化问题,fmincon 约束非线性极小化,fminimax 极小极大最优化,fminsearch,fminunc 无约束非线性最优化,fseminf 半无限极小化,linprog 线性规划,quadprog 二次规划,MATLAB软件求解,优化工具箱主要命令,无约束非线性规划情形,MATLAB软件求解,标准形式:Min F(X),MATLAB求解步骤,首先建立一个函数M文件，如fun.m,调用格式：,X,fval,=,fminunc,(fun,X0,options),或,X,fval,=,fminsearch,(fun,X0,options),1.函数,fminunc、fminsearch,的具体用法,例1 Rosenbrock函数,已知初始点（-1.9，2）。试分析最优解是否与初始点有关？,无约束非线性规划情形,MATLAB软件求解,1）function f=fun1(x),f=100*(x(2)-x(1)2)2+(1-x(1)2;,1.函数,fminunc、fminsearch,的具体用法,无约束非线性规划情形,MATLAB软件求解,2）x0=-1.9,2;,options=optimset(display,iter),x,fval=,fminunc,(fun1,x0,options,),计算结果：,x=0.9999 0.9997;fval=1.9047e-008,若想结果更精确，将options修改为,options=optimset(display,iter,tolfun,1e-10);,1.函数,fminunc、fminsearch,的具体用法,1.函数,fminunc、fminsearch,的具体用法,无约束非线性规划情形,MATLAB软件求解,计算结果：,x=,5.1840 26.8991,;fval=,17.5675,未能得到最优解,说明初始解的选择很关键,一般选择与最优解尽量接近的点.,若改变初始解,比如:取x0=10,10,标准模型:,2.函数,fmincon,的具体用法,约束非线性规划情形,MATLAB软件求解,Min f(X),s.t.G1(X),0,G2(X)=0 (非线性约束),AX b,Aeq.X=beq,(线性约束),lb,X ub,调用格式:,x,fval=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,con),2.函数,fmincon,的具体用法,约束非线性规划情形,MATLAB软件求解,建立m文件函数fun.m,function f=fun(x),f=f(x);,为函数fmincon的其余输入变量赋值，然后调用该函数求出约束规划问题的解。,建立m文件函数nonlcon.m,function c,ceq=nonlcon(x),c=G1(x);ceq=G2(x),2.函数,fmincon,的具体用法,约束非线性规划情形,MATLAB软件求解,例：求解以下约束非线性规划：,Max,f,(,x,),=x,1,x,2,s.t.2(,x,1,+,x,2,),x,3,500,x,3,2,x,j,0，j=1,2,function f=fun2(x),f=-x(1)*x(2);,MATLAB程序,function c,ceq=nlcon(x),c=(x(1)+x(2)*x(3)-250;,ceq=;,2.函数,fmincon,的具体用法,约束非线性规划情形,MATLAB软件求解,x0=10 10 2;,L=0 0 2;,x,fval=fmincon(fun2,x0,L,nlcon),计算结果:,x=62.5000 62.5000 2.0000,fval=-3.9063e+003,max,f,(,x,),=x,1,2,+,x,2,2,-,x,1,x,2,-2,x,1,-5,x,2,s.t.-(,x,1,1),2,+,x,2,0,2,x,1,-3,x,2,+60,x,0,=0,1,例2,转化成标准形,min,f,(,x,),=-x,1,2,-,x,2,2,+,x,1,x,2,+2,x,1,+5,x,2,s.t.(,x,1,1),2,-,x,2,0,-2,x,1,+3,x,2,60,x,0,=0,1,2.函数,fmincon,的具体用法,约束非线性规划情形,MATLAB软件求解,function f=fun22(x),f=-x(1)2-x(2)2+x(1)*x(2)+2*x(1)+5*x(2);,function G,Geq=cont2(x),G=(x(1)-1)2-x(2);,Geq=;,x0=0 1;,A=-2,3;b=6;,Aeq=;beq=;,lb=;ub=;,x,fval=fmincon(fun22,x0,A,b,Aeq,beq,lb,ub,cont2),x=1.0e+008*-0.0006 -2.7649,fval=-7.6432e+016,MATLAB程序:,计算结果:,3、使用,quadprog,求解二次规划问题,二次规划,标准,模型,调用格式:,x,fval=quadprog(H,c,A,b,Aeq,beq,L,U,x0),MATLAB软件求解,例4,写成标准模型,MATLAB软件求解,beq,=2,H=2,-2;-2,4;,c=-4,-12;,A=-1,2;2,1;,b=2,3;,Aeq=1 1;beq=2;,x,fval=quadprog(H,c,A,b,Aeq,beq),计算结果：,x=0.6667 1.3333，f=-16.4444,MATLAB软件求解,MATLAB程序:,小结,无约束非线性规划 Min F(X),调用格式:X,fval=fminunc(F,X0,options),或 X,fval=fminsearch(F,X0,options),二次规划 Min 0.5*X,T,HX+C,T,X,s.t.AX b,AeqX=beq,L X U,调用格式：X,fval=quadprog(H,c,A,b),MATLAB软件求解,约束非线性规划,Min F(X),s.t.G(X)0,Geq=0,AX b,Aeq.X=beq,l,X u,调用格式：,X,fval=fmincon(F,X0,A,b,Aeq,beq,l,u,GGeq),MATLAB软件求解,小结,供应与选址,6个建筑工地水泥的日用量分别为3,5,4,7,6,11,(吨),两个临时料场A,B，日储量各有20吨。假设从料场到工地均有直线道路相连.,范 例,供应与选址,问题1：试制定每天A、B 两料场向各工地供应水泥的供应计划，使总的吨千米数最小。,范 例,问题2：为进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量仍各为20吨，问应建在何处，节省的吨千米数有多大？,建立规划模型,记工地的位置为(a,i,b,i,)，水泥日用量为d,i,i=1,6,料场位置为(x,j,y,j,),日储量为r,j,j=1,2；从料场j向工地i的运送量为z,ij,。,（工地日用量）,（料场日储量）,供应与选址,范 例,问题1的MATLAB程序：,使用临时料场，即料场位置(x,j,y,j,)为已知,决策变量为z,ij,，上述模型为线性规划模型。记决策变量Z=z,11,z,21,z,61,z,12,z,62,a0=1.25 8.75 0.5 5.75 3 7.25;,b0=1.25 0.75 4.75 5 6.5 7.75;,c1=sqrt(5-a0).2+(1-b0).2);,c2=sqrt(2-a0).2+(7-b0).2);c=c1,c2;,A=ones(1,6),zeros(1,6);zeros(1,6),ones(1,6);b=20;20;,Aeq=eye(6),eye(6);beq=3 5 4 7 6 11;,L=zeros(1,12);,Z,val=linprog(c,A,b,Aeq,beq,L),最优目标值f=136.2275（吨千米）,料场A,B运往各工地的水泥的日运量分别为,i,1,2,3,4,5,6,z,i1,(料场A),3,5,0,7,0,1,z,i2,(料场B),0,0,4,0,6,10,供应与选址,范 例,问题1的求解结果,问题2的求解,要为新建料场选址,料场位置(x,j,y,j,)为未知时,决策变量为z,ij,，x,j,y,j,，模型为非线性规划模型。,（工地日用量）,（料场日储量）,供应与选址,范 例,目标函数的函数M 文件:,function f=liaocmb(x),a0=1.25 8.75 0.5 5.75 3 7.25;,b0=1.25 0.75 4.75 5 6.5 7.75;,c1=sqrt(x(13)-a0).2+(x(14)-b0).2);,c2=sqrt(x(15)-a0).2+(x(16)-b0).2);,c=c1,c2;,f=c*x(1:12,1);,供应与选址,范 例,问题2的求解,function c,ceq=liaocys(x),A=ones(1,6),zeros(1,6);zeros(1,6),ones(1,6);,b=20;20;,Aeq=eye(6),eye(6);beq=3 5 4 7 6 11;,c=A*x(1:12,1)-b;,ceq=Aeq*x(1:12,1)-beq;,约束条件的函数M 文件:,供应与选址,范 例,问题2的求解,clear,L=zeros(16,1);,x0=zeros(1,12),5,1,2,7;,options=optimset(largescale,off,display,iter,MaxFunEval,2000);,x,val,=fmincon(liaocmb,x0,L,liaocys,options),解非线性规划的主程序,供应与选址,范 例,问题2的求解,i,1,2,3,4,5,6,z,i1,(料场A),3,0,4,7,6,0,z,i2,(料场B),0,5,0,0,0,11,计算结果：最优目标值f=85.2660（吨千米）,新料场位置的改变，目标值比原来减少了50.9615吨千米。,新料场A,B的坐标为（3.2550，5.6522）和（7.2500，7.7500）。,新料场A,B运往各工地的水泥的日运量分别为,问题2的求解,优化结果是新料场应建在用量最大的工地旁边，你预先估计到这个结果了吗？,供应与,选址,范 例,function c,ceq=liaocys(x),函数fminunc、fminsearch的具体用法,无约束非线性规划 Min F(X),2+(x(14)-b0).,quadprog 二次规划,lb X ub,quadprog 二次规划,c2=sqrt(2-a0).,c=G1(x);ceq=G2(x),无约束非线性规划 Min F(X),ci:第i个项目的收益,函数fminunc、fminsearch的具体用法,建立m文件函数fun.,AeqX=beq,f=-x(1)2-x(2)2+x(1)*x(2)+2*x(1)+5*x(2);,函数fmincon的具体用法,x0=zeros(1,12),5,1,2,7;,已知初始点（-1.,新料场位置的改变，目标值比原来减少了50.,Aeq=1 1;beq=2;,