《线性规划及非线性规划算法以及软件求解ppt课件》由会员分享，可在线阅读，更多相关《线性规划及非线性规划算法以及软件求解ppt课件（302页珍藏版）》请在金锄头文库上搜索。
1、最优化方法最优化方法线性规划问题非线性规划问题非约束优化问题约束优化问题优化问题的分类优化问题的分类p根本概念p最优性条件p线性规划问题的求解p非线性规划问题的求解最优化问题的数学模型最优化问题的数学模型最优化问题的数学模型最优化问题的数学模型(*)最优化问题的根本概念最优化问题的根本概念全局极小(独一极小最优化问题的根本概念最优化问题的根本概念最优化问题的根本概念最优化问题的根本概念最优化问题的根本概念最优化问题的根本概念多部分极小最优化问题的根本概念最优化问题的根本概念最优化问题的根本概念最优化问题的根本概念预备知识预备知识-多元函数的导数多元函数的导数一元函数有一阶导数，二阶导数假设存在
2、，一元函数有一阶导数，二阶导数假设存在，多元函数的一阶导数、二阶导数假设存在又多元函数的一阶导数、二阶导数假设存在又是什么呢？是什么呢？Questions多元函数的一阶导数多元函数的一阶导数-梯梯度度多元函数的一阶导数多元函数的一阶导数-梯梯度度梯梯度度的的几几何何意意义义多元函数的一阶导数多元函数的一阶导数-梯梯度度梯梯度度的的几几何何意意义义多元函数的一阶导数多元函数的一阶导数-梯梯度度Definition 假设假设x*满足满足 ，那么称那么称x* 为稳定点平稳点。为稳定点平稳点。 Remark多元函数的二阶导数多元函数的二阶导数-Hesse矩阵矩阵Jacobian矩阵Jacobian矩阵
3、Jacobian矩阵Jacobian矩阵p根本概念p最优性条件p线性规划问题的求解p非线性规划问题的求解最优性条件最优性条件无约束最优化问题的最优性条件 凸函数极值的最优性条件约束最优化问题的最优性条件无约束优化问题的一阶必要性条件无约束优化问题的一阶必要性条件*约束优化问题的一阶必要性约束优化问题的一阶必要性 条件条件Kuhn-Tucker 条件条件Kuhn-Tucker 条件条件等式和不等式约束下的等式和不等式约束下的Kuhn-Tucker 条件条件等式和不等式约束下的等式和不等式约束下的Kuhn-Tucker 条件条件Lagrange函数函数 vs 广义广义Lagrange函数函数 *等
4、式和不等式约束下的等式和不等式约束下的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 LINGO模型模型;max=2*x1+3*x2;x1+2*x2=8;4*x1=16;4*x2=12;
6、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.00000 1.000000 2 0.000000 1.500000 3 0.000000 0
7、.1250000 4 4.000000 0.000000灵敏度分析灵敏度分析为什么灵敏度分析？为什么灵敏度分析？灵灵敏敏度度分分析析 灵敏度分析所要处理的问题灵敏度分析所要处理的问题系数在什么范围内变化，不会影响已系数在什么范围内变化，不会影响已获得的最优解。获得的最优解。假设系数的变化超越以上范围，如何假设系数的变化超越以上范围，如何在原来最优解的根底上求得新的最优在原来最优解的根底上求得新的最优解。解。当线性规划问题添加一个新的变量或当线性规划问题添加一个新的变量或新的约束，如何在原来最优解的根底新的约束，如何在原来最优解的根底上获得新的最优解。上获得新的最优解。问题：假设该厂从其它处抽调
8、问题：假设该厂从其它处抽调4台时用于消费产品台时用于消费产品I、II。求该厂的最优消费方案。求该厂的最优消费方案。最优单纯形表最优单纯形表 的变化分析 的变化分析 的变化分析解： 的变化分析 的变化分析 的变化分析最优解不变，最优值变化！用用LINGO 软件进展灵敏度分析软件进展灵敏度分析 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINI
9、TY 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 软件进展灵敏度分析软件进展灵敏度分析注：注：仅是最优基不变，最优解、最优值有能够变化！仅是最优基不变，最优解、最优值有能够变化！用用LINGO 软件进展灵敏度分析软件进展灵敏
10、度分析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模型模型 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row S
11、lack 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;endX2的价值系数在范围外变化的价值系数在范围外变化用用LINGO 软件进展灵敏度分析软件进展灵敏度分析 Global optimal
12、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 8.000000 0.000000 4 0.000000 0.2500000最优解、最优值、最优基都变化！最优解、最优值、最优基都变
13、化！用用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: LINGO模型 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2
14、.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*x1=16;4*x2 1 g(1) = 6*x(1)+2*x(2); g(2) = 2*x(1)+2*x(2);end思索思
15、索 梯度梯度无约束优化问题无约束优化问题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 algorithm: large-scale: trust-region New
16、tongrad = 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约束优化问题约束优化问题fminconInput Arg
17、uments约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fmincon约束优化问题约束优化问题fminconOutput Arguments约束优化问题约束优化问题fmincon约束优化问题约束优化问题
18、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 algorithm is a subsp
19、ace 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 Quadratic prog
20、ramming (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 proposed b
21、y 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).Optimizati
22、on 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
23、: 3x1 double eqlin: 0x1 double eqnonlin: 0x1 double ineqlin: 2x1 double ineqnonlin: 0x1 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 二次优化问题二次优化问题quad
24、prog 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, the default algorithm is the large-scale method. Algorithm Large-Scale Optimization. 二次
25、优化问题二次优化问题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 of preconditioned conjugate gradients (PCG). 二次优化问题二次优化问题quadprog Medium-Scale Optimi
26、zation. 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 二次优化问题二次优化问题quadprog 二次优化问题二次优化问题quadprog x = 0.6667 1.3333fval =-8.2222exitflag = 1output = i
27、terations: 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)x = fminimax(fun,x0,A,b,Aeq,beq)x = fminimax(fun,x0,A,b,A
28、eq,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,maxfval,exitflag = fminimax(.)x,fval,maxfval
29、,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)=2*x(i);f2(i)= x(i)*4;f3(i)=1-x(i); e
30、nd plot(x,f1) hold onplot(x,f2) hold onplot(x,f3) hold on极小极大问题极小极大问题极小极大问题极小极大问题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 terminated: magnitude of search direction less than 2*option
31、s.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极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题极小极大问题演示函数演示函数 大型方法的演示函数大型方法的演示函数 演示函数演示函数 中型方法的演示函数中型方法的演示函数
