(整理)單純形法解例1.

1、精品文檔例1用單純形法解下列問(wèn)題：min x1 -2x2 x3s.t x1+x2-2x3+x4 =10, 2x1 - x2 4x3E 8,-x1 2x2 -4x3 , 4, xj -0, j =1,|l|,4.解：將原問(wèn)題化成標(biāo)準(zhǔn)形： max -x1 2x2 -x3 s.t xi +x2 -2x3 +x4=10,2xi -x2 4x3x 8 8,-X 2x2 -4x3% = 4,xj 0,j =1川,6.x4與添加的松弛變量 xs, x6在約束方程組中其系數(shù)列正好構(gòu)成一個(gè)3階單位陣，它們可以作為初始基變量，初始基可行解為X= (0, 0, 0,10, 8, 4) T列出初始單純形表，見表 1。

2、表1Cjf-121-1000Cb基bx1x2 +x3x4x5x60x41011-21000xs82-140100x6 4-12-4001Cj-Zj0-12-1000由于只有 4> 0,說(shuō)明表中基可行解不是最優(yōu)解，所以確定地為換入非基變量；以x2的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量。二. ，10 4、. 4 m - min ( , ) =2 =1 22因此確定2為主元素(表1中以防括號(hào)括起)，意味著將以非基變量 x2去置換基變量 , 采取的做法是對(duì)約束方程組的系數(shù)增廣矩陣實(shí)施初等行變換，將x2的系數(shù)列(1,-1, 2)T變換成x6的系數(shù)列(0, 0,

3、1)T,變換之后重新計(jì)算檢驗(yàn)數(shù)。變換結(jié)果見表2。表2Cj 一-12-1000Cb基bx1x2x3 +x4x5x6x43/2000810-1/20 .一x5103/202011/22x22-1/21-2001/2Cj-Zj400300-1檢驗(yàn)數(shù) 電=30,當(dāng)前基可行解仍然不是最優(yōu)解。繼續(xù)換基”，確定2為主元素，即以非基變量X3置換基變量X5。變換結(jié)果見表 3。表3Cj -12-1000Cb基bxix2x3x4x5x60x483/20010-1/2-1x353/40101/21/42x212110011Cj-Zj19-9/4000-3/2-7/4此時(shí)，3個(gè)非基變量的檢驗(yàn)數(shù)都小于0,產(chǎn)-9/4, 0

4、5= -3/2, (5= -7/4,表明已求得最優(yōu)一*T解：X =(0,12,5,8,0,0)。去除添加的松弛變量，原問(wèn)題的最優(yōu)解為：X =(0,12,5,8)T,最小值為-19例2 用大M法求解下列問(wèn)題：minx1 x2 -3x3s.t x - 2x2 x3 _ 11, 2x1 x2 -4x3 _ 3, x1- 2x3 - 1,X .0, j =1川,3.解 引進(jìn)松弛變量x4、剩余變量x5和人工變量x6、x7,解下列問(wèn)題: min x1 x2 -3x3 0x4 0x5 M (x6 x7) s.t x1 -2x2 +x3 +x4=112x1 “2-4x3=3x1- 2x3x7 = 1xj 0,

5、j =1,2,|l1,7用單純形法計(jì)算如下：表1c-11-300MMCb基bx1|x2x3x4x5x6x70x4111 -211000Mx6321-40-110M4x110-20001Cj-Zj4M1-3M1-M-3+6M0M00由于6位 0,說(shuō)明表中基可行解不是最優(yōu)解，所以確定x1為換入非基變量；以玄的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量。. , 11 3 1、彳 1 m - mn （，_,_ ） =1 =一 12 11因此確定1為主元素（表1中以防括號(hào)括起），意味著將以非基變量 X1去置換基變量X7, 采取的做法是對(duì)約束方程組的系數(shù)增廣矩陣實(shí)施初等行變換

6、，將X1的系數(shù)列（1,2, 1）T變換成X7的系數(shù)列（0, 0, 1）T,變換之后重新計(jì)算檢驗(yàn)數(shù)。變換結(jié)果見表 2。表211-300MMCb基bX1X2X3X4X5X6X70X4100-23100-1MX6 -10100-11-21X1110-20001Cj-ZjM+101-M-10M03M-1由于 3 c3< 0,說(shuō)明表中當(dāng)前基可行解仍不是最優(yōu)解，所以確定X2為換入非基變量；以X2的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量。因此確定1為主元素，意味著將以非基變量X2去置換基變量X6,采取的做法是對(duì)約束方程組的系數(shù)增廣矩陣實(shí)施初等行變換，將X2的系數(shù)列（-

7、2, 1,0）T變換成X7的系數(shù)列（0, 1,0）T,變換之后重新計(jì)算檢驗(yàn)數(shù)。變換結(jié)果見表3。表3c-11-300MMCb基bX1X2X31X4X5X6X70X4120031-22-51X210100-11-21X1110-20001Cj-Zj200-101M-1M+1由于只有 6< 0,表中當(dāng)前基可行解仍不是最優(yōu)解，所以確定X3為換入非基變量；又由于X3的系數(shù)列的正分量只有 3,所以確定3為主元素，意味著將以非基變量 X3去置換基變 量X4 ,對(duì)約束方程組的系數(shù)增廣矩陣實(shí)施初等行變換，將 X3的系數(shù)列（3, 0, -2） T變換成X4的 系數(shù)列（1,0, 0）T,變換之后重新計(jì)算檢驗(yàn)數(shù)

8、。變換結(jié)果見表4。表4c-11-300MMCb基bX1X2X3X4X5X6X7-3X340011/3-2/32/3-5/31X210100-11-21X191002/3-4/34/3-7/3Cj-Zj-20001/31/3M-1/3M-2/3至此，無(wú)負(fù)的檢驗(yàn)數(shù)且基變量中不含人工變量（即人工變量在基可行解中取 0值），求得 *原問(wèn)題的最優(yōu)解： Xi =9 , X2 =1 , X3 =4 ,最小目標(biāo)函數(shù)值為-2。例3用兩階段法求解下列問(wèn)題：max2x1 - xst x1 +x2 之 2,Xi - x2 -1,x1- 3,xi,x2 一 0.解將原問(wèn)題化成標(biāo)準(zhǔn)形為：max2xi -x2s.t x1

9、+ x2 - x3=2x1 - x2- x4=1xix5 = 3xi,x2lH ,x5 一 0第一階段用單純形法求解第一階段的線性規(guī)劃問(wèn)題：min st力=%+x?xi + x2 - x3xi -x2xixi,x2 |,x7一 x+0Q十幾+x=2x7 =i=3求解過(guò)程見表io表iq-00000iiCb基bxix2x3x4x5x6xix62ii-i00i0ixii-i0-i00i0x53i000i00Cj-Zj3-20ii000ix6i02-ii0i-i0xiii-i0-i00i0x520i0ii0-iCj-Zji0-2i-i0i20x2I/20i-I/2I/20I/2-I/20xi3/2i0

10、-i/2-i/20i/2i/20x53/2001/21/21-1/2-1/2Cj-Zj00000021因此，第一階段求得最優(yōu)解為(Xi,X2,X3, x4, x5) =(一，一,0,0, -),基變量為Xi、x2和2 22x5,不包含人工變量。第二階段 以 A階段的最終單純形表為基礎(chǔ)，除去人工變量 、x7及其系數(shù)列，恢復(fù)目標(biāo)價(jià)值向量為 C = (2,-1, 0, 0, 0) T,重新計(jì)算檢驗(yàn)數(shù)，繼續(xù)迭代，見表 2。表2Cj2-1000Cb基bx1x2x3x4x5-1x21/22x13/20x53/201-1/21/2010-1/2-1/20001/21/21Cj-Zj5/2001/23/200

11、x412x120x3102-11010-1000-1101Cj-Zj20-32000x422x130x31010111-10010-1101Cj-Zj60-100-2因此，求得原問(wèn)題的最優(yōu)解為(*42?3, 乂4,%) - (3,0,1,2,0)，最大目標(biāo)函數(shù)值為6。例4寫出下列問(wèn)題的Lagrange函數(shù)及該問(wèn)題的 K-T條件一2一 2min f (xi,x2) = (x1-1)(x2 -2)s.t g1(x1,x2) = x1 x2 - 2 m 0 g2(K,X2)= -xi < 0 g3(K,x2) =* 三 0 %(斗？2) = -x x2 -1 =0 解該問(wèn)題的Lagrange函

12、數(shù)是L (X , 為為=(x1 _ 1)2 + (x2 2/+ *虱 x1 + x2 2)+ &2( x2)3(-x2)J(-x1 x2 -1)由于-:L,=2函 -1)1 - 7 -口x1精品文檔:L _=2d -2) - -1 - '3 "x2故該問(wèn)題的KT條件是2(xi -1) +兀% N = 02(x2 2) +九i % + N = 01( (x1 + x2 - 2) = 0九 2x1 =07-3 x2 = 0，1 , 7-2 ,)-3 之 0例5用0.618法求解問(wèn)題 min f(x)=x3 2x+1的近似最優(yōu)解，已知f(x)的單谷區(qū)間為0,3,要求最后區(qū)間

13、精度名=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)閒1 <f2 ,所以向左搜索，則a =0,b =x2 =1.854,a =0, b =x2 =1.146 ,x2 =x1 =1.146, f2 = f1 =0.2131;x1 =a+0.382(ba) =0.708, f1 = f (x1)=0.0611 ；因?yàn)閒1 ：二f2 ,所以向左搜索，則x2 =x1 =0.7 0 832 =f1 =-0.0 6 1 1x1 =a+0

14、.382(ba) =0.438, f1 = f(x1) =0.208 ;因?yàn)閒1 Af2 ,所以向右搜索，則a =0.438,b =x2 =1.146 , x1 =x2 =0.7086 fl = f2 =-0.0611 ；x2 =a+0.618(b-a)=0.876 , f2 = f (x2) =-0.0798 ;因?yàn)閒1 Af2 ,所以向右搜索，則a =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 ;因?yàn)閎 -a =0.438 <0.5

15、 = 8 ,所以算法停止，得到* a b 0.708 1.146x =0.927 。22例6用FR共軻梯度法求解問(wèn)題min f (x)=x +2x；,要求選取初始點(diǎn)x0 ='、f (x)='2x1、/ 卜 g0 = 02)1。)必0/ d0=r0 =-10 !20 /f(x0 ：Qd0) =f5 -100(、2 ,21 = (5 -100() +2(5200(), 5 -20a J* d 0令-f(x0 +ad0)=1800a 500=0 ， d-=X0 i. 0d 0 二竺、T( 400則 gi=Vf(x1)=20 , |gi|=-205,0-gT-g1 =84-, di =-gi+p0d0 =1(8JI,9g 0 g0 81< 9；I 81 J1400202 50f(x1:"1)=1T(1-T:)2 81(-120 :9)2令f (x1 +od1 )=0,則 0(1 =,于是 x2 =x1 +ot1d1 =1 0 i;da1120FJi -2'61 I II, *26'匕、則 g2=W(x)=0 卜 |g2|=0c