非线性的规划(qh).ppt

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

1、非线性规划主讲人虞继敏1引言非线性规划是运筹学中包含内容最多，应用最广泛的一个分支，计算远比线性规划复杂，由于时间的限制，只能作简单的介绍。例6-1电厂投资分配问题水电部门打算将一笔资金分配去建设n个水电厂，其库容量为ki,i=1,2….n,各电厂水库径流输入量分布为Fi(Q)，发电量随库容与径流量而变化，以Ei(ki,Q)表示。计划部门构造一个模型，即在一定条件下，使总发电量年平均值最大，用数学语言来说，使其期望值最大。对每个电厂i，其年发电量的期望值为Ei(ki,Q)dFi(Q)设V为总投资额，Vi为各水电厂的投资，都是ki的非

2、线性函数，构造非线性规划模型如下：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上的实函数。几个概念定义1如果X满足（P

3、）的约束条件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,….m)（

4、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）为带不等式约束问题。（

5、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

6、(1),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

7、(X)Xf(x1)+(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/x

8、2x12f/x22…..2f/x2xn……..2f/xnx12f/xnx2…..2f/xn2=2最优性条件最优性条件的研究是非线性规划理论研究的一个中心问题。为什么要研究最优性条件？本质上把可