《线性规划及非线性规划算法以及软件求解.ppt》由会员分享，可在线阅读，更多相关《线性规划及非线性规划算法以及软件求解.ppt（302页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、最优化方法最优化方法线性规划问题非线性规划问题非约束优化问题约束优化问题优化问题的分类优化问题的分类p基本概念p最优性条件p线性规划问题的求解p非线性规划问题的求解最优化问题的数学模型最优化问题的数学模型最优化问题的数学模型最优化问题的数学模型(*)最优化问题的基本概念最优化问题的基本概念全局极小(唯一极小）最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念多局部极小最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念预备知识预备知识-多元函数的导数多元函数的导数一元函数有一阶导数，二阶导数（假设
2、存在），一元函数有一阶导数，二阶导数（假设存在），多元函数的一阶导数、二阶导数（假设存在）又多元函数的一阶导数、二阶导数（假设存在）又是什么呢？是什么呢？Questions多元函数的一阶导数多元函数的一阶导数-梯度梯度多元函数的一阶导数多元函数的一阶导数-梯度梯度梯梯度度的的几几何何意意义义多元函数的一阶导数多元函数的一阶导数-梯度梯度梯梯度度的的几几何何意意义义多元函数的一阶导数多元函数的一阶导数-梯度梯度Definition 若若x*满足满足 ，则称则称x*为稳定点（平稳点）。为稳定点（平稳点）。Remark多元函数的二阶导数多元函数的二阶导数-Hesse矩阵矩阵Jacobian矩阵Jac
3、obian矩阵Jacobian矩阵Jacobian矩阵p基本概念p最优性条件p线性规划问题的求解p非线性规划问题的求解最优性条件最优性条件无约束最优化问题的最优性条件 （凸函数极值的最优性条件）约束最优化问题的最优性条件无约束优化问题的一阶必要性条件无约束优化问题的一阶必要性条件（*）约束优化问题的一阶必要性约束优化问题的一阶必要性 条件条件Kuhn-Tucker 条件条件Kuhn-Tucker 条件条件等式和不等式约束下的等式和不等式约束下的Kuhn-Tucker 条件条件等式和不等式约束下的等式和不等式约束下的Kuhn-Tucker 条件条件Lagrange函数函数 vs 广义广义Lagr
4、ange函数函数（*）等式和不等式约束下的等式和不等式约束下的Kuhn-Tucker 条件条件等式和不等式约束下的等式和不等式约束下的Kuhn-Tucker 条件条件p基本概念p最优性条件p线性规划问题的求解p非线性规划问题的求解 数学模型数学模型 如何求解（单纯形算法）如何求解（单纯形算法）灵敏度分析灵敏度分析 软件实现（软件实现（LINGO、MATLAB）线性规划及其软件实现线性规划及其软件实现线线性性规规划划的的数数学学模模型型线线性性规规划划的的数数学学模模型型目标函数约束条件决策变量最优值最优解线线性性规规划划的的数数学学模模型型目标函数约束条件决策变量一般形式一般形式线线性性规规划
5、划的的数数学学模模型型标准形式标准形式线线性性规规划划的的数数学学模模型型标准形式标准形式用单纯形算法求解线性规划问题用单纯形算法求解线性规划问题用单纯形算法求解线性规划问题用单纯形算法求解线性规划问题用单纯形算法求解线性规划问题用单纯形算法求解线性规划问题用用LINGO 软件求解线性规划问题软件求解线性规划问题LINDO:Linear INteractive and Discrete Optimizer LINGO:Linear INteractive General Optimizer 用用LINGO 软件求解线性规划问题软件求解线性规划问题model:Title example 1 LI
6、NGO模型模型;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.000000 0.000000 Row Slack or Surplus Dual Price 1 14.000
7、00 1.000000 2 0.000000 1.500000 3 0.000000 0.1250000 4 4.000000 0.000000灵敏度分析灵敏度分析为什么灵敏度分析？为什么灵敏度分析？灵灵敏敏度度分分析析 灵敏度分析所要解决的问题灵敏度分析所要解决的问题v系数在什么范围内变化，不会影响已获系数在什么范围内变化，不会影响已获得的最优解得的最优解。v如果系数的变化超过以上范围，如何在如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解。原来最优解的基础上求得新的最优解。v当线性规划问题增加一个新的变量或新当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础
8、上获得的约束，如何在原来最优解的基础上获得新的最优解。新的最优解。问题：问题：若该厂从其它处抽调若该厂从其它处抽调4台时用于生产产品台时用于生产产品I、II。求该厂的最优生产计划。求该厂的最优生产计划。最优单纯形表最优单纯形表 的的变变化化分分析析 的的变变化化分分析析 的的变变化化分分析析解：的的变变化化分分析析 的的变变化化分分析析 的的变变化化分分析析最优解不变，最优值变化！用用LINGO 软件进行灵敏度分析软件进行灵敏度分析 Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allow
9、able 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 Increase Decrease 2 8.000000 2.000000 4.000000 3 16.00000 16.00000 8.000000 4 12.00000 INFINITY 4.000000用用LINGO 软件进行灵敏度分析软件进行灵敏
10、度分析注：注：仅是最优基不变，最优解、最优值有可能变化！仅是最优基不变，最优解、最优值有可能变化！用用LINGO 软件进行灵敏度分析软件进行灵敏度分析model:Title LINGO模型模型;max=2*x1+2*x2;x1+2*x2=8;4*x1=16;4*x2=12;endX2的价值系数在范围内变化的价值系数在范围内变化用用LINGO 软件进行灵敏度分析软件进行灵敏度分析Global optimal solution found.Objective value:12.00000 Total solver iterations:1 Model Title:LINGO模型模型 Variabl
11、e 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最优解不变，最优值变化！最优基不变！最优解不变，最优值变化！最优基不变！用用LINGO 软件进行灵敏度分析软件进行灵敏度分析model:Title LINGO模型模型;max=2*x1+5*x2;x1+2*x2=8;4*x1=16;4*x2=12;e
12、ndX2的价值系数在范围外变化的价值系数在范围外变化用用LINGO 软件进行灵敏度分析软件进行灵敏度分析 Global optimal solution found.Objective value:19.00000 Total solver iterations:1 Model Title:LINGO模型模型 Variable Value Reduced 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
13、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第一个资源在范围内变化第一个资源在范围内变化用用LINGO 软件进行灵敏度分析软件进行灵敏度分析 Global optimal solution found.Objective value:15.50000 Total solver iterations:2 Model Title
14、: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.000000 0.000000最优解、最优值都变化！最优基不变！最优解、最优值都变化！最优基不变！用用LINGO 软件进行灵敏度分析软件进行灵敏度分析model:Title LINGO模型模型;max=2*x1+3*x2;x1+2*x2=11;4*
15、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.0e-015*0.1110 -0.8882fval=6.2862e-031exitflag=1output=iterations:2 funcCount:2 cgiterations:1firstorderopt:1.5543e-015 alg
16、orithm:large-scale:trust-region Newtongrad=1.0e-014*-0.1110 -0.1554hessian=(1,1)6 (2,1)2 (1,2)2 (2,2)2无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题无约束优化问题x=1.0000 1.0000fval=8.1777e-010约束优化问题约束优化问题约束优化问题约束优化问题约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约
17、束优化问题fminconInput Arguments约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fminconOutput Arguments约束优化问题约束优化
18、问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fminconAlgorithm Large-Scale Optimization.By default fmincon will choose the large-scale algorithm if the user supplies the gradient in fun(and GradObj is on in options)and if only upper and lower bounds exist or only linear equality constraints exist.This alg
19、orithm 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 method of preconditioned conjugate gradients(PCG).约束优化问题约束优化问题fminconMedium-Scale Optimization fmincon uses a Sequential
20、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 iteration using the BFGS formula.约束优化问题约束优化问题fminconA line search is performed using a merit function similar to that prop
21、osed 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-scale(trust region)method does not currently solve this type of problem,switching to medium-scale(line search).Optimization
22、 terminated successfully:No Active Constraintsx=0.0000 -0.0000 14.2124fval=2.7069e-009约束优化问题约束优化问题fminconexitflag=1output=iterations:5 funcCount:31 stepsize:1 algorithm:medium-scale:SQP,Quasi-Newton,line-searchfirstorderopt:1.4794e-004 cgiterations:lambda=lower:3x1 double upper:3x1 double eqlin:0 x1
23、 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.0700 0.8900二次优化问题二次优化问题二次优化问题二次优化问题二次优化问题二次优化问题quadprog 二次优化问题二次优化问题quadprog 二次优化问题二次优化问题quadprog Output Arguments二次优化问题二次优
24、化问题quadprog Output Arguments二次优化问题二次优化问题quadprog Output Arguments二次优化问题二次优化问题quadprog When the problem has only upper and lower bounds,Or,if the problem has only linear equalities,the default algorithm is the large-scale method.Algorithm Large-Scale Optimization.二次优化问题二次优化问题quadprog This method is a
25、 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 of preconditioned conjugate gradients(PCG).二次优化问题二次优化问题quadprog Medium-Scale Optimization.quadprog uses an active set meth
26、od,which is also a projection method.It finds an initial feasible solution by first solving a linear programming problem.二次优化问题二次优化问题quadprog 二次优化问题二次优化问题quadprog 二次优化问题二次优化问题quadprog 二次优化问题二次优化问题quadprog x=0.6667 1.3333fval=-8.2222exitflag=1output=iterations:3 algorithm:medium-scale:active-set firs
27、torderopt:cgiterations:二次优化问题二次优化问题quadprog lambda.ineqlinans=3.1111 0.4444 0lambda.lowerans=0 0极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题fminimaxx=fminimax(fun,x0)x=fminimax(fun,x0,A,b)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
28、(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,maxfval,exitflag=fminimax(.)x,fval,maxfval,exitflag,output=fminimax(.)x,fval,maxfval,exitflag,output,lambda=fminimax(.)Sy
29、ntax极小极大问题极小极大问题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)=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极小极大问题极小极大问题极小极大问题极小极大问题function
30、 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 terminated: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极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题演示函数演示函数 大型方法的演示函数大型方法的演示函数 演示函数演示函数 中型方法的演示函数中型方法的演示函数