運(yùn)籌學(xué) 單純形法的計(jì)算步驟

關(guān)于運(yùn)籌學(xué)單純形法的計(jì)算步驟第1頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六4．1 單純形表

用表格法求解LP，規(guī)范的表格——單純形表如下：第2頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六計(jì)算步驟(1).找出初始可行基，確定初始基可行解，建立初始單純形表。(2).檢驗(yàn)各非基變量xj的檢驗(yàn)數(shù)，若j

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

>0，j=m+1，…，n中，若有某個(gè)k對應(yīng)xk的系數(shù)列向量Pk0，則此問題是無界解，停止計(jì)算。否則，轉(zhuǎn)入下一步。(4).根據(jù)max(j>0)=k，確定xk為換入變量，按

規(guī)則計(jì)算=min{bi/aik\aik>0}可確定第l行的基變量為換出變量。轉(zhuǎn)入下一步。第3頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六

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第4頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六

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第5頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六

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，4，0)T，z3=14第6頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六§5單純形法的進(jìn)一步討論5．1 人工變量法

解決初始基可行解的問題。當(dāng)某個(gè)約束方程中沒有明顯的基變量時(shí)，在該方程中加上人工變量。第7頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六其中第2、3個(gè)約束方程中無明顯基變量，分別加上人工變x6,x7第8頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六這時(shí)，初始基和初始基可行解很明顯。X(0)=(0，0，0，11，0，3，1)T不滿足原來的約束條件。如何使得可從X(0)開始，經(jīng)迭代逐步得到x6=0，x7=0的基可行解，從而求得問題的最優(yōu)解，有兩種方法：第9頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六反之，若加了人工變量的問題解后最優(yōu)解中仍含人工變量為基變量，便說明原問題無可行解。例3的單純形表格為：

只要原問題有可行解，隨著目標(biāo)函數(shù)向最大化方向的改善，人工變量一定會逐步換出基，從而得到原問題的基可行解，進(jìn)而得到基最優(yōu)解。3.大M法在目標(biāo)函數(shù)中加上懲罰項(xiàng)

max=3x1-x2-x3-Mx6-Mx7其中M為充分大的正數(shù)。第10頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六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

000-1/3-1/3

X*=(4，1，9，0，0),z*=2第11頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六2.兩階段法第一階段：以人工變量之和最小化為目標(biāo)函數(shù) min=x6+x7

第二階段：以第一階段的最優(yōu)解(不含人工變量)為初始解，以原目標(biāo)函數(shù)為目標(biāo)函數(shù)。第12頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六第13頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六第14頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六第15頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六5.2線性規(guī)劃問題解的討論一、無可行解

maxz=2x1+4x2

x1+x210

2x1+x2

40

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

x5

0-1

0000-1

x1x2x3x4x540210-1110[1]1100cj1040/2x1

x5

0-1

200-1-2-111011100

cj-zj0-1-2-10cj-zj210-10Z0=-40Z1=-20第16頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六第17頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六

例:maxz=3x1+4x2

x1+x240

2x1+x260

x1-x2=0

x1,x20

此題初始解是退化的。最優(yōu)解也是退化解。退化解迭代中，當(dāng)換入變量取零值時(shí)目標(biāo)函數(shù)值沒有改進(jìn)，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第18頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六第19頁，共25頁，2022年，5月20日，10點(diǎn)20分，星期六

例maxz=3x1+5x2

3x1+5x215

2x1+x25

2x1+2x211

x1,x20

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

x4x5

00035000

x1x2x3x4x5521010153[5]1003511/5x2

x4x5

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