数模(非线性规划模型)

1数学模型电子教案重庆邮电大学数理学院沈世云2第四章非线性规划一、非线性规划引例线性规划和整数规划它们的目标函数和约束条件都是自变量的线性函数，在实际中还有大量的问题，其目标函数或约束条件很难用线性函数来表示。如果目标函数或约束条件中含有非线性函数，则称这种规划问题为非线性规划问题。先看两个实例。问题1容器设计问题问题提出某公司生产贮藏用容器，订货合同要求该公司制造一种敞口的长方体容器，容积为12立方米，该容器的底为正方形，容器总重量不超过68公斤。已知用作容器四壁的材料为每平方米10元，重3公斤；用作容器底的材料每平方米20元，重2公斤。试问制造该容器所需的最小费用是多少？321,xx21212040)(minxxxXf0,6821212212121221xxxxxxx模型建立设该容器的底边长和高分别为则问题的数学模型为4问题2营业计划的制定问题提出某公司经营两种设备，第一种设备每件售价30元，第二种设备每件售价450元。据统计，售出一件第一种设备所需要的营业时间平均是0.5小时，第二种设备是)25.02(2x小时，其中2x是第二种设备的售出数量。已知该公司在这段时间内的总营业时间为800小时。试决定使其营业额最大的营业计划。模型建立设该公司计划经营第一种设备1x件，第二种设备2x件。其数学模型为2145030)(maxxxXfs．t．0,800)25.02(5.021221xxxxx5定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题．二非现性规划的基本概念一般形式:（1）其中，是定义在En上的实值函数，简记:Xfmin.,...,2,10m;1,2,...,0..ljXhiXgtsjinTnExxxX,,,21jihgf,,1nj1ni1nE:h,E:g,E:EEEf其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式．6定义1把满足问题（1）中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即问题(1)可简记为．njiEXXhXgXD,0,0|)(nEXXfDXmin定义2对于问题(1)，设，若存在,使得对一切，且，都有，则称X*是f(X)在D上的局部极小值点（局部最优解）．特别地当时，若，则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）．DX*0DX*XX*XXXfXf*XfXf*定义3对于问题(1),设,对任意的,都有则称X*是f(X)在D上的全局极小值点（全局最优解）．特别地当时，若，则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）．DX*DXXfXf**XXXfXf*7定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题．非现性规划的基本概念一般形式:（1）其中，是定义在En上的实值函数，简记:Xfmin.,...,2,10m;1,2,...,0..ljXhiXgtsjinTnExxxX,,,21jihgf,,1nj1ni1nE:h,E:g,E:EEEf其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式．8定义1把满足问题（1）中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即问题(1)可简记为．njiEXXhXgXD,0,0|)(nEXXfDXmin定义2对于问题(1)，设，若存在,使得对一切，且，都有，则称X*是f(X)在D上的局部极小值点（局部最优解）．特别地当时，若，则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）．DX*0DX*XX*XXXfXf*XfXf*定义3对于问题(1),设,对任意的,都有则称X*是f(X)在D上的全局极小值点（全局最优解）．特别地当时，若，则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）．DX*DXXfXf**XXXfXf*901010-1..)(min2121222121xxxxtsxxxxf，线性规划问题：用图解法求解下面的非三.非线性规划的图解法10三角形表示的是可行域。同心圆表示的是目标函数的等值线。最优解为（1/2，1/2）最优值为1/2问题：(1/2,1/2)是整体的还是局部的？是严格的还是非严格的？1/21/2112、非线性规划方法概述微分学方法的局限性：实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，微分学方法不易处理。12数值方法的基本思路：迭代给定初始点x0根据x0,依次迭代产生点列{xk}{xk}的最后一点为最优解{xk}有限{xk}无限{xk}收敛于最优解13迭代格式xkxk+1kxkkkxxx1pkkkkptxkkkxxx1称pk为第k轮搜索方向，tk为第k轮沿pk方向的步长。产生tk和pk的不同方法，形成了不同的算法。14，使若存在设0,0,,,:1pRpRxRRfnnn),0(),()(txftpxf处的下降方向。在点是函数则称向量xxfp)(处下降最快的方向。在就是可导，则在若xxfxfxxf)()(-)(定义：下降方向15，使得若存在设0t,0,,,pRpXxRXnnXtpx的可行方向。关于处是点则称向量Xxp定义解非线性规划问题，关键在于找到某个方向，使得在此方向上，目标函数得到下降，同时还是可行方向。这样的方向称为可行下降方向。16第二节凸函数和凸规划1、凸函数及其性质：）有，（若对是非空凸集，设10,:1RSfRSn定义上是凸的。在上的凸函数，或是则称SSff121212((1))()(1)(),,fxxfxfxxxS若上是严格凸的。在上的严格凸函数，或是则称SSff凹的。严格上是在或凹函数严格上的是凸函数，称严格上的是若)(S,)(S)(Sfff121211fXXfXfX1XS2XS，17是非空凸集设nRS定理:上的凸函数；是，则上的凸函数，是若S0S)1(ff上的凸函数。是上的凸函数是若S,S,)2(2121ffff关于凸函数的一些结论定理:则集合是凸函数是非空凸集设,,,1RcfRSncxfSxcfHS)(|),(是凸集。函数f在集合S上关于c的水平集18则可微：是非空开凸集，设,S1RSfRn条件是上的凸函数的充分必要是）（S1fSxxxfxfxxxfT2112121,),()()()(处的梯度。是函数在点）（11111)(,)()(xxxfxxfxfTn定理条件是上的严格凸函数的充要是）（S2f212112121,,),()()()(xxSxxxfxfxxxfTn=1时几何意义：可微函数是凸的等价于切线不在函数图像上方。19定理逆命题不成立）凸函数（此时上的严格是上是正定矩阵时，在当上是半正定的。在是上的凸函数的充要条件是则二阶连续可导是非空开凸集设,)(S)(,:,S221SfSxfxfSfRSfRnnnnnxxxfxxxfxxxfxxxfxfHessexf)(...)(......)(...)()()(2121211222矩阵，称为20,,10,,10..miniqjxhpixgtsxfj）（）（）（2、凸规划及其性质：,,10,,10qjxhpixgRxXjin）（）（简称凸规划。）为非线性凸规划称（上的凸函数是是凸集若,,,MPSfX凸规划定义：21定理）是凸规划。（上的凸函数，则是并且皆为线性函数，上的凸函数皆为若）（）（）（对于非线性规划MPXfxhRxqjxhpixgtsxfMPjnij)(,)(g,,10,,10..min),(i凸规划性质：定理凸规划的任一局部最优解都是它的整体最优解。凸规划是以后重点讨论的一类非线性规划凸函数线性函数22第三节一维搜索方法t为实数一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为：(t)min0t什么叫一维搜索问题？(t)minmax0tt或一般一维搜索问题有效一维搜索问题23一维搜索问题的算法分类：精确一维搜索（最优一维搜索）非精确一维搜索（可接受一维搜索）本节内容：两种精确一维搜索方法：0.618法，Newton法。两种非精确一维搜索方法：Goldstein法,Armijo法。241、0.618法（近似黄金分割法）问题：凸函数是不是单谷函数？严格凸函数是不是单谷函数？单谷函数是不是凸函数？上的单谷函数为称上严格递增且在上严格递减在使得函数如果],[)(,],[,],[)(],,[batbttatbat的单谷区间。称为)(],[tba单谷函数上唯一的极小点。在为显然此时],[)(batt25搜索法求解：(t)min0t(t)minmax0tt或基本过程：给出[a,b],使得t*在[a,b]中。[a,b]称为搜索区间。迭代缩短[a,b]的长度。当[a,b]的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。26假定：已经确定了单谷区间[a,b](t)min0t(t)minmax0tt(t)minbta)(1t)(2tt)(1t)(2ttt1t2ababt1t2新搜索区间为[a,t2]新搜索区间为[t1,b]27区间缩小比例的确定：区间缩短比例为(t2-a)/(b-a)缩短比例为(b-t1)/(b-a)缩短比例满足：每次插入搜索点使得两个区间[a,t2]和[t1,b]相等；每次迭代都以相等的比例缩小区间。618.0215缩短比例0.618法)(1t)(2t)(1t)(2tt1t2ababt1t2退出前一页后一页28确定[a,b],计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解题步骤：)()(21tt是否at2是停止，输出t1否以[a,t2]为新的搜索区间1tb是停止，输出t2否以[t1,b]为新的搜索区间29例：5.0],3,0[12)(min30精度其中单谷区间求解tttt解：t1t2)(1t)(2t30t1、第一轮：t1=1.146,t2=1.8546648.3)(,2131.0)(21ttt2－00.5302、第二轮：t2=1.146,t1=0.7082131.0)(0611.0)(21ttt2－0=1.1460.53、第三轮：t1=0.438,t2=0.7082082.0)(0611.0)(12ttb-t1=1.146-0.4380.51.8540tt2t11.4160tt2t1314、第四轮：t2=0.876,t1=0.7080798.0)(0611.0)(21ttb-t1=1.146-0.7080.5输出：t*=t2=0.876为最优解，最优值为-0.079801.416tt1t2322、Newton法0)()(),(minttt二次可微，其中考虑Newton法基本思想：用探索点tk处的二阶Taylor展开式近似代替目标函数，以展开式的最小点为新的探索点。2))((21))(()(