(2.3.1)-2.3.3線性規(guī)劃的單純形算法

線性規(guī)劃-單純形方法單純形方法基本思路：從可行域中某個基礎可行解（一個頂點）開始（稱為初始基礎可行解）。如可能，從可行域中求出具有更優(yōu)目標函數(shù)值的另一個基礎可行解（另一個頂點），以改進初始解。繼續(xù)尋找更優(yōu)的基礎可行解，進一步改進目標函數(shù)值。當某一個基礎可行解不能再改善時，該解就是最優(yōu)解。一、消去法例2-11：一個企業(yè)需要同一種原材料生產甲乙兩種產品，它們的單位產品所需要的原材料的數(shù)量及所耗費的加工時間各不相同，從而獲得的利潤也不相同（如下表）。那么，該企業(yè)應如何安排生產計劃，才能使獲得的利潤達到最大？解：數(shù)學模型

maxZ=6x1+4x2s.t.2x1+3x21004x1+2x2120x1,x20解：引進松弛變量x3,x40數(shù)學模型標準形式：maxZ=6x1+4x2s.t.2x1+3x2+x3=1004x1+2x2+x4=120x1,x2,

x3,x40約束條件的增廣矩陣為：2310

100（Ab)=4201

120顯然r(A)=r(Ab)=2<4,該問題有無窮多組解。令A=（P1，P2，P3，P4）=

23104201X=（x1,x2,x3,x4)

A=（P1，P2，P3，P4）=

23104201

X=（x1,x2,x3,x4)B=(P3，P4

）=1001P3，P4線性無關，x3,x4是基變量，x1,x2是非基變量。

用非基變量表示的方程：x3=100-2x1-3x2x4=120-4x1-2x2(I)Z=6x1+4x2稱(I)為消去系統(tǒng)，若b=(100,120)t0則稱為正消去系統(tǒng)。

令非基變量（x1,

x2）t=（0，0）t

得基礎可行解：x(1)=(0,0,100,120)t

S1=0

經濟含義：不生產產品甲乙，利潤為零。分析：Z=

6x1+

4x2（分別增加單位產品甲、乙，目標函數(shù)分別增加6、4，即利潤分別增加6百元、4百元。）

增加單位產品對目標函數(shù)的貢獻，這就是檢驗數(shù)的概念。

增加單位產品甲（x1）比乙對目標函數(shù)的貢獻大（檢驗數(shù)最大），把非基變量x1換成基變量，稱x1為進基變量，而把基變量x4換成非基變量，稱x4為出基變量。（在選擇出基變量時，一定保證消去系統(tǒng)為正消去系統(tǒng)）（最小比值原則）

增加單位產品甲（x1）比乙對目標函數(shù)的貢獻大（檢驗數(shù)最大），把非基變量x1換成基變量，稱x1為進基變量，而把基變量x4換成非基變量，稱x4為出基變量。（在選擇出基變量時，一定保證消去系統(tǒng)為正消去系統(tǒng)）（最小比值原則）

確定了進基變量x1

，出基變量x4

以后，得到新的消去系統(tǒng)：x3=40-2x2+（1/2）x4x1=30-（1/2）x2-（1/4）x4(II)Z=180+x2-（3/2）x4令新的非基變量（

x2，x4）=（0，0）t得到新的基礎可行解：x(2)=(30,0,40,0)t

Z2=180經濟含義：生產甲產品30個，獲得利潤18000元。

這個方案比前方案，但是否是最優(yōu)？分析：Z=180+x2-（3/2）x4非基變量x2系數(shù)仍為正數(shù)，確定x2為進基變量。在保證常數(shù)項非負的情況下，確定x3為出基變量。得到新的消去系統(tǒng)：

x1=20+（1/4）x3-（3/8）x4x2=20-（1/2）x3+（1/4）x4(III)Z=200-（1/2）x3-（5/4）x4

令新的非基變量（x3,x4）t=（0,0）t得到新的基礎可行解：x(3)=(20,20,0,0)t

Z3=200經濟含義：分別生產甲乙產品20個，可獲得利潤20000元。分析：Z=200-（1/2）x3-（5/4）x4目標函數(shù)中的非基變量的系數(shù)無正數(shù)，Z3=200是最優(yōu)值，x(3)=(20,20,0,0)t是最優(yōu)解。該企業(yè)分別生產甲乙產品20個，可獲得最大利潤20000元。二、已知初始可行基求最優(yōu)解線性規(guī)劃標準型的矩陣形式(3)：MaxZ=CX(1-17)s.t.AX=b(1-18)X0(1-19)

a11a12….a1nb1A=a21a22….a2nb

=

b2…………am1am2….amnbnc1x10c2x20Ct=X=0=……………..cnxn0并且r(A)=m<n.1.最優(yōu)解判別定理：不妨假設A=（B,N）（B為一個基）相應地有Xt=(XB,XN)

C=(CB,CN)由（1-17）（1-18）Z=

(CB,CN)(XB,XN)t=CBXB+CNX（B,N）(XB,XN)t=B

XB+N

XN=b因為B為一個基,det(B)<>0有XB=B-1b-B-1NXNZ=

CBB-1b+(CN-

CBB-1N)

XN令非基變量XN=0則Xt=(XB,XN)=（B-1b,0）為基礎解，其目標函數(shù)值為S=

CBB-1b只要XB=B-1b0,Xt=（B-1b,0）0X為基礎可行解,B就是可行基。另外，若滿足CN-

CBB-1N0則對任意的x0有Z=CXCBB-1b即對應可行基B的可行解x為最優(yōu)解。定理2-5（最優(yōu)解判別準則）對于可行基B,若

C

-

CBB-1A0

則對應于基B的基礎可行解x就是基礎最優(yōu)解，此時的可行基就是最優(yōu)基。

C

-

CBB-1A為檢驗數(shù)。由于基變量的檢驗數(shù)：CB-CBB-1B=0C

-

CBB-1A=（0，CN-CBB-1N）單純形表：T（B）=B-1bB-1A

CBB-1bC-CBB-1A

=B-1bIB-1N

CBB-1b0CN-CBB-1N注意：

A=（B，N）表格單純形單純形解題步驟：（已知初始可行基）一、作對應B的單純形表：T（B）=B-1bB-1ACBB-1bC-CBB-1A=B-1bIB-1NCBB-1b0CN-CBB-1N單純形解題步驟：二、判別若檢驗數(shù)全小于等于零，則基B所對應的基礎可行解X就是最優(yōu)解，終止。若存在檢驗數(shù)大于零，但所對應的進基變量XS的系數(shù)向量PS小于等于零，則原問題無最優(yōu)解，終止。若存在檢驗數(shù)大于零，且對應的常數(shù)項大于零，則需要換基迭代。三、換基迭代確定進基變量XS，其中max(?j/?j>0)=?s

確定出基變量Xr,根據(jù)最小比值原則min(bio/bis,bis>0,1im)=br0/brs(1rm)brs為主元,Xr為出基變量。對單純形表T（B）進行初等行變換（主元運算）得到新的單純形表。經過上述有限次的換基迭代，就可得到原問題的最優(yōu)解，或判定無最優(yōu)解。表格單純形法例2-12數(shù)學模型標準型:maxZ=10x1+

3x2+4x3-x4+x5s.t.3x1+6x2+2x3+x4

=199x1+3x2+x3+x5=9x1,x2,

x3,

x4,

x50初始可行基B1=(P4,P5)=I

基變量為x4,x5

非基變量x1,x2,x3

初始基礎可行解:X(0)=(0,0,0,19,9)tCj→1034-11iCBXBbX1X2X3X4X5-1X419362101X5993101cj-zj計算檢驗數(shù):基變量檢驗數(shù)=0

非基變量檢驗數(shù)σj=Cj-

CBtPj目標函數(shù)值:Z=CBt*b=-10Cj→1034-11iCBXBbX1X2X3X4X5-1X419362101X5993101cj-zj1046500選擇檢驗數(shù)最大的非基變量X2作為進基變量,并選定該列.

Cj→1034-11iCBXBbX1X2X3X4X5-1X419362101X5993101cj-zj1046500

利用最小比值原則:

計算各基變量的比值Cj→1034-11iCBXBbX1X2X3X4X5-1X4193621019/61X59931019/3cj-zj1046500

利用最小比值原則:

計算各基變量的比值,選擇X5作為出基變量Cj→1034-11iCBXBbX1X2X3X4X5-1X4193621019/61X59931019/3cj-zj1046500

進基變量X2與出基變量X5,交叉位置為主元(3).

Cj→1034-11iCBXBbX1X2X3X4X5-1X4193621019/61X599[3]1019/3cj-zj1046500

第二行除以3Cj→1034-11iCBXBbX1X2X3X4X5-1X419362101X53311/301/3cj-zj1046500

第一行加上第二行的（-6）倍

Cj→1034-11iCBXBbX1X2X3X4X5-1X41-15001-21X53311/301/3cj-zj-246500作主元運算,即用初等行變換把主元位置變成為1,該列元素變成0.得到新的基礎可行解:X(1)=(0,3,0,1,0)tZ=8Cj→1034-11iCBXBbX1X2X3X4X5-1X41-15001-23X23311/301/3cj-zj8判斷X(1)=(0,3,0,1,0)tZ=8是否是最優(yōu)解.再計算檢驗數(shù).Cj→1034-11iCBXBbX1X2X3X4X5-1X41-15001-23X23311/301/3cj-zj8-14030-2X3的檢驗數(shù)大于零.X3進基變量Cj→1034-11iCBXBbX1X2X3X4X5-1X41-15001-23X23311/301/3cj-zj8-14030-2X3的檢驗數(shù)大于零.X3進基變量,計算相應的比值.確定X2出基變量,主元為(1/3)Cj→1034-11iCBXBbX1X2X3X4X5-1X41-15001-2-3X2331[1/3]01/39cj-zj8-14030-2第二行乘以3Cj→1034-11iCBXBbX1X2X3X4X5-1X41-15001-2-3X29931019cj-zj-26作主元運算,得到新的基礎可行解:X(2)=(0,0,9,1,0)tZ=35Cj→1034-11iCBXBbX1X2X3X4X5-1X41-15001-24X3993101cj-zj35判斷是否最優(yōu)解:X(2)=(0,0,9,1,0)tS=35計算檢驗數(shù),所有檢驗數(shù)全小于零,達到最優(yōu)解,X*=(0,0,9,1,0)tZ=35Cj→1034-11iCBXBbX1X2X3X4X5-1X41-15001-24X3993101cj-zj35-41-900-5單純形法的幾何意義：例2.16生產計劃問題（資源利用問題）

勝利家具廠生產桌子和椅子兩種家具。桌子售價50元/個，椅子銷售價格30/個，生產桌子和椅子要求需要木工和油漆工兩種工種。生產一個桌子需要木工4小時，油漆工2小時。生產一個椅子需要木工3小時，油漆工1小時。該廠每個月可用木工工時為120小時，油漆工工時為50小時。問該廠如何組織生產才能使每月的銷售收入最大？數(shù)學模型

maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20數(shù)學模型的標準形:maxZ=50x1+30x2s.t.4x1+3x2+x3=1202x1+x2+x4=50x1,x2,

x3,

x40基礎可行解X(1)=(0,0,120,50)t,目標函數(shù)值Z

=0Cj→503000iCBXBbX1X2X3X40X312043100X4502101cj-zj0X(1)=(0,0,120,50)t相當于O(0,0)X1進基變量,X4出基變量,主元（2）Cj→503000iCBXBbX1X2X3X40X31204310120/40X450(2)10150/2cj-zj0503000第二行除以2Cj→503000iCBXBbX1X2X3X40X3120431050X12511/201/2cj-zj第一行加上第二行的負4倍