非线性的规划.pptx

非线性规划 主讲人 虞继敏;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)=V V1(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* ,?) ;;模型分类 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）为线性问题。;模型分类2 若m=l=0 ，则称（P）为无约束问题。 （P1） Min f(X) X ? En ;模型分类2 若m?0，l=0 ，则称（P）为带等式约束问题。 （P2） Min f(X) s.t. hi(X)=0 (i=1,2,….m) X ? En ;模型分类2 若m=0，l ? 0 ，则称（P）为带不等式约束问题。 （P3） Min f(X) s.t. gj(X) ? 0 (j=1,2….l) X ? En ;模型分类2 若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?1 使得 x= ? x(1)+(1- ?)x(2) ∈ D,则称D为凸集;凸函数的概念 定义：定义在凸集D?En上的函数f(X) 如果对任意两点x(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上的严格