《数学规划(5、5、6合).ppt》由会员分享，可在线阅读，更多相关《数学规划(5、5、6合).ppt（52页珍藏版）》请在三一办公上搜索。
1、数学规划,数学建模与数学实验,数信学院学院数学教研室,简单的优化模型往往是一元或者多元，无约束或者等式约束的最优化问题。而在很多实际问题中，所能够提供的决策变量取值受到很多因素的制约，这样就产生了一般的优化模型，统称为数学规划模型。按照数学规划模型的具体特征，可以将数学规划分为：线性规划模型（目标函数和约束条件都是线性函数的优化问题）；非线性规划模型（目标函数或者约束条件是非线性的函数）；整数规划（决策变量是整数值得规划问题）；多目标规划（具有多个目标函数的规划问题）；目标规划（具有不同优先级的目标和偏差的规划问题）；动态规划（求解多阶段决策问题的最优化方法）,第四章 数学规划,数学规划问题的
2、基本形式为：max(min)f(X)s.t.g(X)()0其中 X 为决策变量向量，f 为目标函数（单目标规划只有一个函数，多目标规划可以理解为一个向量函数的最优化问题），g(X)()0为约束条件，记 D=X|g(X)()0为可行集，因此规划的本质就是在可行集中选择使得目标最优的点。若D=R，则该问题为无条件约束问题，可以用微分法解决（有时仅有关于决策变量的非负约束也可以归结为该类型）；若D中的约束都是等式约束，则可以用Lagrange乘数法解决。但是在实际问题中，D的结构往往非常复杂，不能使用普通的微分方法解决，这时候必须借助于计算软件。,用MATLAB优化工具箱解线性规划,命令：x=lin
3、prog（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，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.
4、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=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To Matlab(xxgh1),投资的收益和风险,二、基本假设和符号规定,三、模型的建立与分析,1.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n,4.模型简化：,四、模型1的求解,由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们
5、从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=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;e
6、nd xlabel(a),ylabel(Q),To Matlab（xxgh5）,计算结果：,五、结果分析,返 回,4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长 很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和 收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:风险度 收益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212,3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承
7、受能力，选择该风险水平下的最优投资组合。,2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。,1.风险大，收益也大。,用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,Aeq,beq,VLB,VUB,X0);5.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6.x,f
8、val=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 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
9、.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,命令的基本格式如下：(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,VU
10、B)(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=fmincon(.),输出极值点,M文件,迭代的初值,参数说明,变量上下限,1、写成标准形式：s.t.,2x1+3x2 6 s.t x1+4x2 5 x1,x2 0,例2,2、先建立M-文件 fun3.m:function f=fun3(
11、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=fun4(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
12、.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,vub,mycon),MATLAB(youh3),3.运算结果为：x=-1.2250 1.2250 fval=1.8951,例4,1先建立M-文件fun.m定义目
13、标函数: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,mycon2),MATLAB(fxx(fun),4.运算结果为:x=4.0000 3.0000fval=-11.0000exitflag=1output=iterations:4 funcCount
14、:17 stepsize:1 algorithm:1x44 char firstorderopt:cgiterations:,返回,应用实例：供应与选址,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？,（一）、建
15、立模型,记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；从料场j向工地i的运送量为Xij。,当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。,（二）使用临时料场的情形,使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划模型为：,设X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6X12=X 7,X22=X 8,X32=X 9,
16、X42=X 10,X52=X 11,X62=X 12 编写程序gying1.m,MATLAB（gying1）,计算结果为：,x=3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval=136.2275,（三）改建两个新料场的情形,改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：,设 X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6 X12=X 7
17、,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 x1=X13,y1=X14,x2=X15,y2=X16,（1）先编写M文件liaoch.m定义目标函数。,MATLAB（liaoch）,(2)取初值为线性规划的计算结果及临时料场的坐标:x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;编写主程序gying2.m.,MATLAB（gying2）,(3)计算结果为：,x=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511
18、 7.1867fval=105.4626exitflag=1,(4)若修改主程序gying2.m,取初值为上面的计算结果:x0=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867,得结果为:x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852fval=103.4760exitflag=1,总的吨千米数比上面结果略优.,
19、(5)若再取刚得出的结果为初值,却计算不出最优解.,MATLAB（gying2）,MATLAB（gying2）,(6)若取初值为:x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499,则计算结果为:x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7.2500 7.7500fval=89.8835exitflag=1总的吨千米数89.8835比上面结果更好.,通过此例可看出fmincon函数在选取初值上的重要性.,MATLAB（gyin
20、g2）,返回,Matlab优化工具箱简介,1.MATLAB求解优化问题的主要函数,2.优化函数的输入变量,使用优化函数或优化工具箱中其它优化函数时,输入变量见下表:,3.优化函数的输出变量下表:,4控制参数options的设置,(3)MaxIter:允许进行迭代的最大次数,取值为正整数.,Options中常用的几个参数的名称、含义、取值如下:,(1)Display:显示水平.取值为off时,不显示输出;取值为iter时,显示每次迭代的信息;取值为final时,显示最终结果.默认值为final.,(2)MaxFunEvals:允许进行函数评价的最大次数,取值为正整数.,例：opts=optims
21、et(Display,iter,TolFun,1e-8)该语句创建一个称为opts的优化选项结构,其中显示参数设为iter,TolFun参数设为1e-8.,控制参数options可以通过函数optimset创建或修改。命令的格式如下：,(1)options=optimset(optimfun)创建一个含有所有参数名,并与优化函数optimfun相关的默认值的选项结构options.,（2）options=optimset(param1,value1,param2,value2,.)创建一个名称为options的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值.,(3)optio
22、ns=optimset(oldops,param1,value1,param2,value2,.)创建名称为oldops的参数的拷贝,用指定的参数值修改oldops中相应的参数.,返回,用Matlab解无约束优化问题,其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。,常用格式如下：（1）x=fminbnd(fun,x1,x2)（2）x=fminbnd(fun,x1,x2，options)（3）x，fval=fminbnd（.）（4）x，fval，exitflag=fmi
23、nbnd（.）（5）x，fval，exitflag，output=fminbnd（.）,To Matlab(wliti1),主程序为wliti1.m:f=2*exp(-x).*sin(x);fplot(f,0,8);%作图语句 xmin,ymin=fminbnd(f,0,8)f1=-2*exp(-x).*sin(x);xmax,ymax=fminbnd(f1,0,8),例2 对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？,解,先编写M文件fun0.m如下:function f=fun0(x)f=-(3-2*x).2*x;,主程序为wliti2
24、.m:x,fval=fminbnd(fun0,0,1.5);xmax=x fmax=-fval,运算结果为:xmax=0.5000,fmax=2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.,To Matlab(wliti2),命令格式为:（1）x=fminunc（fun,X0）；或x=fminsearch（fun,X0）（2）x=fminunc（fun,X0，options）；或x=fminsearch（fun,X0，options）（3）x，fval=fminunc（.）；或x，fval=fminsearch（.）（4）x，fval，exitflag=fm
25、inunc（.）；或x，fval，exitflag=fminsearch（5）x，fval，exitflag，output=fminunc（.）；或x，fval，exitflag，output=fminsearch（.）,2、多元函数无约束优化问题,标准型为：min F(X),3 fminunc为中型优化算法的步长一维搜索提供了两种算法，由options中参数LineSearchType控制：LineSearchType=quadcubic(缺省值)，混合的二次和三 次多项式插值；LineSearchType=cubicpoly，三次多项式插,使用fminunc和 fminsearch可能会得
26、到局部最优解.,说明:,fminsearch是用单纯形法寻优.fminunc的算法见以下几点说明：,1 fminunc为无约束优化提供了大型优化和中型优化算法。由options中的参数LargeScale控制：LargeScale=on(默认值),使用大型算法LargeScale=off(默认值),使用中型算法,2 fminunc为中型优化算法的搜索方向提供了4种算法，由 options中的参数HessUpdate控制：HessUpdate=bfgs（默认值），拟牛顿法的BFGS公式；HessUpdate=dfp，拟牛顿法的DFP公式；HessUpdate=steepdesc，最速下降法,例3
27、 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1),To Matlab(wliti3),1、编写M-文件 fun1.m:function f=fun1(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);2、输入M文件wliti3.m如下:x0=-1,1;x=fminunc(fun1,x0);y=fun1(x),3、运行结果:x=0.5000-1.0000 y=1.3029e-10,To Matlab(wliti31),To Matlab(wliti32),3.用fminsearch函数求解,To Matlab
28、(wliti41),输入命令:f=100*(x(2)-x(1)2)2+(1-x(1)2;x,fval,exitflag,output=fminsearch(f,-1.2 2),运行结果:x=1.0000 1.0000fval=1.9151e-010exitflag=1output=iterations:108 funcCount:202 algorithm:Nelder-Mead simplex direct search,4.用fminunc 函数,To Matlab(wliti44),(1)建立M-文件fun2.m function f=fun2(x)f=100*(x(2)-x(1)2)2+(1-x(1)2,(2)主程序wliti44.m,Rosenbrock函数不同算法的计算结果,可以看出，最速下降法的结果最差.因为最速下降法特别不适合于从一狭长通道到达最优解的情况.,1、求解下列线性规划问题,课内练习,3 Max f(x)=30 x1+450 x2 0.5x1+2x2+0.25x22800 x10,x20,课外练习,返回,
