运筹学资料5非线性规划

第六章第六章非线性规划非线性规划1 引引 言言非线性规划是运筹学中包含内容最多，非线性规划是运筹学中包含内容最多，应用最广泛的一个分支，计算远比线性应用最广泛的一个分支，计算远比线性规划复杂，由于时间的限制，只能作简规划复杂，由于时间的限制，只能作简单的介绍。单的介绍。例例 6-1 电厂投资分配问题电厂投资分配问题水电部门打算将一笔资金分配去建设水电部门打算将一笔资金分配去建设 n个水电厂，其库容量为个水电厂，其库容量为 ki,i=1,2.n, 各各电厂水库径流输入量分布为电厂水库径流输入量分布为 Fi(Q)， 发发电量随库容与径流量而变化，以电量随库容与径流量而变化，以Ei(ki,Q)表示。计划部门构造一个模型表示。计划部门构造一个模型，即在一定条件下，使总发电量年平均，即在一定条件下，使总发电量年平均值最大，用数学语言来说，使其期望值值最大，用数学语言来说，使其期望值最大。对每个电厂最大。对每个电厂 i ， 其年发电量的期其年发电量的期望值为望值为Ei(ki,Q) dFi(Q)设设 V为总投资额，为总投资额， Vi为各为各 水电厂的投资水电厂的投资，都是都是 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).主要内容主要内容非非 线性规划线性规划理论方面理论方面应用方面应用方面算法方面算法方面互补稳定灵敏互补稳定灵敏对偶问题对偶问题最优性最优性 条件条件无无 约束问题约束问题直接法直接法有约束问题有约束问题间接法间接法一般模型一般模型Min f(X)s.t. hi(X) = 0 (i=1,2,.m) （ P）gj(X) 0 (j=1,2.l)X En f(X) hi(X) gj(X) 为为 En上上的实函数。的实函数。几个概念几个概念定义定义 1 如果如果 X满足（满足（ P） 的约束条件的约束条件hi(X)=0 (i=1,2,.m)gj(X) 0 (j=1,2.l)则称则称 X En 为（为（ P） 的一个可行解的一个可行解。记（记（ P） 的所有可行解的集合为的所有可行解的集合为 D，D称为（称为（ P） 可行域。可行域。几个概念几个概念定义定义 2 X*称为（称为（ P） 的一个（整体）的一个（整体）最优解，如果最优解，如果 X* D， 满足满足f(X) f(X*)， X D。几个概念几个概念定义定义 3 X*称为（称为（ P） 的一个（局部）的一个（局部）最优解，如果最优解，如果 X* D， 且存在一个且存在一个 X*的邻域的邻域N(X* ,)= X En X- X* 0满足满足 f(X) f(X*)， X D N(X* ,) f(X)局部最优解局部最优解整体最优解整体最优解模型分类模型分类Min f(X)s.t. hi(X)=0 (i=1,2,.m) （ P）gj(X) 0 (j=1,2.l)X En f(X) hi(X) gj(X) 为为 En上上的实函数。的实函数。模型分类模型分类 1如果如果 f(X) hi(X) gj(X) 中至少有中至少有一个函数不是线性（仿射）函数，则一个函数不是线性（仿射）函数，则称（称（ P） 为非线性问题。为非线性问题。如果如果 f(X) hi(X) gj(X) 都是线性都是线性（仿射）函数，则称（仿射）函数，则称（ P） 为线性问为线性问题。题。模型分类模型分类 2o若若 m=l=0 ， 则称（则称（ P）为）为 无约束问题无约束问题。 （ P1） Min f(X)X En 模型分类模型分类 2o若若 m0， l=0 ， 则称（则称（ P） 为带等式为带等式约束问题。约束问题。 （ P2） Min f(X)s.t. hi(X)=0 (i=1,2,.m)X En 模型分类模型分类 2o若若 m=0， l 0 ， 则称（则称（ P） 为带不等为带不等式约束问题。式约束问题。 （ P3） Min f(X)s.t. gj(X) 0 (j=1,2.l)X En 模型分类模型分类 2o若若 m 0， l 0 ， 则称（则称（ P） 为一般为一般问题。问题。 （ P） Min f(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 0( 0 )则称则称 H(X)在在 X* 点正定点正定 (半正定半正定 ).海赛海赛 (Hesse)矩阵矩阵xxf(X) = H(X)2f/x12 2f/x1x2 2f/x1xn2f/x2x1 2f/x22 2f/x2xn2f/xnx1 2f/xnx2 2f/xn2=2 最优性条件最优性条件最优性条件的研究是非线性规划理论最优性条件的研究是非线性规划理论研究的一个中心问题。研究的一个中心问题。为什么要研究最优性条件？为什么要研究最优性条件？o本质上把可行解集合的范围缩小。本质上把可行解集合的范围缩小。o它是许多算法设计的基础。它是许多算法设计的基础。v无约束问题的最优性条件无约束问题的最优性条件（ P1） Min f(X)X En 定理定理 1（一阶必要条件）（一阶必要条件）设设 f(X)在在 X*点可微，则点可微，则 X*为（为（ P1）的的 一个局部最优解，一定有一个局部最优解，一定有f(X*)=grad f(X*)=0（ X*称为驻点称为驻点 ）v无约束问题的最优性条件无约束问题的最优性条件（ P1） Min f(X)X En 定理定理 2（二阶必要条件）（二阶必要条件）设设 f(X)在在 X*点二阶可微，如果点二阶可微，如果 X*为为（ P1） 的的 一个局部最优解，则有一个局部最优解，则有f(X*) =0 和和 H（ X* ） 为半正定。为半正定。v无约束问题的最优性条件无约束问题的最优性条件（ P1） Min f(X)X En 定理定理 3（二阶充分条件）（二阶充分条件）设设 f(X)在在 X*点二阶可微，如果点二阶可微，如果 f(X*) =0 和和 H(X*)为正定，为正定， 则则 X*为为 (P1) 的的 一个一个局部最优解。（局部最优解。（ H(X)在在 X*的邻域内的邻域内 为为半正定。半正定。v无约束问题的最优