第十讲--非线性规划(一)(运筹学基础-清华大学-王永县)解析PPT课件.ppt
《第十讲--非线性规划(一)(运筹学基础-清华大学-王永县)解析PPT课件.ppt》由会员分享,可在线阅读,更多相关《第十讲--非线性规划(一)(运筹学基础-清华大学-王永县)解析PPT课件.ppt(48页珍藏版)》请在咨信网上搜索。
1、Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 1 13/6/20243/6/2024第二十一讲第十讲第十讲 非线性规划(一)非线性规划(一)1非线性规划问题的现实来源问题的提出2非线性规划的数学模型及特点3解和算法的基本性质4非线性规划求解方法分类Operations Research Operations Research Prof.Wang Prof.Wang School of
2、 Economics&ManagementSchool of Economics&Managementpage page 2 23/6/20243/6/2024第二十一讲1 非线性规划问题的现实来源问题的提出(1)在规划模型中,如果在目标函数或在约束条件中有一个或多个是自变量的非线性函数,则称这种规划为非线性规划问题。就现实问题,严格讲来,基本属于非线性规划模型。现举例说明非线性规划的现实背景。例4-1某公司经营两种设备。第一种设备每件售价为30元,第二种设备每件售价为450元。且知,售出第一、二种设备分别需时为每件约0.5小时和(2+0.25x2)小时,其中x2为第二种设备售出数量。公司的总
3、营业时间为800小时。求:公司为获取最大营业额(销售额)的最优营业计划。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 3 33/6/20243/6/2024第二十一讲1 非线性规划问题的现实来源问题的提出(2)解设公司应经营销售第一、二种设备数额分别为x1件和x2件,追求的目标为最大销售额,即:目标函数f(X)=30 x1+450 x2取极大由于营业时间有限,必须满足:0.5x1+(
4、2+0.25x2)x2800当然,销售设备数不会为负数,即:x10,x20综合得出该问题数学模型为:目标函数max:f(X)=30 x1+450 x2约束条件0.5x1+2x2+0.25x22800 x10,x20Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 4 43/6/20243/6/2024第二十一讲2 非线性规划的数学模型及特点(1)非线性规划的数学模型通常表示成以下形式。m
5、inf(X)hi(X)=0i=1,2,mgj(X)0j=1,2,l例4-3求解下述非线性规划minf(X)=(x12)2+(x22)2 h(X)=x1+x26=0Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 5 53/6/20243/6/2024第二十一讲显然,与直线AB相切的点必为最优解。图4-1(a)中的D点即为最优点,此时目标函数值为:f(X*)=2,x1*=x*2=3A f(
6、X)=4f(X)=2x1x263202 36BCD图4-1(a)2 非线性规划的数学模型及特点(2)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 6 63/6/20243/6/2024第二十一讲例4-4非线性规划为minf(X)=(x12)2+(x22)2h(X)=x1+x260显然,此时的最优解为C点(x1*=x2*=2,f(X*)=0),该点落在可行或内部,其边界约束失去作用。从
7、前面例中看出,非线性规划的最优解(如果存在)可在其可行域上任一点达到。因而,非线性规划数学模型可以没有约束条件,即存在无约束最优化问题。2 非线性规划的数学模型及特点(3)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 7 73/6/20243/6/2024第二十一讲3 解和算法的基本性质(1)1极小点、凸集及其关系极小点定义i)对于X*Q,如果存在一个 0,使所有与X*的距离小于 的
8、XQ(即XQ,且|XX*|f(X*),则称X*为f在Q上的一个严格相对极小点。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 8 83/6/20243/6/2024第二十一讲3 解和算法的基本性质(2)ii)点X*Q,如果对于所有XQ成立f(X)f(X*),则称X*为f在Q上的全局极小点。同样,若对于所有XQ,XX*时,存在f(X)f(X*),则称X*为f在Q上的严格全局极小点。尽管问
9、题的提法往往求全局极小点,然而,无论从理论上或从计算观点看,实践现实性表明我们必须以很多情形上满足一个相对极小点。当然,对于凸规划,这二者是统一的。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 9 93/6/20243/6/2024第二十一讲3 解和算法的基本性质(3)相对极小点的判定可行方向概念:沿给定方向作离开该点运动,若运动轨迹在可行域内,则称该运动方向为可行方向(通常用d表示
10、)。若从某点开始,沿任一可行方向运动(运动距离很小)都不能使目标函数减少,则据定义,知该点即为相对极小点。i)判定极小点的必要条件(证明从略)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 10103/6/20243/6/2024第二十一讲3 解和算法的基本性质(4)命题1(一阶必要条件):设是En子集,f(X)C1(C1表明存在一阶导数)是上函数,若X*是f(X)在上一个相对极小点,
11、则对于任一X*的可行方向dEn必有f(X*)d0。(其中,f(X*)表示函数f(X)的一阶梯度或导数)命题2(二阶必要条件有约束情况):设是En的一个子集,且f(X)2(2表明存在二阶导数)是上的一个函数。若X*是f(X)在上的一个相对极小点。则对于任一X*处的可行方向dn有:A)f(X*)d0B)f(X*)d=0,则必有dT2 f(X*)d02 f(X)表示f(X)的第二阶梯度或二阶导数,又称Hess或海森阵,亦可用H或F表示。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&Man
12、agementSchool of Economics&Managementpage page 11113/6/20243/6/2024第二十一讲3 解和算法的基本性质(5)命题3(二阶必要条件无约束情况):设X*是集合的内点,且X*是函数f(X)C2在上一个相对极小点。则:A)f(X*)=0B)对于所有d,则dT2 f(X*)d0ii)判断极小点的充分条件命题(二阶充分条件无约束):设f(X)C2是定义在以X*为内点的一个区域上的函数,若A)f(X*)=0B)Hess阵H(X*)正定(或负定)则X*是f(X)的严格极小点(或极大点)Operations Research Operations
13、Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 12123/6/20243/6/2024第二十一讲3 解和算法的基本性质(6)iii)极小点的充分必要条件无约束情形。(略)凸函数与凹函数i)定义:凸集:若在X集合中,任意两点之联线都落在该集合内,则称该集合为X的凸集。凸函数:定义在凸集上的函数f(X)称为凸函数,条件是对于每一对x1,x2及每一个a,0a1存在:f(ax1+(1a)x2)a f(x1)+1(1a)f(x2)上式中,若变为,则称为严
14、格凸函数。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 13133/6/20243/6/2024第二十一讲3 解和算法的基本性质(7)凸函数在2维空间的形状象一口锅的纵剖面,参见图4-2。凹函数:定义在凸集上的函数g(X)称为凹函数,条件是函数f(X)=g(X)是凸的。若g(X)是严格凸的,则g(X)是严格凹的,因此凸与凹是严格对应的,以后就只研究凸函数即可。(a)严格凸x凸x非凸x
15、图4-2(b)(c)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 14143/6/20243/6/2024第二十一讲3 解和算法的基本性质(8)ii)有关性质(凸函数性质)设f1(X),f2(X)是凸集上的凸函数,则函数f1(X)+f2(X)在上也是凸函数。设f(X)是凸集上的凸函数,则对任意的a0,函数af(X)是凸的。设f(X)是凸集上的凸函数,对每一个实数C,则集合Cx:x,f
16、(X)C是凸集。iii)凸函数的判定(略)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 15153/6/20243/6/2024第二十一讲3 解和算法的基本性质(9)凸规划定义:已知非线性规划:minf(X)gj(X)0若f(X)为凸函数,gj(X)为凹函数,则称该规划为凸规划。凸规划的局部极值点即为全局极值点。线性规划为凸规划。2下降算法的收敛性问题(定性分析)(略)Operati
17、ons Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 16163/6/20243/6/2024第二十一讲4 非线性规划求解方法分类(1)1一维最优化斐波那契(Fibonacci)法黄金分割法(0.618法)牛顿法(切线法)抛物线逼近法成功和失败法Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&M
18、anagementSchool of Economics&Managementpage page 17173/6/20243/6/2024第二十一讲4 非线性规划求解方法分类(2)2多维最优化无约束情形(i)采用导数:(a)梯度法(b)牛顿法(c)共轭梯度法(d)变尺度法Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 18183/6/20243/6/2024第二十一讲4 非线性规划求解
19、方法分类(3)(ii)不采用导数:(a)直接法(模式搜索法)(b)可变多面体法(c)鲍威尔法(d)随机搜索法Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 19193/6/20243/6/2024第二十一讲4 非线性规划求解方法分类(4)有约束情形(i)线性逼近法(ii)可行方向法(iii)罚函数法(iv)可变容差法非线性规划的求解方法很多,上面列出的仅是一些常用的方法。后面将简单介绍
20、几个最基本解法的思路和步骤。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 20203/6/20243/6/2024第二十一讲第十讲第十讲 非线性规划(二)非线性规划(二)1一维最优化方法2多维无约束寻优方法(使用导数)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&Mana
21、gementSchool of Economics&Managementpage page 21213/6/20243/6/2024第二十一讲1 一维最优化方法(1)目前常用的一些方法有:斐波那契(Fibonacci)法序贯试验法黄金分割法(0.618法)牛顿切线法抛物线逼近法成功与失败试探法下面将着重介绍斐波那契与黄金分割法的主要思路及步骤。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage pa
22、ge 22223/6/20243/6/2024第二十一讲1 一维最优化方法(2)一、斐波那契法与黄金分割法的基本思路1非线性规性的所有求解方法在理论上都是寻找出局部极值点,即所搜寻区域是单峰函数。当然,作为一维搜索方法的斐波那契法与黄金分割法亦不例外。然而,这两种方法的寻优途径不是直接找出最优点,而是不断缩小最优点所处区域,直到符合精度为止。这两种方法的主要特点为:适于单峰(谷)函数;压缩峰(谷)点所处的区域。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSch
23、ool of Economics&Managementpage page 23233/6/20243/6/2024第二十一讲1 一维最优化方法(3)现在分析该法是如何进行寻优的:设已知单峰函数f(t)的峰点t*(最小点)处在t=a,b区间(见图4-3a)在区间a,b中,任取两点a1、b1且a1b1,并计算f(a1)和f(b1),则可出现下列结果:1)f(a1)f(b1),则t*必在区间a,b1,如图4-3中(a)所示。2)f(a1)f(b1),则t*必在a1,b中。如图4-3(b)所示。Operations Research Operations Research Prof.Wang Prof
24、.Wang School of Economics&ManagementSchool of Economics&Managementpage page 24243/6/20243/6/2024第二十一讲1 一维最优化方法(4)0ab2t*a1b1bt f(t)(a)0a a1t*b1bt图4-3 f(t)f(t)f(t)(b)可见,只要在a,b内任取两点,就必能把t*压缩在区间a,b1或a1,b内。若要继续缩小区间,只需再计算1个点,又可缩短一部分区间长度。Operations Research Operations Research Prof.Wang Prof.Wang School of
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十 非线性 规划 运筹学 基础 清华大学 王永县 解析 PPT 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。