线性与非线性规划算法及实现.pptx

《线性与非线性规划算法及实现.pptx》由会员分享，可在线阅读，更多相关《线性与非线性规划算法及实现.pptx（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1线性与非线性规划算法及实现线性与非线性规划算法及实现解决规划问题的基本流程解决规划问题的基本流程第第9.1节节引引入入与与导导言言03第1步：问题的分析理解及描述（数学建模）第2步：解决问题的整体目标（目标函数）第3步：影响目标的各种限制条件（约束条件）第4步：应用相关函数获得求解（算法实现）第1页/共27页哪样一些问题可以描述成为线哪样一些问题可以描述成为线性规划问题？性规划问题？线性规划模型的一般形式线性规划模型的一般形式第第9.31节节线线性性规规划划一一般般形形式式04当当 均为线性函数，上述优化模型称为均为线性函数，上述优化模型称为线性规划线性规划，否则称为，否则称为非线性规

2、划非线性规划。关于线性规划的形式，有诸如标准形式、规范形式等关于线性规划的形式，有诸如标准形式、规范形式等之分之分，在这里我们只关心在这里我们只关心MATLAB 能够接受的形式：能够接受的形式：一般来说不同形式之间可以转换一般来说不同形式之间可以转换(YCXp14)z目标函数目标函数/c价值向量价值向量/A约束矩阵约束矩阵/b右端向量右端向量一个满足约束的一个满足约束的x-可行解可行解/可行解集合可行解集合-可行域可行域第2页/共27页线性规划的图解法线性规划的图解法(2维情形维情形)1通过一个简单的实例通过一个简单的实例通过一个简单的实例通过一个简单的实例,巩固对线性规划的若干巩固对线性规划

3、的若干巩固对线性规划的若干巩固对线性规划的若干概念的理解：概念的理解：概念的理解：概念的理解：exp.1 exp.1 图解法求解线性规划问题图解法求解线性规划问题图解法求解线性规划问题图解法求解线性规划问题:第第9.34节节线线性性规规划划图图解解法法05将前三个约束条件的不等号改为等号将前三个约束条件的不等号改为等号,就是如上三条直线就是如上三条直线,下面考察直线下面考察直线L1,L2,L3及坐标轴围成的可行域及坐标轴围成的可行域:第3页/共27页线性规划的图解法线性规划的图解法(2维情形维情形)2第第9.34节节线线性性规规划划图图解解法法如图所示如图所示:五边形五边形OQ1Q2Q4Q3

4、构成可行域构成可行域06x1x2oL1L2L3Q1Q2Q4(4,1)Q3Z1 Z2 Z3 Z4 Z5 当目标函数当目标函数z=3x1+x2取不同值时，表示一组平行直线，如图中虚线，最优解在取不同值时，表示一组平行直线，如图中虚线，最优解在Q4点，点，Zmax=13第4页/共27页线性规划的图解法线性规划的图解法(2维情形维情形)3一些直观结论和定理：一些直观结论和定理：一些直观结论和定理：一些直观结论和定理：在在在在2 2维情形维情形维情形维情形下，可行域为直线组成的凸多边形下，可行域为直线组成的凸多边形下，可行域为直线组成的凸多边形下，可行域为直线组成的凸多边形，目标函数的等值线为直线，最优

5、解在凸多边形的目标函数的等值线为直线，最优解在凸多边形的目标函数的等值线为直线，最优解在凸多边形的目标函数的等值线为直线，最优解在凸多边形的 某个顶点处取得。某个顶点处取得。某个顶点处取得。某个顶点处取得。可行域可行域可行域可行域空集空集空集空集，如改例中第，如改例中第，如改例中第，如改例中第3 3个约束为个约束为个约束为个约束为-3-3x1+2x2x1+2x2 1414，则无最优解；则无最优解；则无最优解；则无最优解；可行域可行域可行域可行域无界无界无界无界，如去掉例中第如去掉例中第如去掉例中第如去掉例中第3 3个约束个约束个约束个约束-3-3x1+2x2x1+2x2 1414，则可能无最优

6、解；则可能无最优解；则可能无最优解；则可能无最优解；无穷多无穷多无穷多无穷多最优解，如改例中第最优解，如改例中第最优解，如改例中第最优解，如改例中第3 3个约束为个约束为个约束为个约束为3 3x1+x2 x1+x2 14 14，则最优解在凸多边形一条边上取得；则最优解在凸多边形一条边上取得；则最优解在凸多边形一条边上取得；则最优解在凸多边形一条边上取得；推广到推广到推广到推广到n n维欧氏空间维欧氏空间维欧氏空间维欧氏空间，线性规划问题若有最优解，则最优解必是作为可行域的凸多面体的某个顶点。，线性规划问题若有最优解，则最优解必是作为可行域的凸多面体的某个顶点。，线性规划问题若有最优解，则最优解

7、必是作为可行域的凸多面体的某个顶点。，线性规划问题若有最优解，则最优解必是作为可行域的凸多面体的某个顶点。第第9.34节节线线性性规规划划图图解解法法07第5页/共27页线性规划的线性规划的LP解法解法相关函数介绍：相关函数介绍：lp第第9.2节节线线性性规规划划LP解解法法08x=lp(c,A,b)x=lp(c,A,b,v1,v2)%即有约束即有约束v1 x v2x=lp(c,A,b,v1,v2,x0)%x0为初始解，缺省为为初始解，缺省为0 x,lag=lp()%lag为拉格朗日乘子，非为拉格朗日乘子，非 零分量对应于起作用的约束条件零分量对应于起作用的约束条件x,lag,how=lp()

8、%how给出求解信息，无给出求解信息，无可行解可行解infeasible,无有界解无有界解unbounded,成功成功ok不过在高版本中不过在高版本中lp已被已被linprog取代！取代！第6页/共27页lp函数求解示例：函数求解示例：第第9.2节节线线性性规规划划LP解解法法针对前述针对前述exp.1可如下计算：可如下计算：c=-3,1;a=-1,1;1,-2;3,2;b=2,2,14;v1=0,0;x=lp(c,a,b,v1)z=-c*xx=4.0000 1.0000z=13.000009c=-3;1;a=-1,1;1,-2;3,2;b=2;2;14;v1=0,0;x=lp(c,a,b,v

9、1)z=-c*x第7页/共27页线性规划的线性规划的LP解法解法相关函数介绍：相关函数介绍：linprog第第9.2节节线线性性规规划划LP解解法法10 x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)%增加约束增加约束Aeq*x=beqx=linprog(f,A,b,Aeq,beq,lb,ub)%设计变量下上界设计变量下上界x,fval,exitflag,output,lambda=linprog()%fval返回目标函数值返回目标函数值/exitflag返回退出条件返回退出条件/output返回返回优化信息优化信息/lambda返回显示哪些主动约束（返回显示

10、哪些主动约束（参数繁杂参数繁杂会用即可会用即可）第8页/共27页linprog函数求解示例：函数求解示例：第第9.2节节线线性性规规划划LP解解法法11exp.2求解下列线性规划问题：求解下列线性规划问题：f=-5;-4;-6;A=1,-1,1;3,2,4;3,2,0;b=20;42;30;lb=zeros(3,1);x,fval,exitflag,output,lambda=linprog(f,A,b,lb);x,fval,lambda.ineqlin,lambda.lower第9页/共27页范例范例-化工公司产品生产计划化工公司产品生产计划第第9.7节节化化工工公公司司生生产产计计划划12

11、1.问题：略问题：略2.建模：建模：3.求解：求解：第10页/共27页范例范例-化工公司产品生产计划化工公司产品生产计划第第9.7节节化化工工公公司司生生产产计计划划13f=-400;-1000;-300;200;A=0,-2,1,1;2,3,0,0;3,4,0,0;b=0;16;24;Aeq=0,-2,1,1;beq=0;lb=zeros(4,1);ub=inf*ones(4,1);ub(3)=5;x0=zeros(4,1);x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub,x0)x=lp(f,A,b,lb,ub,x0,1)第

12、11页/共27页Thats all3Q!下下次次课课内内容容非非线线性性规规划划算算法法实实现现14第12页/共27页第十章第十章 非线性规划非线性规划内容：内容：内容：内容：本讲主要介绍非线性规划问题的求解本讲主要介绍非线性规划问题的求解本讲主要介绍非线性规划问题的求解本讲主要介绍非线性规划问题的求解目的：目的：目的：目的：学习非学习非学习非学习非 线性规划算法的线性规划算法的线性规划算法的线性规划算法的 MATLAB MATLAB实现实现实现实现 要求：要求：要求：要求：能够运用软件直接对小规模非线性规划能够运用软件直接对小规模非线性规划能够运用软件直接对小规模非线性规划能够运用软件直接对

13、小规模非线性规划 问题进行求解问题进行求解问题进行求解问题进行求解了解非线性规划问题区别于线性规划问题的基本概念、形式和算法了解非线性规划问题区别于线性规划问题的基本概念、形式和算法了解非线性规划问题区别于线性规划问题的基本概念、形式和算法了解非线性规划问题区别于线性规划问题的基本概念、形式和算法掌握约束和无约束优化函数掌握约束和无约束优化函数掌握约束和无约束优化函数掌握约束和无约束优化函数constrconstr和和和和fminufminu通过范例通过范例通过范例通过范例,掌握非线性规划问题求解一般过程掌握非线性规划问题求解一般过程掌握非线性规划问题求解一般过程掌握非线性规划问题求解一般过程

14、第第10.1节节引引入入与与导导言言01第13页/共27页关于非线性规划的引入和概述关于非线性规划的引入和概述 非非非非线性规划线性规划线性规划线性规划同时涵盖运筹学中的同时涵盖运筹学中的同时涵盖运筹学中的同时涵盖运筹学中的约束约束约束约束优化和优化和优化和优化和无约束无约束无约束无约束优化两种类型优化两种类型优化两种类型优化两种类型，简单说就是简单说就是简单说就是简单说就是目标函数目标函数目标函数目标函数或或或或约束条件约束条件约束条件约束条件(可以不带可以不带可以不带可以不带constraintconstraintconstraintconstraint)均为非线性函数的优化模型，称为均为

15、非线性函数的优化模型，称为均为非线性函数的优化模型，称为均为非线性函数的优化模型，称为非线性规划非线性规划非线性规划非线性规划。非线性规划问题同样是企业运作、科技研发和工程设计的常见问题，甚至在某种意义上应用面比线性规划更广。因为非线性规划问题同样是企业运作、科技研发和工程设计的常见问题，甚至在某种意义上应用面比线性规划更广。因为非线性规划问题同样是企业运作、科技研发和工程设计的常见问题，甚至在某种意义上应用面比线性规划更广。因为非线性规划问题同样是企业运作、科技研发和工程设计的常见问题，甚至在某种意义上应用面比线性规划更广。因为非线性本身就意味着混沌和无序，这与现实世界一致。非线性本身就意味

16、着混沌和无序，这与现实世界一致。非线性本身就意味着混沌和无序，这与现实世界一致。非线性本身就意味着混沌和无序，这与现实世界一致。MATLABMATLABMATLABMATLAB优化工具箱优化工具箱优化工具箱优化工具箱(OptimOptimOptimOptim)针对约束和非约束分别由函数针对约束和非约束分别由函数针对约束和非约束分别由函数针对约束和非约束分别由函数constrconstrconstrconstr和和和和fminufminufminufminu进行求解。进行求解。进行求解。进行求解。constrconstrconstrconstr升级为升级为升级为升级为fminconfmincon

17、fminconfmincon，fminufminufminufminu升级为升级为升级为升级为fminuncfminuncfminuncfminunc第第10.1节节引引入入与与导导言言02第14页/共27页在后继版本中不再提供支持？在后继版本中不再提供支持？熟悉新函数熟悉新函数版本更新带来的函数升级版本更新带来的函数升级第第10.1节节old name和和new name03第15页/共27页非线性规划模型的一般形式非线性规划模型的一般形式1下面分别给出约束和非约束优下面分别给出约束和非约束优化的一般形式，以及各自简单化的一般形式，以及各自简单的例子的例子:第第10.31节节约约束束优优化化

18、模模型型04第16页/共27页非线性规划模型的一般形式非线性规划模型的一般形式2第第10.31节节无无约约束束优优化化模模型型05无约束优化只有一个目标函数，这个目标函数必须是非线性的，实际问题真正无约束并不多无约束优化只有一个目标函数，这个目标函数必须是非线性的，实际问题真正无约束并不多无约束优化只有一个目标函数，这个目标函数必须是非线性的，实际问题真正无约束并不多无约束优化只有一个目标函数，这个目标函数必须是非线性的，实际问题真正无约束并不多:第17页/共27页非线性规划方法概要非线性规划方法概要 由于本身的复杂性，非线性规划远不如线性规划问题那样具备很由于本身的复杂性，非线性规划远不如线

19、性规划问题那样具备很由于本身的复杂性，非线性规划远不如线性规划问题那样具备很由于本身的复杂性，非线性规划远不如线性规划问题那样具备很高效率高效率高效率高效率的求解方法。的求解方法。的求解方法。的求解方法。相对而言无约束优化更容易求解一些，一个基本的思路就是，相对而言无约束优化更容易求解一些，一个基本的思路就是，相对而言无约束优化更容易求解一些，一个基本的思路就是，相对而言无约束优化更容易求解一些，一个基本的思路就是，化约束优化为一系列无约束化约束优化为一系列无约束化约束优化为一系列无约束化约束优化为一系列无约束优化问题，例如：序列无约束极优化问题，例如：序列无约束极优化问题，例如：序列无约束极

20、优化问题，例如：序列无约束极小化技术、可变容差法，等等小化技术、可变容差法，等等小化技术、可变容差法，等等小化技术、可变容差法，等等 对于具体算法细节，我们虽然不会本课程中深入探究，但能够从对于具体算法细节，我们虽然不会本课程中深入探究，但能够从对于具体算法细节，我们虽然不会本课程中深入探究，但能够从对于具体算法细节，我们虽然不会本课程中深入探究，但能够从算法本身的着手改进算法本身的着手改进算法本身的着手改进算法本身的着手改进将会是很有价值的工作，比如本章作将会是很有价值的工作，比如本章作将会是很有价值的工作，比如本章作将会是很有价值的工作，比如本章作者开发的逼近精确罚函数法，感兴趣可以仔细研

21、读者开发的逼近精确罚函数法，感兴趣可以仔细研读者开发的逼近精确罚函数法，感兴趣可以仔细研读者开发的逼近精确罚函数法，感兴趣可以仔细研读第第9.34节节非非线线性性规规划划方方法法概概要要06第18页/共27页MATLAB非线性规划函数非线性规划函数约束优化函数介绍：约束优化函数介绍：constr第第10.6节节非非线线性性规规划划函函数数07调用语法：调用语法：constr(fmincon)X,OPTIONS=constr(FUN,x0,OPTIONS,VLB,VUB)具体含义请参见联机具体含义请参见联机help第19页/共27页MATLAB非线性规划函数非线性规划函数无约束优化函数介绍：无约

22、束优化函数介绍：fminu(fminunc)第第10.6节节非非线线性性规规划划函函数数08调用语法：调用语法：fminuX,OPTIONS=fminu(FUN,x0,)具体含义请参见具体含义请参见tbp154求解非线性规划问题，需要首先编制一个求解非线性规划问题，需要首先编制一个m文件，描述需要求解的问题，也即求解需以文件，描述需要求解的问题，也即求解需以“被调被调”的形式进行的形式进行第20页/共27页非线性规划问题的范例非线性规划问题的范例-圈地圈地1 某旅游发展有限公司计划某旅游发展有限公司计划开发度假村，公司要求先用一开发度假村，公司要求先用一批旧砖建一圈矩形围墙，以便批旧砖建一圈矩

23、形围墙，以便存放建筑材料旧砖的数量是存放建筑材料旧砖的数量是固定的，围墙的高度不能低于固定的，围墙的高度不能低于两米，围墙围住的面积越大越两米，围墙围住的面积越大越好要你来设计。好要你来设计。第第10.6节节非非线线性性规规划划函函数数09第21页/共27页非线性规划问题的范例非线性规划问题的范例-圈地圈地2第第10.6节节非非线线性性规规划划函函数数10第22页/共27页非线性规划问题的范例非线性规划问题的范例-圈地圈地3具体非线性规划模型：具体非线性规划模型：第第10.7节节范范例例圈圈地地问问题题11tbp172.mfunction F,G=tbp172(x)F=-x(1)*x(2);G

24、(1)=(x(1)+x(2)*x(3)-120;第23页/共27页非线性规划问题的范例非线性规划问题的范例-圈地圈地4第第10.7节节范范例例圈圈地地问问题题12loadtbp172.mx=10;10;2;options(13)=0%等式约束的个数为等式约束的个数为0 xl=0;0;2;xu=inf;inf;inf;x,options=constr(tbp172,x,options,xl,xu);x,fmin=options(8)关于关于constr的升级函数的升级函数fmincon，请参考联机请参考联机帮助系统范例帮助系统范例第24页/共27页非线性规划问题的范例非线性规划问题的范例-无约束无约束3第第10.7节节范范例例-无无约约束束优优化化13补充范例补充范例:求解：求解：fun.mfunction y=fun(x)a=2;b=2;y=x(1)2/a+x(2)2/b;x0=1,1;x=fminu(fun,x0)精确解为精确解为0，0第25页/共27页预习第预习第预习第预习第1111章章章章 图的模型及矩阵表示图的模型及矩阵表示图的模型及矩阵表示图的模型及矩阵表示下下次次课课内内容容图图的的模模型型及及矩矩阵阵表表示示14第26页/共27页