15單純形法[學(xué)校資料]

1、1.5 單純形法單純形法 1.5.1 引例引例maxZ=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0 01教育特選1解：解：(1)、確定初始可行解、確定初始可行解B=(P3 P4 P5)=IZ =0 +40X1+50X2X3 =30-( X1+ 2X2 )X4=60-( 3X1+ 2X2)X5 =24 -2 X2令令X1 = X2 =0X(1) =(0, 0, 30, 60, 24)TZ(1) =02教育特選1(2)、判定解是否最優(yōu)、判定解是否最優(yōu)Z=0+40X1+50X2當(dāng)當(dāng)X1從從0或或X2從從0Z從從0 X

2、(1) 不是最優(yōu)解不是最優(yōu)解3教育特選1(3)、由一個(gè)基可行解、由一個(gè)基可行解另一個(gè)基可行解。另一個(gè)基可行解。 50 40 選選X2從從0，X1 =0X3 =30-2X2 0 0 X2 30/2 X4 =60-2X2 0 0 X2 60/2 X5 =24-2X2 0 0 X2 24/2 X2=min(30/2 , 60/2 , 24/2 ) =12X2進(jìn)基變量，進(jìn)基變量， X5出基變量。出基變量。4教育特選1B B2 2=(P3 P4 P2)Z=0+40X1+50X2 X3 +2X2 =30-X1 X4+2X2 =60-3X1 2X2=24-X5 5教育特選1 1/2 ，代入式，代入式， ，Z

3、=600 +40X1 -25X5X3 =6 -X1 +X5 X4 = 36-3X1 +X5 X2=12 -1/2X5令令X1 =X5 =0 X(2) =(0, 12, 6, 36, 0)T Z(2) =6006教育特選1(2)(2) 判斷判斷 400 X(2)不是不是。(3)(3) 選選X1從從0， X5 =0 X3= 6- X1 0 0 X4= 36-3X1 0 0 X2=12 0 0 X1=min( 6/1 , 36/3 , 1 ) =6X1進(jìn)基，進(jìn)基， X3出基。出基。7教育特選1B3 =(P1 P4 P2 )Z=840-40X3+15X5X1=6 - X3 + X5 X4= 18+3X

4、3 - 2X5X2=12 -1/2X5令令X3 =X5 =0 X(3) =(6, 12, 0, 18, 0)TZ(3) =8408教育特選1(2)(2) 150 X(3)不是不是(3)(3) 選選X5從從0， X3 =0 X1=6 +X5 0 0 X4= 18 -2X5 0 0 X2=12-1/2 X5 0 0 X5=min( 18/2 , 12/1/2 ) =9X5進(jìn)基，進(jìn)基， X4出基。出基。9教育特選1B4=(P1 P5 P2 )Z=975- 35/2X3 - 15/2X4X1= 15 + 1/2X3 - 1/2X4X5= 9 + 3/2X3 - 1/2X4X2= 15/2 -3/4X3

5、 + 1/4X4令令X3 =X4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =97510教育特選10(0,0)X X2 2X X1 1A A D DC CB B(0,12)(6,12)(15,7.5)11教育特選1 maxZ=CX當(dāng)當(dāng)LP的數(shù)學(xué)模型為矩陣型的數(shù)學(xué)模型為矩陣型 AX=b 時(shí)，時(shí)， X 0 0兩個(gè)重要公式：兩個(gè)重要公式：XB =B-1 b-B-1 NXNZ=CB B-1 b+(CN -CB B-1 N)XN當(dāng)當(dāng)XN =0時(shí)，時(shí)， B-1 b 0X=Z= CB B-1 b12教育特選1當(dāng)當(dāng)LPLP的數(shù)學(xué)模型為一般型時(shí)的數(shù)學(xué)模型為一般型時(shí)njjjXCZ1

6、max), 2 , 1(0), 2 , 1(1njXmibXajnjijij兩個(gè)重要公式形如：兩個(gè)重要公式形如：nmjjmiijijmiiinmjjijiiXaCCbCZmiXabX1111)(), 2 , 1(13教育特選11 00 a1m+1 a1n0 10 a2m+1 a2n0 01 amm+1 amn設(shè)設(shè)A=A=B=(P1 P2 Pm )=InmjijijimibXaX1), 1(), 2 , 1(1miXabXnmjjijii14教育特選1nmjjmiijijimiinmjiinmjjijimiiminmjiiiiXaCCbCXCXabCXCXCZ11111111)()(miiiTm

7、bCZbbX11)0,0,(當(dāng)當(dāng)Xj =0 (j=m+1,n)時(shí)時(shí),15教育特選11.5.2 單純形法原理單純形法原理njjjXCZ1max), 2 , 1(0), 2 , 1(1njXmibXajnjijijnmjjmiijijmiiinmjjijiiXaCCbCZmiXabX1111)(), 2 , 1(16教育特選1此時(shí)，此時(shí)，B=(P1 P2 Pm )對應(yīng)的基本可行解為對應(yīng)的基本可行解為miiiTmbCZbbX11)0,0,(nmjjijiinmjjjmiXabXXZZ110), 2 , 1(1)(1)17教育特選1定理定理1 1：對解：對解X(1) ，若檢驗(yàn)數(shù)，若檢驗(yàn)數(shù) j ( j=

8、m+1,n)全全部部 0，則則X(1)為最優(yōu)解。為最優(yōu)解。定理定理2 2：對：對X(1)，若有某個(gè)非基變量，若有某個(gè)非基變量Xm+k m+k00且相應(yīng)的且相應(yīng)的Pm+k =(a1m+k , ,amm+k )T 0，則原問題則原問題無有限最優(yōu)解。無有限最優(yōu)解。18教育特選1定理定理2證明證明Xi =bi - aij xjJ=m+1n令非基變量令非基變量Xm+k = ( 0)X(2) =(b1 - a1m+k , ,bm - amm+k ,0, , , ,0)TAX(2) =b X(2) 0Z=Z0+ m+k 當(dāng)當(dāng) 時(shí)時(shí) Z 19教育特選1例：例： Z=30X1+20X2 -X1+3X2 +X3

9、=10-3X1+2X2 +X4 =15初始基初始基B1 =(P3 P4 )X(1) =(0, 0, 10, 15 )T Z(1) =0Z=030X1+20X2X3=10-(-X1 +3X2 )X4 =15-(-3X1 +2X2 )20教育特選1選中選中X1從從0，X2 =0 X3=10-(-X1 ) 0 0 X4=15-(-3X1 ) 0 0 求求X1， X1+ , ,Z Z+ 21教育特選1換基迭代公式：換基迭代公式：(1)、決定換入變量：決定換入變量：maxmax j = m+k ，則則Xm+k 為換入變量為換入變量 j00(2)、決定換出變量：決定換出變量：bi -aim+kXm+k 0

10、 0 ( i=1 ,2 , m)Xm+k biaim+k(aim+k 0 0 )22教育特選1= = min aim+k 0 =0 =biaim+kbrarm+k則則X Xr為換出變量為換出變量。23教育特選1定理定理3：經(jīng)單純形法得到的：經(jīng)單純形法得到的X(2) =(b1 - a1m+k , ,bm - amm+k ,0, , , ,0)T是基本可行解，且是基本可行解，且Z(2) Z(1) 24教育特選1證明：設(shè)證明：設(shè)Xr = Xm , Xm =0, Xm+k = =bmAmm+k(0)X(1)中中P1 , Pm線性無關(guān)，下證線性無關(guān)，下證P1 , Pm -1 , Pm +k線性無關(guān)。線性

11、無關(guān)。若否，因?yàn)槿舴?，因?yàn)镻1 , Pm線性無關(guān)線性無關(guān)則則Pm +k = a1m +k P1+ + amm +k Pm 而而Pm +k = l1 P1+ lm -1 Pm -1 25教育特選1 - (a1m +k - l1 )P1 + +(am -1m +k - lm -1 ) Pm -1+ am m+k Pm =0P1 , ,Pm線性相關(guān)，矛盾。線性相關(guān)，矛盾。X(2)是基本解，且是可行解是基本解，且是可行解 26教育特選1單純形法基本步驟單純形法基本步驟(1)、定初始基，初始基本可行解、定初始基，初始基本可行解(3)、若有若有 k 0 0，Pk全全 0，停，停， 沒有有限最優(yōu)解；沒有有限

12、最優(yōu)解； 否則轉(zhuǎn)否則轉(zhuǎn)(4)(2)、對應(yīng)于非基變量檢驗(yàn)數(shù)、對應(yīng)于非基變量檢驗(yàn)數(shù) j全全 0。 若是，停，得到最優(yōu)解；若是，停，得到最優(yōu)解； 若否，轉(zhuǎn)若否，轉(zhuǎn)(3)。27教育特選1= = min aim+k 0 =0 =biaim+kbrarm+k定定X Xr為換出變量，為換出變量，a arm+k為為主元。主元。由最小由最小比值法求：比值法求：maxmax j = m+kXm+k 換入變量換入變量 j00(4)、28教育特選1轉(zhuǎn)轉(zhuǎn)(2) (2) m+k 0 a1m+k 0arm+k 1amm+k 0初等行變換初等行變換Pm+k = =(5)、以、以a arm+k為中心，換基迭代為中心，換基迭代2

13、9教育特選1證明可用歸納法（略）證明可用歸納法（略）X(1)X(2)X(3)X XX在邊界上在邊界上X在內(nèi)部在內(nèi)部X X +(1- ) X(2) (0 1)X X(1) +(1- ) X(3) X(1) (1- ) X(2) (1- )X(3) X=+(0 1)30教育特選1證明：證明： 設(shè)設(shè)X(1) , ,X(k) 為可行域頂點(diǎn)，若為可行域頂點(diǎn)，若X*不是不是頂點(diǎn)，但頂點(diǎn)，但 max Z = C X* X*=定理定理2：可行域有界，最優(yōu)值必可在頂點(diǎn)得到：可行域有界，最優(yōu)值必可在頂點(diǎn)得到 i X(i)ki=1 i =1ki=10 i 1 1CX*= iC X(i)ki=1 i CX(m)ki=

14、1= CX(m) 設(shè)設(shè) CX(m) Max (C X(i) 1 1 i k k31教育特選1Z(1) = Ci bii=1mZ(2) = Ci (bi - aim+k)+ Cm+k i=1m = Ci bi - + Cm+k i=1m Ci aim+ki=1m = Ci bi +Cm+k - Ci aim+k i=1m i=1mZ(2) - Z(1) =(Cm+k -Zm+k ) = m+k 0 32教育特選11.5.3 單純形表單純形表 C1 C2 Cm Cm+1 Cm+k Cn X1 X2 Xm Xm+1 Xm+k XnCB XB Z0 0 0 0 m+1 m+k nC1 X1 b1 1

15、0 0 a1m+1 a1m+k a1nC2 X2 b2 0 1 0 a2m+1 a2m+k a2nCr Xr br 0 0 0 arm+1 arm+k arnCm Xm bm 0 0 1 amm+1 amm+k annmiiibCZ10miijijjaCC133教育特選1 40 50 0 0 0 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 40 50 0 0 0 0 0 X3 30 1 2 1 0 0 15 30 1 2 1 0 0 150 0 X4 6060 3 3 2 0 1 0 302 0 1 0 300 0 X5 24 0 (2) 0

16、 0 1 12 24 0 (2) 0 0 1 12 XB 600 40 0 0 0 -25 600 40 0 0 0 -250 0 X3 6 (1) 0 1 0 -1 66 (1) 0 1 0 -1 60 0 X4 36 3 0 0 1 -1 1236 3 0 0 1 -1 1250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 840 0 0 -40 0 15 840 0 0 -40 0 1540 40 X1 6 1 0 1 0 -16 1 0 1 0 -10 0 X4 18 0 0 -3 1 2 18 0 0 -3 1 250 50 X2 12 0 1 0 0 1

17、/2 12 0 1 0 0 1/234教育特選1 XB 975 0 0 -35/2 -15/2 0 975 0 0 -35/2 -15/2 040 40 X1 15 1 0 -1/2 1/2 0 15 1 0 -1/2 1/2 0 0 0 X5 9 0 0 -3/2 1/2 1 9 0 0 -3/2 1/2 1 50 50 X2 15/2 0 1 3/4 -1/4 0 15/2 0 1 3/4 -1/4 0本問題的最優(yōu)解本問題的最優(yōu)解 X=(15, 15/2, 0, 0, 9)T Z=97535教育特選1幾點(diǎn)說明：幾點(diǎn)說明：(1)(1)、例、例 maxZ=maxZ=X1 +2X2X1 4X2

18、3X1+2X2 8 X1 , X2 0 0 X1+X3 = = 4X2+X4 = = 3X1+2X2+X5= = 8 X1 X5 0 036教育特選1 1 2 0 0 0 1 2 0 0 0 X1 X2 X3 X4 X5CB XB 0 1 2 0 0 00 1 2 0 0 00 0 X3 4 1 0 1 0 0 4 1 0 1 0 00 0 X4 3 0 (1) 0 1 03 0 (1) 0 1 00 0 X5 8 1 2 0 0 1 8 1 2 0 0 1CB XB 6 1 0 0 -2 0 6 1 0 0 -2 00 0 X3 4 1 0 1 0 0 4 1 0 1 0 0 2 2 X2

19、3 0 1 0 1 0 3 0 1 0 1 0 0 0 X5 2 2 (1) 0 0 -2 1 (1) 0 0 -2 1 ( (接下表接下表) )37教育特選1 1 2 0 0 0 1 2 0 0 0 X1 X2 X3 X4 X5 CB XB 8 0 0 0 0 -18 0 0 0 0 -10 0 X3 2 0 0 1 (2) -1 2 0 0 1 (2) -12 2 X2 3 0 1 0 1 03 0 1 0 1 01 1 X1 2 1 0 0 -2 1 2 1 0 0 -2 1CB XB 8 0 0 0 0 -1 8 0 0 0 0 -10 0 X4 1 0 0 1/2 1 -1/2 1

20、0 0 1/2 1 -1/2 2 2 X2 2 0 1 -1/2 0 1/2 2 0 1 -1/2 0 1/2 1 1 X1 4 4 1 0 1 0 0 1 0 1 0 0 38教育特選1X X(1)(1)= = (2,3) Z Z(1)(1)=8 =8 X X(2)(2)= = (4,2) Z Z(2)(2)=8=8無窮多解無窮多解全部解：全部解：X X= + (1-) (0 1)2 4 3 239教育特選1(2)(2)、例：、例： 求求 minZ=minZ=X1 -X2+X3 -3X5X2+X3 -X4+2X5 = = 6X1+2X2 -2X4 = = 52X2 +X4+3X5 +X6 =

21、 = 8X1 X6 0 040教育特選1 1 -1 1 0 -3 0 1 -1 1 0 -3 0 X1 X2 X3 X4 X5 X6CB XB 11 0 -4 0 3 -5 011 0 -4 0 3 -5 01 1 X3 6 0 1 1 -1 2 0 6 0 1 1 -1 2 01 1 X1 5 1 2 0 -2 0 05 1 2 0 -2 0 00 0 X6 8 0 2 0 1 3 1 8 0 2 0 1 3 1CB XB -7/3 0 -2/3 0 14/3 0 5/3 -7/3 0 -2/3 0 14/3 0 5/31 1 X3 2/3 0 -1/3 1 -5/3 0 -2/3 2/3

22、0 -1/3 1 -5/3 0 -2/3 1 1 X1 5 1 2 0 -2 0 05 1 2 0 -2 0 0-3 -3 X5 8/38/3 0 2/3 0 1/3 1 1/30 2/3 0 1/3 1 1/3CB XB -4 1/3 0 0 4 0 5/3-4 1/3 0 0 4 0 5/31 1 X3 3/2 1/6 0 1 -2 0 -2/33/2 1/6 0 1 -2 0 -2/3-1 -1 X2 5/2 1/2 1 0 -1 0 0 5/2 1/2 1 0 -1 0 0 -1 -1 X5 1 -2/3 0 0 1 1 1/31 -2/3 0 0 1 1 1/341教育特選1判定定理

23、判定定理1 1：基本可行解：基本可行解X X，當(dāng)全部，當(dāng)全部 j 0 0時(shí)，時(shí)，X X為為最優(yōu)解。最優(yōu)解。判定定理判定定理2 2：對可行基：對可行基B B，當(dāng)某，當(dāng)某 k00，且，且Pk=(a1k amk )T 0，則原問題無有限最優(yōu)解。則原問題無有限最優(yōu)解。 換入變量：換入變量：maxmax j = j = m+k Xm+k j 00, 則判定原問題無可行解。則判定原問題無可行解。58教育特選1兩階段法原理：兩階段法原理：(1)、輔助問題的基本可行解、輔助問題的基本可行解X(0) 為最優(yōu)解，對應(yīng)為最優(yōu)解，對應(yīng)最小值最小值 =0 則則X(0) 的前的前n個(gè)分量是原問題的基本可行解。個(gè)分量是原問

24、題的基本可行解。59教育特選1 設(shè)設(shè)X(0)=(X1(0) Xn(0) , y1(0) yn(0) )T 使使 aij xj(0)+ yi(0) bi ( i=1, 2, ,n )nj=1 =0, y1(0) = = yn(0) =0 aij xj(0) bi ( i=1, ,m )nj=1證明：證明：60教育特選1(2)、原問題有可行解時(shí)，輔助問題最優(yōu)值、原問題有可行解時(shí)，輔助問題最優(yōu)值 =0 。證明：若原問題有可行解證明：若原問題有可行解X(0)=(X1(0) , , Xn(0)T使使 aij xj(0) bi ( i=1, ,m )j=1n作作X(1)=( X1(0) Xn(0) ,0

25、0 )T = yi 0 =0i=1m必為輔助問題最優(yōu)解必為輔助問題最優(yōu)解61教育特選1maxZ= -X1 +2X2 X1 +X2 2-X1 +X2 1 X2 3 3X1 X2 0例例2 2：62教育特選1第第(1)階段：階段：minW=X6 +X7 X1 +X2 -X3 +X6 = =2-X1 +X2 -X4 +X7 = =1 X2 +X5 = =3X1 X7 063教育特選1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 X1 X2 X3 X4 X5 X6 X7CB XB 3 3 0 -2 1 1 0 1 1 0 0 0 0 01 1 X6 2 1 1 -1 0 0 1 0 2 1

26、 1 -1 0 0 1 0 1 1 X7 1 -1 1 -1 (1) 0 -1 0 0 1 (1) 0 -1 0 0 1 0 X5 3 0 1 0 0 1 0 0 3 0 1 0 0 1 0 0 CB XB 1 1 -2 -2 0 1 -1 0 1 -1 0 0 2 X6 1 (2) 0 -1 1 0 1 -1 1 (2) 0 -1 1 0 1 -1 X2 1 -1 1 -1 1 0 -1 0 0 1 1 0 -1 0 0 1 X5 2 1 0 0 1 1 0 -1 2 1 0 0 1 1 0 -1 XB 0 0 0 0 0 0 0 0 0 0 0 1 1 X1 1/2 1 0 -1/2 1/

27、2 0 1/2 -1/2 1/2 1 0 -1/2 1/2 0 1/2 -1/2 X2 3/2 0 3/2 0 1 -1/2 -1/2 0 1/2 1/21 -1/2 -1/2 0 1/2 1/2 X5 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 64教育特選1 -1 2 0 0 0 X1 X2 X3 X4 X5CB XB 3/2 0 0 1/2 3/2 0 -1 X1 1/2 1 0 -1/2 (1/2) 0 2 X2 3/2 0 1 -1/2 -1/2 0 0 X5 3/2 0 0 1/2 1/2 1 XB 4 -3

28、0 2 0 0 X4 1 2 0 -1 1 0 X2 2 1 1 -1 0 0 X5 1 -1 0 (1) 0 1 XB 6 1 0 0 0 -2 X4 2 1 0 0 1 1 X2 3 0 1 0 0 1 X3 1 -1 0 1 0 165教育特選1例例3：maxZ= 2X1 +X2 5X1 +10X2 82X1 +2X2 1X1 ，X2 066教育特選1第第(1)(1)階段：階段：minW= X55X1 +10X2 -X3 +X5 =82X1 +2X2 +X4 = =1X1 X5 067教育特選1 0 0 0 0 1 0 0 0 0 1 X1 X2 X3 X4 X5 CB XB 8 -5

29、-10 1 0 01 X5 8 5 10 -1 0 10 X4 1 2 (2) 0 1 0 XB 3 5 0 1 5 01 X5 3 -5 0 -1 -5 10 X2 1/2 1 1 0 1/2 068教育特選1X2X1O69教育特選1第第1階段階段 最優(yōu)基最優(yōu)基B* min = *(1)、 *0 (2)、 * =0 yi 0( i=1,2, ,m) B* 基變量無人工變量基變量無人工變量 B* 基變量含人工變量基變量含人工變量yr 單純形表中，單純形表中， yr+ ark yk + arj xj =0 () k Jj JJ：非基變量下標(biāo)集合：非基變量下標(biāo)集合70教育特選11) arj 全全

30、=0 () 式多余方程式多余方程2) arj 有有 0 元，設(shè)為元，設(shè)為ars 0 以以ars為主元，換基迭代，最后得到為主元，換基迭代，最后得到71教育特選1例例4 4、求、求maxZ= -4X1 -3X3 1/2X1 +X2+1/2X3-2/3X4 = 23/2X1 +3/4X3 = =33X1 -6X2 +4X4 = 0X1 , X2 , X3 , X4 0滿足滿足72教育特選1 0 0 0 0 1 1 1 X1 X2 X3 X4 y1 y2 y3 CB XB 5 -5 5 -5/4 -10/3 0 0 0 1 y1 2 1/2 1 1/2 -2/3 1 0 0 1 y2 3 3/2 0

31、 3/4 0 0 1 0 1 y3 0 3 6 0 4 0 0 1 CB XB 5 0 -5 -4/5 10/3 0 0 5/3 1 y1 2 0 2 1/2 -4/3 1 0 -1/6 1 y2 3 0 3 3/4 2 0 1 -1/2 0 X1 0 1 -2 0 4/3 0 0 1/3第第 一一 階階 段段 一一二二73教育特選1 CB XB 0 0 0 0 0 5/2 0 5/4 0 X2 1 0 1 1/4 -2/3 1/2 0 -1/2 1 y2 0 0 0 0 0 -3/2 1 -1/4 0 X1 2 1 0 1/2 0 1 0 1/6第一階段第一階段三三 -4 0 -3 0 X1

32、 X2 X3 X4CB XB -8 0 0 -1 0 0 X2 1 0 1 1/4 -2/3-4 X4 2 1 0 1/2 0第二階段第二階段74教育特選1的特殊情況的特殊情況: :第第1 1階段結(jié)束時(shí)階段結(jié)束時(shí), ,有人工變量有人工變量在基中取在基中取0,0,但但Xi系數(shù)全為系數(shù)全為0,0,此方程為多余方此方程為多余方程。程。75教育特選1例例5 5、求、求minZ=4X1 +3X31/2X1 +X2 +1/2X3 -2/3X4 =23/2X1 -1/2X3 = =33X1 -6X2 +4X4 =0X1 , X2 , X3 , X4 0滿足滿足76教育特選1 0 0 0 0 1 1 1 X1 X2 X3 X4 y1 y2 y3 CB XB 5 -5 5