最优化例题讲解

例1用单纯形法解下列问题：minx1-2x2x3s.tx1+x2-2x3+x4=10,2x1-x24x3_8,-x1.2x2_4%-4,xj-0,j=1,,4.解：将原问题化成形：max-x12x2-x3s.tx1+x2-2x3+x4=10,2x1-x24x3x88,-X2x2-4x3%=4,xj-0,j=1；,6.x4与添加的松弛变量xs,x6在约束方程组中其系数列正好构成一个3阶单位阵，它们可以作为初始基变量，初始基可行解为X=（0,0,0,10,8,4）T列出初始单纯形，见表1。表1Cj--12-10001Cb基bx1x2*x3x4x5x60x40xs0x6108411-21002-14010-1[2]-4001Cj-Zj0-12-1000由于只有4>0,说明表中基可行解不是最优解，所以确定x2为换入非基艾量；以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。口.，104、4e=min（Y,-）=2=-因此确定2为主元素（表1中以防括号［］括起），意味着将以非基变量x2去置换基变量％,采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x2的系数列（1,-1,2）T变换成x6的系数列（0,0,1）T,变换之后重新计算检验数。变换结果见表2。表2cj一-12-10001Cb基bx1x2x31x4xsx60x40x52x281023/20010-1/23/20[2]011/2-1/21-2001/2Cj-Zj400300-1检验数电=3>0,当前基可行解仍然不是最优解。继续换基”，确定2为主元素，即以非基变量X3置换基变量X5。变换结果见表3。表3Cjf-12-1000Cb基bx1x2x3x4x5x60x483/20010-1/2-1x353/40101/21/42x212110011Cj-Zj19-9/4000-3/2-7/4此时，3个非基变量的检验数都小于0,q=-9/4,05=-3/2,(5=-7/4,表明已求得最优解：X=(0,12,5,8,0,0)T。去除添加的松弛变量，原问题的最优解为：X=(0,12,5,8)，最小值为-19例2用大M法求解下列问题：minx1x2。3x3s.txi—2x2+x3<11,2xix2-4x3-3,xi-2x3-1,xj-0,j=1；,3.解引进松弛变量乂、、剩余变量x5和人工变量x6、x7,解下列问题:minx1x2-3x30x40x5M(x6x7)s.tx1-2x2+x3+x4=112x1r2-4x3-x5xj=3x1-2x3x7=1xj—0,j=1,2,,7用单纯形法计算如下：11m-min(,-,-)=1=一表1c-11-300MMCb基bx1x2x3x4x5x6x70x4111JF-211000Mx6321-40-110M4―x71[1]0-20001Cj-Zj4M1-3M1-M-3+6M0M00由于①<应<0,说明表中基可行解不是最优解，所以确定x1为换入非基变量；以x1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素（表1中以防括号［］括起），意味着将以非基变量X1去置换基变量X7,采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将X1的系数列（1,2,1）T变换成X7的系数列（0,0,1）T,变换之后重新计算检验数。变换结果见表2。表2cj—111-300MMCb基bX1X2X3X4X5X6X70X4100▼-23100-1MX6◄—10[1]00-11-21X1110-20001Cj-ZjM+101-M-10M03M-1TOC\o"1-5"\h\z由于⑦<$<0,说明表中当前基可行解仍不是最优解，所以确定X2为换入非基变量；以X2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素，意味着将以非基变量X2去置换基变量X6,采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将X2的系数列（-2,1,0）T变换成X6的系数列（0,1,0）T,变换之后重新计算检验数。变换结果见表3。表3c-11-3100MMCb基bX1X2X3，X4X5X6X70X4<1200[3]1-22-51X210100-11-21X1110-20001Cj-Zj200-101M-1M+1TOC\o"1-5"\h\z由于只有6<0,表中当前基可行解仍不是最优解，所以确定X3为换入非基变量；又由于X3的系数列的正分量只有3,所以确定3为主元素，意味着将以非基变量X3去置换基变量X4,对约束方程组的系数增广矩阵实施初等行变换，将X3的系数列（3,0,-2）T变换成X4的系数列（1,0,0）T,变换之后重新计算检验数。变换结果见表4。表4c-11-300MMCb基bXiX2X3X4X5X6X7-3X340011/3-2/32/3-5/31X210100-11-21X191002/3-4/34/3-7/3cj-zj-20001/31/3M-1/3M-2/3TOC\o"1-5"\h\z至此，无负的检验数且基变量中不含人工变量（即人工变量在基可行解中取0值），求得**原问题的取优解：X1=9,X2=1,X3-4,取小目标值为-2。max2x1-x2s.tx1+x2>2,x1-X2二1,TOC\o"1-5"\h\zX1-3,X1,X2一0.解将原问题化成标准形为：min-2xiX2s.tx1+x2—x3=2Xi-X2-X4—1XiX5=3Xi,X2,X5一0第一阶段用单纯形法求解第一阶段的线性规划问题：ming=%*X7stx1+x2-x3+%=2X1-X2-X4+X7=1X1+X5=3X1,X2…，X7至0求解过程见表1。表1q-0000011Cb基bX1X2X3X4X5X6X71X6211-100101X71[1]-10-10010X531000100qj-zj3-20110001X610[2]-1101-10X111-10-10010X52010110-1qj-zj10-21-10120X21/201-1/21/201/2-1/20X13/210-1/2-1/201/21/20X53/2001/21/21-1/2-1/2Cj-Zj00000021因此，第一阶段求得最优解为(xi,x2,x3,x4,%)=(—,—,0,0,—),基变量为xi、x2和222xs,不包含人工变量。第二阶段以A阶段的最终单纯形表为基础，除去人工变量h、x7及其系数列，恢复目标价值向量为C=(2,-i,0,0,0)T,重新计算检验数，继续迭代，见表2。表2Cj—-2i000Cb基bxix2x3x4xsix2-2xi0xsi/23/23/20i-i/2[i/2]0i0-i/2-i/2000i/2i/2iCj-Zj-5/200-i/2-3/200x4-2xi0x—i2i02-ii0ii-i000-i[i]0iCj-Zj-403-2000x4-2xi0x—23i0i0iii000i0-ii0iCj-Zj-60i002因此，求得原问题的最优解为(xi,x2,x3,x4,%)T-(3,0,i,2,0)T,最大目标函数值为6。TOC\o"1-5"\h\z例4用K—T条件求下列问题-2-2minf(x1,x2)=(x-1)(x2-2)s.tx+x2-2E0-Xi-0-x2-0”x27=0解该问题的Lagrange函数是L(X,九,N)—(xi-1)+(x2—2)—7m(-xi—x2+2)-7-2xi—7-3x2+N(—xi+x2—1)由于.:L.一二2(xi-i)'i-'2-Jxi：L=2(x2-2)i-3」x2故该问题的K—T条件是0xi-1)+/j〜—N=02(x2-2)十力一%+N=0,1(-X1-x22)—0Z2X=0&x2=0?1,%,b>0作为K—T点，除满足上述条件:自然还应满足可行性条件/x2-2,0,—x1*X2—1=0x1>0,x2>0为使求解易于进行，从互补松紧条件入手讨论：设x1#0,冷#0,Q=0由互补松紧条件知％=%=0,由K—T条件知2(x1-1)-」=0,2(x2-2)」=0再由可行性条件-又+x2-1=0得至|Jx〔=1,x2=2*=0,但是显然不满足可行性x1+x2-2<0,故此解舍弃。设%#0由互补松紧条件知x1+x2-2=0,再加上可行性条件一x1+x2-1=0知13一x1=—,x2=—，从而由互补松紧条件知卜2=%=0,将已知值代入易得％=1,N=0,TOC\o"1-5"\h\z223T易知这时K—T条件和可行性条件满足，因而X=(一,及)T为K—T点。易见f(x1，x2)和2—g1(x［，x2)=x1十x2—2为凸函数，h(x,,x2)=—x1十x2—1是线性函数，所以由定理3.6知X*=(L3)T为全局最优解。(*但工)=f01正定)2202例5用0.618法求解问题minf(x)=x3—2x+1的近似最优解，已知f(x)的单峰区间为［0,3］,x_0,要求最后区间精度8=0.5。解a=0,b=3,a=0,b=x2=1.854,a=0,b=x2=1.146,x1=a+0.382(b-a)=1.146,f1=f(x1)=0.2131；x2=a+0.618(b—a)=1.1854,f2=f(x2)=3.6648；因为f1：二f2,所以向左搜索，则x2=x[=1.146,f2=f[=0.2131；x1=a+0.382(b-a)=0.708,f1=f(x1)=-0.0611；因为f1；f2,所以向左搜索，则x2=x1=0.70862=力=-0.061；1x1=a+0.382(b-a)=0.438,f1二f(x1)二0.208；因为f1>f2,所以向右搜索，则a=0.438,b=x2=1.146,x1=x2=0.7086,f1=f2=-0.0611；x2=a+0.618(b-a)=0.876,f2=f(x2)=—0.0798；因为f1Af2,所以向右搜索，则a=0.708,b=x2=1.146,x1=x2=0.876,f1=f2=-0.0798;x2=a+0.618(b—a)=0.9787,f2=f(x2)=-0.0199；因为七―a=0.438<0.5=6,所以算法停止，得到0.7081.1462=0.927。例6用FR共轲梯度法求解问题minf(x)=x2+2x2,要求选取初始点x0=,101产j,d0=T0=f(x0七二do);f,、2+2(5—200(),'5_10a、21=(5-10a)R_20aJ20则U0=5,180.二x，，二0d0一.,一1则g1=1f(x)=40320一9」205，g1=-9-，9T-0邛g0g0481，d1=-g1-：0d。=400一I100,81f(x1：d1)=箸(12020：)2令—f(x1+ad1)=0,则0tl=—,于d:20■二.1d1=I-6一.2贝Ug2=f(x)=6)一—一0I，|gz|=0＜以故x0J01为所求。V?用外罚函数法求解:_22minfx=x1-1x2s.tx27_0P(x,M)=(x1—1)2+x2+M[min(0,X2-1寸彳22(X1-1)X2,即Px,M=Xz-1-0222_(x1-1)x2Mx27,x27::0•d令df(x0+ad0)=1800a-500=0，d、t于是令得:.:P一=2(X1-1)X1TOC\o"1-5"\h\zp_2x2,X2-1.x2-2x22Mx2-1,x2：二1:PFP一二二0X1X2X1M=1X2MM—M1最优值：MPx,M:二「Ml-1M1当MTy时，x1（M）T1,x2（M,P（x,M尸f（x）=1例8用内罚函数法求解:,13min（x11）x212s.tx1-1>0x2-01Q1斛止乂障碍函数即心=万的^^+M心1+一）,x2用解析法求minP（x,rk）,令F（x，/k）%4（x11）2F（x，「k）.rk门—：——=rk_0--二0,-x2x2-（x1-1）解得：％rk=（x1，x2）T=31+2j「k，口"）'。当rkT0时，xrkTx=（1，0）T,故x=（1，0）T是原问题的最优解。例9用内罚函数法求解：minf（x）=（x+12s.tx-0解定义障碍函数P（x，rk）=（x+1）2-rklnx,用解析法求minP(x，rQ,令dP（x，rk）“dx=2（x1）--=0,x解得:-1J2rk2当rkT0时，x「kTx=0,故x=0是原问题的最优解。