运筹学课件

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

11运筹学李常敏上海大学管理学院E-mail:lcm@shu.edu.cn办公室:宝山东区427室上课时间:周四1-4地点:C1081Copyright@LiChangmin2课程介绍•教学目标:–掌握非线性规划的理论,包括基本概念、最优性条件。–理解非线性规划的几类经典的数值解法(无约束极值问题、约束极值问题)–能应用所学知识,进行基本的模型构建和数值分析23学习方式:–部分证明省略,以思路讲解为主;–阅读著名期刊上(见学院网站的重要期刊中的运筹学领域)的文章,并及时总结;–两周后定下一个自己感兴趣的专题,搜集资料,每周完善:•10月8日介绍该专题的实际背景、研究现状和未来的发展趋势,介绍1篇代表性论文;•10月22日根据你对该专题的了解,介绍1篇最新进展的英文学术论文,及自己的研究工作。34主要参考教材1.沈荣芳.运筹学高级教程(第二版),高等教育出版社,2008.2.陈开明.非线性规划.复旦大学出版社,1991.3.吴祈宗,候福均.运筹学与最优化方法(第二版),机械工业出版社,2013.4.BazaraaMS,SheraliHD,ShettyCM.Nonlinearprogramming:theoryandalgorithms.JohnWiley&Sons,2013.5.Bertsekas,DimitriP.Nonlinearprogramming.AthenaScientific,1999.5非线性规划在科学管理和其他领域中,大量应用问题可以归结为线性规划问题,但是,也有另外一些问题,其目标函数和(或)约束条件很难用线性函数表达。如果目标函数和(或)约束条件中包含有自变量的非线性函数,则这样的规划问题就属于非线性规划。一般来说,求解非线性规划问题比线性规划问题困难得多。而且,也不象线性规划那样有单纯形法这一通用的方法,非线性规划目前还没有适合于各种问题的一般算法,这是需要深入研究的一个领域。非线性规划研究核心问题:最优性条件(必要条件,充分条件,Lagrange乘子理论,灵敏性分析,对偶理论)迭代算法6解:设投资决策变量为问题归结为总资金的限制条件下,极大化总收益和总投资之比,数学模型为111max0..(1)0,(1,2,,)niiiniiiniiiiibxQaxaxAstxxin1,(i=1,2,…,n)0,iixi决定投资第个项目决定不投资第个项目例:投资决策问题某企业有n个项目可供选择投资,并且至少要对其中一个项目投资.已知该企业拥有总资金A元,投资于第i(i=1,2,…,n)个项目需要花资金ai元,并预计收益为bi元,试选择最佳投资方案使得总收益和总投资之比最大.7一般地,非线性规划的数学模型为min()xXfxmax()min()xXxXfxfx由于可转化为等价模型,故仅考虑极小化问题.其中X称为可行域,nXR可行域中的点称为可行点,f(x)称为目标函数12(,,,)Tnxxxx当时,非线性规划模型称为无约束问题;当时,非线性规划模型称为有约束问题nXRnXR使f(x)在X上取得最小值的点称为最优解,对应的目标函数值称为最优值定义:如果目标函数或约束条件中至少有一个是非线性函数,则称这种规划为非线性规划问题。8为统一起见,称以下模型minf(x)s.t.gi(x)≤0i=1,2,…,m(1)hj(x)=0j=1,2,…,l为标准的非线性规划模型,其中f(x),gi(x),hj(x)中至少有一个是x的非线性函数.称gi(x)≤0为不等式约束,hj(x)=0为等式约束.|()0,1,2,,;()0,1,2,ijDxgximhxjl满足所有约束条件的x称为可行解,所有可行解构成的集合称为可行域。9例:考虑如下非线性规划问题:minf(x,y)=[(x-14)2+(y-15)2]1/2s.t.(x-8)2+(y-9)2≤49x≥2,x≤13x+y≤24非线性规划的最优解未必在顶点处达到;非线性规划的最优解是一组同心圆最先与可行域相交的点,在可行域的边界上达到二维非线性规划问题的图解分析10例:请考虑如下非线性规划问题:minf(x,y)=(x-8)2+(y-8)2s.t.(x-8)2+(y-9)2≤49x≥2,x≤13x+y≤24非线性规划的最优解在可行域内部达到11可以看出,x2,x3,x4是局部最优解,且x3还是全局最优解,x2,x3是严格局部最优解,x4不是严格局部最优解.xf0x1x2x3x4x5f(x)D一个全局最优解一定是局部最优解,反之不真。对求极小化非线性规划问题,如果目标函数为凸函数,可行域为凸集,则局部最优解一定为全局最优解。与线性规划不同,非线性规划有局部最优解和全局最优解之分.12凸集i)定义——非空集合D称为凸集,如果对于任意的x1,x2D及任意实数a,0a1,有ax1+(1-a)x2∈D.凸集的几何意义:若一个集合是凸的,则该集合中任意两点的线段也必包含在此集合中。x1x2Dx1x2D凸集不是凸集凸集、凸函数和凸规划13(1)集合D={x∈Rn|Ax≤b,x≥0}是凸集。例:121112,,,,01,1,2,,1,.,,,nmiimmniiiiimxxxRimDxRxxDxxxx2设对任意的且则集合是凸集中的点叫做点的凸组合.(D称为多胞形或多面体)定理:设D1,D2是Rn中的凸集,则11121212121,.2,..3.DxxDDDxyxDyDDDDD是凸集其中是实数是凸集也是凸集是凸集14凸函数与凹函数定义:D为凸集,若对任意x1,x2D及任意实数a,0≤a≤1有f(ax1+(1-a)x2)≤af(x1)+(1-a)f(x2)则称f(x)为凸函数;若≤变为,称f(x)为严格凸函数。若上式中的≤()变为≥(),则称f(x)为凹函数/严格凹函数。凸函数的特征是,曲线上任意两点的连线总是位于这两点间曲线的上方。15凸函数的判定(一阶条件):设f(x)在凸集D上有一阶连续导数,则f(x)是D上凸函数的充要条件是对任意两点x,z∈D,x≠z,必有()()()()Tfzfxfxzx如果上式严格成立,则是严格凸函数的充要条件。几何意义:凸函数f(x)在曲线上任何一点做曲线的切线,那么f(x)都在切线上方。16(二阶条件):设D是一个非空开凸集,设f在D上二次可微,则f(x)是凸函数,当且仅当对所有x∈D,Hessian矩阵是半正定矩阵;2()fx注意:Hessian矩阵在D中的每一点都是正定的,则f是严格凸的;可是,如果f是严格凸的,则Hessian矩阵在S中的每一点都是半正定的。上述定理在检验函数的凹凸性是有效的,特别是当函数为二次函数时,Hessian矩阵不依赖点x,因此检验其凸性简化为检验一个单一矩阵的特征值的非负性。17例:检验函数f(x1,x2)=2x1+6x2-2x12-3x22+4x1x2是凸的,凹的。或者两者都不是。解:将f改写为下面更方便的形式:11121222441(,)2,6,462xxfxxxxxx以下通过解下面的方程来计算特征值2440det()det(4)(6)1646108HI方程的解为12517517.Hf和,故为负定矩阵,为凹函数18凸规划定义:已知非线性规划若可行域D是凸集,且f(x)是定义在D上的凸函数,则该非线性规划称为凸规划。min()..()0,1,2,,()0,1,2,,ijfxstgximhxjp定理:对非线性规划,如果gj(x)(i=1,2,…,m)是Rn上的凸函数,hj(x)(j=1,2,…,p)为线性函数,且f(x)为可行域D上的凸函数,则该非线性规划问题是凸规划。(作业1)19定理1:设D为非空凸集,f(x)连续,考虑如下问题(1)如果f是凸函数,则局部最优解也是全局最优解;(2)如果f是严格凸函数,则x*为唯一的全局最优解。min()xDfx20定理(最优性条件):考虑凸规划,(1)x*是最优解的充要条件是对x∈X,有(2)若D是开集,x*是最优解的充要条件是min()xXfx**()()0Tfxxx*()0.fx由定理结论(1)可知,如果某点x*是最优解,则对任意x∈D,向量x-x*与函数f在点x*处的梯度向量所成的角度小于90。.*()fx21例:考虑如下非线性规划问题:22121212123min()()(5)22..23110,0fxxxxxstxxxx试验证最优性条件成立。分析:题意是要求验证非线性规划的最优解x*满足**()()0,.TfxxxxD对任意的22(1,3)(0,2)(0,0)11(,0)22x1x3(,5)2(1,3)(1,4)Tf解:显然,目标函数是凸函数,且约束条件为线性函数,故此规划问题为凸规划.22123()()(5)2fxxx点x*=(1,3)T是唯一最优解.由于f在点(1,3)的梯度为从图中可以看出,向量与所成的角度小于等于90。.(1,3)(1,4),Tf(1,4)T12(1,3)Txx23而对点(0,0)T而言,显然不是最优解。因为(0,0)(3,10),Tf对任意非零点x∈D,有-3x1-10x20,即向量(x1-0,x2-0)T与所成角度大于90。,不满足最优性条件,原点不会是最优解。为使目标函数值下降,最好的局部下降方向是(0,0)f(0,0)(3,10),Tf3(,5)2(1,3)(0,2)(0,0)11(,0)22x1x(0,0)(3,10)Tf24***1**1,,0,01,,.nniiiiixxxfxxxxinx(1)点为局部极小解的必要条件是,***,,,1,0.jjiiifxixxjixxix(2)固定令有,******10,,,,0200.ijjiiiiifxxxxjixxxfxxx(3)如果令则有,于是,有,如果思考题:如果某凸规划的可行域为D={x|x≥0},请讨论此凸规划问题的最优解的充要条件的形式。25无约束问题一阶二阶必要和充分条件等式约束问题Lagrange乘子理论一般约束问题一阶二阶必要和充分条件最优性条件26二阶必要条件:设f:Rn→R1在点x*∈Rn处二阶可微,如果x*是局部极小解,则▽f(x*)=0,且▽2f(x*)为半正定矩阵.对无约束极值问题minf(x),x∈Rn(1)一阶必要条件:设f:Rn→R1在点x*∈Rn处可微,如果x*是局部极小点,则▽f(x*)=0.27定义:设f:Rn→R1在点x*处可微,若▽f(x*)=0,称x*为函数f的驻点.驻点极小点驻点极大点驻点拐点fOx10,(0,),(')('),'.nfRRpntfxtpfxpfx定义:设:,为维非零向量,若存在对有则称向量是在点处的下降方向281'(')0,'.nnTfEExpEfxppfx定理:设:在点处可微,若存在使得则向量是在点处的下降方向''0,fxfxTaylort证明:由条件在点处可微,根据在点处的展式,对于任意的有(')(')(')()Tfxtpfxtfxpotp(')00,0,(0,),Tfxptt由于和于是存在对任意的有(')()0Ttfxpotp(')('),'.fxtpfxpfx于是有即是在点处的下降方向(')fx(')fxp'x()fx29对无约束极值问题minf(x),x∈Rn(1)定理(一阶必要条件):设f:Rn→R1在点x*∈Rn处可微,如果x*是局部极小点,则▽f(x*)=0.**()0(),fxpfx证明:(反证法)假设,取则有2****(

1 / 55
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功