运筹学资料非线性规划资料.ppt

《运筹学资料非线性规划资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学资料非线性规划都是ki的非线性函数，构造非线性规划模型如下：MaxEi(ki,Q)dFi(Q)s.t.V1(k1)+V2(k2)+……+Vn(kn)=VV1(k1),V2(k2),……,Vn(kn)0利用一定的算法，可求出最优分配ki*和Vi*(i=1,2,….n).主要内容非线性规划理论方面应用方面算法方面互补稳定灵敏对偶问题最优性条件无约束问题直接法有约束问题间接法一般模型Minf(X)s.t.hi(X)=0(i=1,2,….m)（P）gj(X)0(j=1,2….l)XEnf(X)hi(X)gj(X)为En上的实函数。几个概

2、念定义1如果X满足（P）的约束条件hi(X)=0(i=1,2,….m)gj(X)0(j=1,2….l)则称XEn为（P）的一个可行解。记（P）的所有可行解的集合为D，D称为（P）可行域。几个概念定义2X*称为（P）的一个（整体）最优解，如果X*D，满足f(X)f(X*)，XD。几个概念定义3X*称为（P）的一个（局部）最优解，如果X*D，且存在一个X*的邻域N(X*,)=XEnX-X*<>0满足f(X)f(X*)，XDN(X*,)f(X)局部最优解整体最优解模型分类Minf(X)s.t.hi(X)=0(i=1,2

3、,….m)（P）gj(X)0(j=1,2….l)XEnf(X)hi(X)gj(X)为En上的实函数。模型分类1如果f(X)hi(X)gj(X)中至少有一个函数不是线性（仿射）函数，则称（P）为非线性问题。如果f(X)hi(X)gj(X)都是线性（仿射）函数，则称（P）为线性问题。模型分类2若m=l=0，则称（P）为无约束问题。（P1）Minf(X)XEn模型分类2若m0，l=0，则称（P）为带等式约束问题。（P2）Minf(X)s.t.hi(X)=0(i=1,2,….m)XEn模型分类2若m=0，l0，则称（P）为带不等式约束问题。

4、（P3）Minf(X)s.t.gj(X)0(j=1,2….l)XEn模型分类2若m0，l0，则称（P）为一般问题。（P）Minf(X)s.t.hi(X)=0(i=1,2,….m)gj(X)0(j=1,2….l)XEn凸函数的概念凸集概念：设D是n维线性空间En的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。即：若D中的任意两点x(1),x(2)∈D，存在0<<1使得x=x(1)+(1-)x(2)∈D,则称D为凸集凸函数的概念定义：定义在凸集DEn上的函数f(X)如果对任意两点x(1),

5、x(2)∈D，均有0<<1使得f(x(1)+(1-)x(2))f(x(1))+(1-)f(x(2))则称函数f(X)为D上的凸函数.凸函数的概念若严格不等式成立,则称函数f(X)为D上的严格凸函数.如果-g(X)为D上的(严格)凸函数,则g(X)为D上的(严格)凹函数.f(X)Xf(X1)f(X2)X1X2f(X)Xf(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)f(X)Xf(x1)+(1-)f(x2)f(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)f(X)Xf(x1

6、)+(1-)f(x2)f(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)任意两点的函数值的连线上的点都在曲线的上方线性函数既是凸函数,又是凹函数,反之也然.梯度向量f(X)=gradf(X)=(f/x1,f/x2,…..,f/xn)正定矩阵如果对矩阵H(X),对任意XN(X*,)ZEn均有ZTH(X)Z>0(0)则称H(X)在X*点正定(半正定).海赛(Hesse)矩阵xxf(X)=H(X)2f/x122f/x1x2…..2f/x1xn2f/x2x12f/x22….

7、.2f/x2xn……..2f/xnx12f/xnx2…..2f/xn2=2最优性条件最优性条件的研究是非线性规划理论研究的一个中心问题。为什么要研究最优性条件？本质上把可行解集合的范围缩小。它是许多算法设计的基础。无约束问题的最优性条件（P1）Minf(X)XEn定理1（一阶必要条件）设f(X)在X*点可微，则X*为（P1）的一个局部最优解，一定有f(X*)=gradf(X*)=0（X*称为驻点）无约束问题的最优性条件（P1）Minf(X)XEn定理2（二阶必要条件）设f(X)在X*点二阶可微，如果X*为（P1）的一

8、个局部最优解，则有f(X*)=0和H（X*）为半正定。无约束问题的最优性条件（P1）Minf(X)XEn定理3（二阶充分条件）设f(X)在X*点二