Matlab PPT 第七章最优化计算方法

1、第七章第七章 最优化计算方法最优化计算方法一、实验目的：一、实验目的：第一节第一节 线性方程组的应用线性方程组的应用1、了解线性规划问题及可行解、最优解的概念、了解线性规划问题及可行解、最优解的概念 ； 2、掌握、掌握Matlab软件关于求解线性规划的语句和方法。软件关于求解线性规划的语句和方法。二、实验原理和方法：二、实验原理和方法：在生活实践中，很多重要的实际问题都是线性的（至少能在生活实践中，很多重要的实际问题都是线性的（至少能够用线性函数很好的近似表示），所以我们一般把这些问够用线性函数很好的近似表示），所以我们一般把这些问题化为线性的目标函数和约束条件进行分析，通常将目标题化为线性的

2、目标函数和约束条件进行分析，通常将目标函数和约束都是线性表达式的规划问题称为线性规划函数和约束都是线性表达式的规划问题称为线性规划 。它的一般形式是：它的一般形式是： )n, 2 , 1i (0 xbxaxaxabxaxaxabxaxaxa. t . sxcxcxcfminimnmn22m11m2nn22221211nn1212111nn2211也可以用矩阵形式来表示：也可以用矩阵形式来表示：0 x,bAx. t . sxcfminT线性规划的可行解是满足约束条件的解；线性规划线性规划的可行解是满足约束条件的解；线性规划的最优解是使目标函数达到最优的可行解。的最优解是使目标函数达到最优的可行解

3、。线性规划关于解的情况可以是：线性规划关于解的情况可以是：1、无可行解，即不存在满足约束条件的解；、无可行解，即不存在满足约束条件的解；2、有唯一最优解，即在可行解中有唯一的最有解；、有唯一最优解，即在可行解中有唯一的最有解；4、有可行解，但由于目标函数值无界而无最优解。、有可行解，但由于目标函数值无界而无最优解。3、有无穷最优解，即在可行解中有无穷个解都可使目、有无穷最优解，即在可行解中有无穷个解都可使目 标函数达到最优；标函数达到最优； 一般求解线性规划的常用方法是单纯形法和改进一般求解线性规划的常用方法是单纯形法和改进的单纯形法，这类方法的基本思路是先求得一个可行的单纯形法，这类方法的基

4、本思路是先求得一个可行解，检验是否为最优解；若不是，可用迭代的方法找解，检验是否为最优解；若不是，可用迭代的方法找到另一个更优的可行解，经过有限次迭代后，可以找到另一个更优的可行解，经过有限次迭代后，可以找到可行解中的最优解或者判定无最优解。到可行解中的最优解或者判定无最优解。 三、内容与步骤：三、内容与步骤：在在Matlab优化工具箱中，优化工具箱中，linprog函数是使用单纯形法求解函数是使用单纯形法求解下述线性规划问题的函数。下述线性规划问题的函数。vubxvlbbeqaeqxbAxtsxcfT;,.min它的命令格式为：它的命令格式为：)0,(,),(,xvubvlbbeqaeqbA

5、clinprogfvalxvubvlbbeqaeqbAclinprogfvalx其中：其中：A为约束条件矩阵，为约束条件矩阵，b,c分别为目标函数的系数向量和分别为目标函数的系数向量和约束条件中最右边的数值向量；也可设置解向量的上界约束条件中最右边的数值向量；也可设置解向量的上界vlb和和下界下界vub，即解向量必须满足，即解向量必须满足vlb=x=vub；还可预先设置；还可预先设置初始解向量初始解向量x0。如没有不等式，而只有等式时，如没有不等式，而只有等式时，A= ,b= ;输出的结果：输出的结果：x表示最优解向量；表示最优解向量；fval表示最优值。表示最优值。【例【例 1】 求解线性规

6、划问题：求解线性规划问题： 3 , 2 , 1i , 0 x1xx23x2xx411xx2x. t . sxxx3fmaxi31321321321解：考虑到解：考虑到linprog函数只解决形如函数只解决形如的线性规划。所以先要将线性规划的线性规划。所以先要将线性规划变为如下形式：变为如下形式：0;,. .minxbeqaeqxbAxtsxcfT3 ,2, 1i ,0 x3x2xx411xx2x1xx2. t . sxxx3fmini32132131321然后建立然后建立M文件如下：文件如下：c=-3;1;1;A=1 -2 1;4 -1 -2;b=11;-3;aeq=2 0 -1;beq=-1

7、;vlb=0;0;0;x,fval=linprog(c,A,b,aeq,beq,vlb) Matlab程序：程序： ch701.m以以ch701作为文件名保存此作为文件名保存此M文件后，在命令窗口文件后，在命令窗口输入输入ch701后即可得到结果：后即可得到结果：x = 4.0000 1.0000 9.0000同时返回同时返回fval=-2对应到原来的线性规划中即知目标函数的最大值为对应到原来的线性规划中即知目标函数的最大值为2，此时，此时x1=4,x2=1,x3=9。 第二节第二节 无约束规划计算方法无约束规划计算方法一、实验目的一、实验目的1、了解无约束规划问题的求解原理与方法、了解无约束

8、规划问题的求解原理与方法 ； 2、会用、会用Matlab软件求解无约束规划问题。软件求解无约束规划问题。 二、实验原理和方法二、实验原理和方法无约束规划问题的解法一般按目标函数的形式分为两大类：无约束规划问题的解法一般按目标函数的形式分为两大类：一类是一元函数的一维搜索法，如黄金分割法、插值法等；一类是一元函数的一维搜索法，如黄金分割法、插值法等；另一类是求解多元函数的下降迭代法。另一类是求解多元函数的下降迭代法。迭代的基本思想和步骤大致可分为以下四步：迭代的基本思想和步骤大致可分为以下四步：继续迭代返回否则，令如果是，则结束运算；优解。是否满足精度要求的最检验新得到的点由此得到下一个点使得方

9、向选取适当的步长出发，沿由）的值时下降的；目标函数使得沿着这个方向的后，选取一个搜索方向得到并令选取初始点)2(, 1)4)()(,3)(,)2; 0,) 1110kkxPxxxfPxfPxxfPxkxkkkkkkkkkkkkkk三、实验内容与步骤三、实验内容与步骤在在Matlab软件中，求解无约束规划的常用命令是：软件中，求解无约束规划的常用命令是： x=fminunc(fun,x0) 其中，其中，fun函数应预先定义到函数应预先定义到M文件中，并设置初始文件中，并设置初始解向量为解向量为x0。 【例【例 2】求解求解1212221x2xxx21x23)x(fmin取取T)0()4 , 2(

10、x解：首先建立函数文件解：首先建立函数文件fun702.m) 1 (2)2() 1 (2)2(2/12)1 (2/3)(702xxxxxfxfunffunction 以以fun702为文件名保存此函数文件。为文件名保存此函数文件。 在命令窗口输入：在命令窗口输入： x0=-2;4;x=fminunc(fun702,x0)结果显示：结果显示： f = -1.0000 x = 1.0000 1.0000即极小值为即极小值为-1，是，是x1=1,x2=1时取得。时取得。Matlab程序：程序： ch702.m【例【例 3】 解非线性方程组解非线性方程组01)5 . 0()2(012221221xxx

11、x解：解此非线性方程组等价于求解无约束非线性规划问题：解：解此非线性方程组等价于求解无约束非线性规划问题： 222212221) 1)5 . 0()2() 1(minxxxx然后建立函数文件然后建立函数文件fun703.m 2)12)5 . 0)2(2)2) 1 (2)1)2(2)1 ()(703xxxxfxfunffunction在命令窗口输入：在命令窗口输入： x0=0;0;x=fminunc(fun703,x0)结果显示：结果显示： f =5.2979e-011 x =1.0673 0.1392则非线性方程组的解为则非线性方程组的解为x1=1.0673,x2=0.1392。 Matlab

12、程序：程序： ch703.m第三节第三节 约束非线性规划计算方法约束非线性规划计算方法 一、实验目的一、实验目的1、了解约束非线性规划问题的求解原理与方法；、了解约束非线性规划问题的求解原理与方法； 2、会用、会用Matlab软件求解约束非线性规划问题。软件求解约束非线性规划问题。 二、实验原理和方法二、实验原理和方法对于约束非线性规划，随着目标函数和约束条件的不同，对于约束非线性规划，随着目标函数和约束条件的不同，解法也不同，一般来说，有两类方法：解法也不同，一般来说，有两类方法：（1）、将约束问题化为无约束问题的求解方法；）、将约束问题化为无约束问题的求解方法；（2）、用线性规划来逼近非线

13、性规划；）、用线性规划来逼近非线性规划； 三、实验内容与步骤三、实验内容与步骤 约束非线性规划的一般形式为：约束非线性规划的一般形式为： )(minxfxubxlbxceqxgbeqxaeqbAxt s）（非线性约束线性约束0)(, 0)()(*,.其中，其中，f(x)为多元实值函数为多元实值函数;g(x)为向量函数为向量函数,并且并且f(x),g(x)中至中至少有一个函数是非线性函数的（否则成为线性规划问题）。少有一个函数是非线性函数的（否则成为线性规划问题）。x=fmincon(fun,x0,A,b)x=fmincon(fun,x0,A,b,Aeq,beq)x=fmincon(fun,x0

14、,A,b,Aeq,beq,lb,ub)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)在在Matlab优化工具箱中，优化工具箱中，fmincon函数是用函数是用SQP算法来算法来解决一般的约束非线性规划的函数，它的命令格式为：解决一般的约束非线性规划的函数，它的命令格式为：【例【例 4】 求解约束非线性规划：求解约束非线性规划： 3. .)3(max222222111xetsxexexxx(初值为初值为1;1)解解: :首先建立一个首先建立一个m文件文件fun7041.mfunctiony=fun7041(x)y=-exp(x(1)*x(2)2*(3-ex

15、p(x(1)-x(2)2);存储为存储为fun7041.m首先将问题转化为首先将问题转化为matlab要求的格式要求的格式;即求出即求出fun,A,b,Aeq,Beq,X0,Lb,Ub然后建立一个然后建立一个m文件文件fun7042.mfunctionc,cep=fun7042(x)c=;%c为非线性不等式为非线性不等式,且为且为c=0cep=exp(x(1)+x(2)2-3;%cep为非线性等式为非线性等式然后存储为然后存储为fun7042.m最后在命令窗口中输入：A=;b=;Aeq=;Beq=;Lb=;Ub=;x,f=fmincon(fun7041,1;1,fun7042)-f因题目中有非

16、线性约束条件，所以建立非线性约束因题目中有非线性约束条件，所以建立非线性约束m-文件。文件。Matlab程序：程序： ch704.m结果为:x = 0.8852 0.7592f = 6.2043e-016ans= - 6.2043e-016最后的结果为: - 6.2043e-016【例【例 5】 求解约束非线性规划：求解约束非线性规划： 1 ; 1 ; 1 ; 1 0102335. .)4()3()2() 1(min4321432124232221初值为ixxxxxxxxxtsxxxx解：首先建立一个解：首先建立一个m文件文件fun705.mfunctiony=fun705(x)y=(x(1)

17、-1)2+(x(2)-2)2+(x(3)-3)2+(x(4)-4)2;存储为存储为fun705.m文件文件.x0=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(fun705,x0,A,B,Aeq,Beq,Lb)答案为:x = 0.0000 0.6667 1.6665 2.6668g = 6.3333Matlab程序：程序： ch705.m非现性规划的基本概念非现性规划的基本概念定义定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题非线性规划问题 一般形式一般形式: （1）

18、其中 ， 是定义在 En 上的实值函数，简记: Xfmin .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf 其它情况其它情况: 求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式用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,

19、C,A,b, 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、二次规划、二次规划标准型为： Min Z= 21XTHX+cTX s.t. AX=b beqXAeq VLBXVUB 例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10

20、, x20 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.6667 1.3333 z = -8.2222212121622 11- 1 ),(minxxxxxxzT212100222 11 1 xxxxs.t. 1. 首先建立M文件fun.m,定义目标函数F（X）:function f=fun(X);f=F(X);2、一般非线性规划、一般非线

21、性规划标准型为： min F(X) s.t AX=b beqXAeq G(X)0 Ceq(X)=0 VLBXVUB 其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：2. 若约束条件中有非线性约束:G(X)0或Ceq(X)=0,则建立M文件nonlcon.m定义函数G(X)与Ceq(X): function G,Ceq=nonlcon(X) G=. Ceq=. 3. 建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下： (1) x=fmincon(fun,X0,A,b)

22、(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= fmincon(.)输出极值点M文件迭代的初值参数说明变量上下限注意：

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

24、1212minxxxxf 2x1+3x2 6 s.t x1+4x2 5 x1,x2 0例例22、先建立先建立M-文件文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)23、再建立主程序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.02941先建立先建立M文件文件

25、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);) 12424()(22122211xxxxxexfx x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例例32再建立再建立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;

26、1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon)3. 运算结果为运算结果为： x=-1.22501.2250fval=1.8951 例4 100 , 50 07 025 . .2min 21222122221121xxxxXgxxXgtsxxXf1先建立先建立M-文件文件fun.m定义目标函数定义目标函数: function f=fun(x); f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2.m定义非线性约束：定义非线性约束：functiong,ceq=myco

27、n2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;3.主程序主程序fxx.m为为:x0=3;2.5;VLB=00;VUB=510;x,fval,exitflag,output=fmincon(fun,x0,VLB,VUB,mycon2)4.运算结果为运算结果为:x=4.00003.0000fval=-11.0000exitflag=1output=iterations:4funcCount:17stepsize:1algorithm:1x44charfirstorderopt:cgiterations:应用实例：应用实例：供应与选址供应与选址 某公司有6个建筑工地要开工，

28、每个工地的位置（用平面坐标系a，b表示，距离单位：千米 ）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。 （1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。 （2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？工地位置（a，b）及水泥日用量 d 1 2 3 4 5 6 a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.25 d 3 5 4

29、7 6 11 （一）、建立模型（一）、建立模型 记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为di，i=1,6;料场位置为料场位置为(xj，yj)，日储量为，日储量为ej，j=1,2；从料场；从料场j向工地向工地i的运送量为的运送量为Xij。目标函数为：216122)()(minjiijijijbyaxXf 约束条件为：2 , 1 ,6 , 2 , 1 ,6121jeXidXjiijijij 当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。（二）使用临时料场的情形（二）使用临时料场的情形 使用两个临时料场A(5,1)，B(2,7).求从

30、料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题. 线性规划模型为：2161),(minjiijXjiaaf2 , 1 , 6 , 2 , 1 , s.t.6121jeXidXjiijijij其中 22)()(),(ijijbyaxjiaa，i=1,2,6,j=1,2,为常数。 设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, X42= X 10, X52= X 11, X62= X 12 编写程

31、序gying1.m计算结果为：计算结果为：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即由料场 A、B 向 6 个工地运料方案为： 1 2 3 4 5 6 料场 A 3 5 0 7 0 1 料场 B 0 0 4 0 6 10 总的吨千米数为136.2275。 （三）改建两个新料场的情形（三）改建两个新料场的情形 改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规

32、划模型为：216122)()(minjiijijijbyaxXf2 , 1 , 6 , 2 , 1 , . .6121jeXidXtsjiijijij设 X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, 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定义目标函数。(2) 取初值为线性规划的计算结果及临时料场的坐标: x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;编写主程序gying2.m.(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 7.1867fval = 105.4626exitf