最優(yōu)化例題講解

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=解：將原問題化成標(biāo)準(zhǔn)形：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在約束方程組中其系數(shù)列正好構(gòu)成一個(gè)3階單位陣，它們可以作為初始基變量，初始基可行解為X=(0,0,0,10,8,4)T列出初始單純形表，見表1。表1-12I-1000CB基bx1x?Jx3x4x5x60 x41011-21000 x582-14010044-12-40010-12-1000由于只有。2，說明表中基可行解不是最優(yōu)解，所以確定x2為換入非基變量；以x2的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量。因此確定2為主元素(表1中以防括號(hào)甘舌起)，意味著將以非基

3、變量x2去置換基變量x6,采取的做法是對(duì)約束方程組的系數(shù)增廣矩陣實(shí)施初等行變換，將x2的系數(shù)列(1,-1,2)t變換成x6的系數(shù)列(0,0,1)t，變換之后重新計(jì)算檢驗(yàn)數(shù)。變換結(jié)果見表2。表2-12-1,000Cb基bx1x2x3,rx4x5x60 x483/20010-1/20 x5103/202011/22x22-1/21-2001/2c/-z/400300-1檢驗(yàn)數(shù)。3=30,當(dāng)前基可行解仍然不是最優(yōu)解。繼續(xù)“換基”，確定2為主元素，即以非基變量x3置換基變量x5。變換結(jié)果見表3。表3-12-1000CB基bx1x2x3x4x5x60 x483/20010-1/2-1x353/40101

4、/21/42x212110011c廠勺19-9/4000-3/2-7/4此時(shí)，3個(gè)非基變量的檢驗(yàn)數(shù)都小于0，。=-9/4，。5=-3/2，。5=刁/4，表明已求得最優(yōu)解：X*=(0,12,5,8,0,0)t。去除添加的松弛變量，原問題的最優(yōu)解為：X*=(0,12,5,8)t,最小值為-19例2用大M法求解下列問題：minx+x3x123s.x2x+x3,123x-2x=1,13x0,j=1,3.解引進(jìn)松弛變量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用單純形法計(jì)算如下：表111-300MMCb基bx1x2x3x4x5x6x70 x411Jr-211000Mx6321-40-110M110-20001C眄4M1-3M1-M-3+6M0M00由于Oo20，說明表中基可行解不是最優(yōu)解，所以確定x1為換入非基變量；以兀的系數(shù)列的正分量對(duì)

6、應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量。0=min(11,-,1)=1=丄1211因此確定1為主元素(表1中以防括號(hào)括起)，意味著將以非基變量X去置換基變量x7，采取的做法是對(duì)約束方程組的系數(shù)增廣矩陣實(shí)施初等行變換，將X1的系數(shù)列(1,2,1)t變換成x7的系數(shù)列(0,0,1)t，變換之后重新計(jì)算檢驗(yàn)數(shù)。變換結(jié)果見表2。表2Cjf11-300MMCB基bX1X2,X3X4X5X6X70X4100-23100-1M*10100-11-21X1110-20001c內(nèi)M+101-M-10M03M-1由于230，說明表中當(dāng)前基可行解仍不是最優(yōu)解所以確定x2為換入非基變量；以x2的系數(shù)

7、列的正分量對(duì)應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量。因此確定1為主元素，意味著將以非基變量X2去置換基變量x6,采取的做法是對(duì)約束方程組的系數(shù)增廣矩陣實(shí)施初等行變換，將X2的系數(shù)列(-2,1,0)t變換成x6的系數(shù)列(0,1,0)T,變換之后重新計(jì)算檢驗(yàn)數(shù)。變換結(jié)果見表3。表311-300MMCB基bX1X2卜x4X5X6X70J4120031-22-51X210100-11-21X1110-20001200-101M-1M+1由于只有O32,12x一x1,12x0125第一階段用單純形法求解第一階段的線性規(guī)劃問題：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因此，第一階段求得最優(yōu)解為(x,x,x,x,x)T=(；,0,0,；)T，基變量為x2和1234

9、522212x5，不包含人工變量。第二階段以第一階段的最終單純形表為基礎(chǔ)，除去人工變量x6、x7及其系數(shù)列，恢復(fù)目標(biāo)價(jià)值向量為C=(2,-1,0,0,0)T,重新計(jì)算檢驗(yàn)數(shù)，繼續(xù)迭代，見表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因此，求得原問題的最優(yōu)解為(x1,x2,x3，佇x5)t=(3,0，1，2,0

10、)T，最大目標(biāo)函數(shù)值為6。例4用KT條件求下列問題minf(x,x)=(x-1)2+(x-2)21212s.tx+x-2012-x01-x02x+x1=012解該問題的Lagrange函數(shù)是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點(diǎn)，除滿足上述條件，自然還應(yīng)滿足可行性條件x+x2W0120,x012為使求解易于進(jìn)行，從互補(bǔ)松緊條件入手討論：1設(shè)x豐0,x豐0,九=0121由互補(bǔ)松緊條件知九=九=0,由KT條件知322(x1)卩=0,2(x2)+卩=012再由可行性條件-x+x1=0得到x=1,x=2,R=0,但是顯然不滿足可行性1212x+x20,故此解舍棄。122設(shè)九豐01由互補(bǔ)松緊條件知x+x2=0,再加上可行性條件x+x1=0知121213x=

12、,x=，從而由互補(bǔ)松緊條件知九=九=0，將已知值代入易得九=1，R=0，122223113易知這時(shí)KT條件和可行性條件滿足，因而X*=(牙，)T為KT點(diǎn)。易見f(x,x)和2212g(x,x)=x+x2為凸函數(shù)，h(x,x)=x+x1是線性函數(shù)，所以由定理3.611212121213知x*=(20要求最后區(qū)間精度=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；因?yàn)閒1f2，所以向左搜索，貝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因?yàn)閒1f2，所以向右搜索，貝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；因?yàn)閒1f2，所以向右搜索，貝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因?yàn)閨b-a=0.4380.5=,所以算法停止，得到0.708+1.1462=0.927。r5A要求選取初始點(diǎn)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解定義障礙函數(shù)P(x,rk)=-2(x1+1)3+x2+rk(-+),12x11x2用解析法求minP(x,rk),令*=4(x1+1)2-古=