1-3-單純形法完成課件

3.5人工變量及其處理方法

引用人工變量是用單純形法求解線性規(guī)劃問題時(shí)解決可行解問題的常用方法。人工變量法的基本思路是若原線性規(guī)劃問題的系數(shù)矩陣中沒有單位向量，則在每個(gè)約束方程中加入一個(gè)人工變量便可在系數(shù)矩陣中形成一個(gè)單位向量。

由于單位矩陣可以作為基陣，因此可選加入的人工變量為基變量。然后，再通過基變換，使得基變量中不含非零的人工變量。如果在最終的單純形表中還存在非零的人工變量，這表示無(wú)可行解。3.5人工變量及其處理方法引用人工變量是用單純1對(duì)于如下線性規(guī)劃問題對(duì)于如下線性規(guī)劃問題2首先分別對(duì)每個(gè)約束方程中加入一個(gè)人工變量

這樣我們就可選……為基變量，令非基變……

=0便可以得到一個(gè)初始基可行解

X(0)=(0，0，0…b1，b2…bm)TX(0)=(0，0，0…b1，b2…bm)T33.5.1約束方程為“>=”或“=”的情形（加人工變量）

人工變量法（確定初始可行基）：原約束方程：AX=b加入人工變量：xn+1，，xn+m人工變量是虛擬變量，加入原方程中是作為臨時(shí)基變量，經(jīng)過基的旋轉(zhuǎn)變換，將人工變量均能換成非基變量，所得解是最優(yōu)解；若在最終表中檢驗(yàn)數(shù)小于零，而且基變量中還有某個(gè)非零的人工變量，原問題無(wú)可行解。3.5.1約束方程為“>=”或“=”的情形（加人工變量）4其中第2、3個(gè)約束方程中無(wú)明顯基變量，分別加上人工變x6,x7,其中第2、3個(gè)約束方程中無(wú)明顯基變量，分別加上人工變x6,5這時(shí)，初始基和初始基可行解很明顯。X(0)=(0，0，0，11，0，3，1)T不滿足原來(lái)的約束條件。如何使得可從X(0)開始，經(jīng)迭代逐步得到x6=0，x7=0的基可行解，從而求得問題的最優(yōu)解，有兩種方法：這時(shí)，初始基和初始基可行解很明顯。X(0)=(0，0，0，163.5.2大M法（又稱懲罰法）

由于人工變量對(duì)目標(biāo)函數(shù)有很大的負(fù)影響，只要人工變量取值大于0，目標(biāo)函數(shù)值就不可能是最優(yōu)。單純形法的尋優(yōu)機(jī)制會(huì)自動(dòng)將人工變量趕到基外，從而可以找到原問題的一個(gè)可行基。這種方法我們通常稱其為大M法，又稱懲罰法。

原理：當(dāng)目標(biāo)函數(shù)為maxz，對(duì)應(yīng)的人工變量目標(biāo)系數(shù)為—M;當(dāng)目標(biāo)函數(shù)為minz，對(duì)應(yīng)的人工變量目標(biāo)系數(shù)為+M,其中

M為充分大的正數(shù)。根據(jù)最優(yōu)檢驗(yàn)數(shù)判別定理進(jìn)行基的轉(zhuǎn)換，使得人工變量逐漸換出基底，再尋求原問題的最優(yōu)解。3.5.2大M法（又稱懲罰法）

由于人工變量對(duì)目標(biāo)7

解先化標(biāo)準(zhǔn)型例3.12用單純形法求解線性規(guī)劃問題例3.12用單純形法求解線性規(guī)劃問題8然后，再添加人工變量

，將原線性規(guī)劃問題變?yōu)槔?.12用單純形法求解的過程見下表1-3-單純形法完成課件91-3-單純形法完成課件103.5.3

兩階段法原理：當(dāng)目標(biāo)函數(shù)為maxZ，對(duì)應(yīng)的人工變量目標(biāo)系數(shù)為-1;當(dāng)目標(biāo)函數(shù)為minZ，對(duì)應(yīng)的人工變量目標(biāo)系數(shù)為+1。

第一階段將原目標(biāo)系數(shù)暫時(shí)取零值。根據(jù)最優(yōu)檢驗(yàn)數(shù)判別定理進(jìn)行基的轉(zhuǎn)換，使得人工變量逐漸換出基底。

第二階段再去掉人工變量對(duì)應(yīng)的列，恢復(fù)原線性規(guī)劃問題的目標(biāo)系數(shù)，尋原問題的最優(yōu)解。3.5.3兩階段法原理：當(dāng)目標(biāo)函數(shù)為maxZ111-3-單純形法完成課件121-3-單純形法完成課件131-3-單純形法完成課件143.5.4線性規(guī)劃問題解的討論一、無(wú)可行解

maxz=2x1+4x2

x1+x210

2x1+x2

40

x1,x20人工變量不能從基底換出，此時(shí)原線性規(guī)劃問題無(wú)可行解。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兩階段法3.5.4線性規(guī)劃問題解的討論一、無(wú)可行解人工變量不能151-3-單純形法完成課件16

例: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

例:maxz=3x1+4x2

171-3-單純形法完成課件18

例maxz=3x1+5x2

3x1+5x215

2x1+x25

2x1+2x211

x1,x20

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

x4x5

00035000

x1x2x3x4x5521010153[5]1003511/2x2

x4x5

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

cj-zj00-100cj-zj35000Z0=01122001Z1=15x1x2例maxz=3x1+5x2

19四、無(wú)（有）界解

maxz=x1+x2

-2x1+x24

x1-x22

-3x1+x23

x1,x20

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

maxz=x1+x2

20

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

無(wú)可行解

退化

無(wú)窮多解

無(wú)界解人工變量不能從基底中換出基可行解中非零元素個(gè)數(shù)小于基變量數(shù)檢驗(yàn)數(shù)中零的個(gè)數(shù)多于基變量的個(gè)數(shù)檢驗(yàn)數(shù)大于零，但對(duì)應(yīng)列元素小于等于零，無(wú)換出變量線性規(guī)劃解除有唯一最優(yōu)解的情況外，還有如下幾211-3-單純形法完成課件22唯一最優(yōu)解

否

否否

是是是添加松弛變量、人工變量列出初始單純形表計(jì)算非基變量各列的檢驗(yàn)數(shù)бj所有бj0基變量中有非零的人工變量某非基變量檢驗(yàn)數(shù)為零無(wú)可行解無(wú)窮多最優(yōu)解對(duì)任一бj>0有aik≤0無(wú)界解令бk=max{бj}xk為換入變量對(duì)所有aik>0計(jì)算θi=bi/aik令θl=min{θi}第l個(gè)基變量為換出變量，alk為主元素

迭代運(yùn)算.用非基變量xk替換換出變量

.對(duì)主元素行(第l行)

令bl/alk→bl;alj/alk→ajl對(duì)主元素列(第k列)令1→alk;0→其它元素表中其它行列元素令aij-ali/alk·aik→aij

bi-bl/alk·aik→bi

бj-alj/alk·бk→бj否對(duì)目標(biāo)函數(shù)求極大值標(biāo)準(zhǔn)型線性規(guī)劃問題，單純形法計(jì)算步驟的框圖：唯一最優(yōu)解否否否是是是添加松弛變量、人工變量23練習(xí)

下表中給出某線性規(guī)劃問題計(jì)算過程中的一個(gè)單純形表，目標(biāo)函數(shù)為MaxZ=28x4+x5+2x6,約束條件為≤，表中x1,x2,x3為松弛變量，表中解的目標(biāo)函數(shù)值為Z=14（1）求a~g的值；（2）判斷給出的解是否為最優(yōu)解；

x1x2x3x4x5x6x6ax25x403600de-14/32f00115/20100cj-zjbc00-1g練習(xí)下表中給出某線性規(guī)劃問題計(jì)算過程中的一個(gè)單純24練習(xí)

下表是某求極大值線性規(guī)劃問題的初始表及迭代后的表，x4,x5為松弛變量，求表中的a~l的值及各下表m~t的值x1x2x3x4x5xm6xn1b-1c3de1001cj-zja1-200xsfxt4gh2i-11??01cj-zj07jkl練習(xí)下表是某求極大值線性規(guī)劃問題的初始表及迭代后的表25課后作業(yè)P451.5（1）（2）大M法（3）（4）兩階段法作業(yè)要求上交課后作業(yè)P451.5（1）（2）大M法26

3.5人工變量及其處理方法

引用人工變量是用單純形法求解線性規(guī)劃問題時(shí)解決可行解問題的常用方法。人工變量法的基本思路是若原線性規(guī)劃問題的系數(shù)矩陣中沒有單位向量，則在每個(gè)約束方程中加入一個(gè)人工變量便可在系數(shù)矩陣中形成一個(gè)單位向量。

由于單位矩陣可以作為基陣，因此可選加入的人工變量為基變量。然后，再通過基變換，使得基變量中不含非零的人工變量。如果在最終的單純形表中還存在非零的人工變量，這表示無(wú)可行解。3.5人工變量及其處理方法引用人工變量是用單純27對(duì)于如下線性規(guī)劃問題對(duì)于如下線性規(guī)劃問題28首先分別對(duì)每個(gè)約束方程中加入一個(gè)人工變量

這樣我們就可選……為基變量，令非基變……

=0便可以得到一個(gè)初始基可行解

X(0)=(0，0，0…b1，b2…bm)TX(0)=(0，0，0…b1，b2…bm)T293.5.1約束方程為“>=”或“=”的情形（加人工變量）

人工變量法（確定初始可行基）：原約束方程：AX=b加入人工變量：xn+1，，xn+m人工變量是虛擬變量，加入原方程中是作為臨時(shí)基變量，經(jīng)過基的旋轉(zhuǎn)變換，將人工變量均能換成非基變量，所得解是最優(yōu)解；若在最終表中檢驗(yàn)數(shù)小于零，而且基變量中還有某個(gè)非零的人工變量，原問題無(wú)可行解。3.5.1約束方程為“>=”或“=”的情形（加人工變量）30其中第2、3個(gè)約束方程中無(wú)明顯基變量，分別加上人工變x6,x7,其中第2、3個(gè)約束方程中無(wú)明顯基變量，分別加上人工變x6,31這時(shí)，初始基和初始基可行解很明顯。X(0)=(0，0，0，11，0，3，1)T不滿足原來(lái)的約束條件。如何使得可從X(0)開始，經(jīng)迭代逐步得到x6=0，x7=0的基可行解，從而求得問題的最優(yōu)解，有兩種方法：這時(shí)，初始基和初始基可行解很明顯。X(0)=(0，0，0，1323.5.2大M法（又稱懲罰法）

由于人工變量對(duì)目標(biāo)函數(shù)有很大的負(fù)影響，只要人工變量取值大于0，目標(biāo)函數(shù)值就不可能是最優(yōu)。單純形法的尋優(yōu)機(jī)制會(huì)自動(dòng)將人工變量趕到基外，從而可以找到原問題的一個(gè)可行基。這種方法我們通常稱其為大M法，又稱懲罰法。

原理：當(dāng)目標(biāo)函數(shù)為maxz，對(duì)應(yīng)的人工變量目標(biāo)系數(shù)為—M;當(dāng)目標(biāo)函數(shù)為minz，對(duì)應(yīng)的人工變量目標(biāo)系數(shù)為+M,其中

M為充分大的正數(shù)。根據(jù)最優(yōu)檢驗(yàn)數(shù)判別定理進(jìn)行基的轉(zhuǎn)換，使得人工變量逐漸換出基底，再尋求原問題的最優(yōu)解。3.5.2大M法（又稱懲罰法）

由于人工變量對(duì)目標(biāo)33

解先化標(biāo)準(zhǔn)型例3.12用單純形法求解線性規(guī)劃問題例3.12用單純形法求解線性規(guī)劃問題34然后，再添加人工變量

，將原線性規(guī)劃問題變?yōu)槔?.12用單純形法求解的過程見下表1-3-單純形法完成課件351-3-單純形法完成課件363.5.3

兩階段法原理：當(dāng)目標(biāo)函數(shù)為maxZ，對(duì)應(yīng)的人工變量目標(biāo)系數(shù)為-1;當(dāng)目標(biāo)函數(shù)為minZ，對(duì)應(yīng)的人工變量目標(biāo)系數(shù)為+1。

第一階段將原目標(biāo)系數(shù)暫時(shí)取零值。根據(jù)最優(yōu)檢驗(yàn)數(shù)判別定理進(jìn)行基的轉(zhuǎn)換，使得人工變量逐漸換出基底。

第二階段再去掉人工變量對(duì)應(yīng)的列，恢復(fù)原線性規(guī)劃問題的目標(biāo)系數(shù)，尋原問題的最優(yōu)解。3.5.3兩階段法原理：當(dāng)目標(biāo)函數(shù)為maxZ371-3-單純形法完成課件381-3-單純形法完成課件391-3-單純形法完成課件403.5.4線性規(guī)劃問題解的討論一、無(wú)可行解

maxz=2x1+4x2

x1+x210

2x1+x2

40

x1,x20人工變量不能從基底換出，此時(shí)原線性規(guī)劃問題無(wú)可行解。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兩階段法3.5.4線性規(guī)劃問題解的討論一、無(wú)可行解人工變量不能411-3-單純形法完成課件42

例: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

例:maxz=3x1+4x2

431-3-單純形法完成課件44

例maxz=3x1+5x2

3x1+5x215

2x1+x25

2x1+2x211

x1,x20

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

x4x5

00035000

x1x2x3x4x5521010153[5]1003511/2x2

x4x5

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

cj-zj00-100cj-zj35000Z0=01122001Z1=15x1x2例maxz=3x1+5x2

45四、無(wú)（有）界解

maxz=x1+x2

-2x1+x24

x1-x22

-3x1+x23

x1,x20

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

maxz=x1+x2

46

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

無(wú)可行解

退化

無(wú)窮多解

無(wú)界解人工變量不能從基底中換出基可行解中非零元素個(gè)數(shù)小于基變量數(shù)檢驗(yàn)數(shù)中零的個(gè)數(shù)多于基變量的個(gè)數(shù)檢驗(yàn)數(shù)大于零，但對(duì)應(yīng)列元素小于等于零，無(wú)換出變量線性規(guī)劃解除有唯一最優(yōu)解的情況外，還有如下幾471-3-單純形法完成課件48唯一最優(yōu)