运筹学资料5非线性规划.pptx

会计学 1 运筹学资料5非线性规划 1 引 言 非线性规划是运筹学中包含内容最多，应用最广泛的一个分支，计算远比线性规划复杂，由于时间的限制，只能作简单的介绍。 例6-1 电厂投资分配问题 水电部门打算将一笔资金分配去建设n个水电厂，其库容量为ki,i=1,2….n,各 第1页/共51页 电厂水库径流输入量分布为Fi(Q)，发电量随库容与径流量而变化，以Ei(ki,Q)表示。计划部门构造一个模型，即在一定条件下，使总发电量年平均值最大，用数学语言来说，使其期望值最大。对每个电厂i ，其年发电量的期望值为 Ei(ki,Q) dFi(Q) 设V为总投资额，Vi为各水电厂的投资， 第2页/共51页 都是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). 第3页/共51页 主要内容 非线性规划 理论方面 应用方面 算法方面 互补稳定灵敏 对偶问题 最优性条件 无约束问题 直接法 有约束问题 间接法 第4页/共51页 一般模型 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上的实函数。 第5页/共51页 几个概念 定义1 如果X满足（P）的约束条件 hi(X)=0 (i=1,2,….m) gj(X)  0 (j=1,2….l) 则称X  En 为（P）的一个可行解。 记（P）的所有可行解的集合为D， D称为（P）可行域。 第6页/共51页 几个概念 定义2 X*称为（P）的一个（整体）最优解，如果X* D，满足 f(X)  f(X*)， X D。 第7页/共51页 几个概念 定义3 X*称为（P）的一个（局部）最优解，如果X* D，且存在一个X*的邻域 N(X* ,)= X  En X- X*  0 满足 f(X)  f(X*)，  X D N(X* ,) 第8页/共51页 f(X) 局部最优解 整体最优解 第9页/共51页 模型分类 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上的实函数。 第10页/共51页 模型分类1 如果 f(X) hi(X) gj(X) 中至少有一个函数不是线性（仿射）函数，则称（P）为非线性问题。 如果 f(X) hi(X) gj(X) 都是线性（仿射）函数，则称（P）为线性问题。 第11页/共51页 模型分类2 若m=l=0 ，则称（P）为无约束问题。 （P1） Min f(X) X  En 第12页/共51页 模型分类2 若m0，l=0 ，则称（P）为带等式约束问题。 （P2） Min f(X) s.t. hi(X)=0 (i=1,2,….m) X  En 第13页/共51页 模型分类2 若m=0，l  0 ，则称（P）为带不等式约束问题。 （P3） Min f(X) s.t. gj(X)  0 (j=1,2….l) X  En 第14页/共51页 模型分类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 第15页/共51页 凸函数的概念 凸集概念： 设D是n维线性空间En的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。