教案4-單純形法省公開課一等獎全國示范課微課金獎?wù)n件

本節(jié)重點：單純形表（尤其是檢驗數(shù)行）單純形法計算步驟大M法兩階段法解存在情況判別第1頁4．1 單純形表

用表格法求解LP，規(guī)范表格——單純形表以下：第2頁計算步驟(1).找出初始可行基，確定初始基可行解，建立初始單純形表。(2).檢驗各非基變量xj檢驗數(shù)，若

j

0，j=m+1，…，n；則已得到最優(yōu)解，可停頓計算，不然轉(zhuǎn)入下一步。(3).在

j

>0，j=m+1，…，n中，若有某個

k對應(yīng)xk系數(shù)列向量Pk

0，則此問題是無界解，停頓計算。不然，轉(zhuǎn)入下一步。(4).依據(jù)max(

j>0)=

k，確定xk為換入變量，按

規(guī)則計算

=min{bi/aik\aik>0}可確定第l行基變量為換出變量。轉(zhuǎn)入下一步。第3頁用單純形方法求解

maxz=40x1+45x2+24x3

s.t.

第4頁

23000

12

10040

01004

001

02300000081612x3x4x54-3

23000

2

1

0

10-1/2

-92000-3/4003x3x4x224-()

3

0

1001/4

16

4

0010X(0)=(0，0，8，16，12)T，z0=0第5頁

23000

2

1

010-1/2-1300-201/4203x1x4x2-412

3

0

100

1/4

8

0

0-41

2

23000

2

1

0

10-1/2

-92000-3/4003x3x4x224-

3

0

1001/4

16

4

0010()

X(1)=(0，3，2，16，0)T，z1=9第6頁

23000

2

1

010-1/2-1300-201/4203x1x4x2-412

3

0

100

1/4

8

0

0-41

2()

23000

4

1

00

1/40-1400-1.5-1/8

0203x1x5x2

2

0

11/2

-1/8

0

4

0

0-2

1/21

X(2)=(2，3，0，8，0)T，z2=13

X(3)=(4，2，0，0,4)T，z3=14第7頁練習(xí)第8頁§5單純形法深入討論一、目標(biāo)函數(shù)為Min情形三種處理方法：1令Z’=-Z===>MaxZ’=-CX；2求MinZ，當(dāng)全部檢驗數(shù)cj-zj>=0時為最優(yōu)，不然要迭代，換入檢驗數(shù)最小那個變量，確定換出變量方法和前面Max情形一樣；3要求檢驗數(shù)為zj-cj，其余過程和前面Max情形一樣。5.1幾個情況第9頁二、約束方程為“>=”或“=”情形（加人工變量）人工變量法（確定初始可行基）：原約束方程：AX=b加入人工變量：xn+1，，xn+m人工變量是虛擬變量，加入原方程中是作為暫時基變量，經(jīng)過基旋轉(zhuǎn)變換，將人工變量均能換成非基變量，所得解是最優(yōu)解；若在最終表中檢驗數(shù)小于零，而且基變量中還有某個非零人工變量，原問題無可行解。第10頁其中第2、3個約束方程中無顯著基變量，分別加上人工變x6,x7,第11頁這時，初始基和初始基可行解很顯著。X(0)=(0，0，0，11，0，3，1)T不滿足原來約束條件。怎樣使得可從X(0)開始，經(jīng)迭代逐步得到x6=0，x7=0基可行解，從而求得問題最優(yōu)解，有兩種方法：第12頁反之，若加了人工變量問題解后最優(yōu)解中仍含人工變量為基變量，便說明原問題無可行解。例8單純形表格為：

只要原問題有可行解，伴隨目標(biāo)函數(shù)向最大化方向改進，人工變量一定會逐步換出基，從而得到原問題基可行解，進而得到基最優(yōu)解。5.2大M法在目標(biāo)函數(shù)中加上處罰項。

max=3x1-x2-x3-Mx6-Mx7其中M為充分大正數(shù)。第13頁3-6M M-1 3M-1 0

-M 0 0

0x4

103-20100-1-Mx610[1]00-11-21-1x31-2010001

1 -1+M 0 0

-M 0-3M+1

0x4

12[3]001-2-1x210100-14-1x31-20100

1 0 0 0

-1

3x1

41001/3-2/3-1x210100-1-1x390012/3-4/3

-2000

-1/3-1/3

X*=(4，1，9，0，0)T,z*=2113/21〔〕第14頁5.3兩階段法第一階段：以人工變量之和最小化為目標(biāo)函數(shù)。 min

=x6+x7

第二階段：以第一階段最優(yōu)解(不含人工變量)為初始解，以原目標(biāo)函數(shù)為目標(biāo)函數(shù)。第15頁第16頁第17頁第18頁MaxZ=2x1+x2+x3s.t.4x1+2x2+2x3≥42x1+4x2≤204x1+8x2+2x3≤16x1，x2，x3≥0用兩階段法求下面線性規(guī)劃問題解第19頁5.4線性規(guī)劃問題解討論一、無可行解

maxz=2x1+4x2

x1+x210

2x1+x2

40

x1,x20人工變量不能從基底換出，此時原線性規(guī)劃問題無可行解。x1x2

CBXBbX3

x5

0-1

0000-1

x1x2x3x4x540210-1110[1]1100cj

1040/2x1

x5

0-1

200-1-2-111011100

cj-zj0-1-2-10cj-zj210-10Z0=-40Z1=-20兩階段法第20頁第21頁

例:maxz=3x1+4x2

x1+x240

2x1+x260

x1-x2=0

x1,x20

此題初始解是退化。最優(yōu)解也是退化解。退化解迭代中，當(dāng)換入變量取零值時目標(biāo)函數(shù)值沒有改進，x1x20x340111000x4602101-1-Mx50[1]-10010x3400[2]100x46003013x101-1003+M4-M000zj-cj

000-7/3

zj-cj

0x30001-1/3

4x2200101/33x1201001/3cj→3400-M

CB

XBbx5

θx1x2x3

x4

0700zj-cj00-3.50zj-cj4x220011/200x4000-3/213x120101/20第22頁第23頁

例maxz=3x1+5x2

3x1+5x215

2x1+x25

2x1+2x211

x1,x20

假如將x1換入基底，得另一解，由可行域凸性易知，有兩個最優(yōu)解必有沒有窮多組最優(yōu)解當(dāng)非基底變量檢驗數(shù)中有取零值，或檢驗數(shù)中零個數(shù)大于基變量個數(shù)時，有沒有窮多解。

CBXBbx3

x4x5

00035000

x1x2x3x4x5521010153[5]1003511/2x2

x4x5

50033/511/50027/50-1/51054/50-2/501

cj-zj00-100cj-zj35000Z0=01122001Z1=15x1x2第24頁四、無（有）界解

maxz=x1+x2

-2x1+x24

x1-x22

-3x1+x23

x1,x20

若檢驗數(shù)有大于0，而對應(yīng)系數(shù)列中元素全部小于或等于零（無換出變量）則原問題有沒有界解。練習(xí)：寫出單純形表,分析檢驗數(shù)與系數(shù)關(guān)系并畫圖驗證。第25頁

線性規(guī)劃解除有唯一最優(yōu)解情況外，還有以下幾