最优化例题讲解

1、例1用单纯形法解下列问题：minx一2x+x123s.tx+x一2x+x=10,1234TOC o 1-5 h z HYPERLINK l bookmark8 o Current Document 2x一x+4x8,123x+2x4x0,j=解：将原问题化成标准形：max一x+2x一x123 HYPERLINK l bookmark6 o Current Document s.tx+x一2x+x=10,12342xx+4x+x=8, HYPERLINK l bookmark18 o Current Document 1235一x+2x一4x+x=4, HYPERLINK l bookmark2

2、0 o Current Document 1236x0,j=1,6.jx4与添加的松弛变量x5,x6在约束方程组中其系数列正好构成一个3阶单位阵，它们可以作为初始基变量，初始基可行解为X=(0,0,0,10,8,4)T列出初始单纯形表，见表1。表1-12I-1000CB基bx1x?Jx3x4x5x60 x41011-21000 x582-14010044-12-40010-12-1000由于只有。2，说明表中基可行解不是最优解，所以确定x2为换入非基变量；以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定2为主元素(表1中以防括号甘舌起)，意味着将以非基

3、变量x2去置换基变量x6,采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x2的系数列(1,-1,2)t变换成x6的系数列(0,0,1)t，变换之后重新计算检验数。变换结果见表2。表2-12-1,000Cb基bx1x2x3,rx4x5x60 x483/20010-1/20 x5103/202011/22x22-1/21-2001/2c/-z/400300-1检验数。3=30,当前基可行解仍然不是最优解。继续“换基”，确定2为主元素，即以非基变量x3置换基变量x5。变换结果见表3。表3-12-1000CB基bx1x2x3x4x5x60 x483/20010-1/2-1x353/40101

4、/21/42x212110011c厂勺19-9/4000-3/2-7/4此时，3个非基变量的检验数都小于0，。=-9/4，。5=-3/2，。5=刁/4，表明已求得最优解：X*=(0,12,5,8,0,0)t。去除添加的松弛变量，原问题的最优解为：X*=(0,12,5,8)t,最小值为-19例2用大M法求解下列问题：minx+x3x123s.x2x+x3,123x-2x=1,13x0,j=1,3.解引进松弛变量x4、剩余变量x5和人工变量x6、x7，解下列问题:minx+x-3x+0 x+0 x+M(x+x)TOC o 1-5 h z234567 HYPERLINK l bookmark28 o

5、 Current Document s.tx-2x+x+x=111234 HYPERLINK l bookmark30 o Current Document x+x4xx+x=312356x2x+x=1 HYPERLINK l bookmark32 o Current Document 137x0,j二1,2,匸j用单纯形法计算如下：表111-300MMCb基bx1x2x3x4x5x6x70 x411Jr-211000Mx6321-40-110M110-20001C眄4M1-3M1-M-3+6M0M00由于Oo20，说明表中基可行解不是最优解，所以确定x1为换入非基变量；以兀的系数列的正分量对

6、应去除常数列，最小比值所在行对应的基变量作为换出的基变量。0=min(11,-,1)=1=丄1211因此确定1为主元素(表1中以防括号括起)，意味着将以非基变量X去置换基变量x7，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将X1的系数列(1,2,1)t变换成x7的系数列(0,0,1)t，变换之后重新计算检验数。变换结果见表2。表2Cjf11-300MMCB基bX1X2,X3X4X5X6X70X4100-23100-1M*10100-11-21X1110-20001c內M+101-M-10M03M-1由于230，说明表中当前基可行解仍不是最优解所以确定x2为换入非基变量；以x2的系数

7、列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素，意味着将以非基变量X2去置换基变量x6,采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将X2的系数列(-2,1,0)t变换成x6的系数列(0,1,0)T,变换之后重新计算检验数。变换结果见表3。表311-300MMCB基bX1X2卜x4X5X6X70J4120031-22-51X210100-11-21X1110-20001200-101M-1M+1由于只有O32,12x一x1,12x0125第一阶段用单纯形法求解第一阶段的线性规划问题：minrn二x+x67s.t.x+x一x+x二21236x一

8、x一x+x二11247x+x二315x,x，x0127求解过程见表1。表1Cjf0000011CB基bx1x2x3x4x5x6x71x6211-100101x711-10-10010 x531000100c-zj3-20110001x6102-1101-10 xi11-10-10010 x52010110-1CT10-21-10120 x21/201-1/21/201/2-1/20 xi3/210-1/2-1/201/21/20 x53/2001/21/21-1/2-1/2CP00000021313因此，第一阶段求得最优解为(x,x,x,x,x)T=(；,0,0,；)T，基变量为x2和1234

9、522212x5，不包含人工变量。第二阶段以第一阶段的最终单纯形表为基础，除去人工变量x6、x7及其系数列，恢复目标价值向量为C=(2,-1,0,0,0)T,重新计算检验数，继续迭代，见表2。表2C厂-21000CB基bx1x2x3x4x51x21/201-1/210-2xi3/210-1/2-1/200 x53/2001/21/21-5/200-1/2-3/200 x4102-110-2xi211-1000 x310-1101-403-2000 x201011-2x13100010 x310-1101-601002因此，求得原问题的最优解为(x1,x2,x3，佇x5)t=(3,0，1，2,0

10、)T，最大目标函数值为6。例4用KT条件求下列问题minf(x,x)=(x-1)2+(x-2)21212s.tx+x-2012-x01-x02x+x1=012解该问题的Lagrange函数是L(X,入，卩)=(x1)2+(x2)2入(xx+2)入x入x+卩(x+x1)TOC o 1-5 h z HYPERLINK l bookmark79 o Current Document 12112213212由于-=2(x1)+九一九一卩 HYPERLINK l bookmark115 o Current Document dx1121-=2(x2)+九一九+卩 HYPERLINK l bookmark

11、117 o Current Document dx2132故该问题的KT条件是2(x1)+九一九一卩二01122(x2)+i九+=0213入(xx+2)=00123作为KT点，除满足上述条件，自然还应满足可行性条件x+x2W0120,x012为使求解易于进行，从互补松紧条件入手讨论：1设x丰0,x丰0,九=0121由互补松紧条件知九=九=0,由KT条件知322(x1)卩=0,2(x2)+卩=012再由可行性条件-x+x1=0得到x=1,x=2,R=0,但是显然不满足可行性1212x+x20,故此解舍弃。122设九丰01由互补松紧条件知x+x2=0,再加上可行性条件x+x1=0知121213x=

12、,x=，从而由互补松紧条件知九=九=0，将已知值代入易得九=1，R=0，122223113易知这时KT条件和可行性条件满足，因而X*=(牙，)T为KT点。易见f(x,x)和2212g(x,x)=x+x2为凸函数，h(x,x)=x+x1是线性函数，所以由定理3.611212121213知x*=(20要求最后区间精度=0.5。解a=0,b=3，x1=a+0.382(ba)=1.146，f1=f(x1)=0.2131；x2=a+0.618(ba)=1.1854，f2=f(x2)=3.6648；因为f1f2，所以向左搜索，贝ya=0,b=x2=1.854，x2=x1=1.146,f2=f1=0.213

13、1；x1=a+0.382(ba)=0.708，f1=f(x1)=0.0611因为f1f2，所以向右搜索，贝ya=0.438,b=x2=1.146，x1=x2=0.7086,f1=f2=0.0611；x2=a+0.618(ba)=0.876，f2=f(x2)=0.0798；因为f1f2，所以向右搜索，贝9a=0.708,b=x2=1.146，x1=x2=0.876,f1=f2=0.0798；x2=a+0.618(ba)=0.9787，f2=f(x2)=0.0199；x2因为|b-a=0.4380.5=,所以算法停止，得到0.708+1.1462=0.927。r5A要求选取初始点x0=5J5丿vf

14、(x)=2x1(10A，d0=-gf(x0+ad0)=f(510a=(510a)2+2(520a)2,d令daf(x0+ad0)=1800a500=0，a0丄，于是x1=x0+a0d018、20一95一9Jr40Ar400A则g1=Vf(x1)=920sLg14g0Tg0811=g1+B0d08110081丿例6用FR共轭梯度法求解问题minf(x)=x12+2x22=10-6。f(x1+adj=迴(1空a)2+50(1+空)2,1819819令daf(x1+叫)=0，则a1=，于是x2=x1+a1d11r0A则g2=Vf(x2)=r0A，|g2”=002P(x,M)=(x一1)2+x2+MImin12(0,x-1)2P(x,M)=(x1)2+x2,12(x1)2+x2+M(x1)2,x112x01x02解定义障碍函数P(x,rk)=-2(x1+1)3+x2+rk(-+),12x11x2用解析法求minP(x,rk),令*=4(x1+1)2-古=