运筹学12非线性规划-副本

《运筹学12非线性规划-副本》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、无约束条件下单变量函数寻优一、消去法原理：逐步缩小搜索区间，直至极值点存在的区间达到允许的误差范围为止。设要寻求f(X)的极小值点为X*，起始搜索区间为[a0,b0]。x1、x2[a0,b0]，且x2＜x1，计算f(x1)和f(x2)，并且比较结果：f(x)xoa0b0X*x1,x2在x*的右侧x1x2f(x)xoa0b0X*x1,x2在x*的左侧x1x2f(x)xoa0b0X*x1,x2在x*的两侧x1x2①x1,x2均在x*的右侧，f(x2)＜f(x1)，去掉[x1,b0]，此时x*[a0,x1]②x1,x2均在x*

2、的左侧，f(x2)＞f(x1)，去掉[a0,x2]，此时x*[x2,b0]③x1,x2均在x*的两侧，f(x2)＝f(x1)：a.去掉[x1,b0]，此时x*[a0,x1]b.去掉[a0,x2]，此时x*[x2,b0]二、黄金分割法(0.618法)：是一种常用的消去法与对分法、Fibonacci法比较，具有计算次数少，过程简单的特点。1、原理：LxL-xLx1x22、取点法则：Lx1x2a0b0L①f(x2)≤f(x1)，取[a1=a0,b1=x1]x’1=x2x’2=b1-(b1-a1)a1b1

3、x’1x’2②f(x2)＞f(x1)，取[a1=x2,b1=b0]x’1=a1+(b1-a1)x’2=x1a1b1x’1x’2计算n个点后，总缩短率为En=n-1＜，可得试点数n。3、计算步骤：求函数f(x)的极值点第一步：取初始区间[a0,b0]x1x2a0b0⑴若求f(x)的极小值点，则①f(x2)≤f(x1)，取[a1=a0,b1=x1]x’1=x2x’2=b1-(b1-a1)②f(x2)＞f(x1)，取[a1=x2,b1=b0]x’1=a1+(b1-a1)x’2=x1a1b1x’1x

4、’2a1b1x’1x’2⑵若求f(x)的极大值点，则①f(x2)≥f(x1)，取[a1=a0,b1=x1]x’1=x2x’2=b1-(b1-a1)②f(x2)＜f(x1)，取[a1=x2,b1=b0]x’1=a1+(b1-a1)x’2=x1第二步：求区间的缩短率例求解f(x)=-18x2+72x+28的极大值点，≤0.1，起始搜索区间为[0,3]解：①用间接法：令f’(x)=-36x+72=0，得驻点x=2又因为f’’(x)=-36＜0，故x=2为f(x)的极大值点，fmax=100②用直接法中的黄金分割法：令

5、n-1=，得n=1+(lg)/(lg)≈5.78442约6步即可，计算结果见下表：kakbkf(ak)f(bk)pk=bk-akpk/p0x1k=ak+·pkx2k=bk-·pkf(x2k)△f(x1k)0032882311.8541.14686.9＜99.62f(x)xo3x1x211.146386.9821.8540.6182.2921.85499.62＞98.4621.1462.29286.998.461.1460.3821.8541.58496.89＜99.6231.5842.29296.8998.460.

6、7080.2362.0221.85499.62＜99.9941.8542.29299.6298.460.4380.1462.1252.02299.99＞98.7251.8542.12599.6299.720.2710.09032、算法步骤：设S=f(X)=f(x1,x2)，极值点存在的区间为x1*[a1,b1]，x2*[a2,b2]第一步：从X(0)=(x1(0),x2(0))T出发①先固定x1=x1(0):求以x2为单变量的目标函数的极值点，得X(1)=(x1(0),x2(1))T，S(1)=f(X(1))②再固定x2=

7、x2(1):求以x1为单变量的目标函数的极值点，得X(2)=(x1(2),x2(1))T，S(2)=f(X(2))此时S(2)优于S(1)，且搜索区间缩短为x1*[x1(2),b1]，x2*[x2(1),b2]第二步：如此交替搜索，直至满足给定精度为止

8、f(X(k))-f(X(k-1))

9、＜或

10、S(k)-S(k-1)

11、＜ox1X(0)X(1)X(2)X(3)X(4)x2例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的极小值点，=0.01解：设起始点X(0)=(0,0)T，用变量轮换法计

12、算：①先固定x1=x1(0)=0:则f(0,x2)=x22-4x2+60，寻优得x2(1)=2于是X(1)=(x1(0),x2(1))T=(0,2)T，S(1)=f(X(1))=56②再固定x2=x2(1)=2:则f(x1,2)=x12-12x1+56，寻优得x1(2)=6于