线性规划及非线性规划算法以及软件求解-课件.ppt

1、最优化方法最优化方法线性规划问题非线性规划问题非约束优化问题约束优化问题优化问题的分类优化问题的分类p基本概念p最优性条件p线性规划问题的求解p非线性规划问题的求解最优化问题的数学模型最优化问题的数学模型最优化问题的数学模型最优化问题的数学模型(*)最优化问题的基本概念最优化问题的基本概念全局极小(唯一极小）2122212121322)(xxxxxxxxf最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念多局部极小298.0f0f298.0f2221614221605.12),(11xxxxxxxxf最优化问题的基本概念最优

2、化问题的基本概念最优化问题的基本概念最优化问题的基本概念预备知识预备知识-多元函数的导数多元函数的导数一元函数有一阶导数，二阶导数（假设存在），一元函数有一阶导数，二阶导数（假设存在），多元函数的一阶导数、二阶导数（假设存在）又多元函数的一阶导数、二阶导数（假设存在）又是什么呢？是什么呢？Questions多元函数的一阶导数多元函数的一阶导数-梯度梯度多元函数的一阶导数多元函数的一阶导数-梯度梯度梯梯度度的的几几何何意意义义多元函数的一阶导数多元函数的一阶导数-梯度梯度梯梯度度的的几几何何意意义义多元函数的一阶导数多元函数的一阶导数-梯度梯度Definition 若若x*满足满足 ，则称则称x

3、*为稳定点（平稳点）。为稳定点（平稳点）。Remark多元函数的二阶导数多元函数的二阶导数-Hesse矩阵矩阵Jacobian矩阵Jacobian矩阵Jacobian矩阵Jacobian矩阵p基本概念p最优性条件p线性规划问题的求解p非线性规划问题的求解最优性条件最优性条件无约束最优化问题的最优性条件 （凸函数极值的最优性条件）约束最优化问题的最优性条件无约束优化问题的一阶必要性条件无约束优化问题的一阶必要性条件（*）约束优化问题的一阶必要性约束优化问题的一阶必要性 条件条件Kuhn-Tucker 条件条件Kuhn-Tucker 条件条件等式和不等式约束下的等式和不等式约束下的Kuhn-Tuc

4、ker 条件条件等式和不等式约束下的等式和不等式约束下的Kuhn-Tucker 条件条件Lagrange函数函数 vs 广义广义Lagrange函数函数（*）等式和不等式约束下的等式和不等式约束下的Kuhn-Tucker 条件条件等式和不等式约束下的等式和不等式约束下的Kuhn-Tucker 条件条件p基本概念p最优性条件p线性规划问题的求解p非线性规划问题的求解 数学模型数学模型 如何求解（单纯形算法）如何求解（单纯形算法）灵敏度分析灵敏度分析 软件实现（软件实现（LINGO、MATLAB）线性规划及其软件实现线性规划及其软件实现线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划

5、的数学模型 0,124 614 8 2 s.t.00032max54321524132154321xxxxxxxxxxxxxxxxxZ目标函数约束条件决策变量最优值最优解.14,2,4*2*1zxx线性规划的数学模型线性规划的数学模型.0,.,)(a.aa .)(a.aa )(a.aa s.t.max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxxxbxxxbxxxxcxcxcZ目标函数约束条件决策变量一般形式一般形式线性规划的数学模型线性规划的数学模型1 12211 11221121 1222221 12212min.s.t.aa.a aa

6、.a .aa.a ,.nnnnnnmmmnnmZc xc xc xxxxbxxxbxxxbx x（m ax）,0.nx 标准形式标准形式线性规划的数学模型线性规划的数学模型min(max)s.t.z CXAXbX0标准形式标准形式如果矩阵A的秩小于m,怎么办？如果（增广）矩阵的秩小于m，则行向量组线性相关，可以通过方程组的的初等变换把相关的方程组去掉，仅剩下线性无关的行向量组非标准形式化为标准形式Example非标准形式化为标准形式非标准形式化为标准形式0,282.35min2122121xxxxxtsxxZ单单纯纯形形算算法法单单纯纯形形算算法法 解：10100121A 1021B1 423

7、21282xxxxx 基解T)0,0,2,4(X 是基可行解 1001B2 24321228xxxxx 基解T)2,0,0,8(X 是基可行解 0112B3 42132282xxxxx 基解T)0,4,2,0(X 是基可行解 1102B4 28242312xxxxx 基解T)2,0,4,0(X 不是基可行解 1001B5 24213228xxxxx 基解T)2,8,0,0(X 是基可行解 基基解解基基可可行行解解线性规划解的定义Remark最优解一定可在极点处取得，而极点和基可行解是一最优解一定可在极点处取得，而极点和基可行解是一一对应的，所以求线性规划问题最优解的思路一对应的，所以求线性规划

8、问题最优解的思路仅在基可行解里寻找最优解！仅在基可行解里寻找最优解！线性规划解的定义Questions为什么不在极点里找，为什么不在极点里找，而在基可行解里找呢？而在基可行解里找呢？单纯形算法线性规划问题的最优解一定可以在基可行解处线性规划问题的最优解一定可以在基可行解处取得，理论上可以用枚举法比较所有的基可行取得，理论上可以用枚举法比较所有的基可行解，得到最优解。但在解，得到最优解。但在n，m较大时，在实际较大时，在实际中可行吗？中可行吗？Questions单纯形算法单纯形算法单纯形算法不是比较所有的基可行解，每次单纯形算法不是比较所有的基可行解，每次只寻找比当前基可行解更好的基可行解，从只

9、寻找比当前基可行解更好的基可行解，从而大大减少了计算量！而大大减少了计算量！用单纯形算法求解线性规划问题用单纯形算法求解线性规划问题 0,124 614 8 2 s.t.00032max54321524132154321xxxxxxxxxxxxxxxxxZ用单纯形算法求解线性规划问题用单纯形算法求解线性规划问题用单纯形算法求解线性规划问题用单纯形算法求解线性规划问题用用LINGO 软件求解线性规划问题软件求解线性规划问题LINDO:Linear INteractive and Discrete Optimizer LINGO:Linear INteractive General Optimiz

10、er 用用LINGO 软件求解线性规划问题软件求解线性规划问题model:Title example 1 LINGO模型模型;max=2*x1+3*x2;x1+2*x2=8;4*x1=16;4*x2=12;end用用LINGO 软件求解线性规划问题软件求解线性规划问题Global optimal solution found.Objective value:14.00000 Total solver iterations:2 Model Title:example 1 LINGO模型 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.0

11、00000 0.000000 Row Slack or Surplus Dual Price 1 14.00000 1.000000 2 0.000000 1.500000 3 0.000000 0.1250000 4 4.000000 0.000000灵敏度分析灵敏度分析为什么灵敏度分析？为什么灵敏度分析？灵灵敏敏度度分分析析 灵敏度分析所要解决的问题灵敏度分析所要解决的问题v系数在什么范围内变化，不会影响已获系数在什么范围内变化，不会影响已获得的最优解得的最优解。v如果系数的变化超过以上范围，如何在如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解。原来最优解的基础上求得新

12、的最优解。v当线性规划问题增加一个新的变量或新当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得的约束，如何在原来最优解的基础上获得新的最优解。新的最优解。问题：问题：若该厂从其它处抽调若该厂从其它处抽调4台时用于生产产品台时用于生产产品I、II。求该厂的最优生产计划。求该厂的最优生产计划。最优单纯形表最优单纯形表 的的变变化化分分析析b 的的变变化化分分析析b 的的变变化化分分析析b28000408/12/112/1204/101bB解：08/12/112/1204/101B 的的变变化化分分析析b 的的变变化化分分析析b173*34*2*z 的的变变化化分分析析C最优解

13、不变，最优值变化！132c用用LINGO 软件进行灵敏度分析软件进行灵敏度分析 Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increa

14、se Decrease 2 8.000000 2.000000 4.000000 3 16.00000 16.00000 8.000000 4 12.00000 INFINITY 4.000000用用LINGO 软件进行灵敏度分析软件进行灵敏度分析注：注：仅是最优基不变，最优解、最优值有可能变化！仅是最优基不变，最优解、最优值有可能变化！用用LINGO 软件进行灵敏度分析软件进行灵敏度分析model:Title LINGO模型模型;max=2*x1+2*x2;x1+2*x2=8;4*x1=16;4*x2=12;endX2的价值系数在范围内变化的价值系数在范围内变化用用LINGO 软件进行灵敏度

15、分析软件进行灵敏度分析Global optimal solution found.Objective value:12.00000 Total solver iterations:1 Model Title:LINGO模型模型 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price 1 12.00000 1.000000 2 0.000000 1.000000 3 0.000000 0.2500000 4 4.000000 0.000000最优解不

16、变，最优值变化！最优基不变！最优解不变，最优值变化！最优基不变！用用LINGO 软件进行灵敏度分析软件进行灵敏度分析model:Title LINGO模型模型;max=2*x1+5*x2;x1+2*x2=8;4*x1=16;4*x2=12;endX2的价值系数在范围外变化的价值系数在范围外变化用用LINGO 软件进行灵敏度分析软件进行灵敏度分析 Global optimal solution found.Objective value:19.00000 Total solver iterations:1 Model Title:LINGO模型模型 Variable Value Reduced

17、Cost X1 2.000000 0.000000 X2 3.000000 0.000000 Row Slack or Surplus Dual Price 1 19.00000 1.000000 2 0.000000 2.000000 3 8.000000 0.000000 4 0.000000 0.2500000最优解、最优值、最优基都变化！最优解、最优值、最优基都变化！用用LINGO 软件进行灵敏度分析软件进行灵敏度分析model:Title LINGO模型模型;max=2*x1+3*x2;x1+2*x2=9;4*x1=16;4*x2=12;end第一个资源在范围内变化第一个资源在范围内

18、变化用用LINGO 软件进行灵敏度分析软件进行灵敏度分析 Global optimal solution found.Objective value:15.50000 Total solver iterations:2 Model Title:LINGO模型 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.500000 0.000000 Row Slack or Surplus Dual Price 1 15.50000 1.000000 2 0.000000 1.500000 3 0.000000 0.1250000 4 2.000

19、000 0.000000最优解、最优值都变化！最优基不变！最优解、最优值都变化！最优基不变！用用LINGO 软件进行灵敏度分析软件进行灵敏度分析model:Title LINGO模型模型;max=2*x1+3*x2;x1+2*x2=11;4*x1=16;4*x2 1 g(1)=6*x(1)+2*x(2);g(2)=2*x(1)+2*x(2);end考虑考虑 梯度梯度无约束优化问题无约束优化问题options=optimset(GradObj,on);x0=1,1;x,fval,exitflag,output,grad,hessian=fminunc(myfun,x0,options)x=1.0

20、e-015*0.1110 -0.8882fval=6.2862e-031exitflag=1output=iterations:2 funcCount:2 cgiterations:1firstorderopt:1.5543e-015 algorithm:large-scale:trust-region Newtongrad=1.0e-014*-0.1110 -0.1554hessian=(1,1)6 (2,1)2 (1,2)2 (2,2)2无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题

21、无约束优化问题无约束优化问题无约束优化问题x=1.0000 1.0000fval=8.1777e-010约束优化问题约束优化问题约束优化问题约束优化问题约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fminconInput Arguments约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon

22、约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fminconOutput Arguments约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fminconAlgorithm Large-Scale Optimization.By default fmincon will choose the large-scale algorithm if the user supplies the gradient in fun

23、(and GradObj is on in options)and if only upper and lower bounds exist or only linear equality constraints exist.This algorithm is a subspace trust region method and is based on the interior-reflective Newton method.Each iteration involves the approximate solution of a large linear system using the

24、method of preconditioned conjugate gradients(PCG).约束优化问题约束优化问题fminconMedium-Scale Optimization fmincon uses a Sequential Quadratic programming(SQP)method.In this method,a Quadratic Programming(QP)subproblem is solved at each iteration.An estimate of the Hessian of the Lagrangian is updated at each i

25、teration using the BFGS formula.约束优化问题约束优化问题fminconA line search is performed using a merit function similar to that proposed by 4,5,and 6.The QP subproblem is solved using an active set strategy similar to that described in 3.约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fminconWarning:Large-sc

26、ale(trust region)method does not currently solve this type of problem,switching to medium-scale(line search).Optimization terminated successfully:No Active Constraintsx=0.0000 -0.0000 14.2124fval=2.7069e-009约束优化问题约束优化问题fminconexitflag=1output=iterations:5 funcCount:31 stepsize:1 algorithm:medium-sca

27、le:SQP,Quasi-Newton,line-searchfirstorderopt:1.4794e-004 cgiterations:lambda=lower:3x1 double upper:3x1 double eqlin:0 x1 double eqnonlin:0 x1 double ineqlin:2x1 double ineqnonlin:0 x1 double约束优化问题约束优化问题fmincongrad=1.0e-003*0.1479 0.0006 0hessian=6.0076 2.0257 0.3049 2.0257 2.0055 0.0700 0.3049 0.07

28、00 0.8900二次优化问题二次优化问题二次优化问题二次优化问题二次优化问题二次优化问题quadprog 二次优化问题二次优化问题quadprog 二次优化问题二次优化问题quadprog Output Arguments二次优化问题二次优化问题quadprog Output Arguments二次优化问题二次优化问题quadprog Output Arguments二次优化问题二次优化问题quadprog When the problem has only upper and lower bounds,Or,if the problem has only linear equalities

29、,the default algorithm is the large-scale method.Algorithm Large-Scale Optimization.二次优化问题二次优化问题quadprog This method is a subspace trust-region method based on the interior-reflective Newton method described.Each iteration involves the approximate solution of a large linear system using the method o

30、f preconditioned conjugate gradients(PCG).二次优化问题二次优化问题quadprog Medium-Scale Optimization.quadprog uses an active set method,which is also a projection method.It finds an initial feasible solution by first solving a linear programming problem.二次优化问题二次优化问题quadprog 二次优化问题二次优化问题quadprog 二次优化问题二次优化问题quad

31、prog 二次优化问题二次优化问题quadprog x=0.6667 1.3333fval=-8.2222exitflag=1output=iterations:3 algorithm:medium-scale:active-set firstorderopt:cgiterations:二次优化问题二次优化问题quadprog lambda.ineqlinans=3.1111 0.4444 0lambda.lowerans=0 0极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题fminimaxx=fminimax(fun,x0)x=fminimax(fun,x0,A,b

32、)x=fminimax(fun,x0,A,b,Aeq,beq)x=fminimax(fun,x0,A,b,Aeq,beq,lb,ub)x=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)Syntax极小极大问题极小极大问题fminimaxx=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,.)x,fval=fminimax(.)x,fval,maxfval=fminimax(.)x,fval,

33、maxfval,exitflag=fminimax(.)x,fval,maxfval,exitflag,output=fminimax(.)x,fval,maxfval,exitflag,output,lambda=fminimax(.)Syntax极小极大问题极小极大问题ExampleFind values of x that minimize the maximum value of f1(x),f2(x),f3(x)Where f1(x)=2x f2(x)=4x f3(x)=1-x 0=x=1极小极大问题极小极大问题clear for i=1:180 x(i)=1/180*i f1(i)

34、=2*x(i);f2(i)=x(i)*4;f3(i)=1-x(i);end plot(x,f1)hold onplot(x,f2)hold onplot(x,f3)hold on极小极大问题极小极大问题00.20.40.60.8100.511.522.533.54极小极大问题极小极大问题function f=myfun(x)f(1)=2*x;f(2)=4*x;f(3)=1-x;clear x0=0.2;%Make a starting guess at solutionx,fval=fminimax(myfun,x0,0,1)极小极大问题极小极大问题Optimization terminate

35、d:magnitude of search direction less than 2*options.TolX and maximum constraint violation is less than options.TolCon.Active inequalities(to within options.TolCon=1e-006):lower upper ineqlin ineqnonlin 2 3x=0.2000fval=0.4000 0.8000 0.8000极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题演示函数演示函数 大型方法的演示函数大型方法的演示函数 演示函数演示函数 中型方法的演示函数中型方法的演示函数