1第一章線性規(guī)劃2§1-3單純形法

一.線性規(guī)劃的基本定義二.線性規(guī)劃解之間的關(guān)系三.線性規(guī)劃解的性質(zhì)四.單純形法引例五.單純形法(SM)原理六.單純形法的表算七.單純形法的進一步討論

1.人工變量法

2.多最優(yōu)解的情況八.單純形法的矩陣描述31.人工變量法對于標準的線性規(guī)劃問題：

其中，約束方程組的系數(shù)矩陣中不含有m階的單位矩陣，即：其約束方程可以表示為：4

引入m個人工變量xn+I,i=1,2,…,m,這m個人工變量便可以構(gòu)成m階的單位矩陣，取這m個人工變量為初始基變量，便可得到新的約束方程組：5上式最通常的表示為：

其中xn+1,xn+2,…,xn+m即為引入的人工變量。引入人工變量之后，該約束方程組便可得到一個m×m階的單位矩陣，符合用單純形法進行計算的初始格式，因此，在引入人工變量后，就很容易進行求解了。6

但是，我們必須注意：人工變量是不存在的量，只是為了計算的方便而引入的，因此，在計算的結(jié)果中必須要剔除人工變量，所得到的解才是原問題的最優(yōu)解。如果所得的最優(yōu)解中，每個人工變量都是0，那么自然就可以剔除所增加的人工變量，得到原規(guī)劃問題的最優(yōu)解；如果至少有一個人工變量的取值是大于0的，說明什么？出現(xiàn)這種情況，則說明：原線性規(guī)劃無可行解。7

我們介紹兩種特殊的方法來避免人工變量取正值的情況。（1）大M法基本思想：在有最優(yōu)解的線性規(guī)劃問題中，由于人工變量在最優(yōu)解中的取值必須為0，所以，通過引入一個無窮大的正數(shù)M來將原目標函數(shù)進行修正。

這個無窮大的正數(shù)M通常稱為罰因子。8具體做法是：考慮如下新的線性規(guī)劃問題：如果最優(yōu)解中含有正的人工變量，由上式的結(jié)構(gòu)特點可知：目標函數(shù)不可能實現(xiàn)最大化。這時，原線性規(guī)劃問題無可行解。取無窮大正數(shù)M作為罰因子的作用就是迫使所有的人工變量都為0。這樣，新的線性規(guī)劃問題就和原來的線性規(guī)劃問題完全等價。9例

用大M法求解例2中的環(huán)保線性規(guī)劃問題。解：由例2得該問題的數(shù)學模型為：10引進剩余變量，松弛變量，人工變量，以及無窮大正數(shù)M，得新線性規(guī)劃模型為：11用單純形表表示為：Cj→-1000-8000000-M-MΘiCBXBbx1x2x3x4x5x6x7x8-MX71[1]0-1000101-MX81.60.810-1000120X521000100020X61.401000100－-z2.6M-1000+1.8M-800+M－M－M0000

求得-z(0)＝2.6M，以及非基變量對應的σ值：

σ1＝-1000+1.8M；因為有σ>0,所以該初始基可行解不是最優(yōu)解。由得x1為入基變量。

再求對應x1的θ值：θ7=1/1=1；θ8=1.6/0.8=2；θ5=2/1=2；θ6=“－”,由min{1,2,2}=1=θ1得對應得基變量x7為出基變量。由x1所在的列和x7所在的行的交點a11=1為主元。σ2＝-8000+M；σ3＝-M；σ4＝-M12以a11為主元做旋轉(zhuǎn)運算得新的基可行解如下表所示：

求得-z(1)＝1000+0.8M，以及非基變量對應的σ值：

σ2=-800+M

；因為還有σ>0,所以該基可行解也不是最優(yōu)解。由得x2為入基變量。

再求對應x2的θ值：θ1=“-”；θ8=0.8/1=0.8；θ5=“-”；θ6=1.4/1＝1.4,由min{0.8,1.4}=0.8=θ8對應得基變量x8為出基變量。由x1所在的列和x7所在的行的交點a22=1為主元。Σ3=-1000+0.8M；

σ4=-M；σ7=1000-1.8M

Cj→-1000-8000000-M-MΘiCBXBbx1x2x3x4x5x6x7x8-1000X1110-100010--MX80.80[1]0.8-100-0.810.80X51001010-10-0X61.4010001001.4-z1000+0.8M0-800+M-1000+0.8M－M001000-1.8M013以a22為主元做旋轉(zhuǎn)運算得新的基可行解如下表所示：

求得-z(2)＝1640，以及非基變量對應的σ值：

σ3=-360

；對于無窮大的正數(shù)M，所有的σ都滿足σ≤0的要求,所以該基可行解為最優(yōu)解。即：x*=(1,0.8,0,0,1,0.6,0,0)T；Z*=-1640剔除人工變量、剩余變量和松弛變量，得原問題得最優(yōu)解為：x*=(1,0.8)T；Z*=1640σ4=-800；

σ7=360-M；σ8=800-M

Cj→-1000-8000000-M-MΘiCBXBbx1x2x3x4x5x6x7x8-1000X1110-100010-800X20.8010.8-100-0.810X51001010-100X60.600-0.80010-1-z164000-360－80000360-M800-M14（2）兩階段法

根據(jù)先引入人工變量，但在最優(yōu)解中得人工變量必須為0的基本思想，將新的規(guī)劃問題分為兩個階段進行求解。第一階段：求以人工變量為目標函數(shù)為最小的線性規(guī)劃問題，如果該問題有最優(yōu)解，且目標函數(shù)為0，則原規(guī)劃有解；如果該階段問題的最優(yōu)目標函數(shù)值不為0，則說明人工變量中至少有一個為正數(shù)，原規(guī)劃問題無可行解，計算停止；第二階段：如果該問題有最優(yōu)解，且目標函數(shù)為0，則以第一階段問題的最優(yōu)解為初始基可行解求原規(guī)劃問題。15具體做法為：第一階段：設為引入的人工變量，求下列線性規(guī)劃問題：16如果求得最優(yōu)解X*，則最優(yōu)目標值將出現(xiàn)兩種情況：

(1)Z*=0，表明所有引入的人工變量在最優(yōu)解中的值為0，剔除所有人工變量后的最優(yōu)解即可作為原線性規(guī)劃問題的一個基可行解進入第二階段的計算；

(2)Z*>0，說明至少有一個人工變量取正值，原線性規(guī)劃問題無可行解，計算終止。17第二階段：在第①種情況下的最終單純形表中，刪除所有人工變量所在的列，所有的C值改為原規(guī)劃問題中目標函數(shù)的價值系數(shù)Cj，建立原規(guī)劃問題的單純形表，并以刪除人工變量后的X*作為初始可行解，進行單純形算法的迭代計算，直至得到原規(guī)劃問題的最優(yōu)解。18例：

用兩階段法求下列線性規(guī)劃問題：解：首先引入剩余變量x4將原規(guī)劃問題化為標準形式：

19第一階段：引入人工變量x5、x6，并化為標準形式得：20

由此得第一階段問題的單純形表、z0以及各σ和θ值如下表所示：

Cj→0000-1-1θiCBXBbx1x2x3x4x5x6-1X52[1]11-1102-1X6621-20013-z832-1－100σ不滿足σ≤0的要求，該解不是最優(yōu)解，以a11進行第一次迭代，得新的基可行解以及z1、σ和θ各值如下表所示：Cj→0000-1-1θiCBXBbx1x2x3x4X5x60X12111-110--1X620-1-4[2]-211-z20-1-42-3021所計算的σ值中依然由正數(shù)出現(xiàn)，所得的解依然不是最優(yōu)解。以a24為主元進行再一次旋轉(zhuǎn)迭代得新的基可行解以及z2、σ和θ各值如下表所示：Cj→0000-1-1θiCBXBbx1x2x3x4X5x60X1311/2-1001/2-0X410-1/2-21-11/21-z00000-1-1所有非基變量滿足σ≤0，該基可行解為最優(yōu)解。即：，且原問題有最優(yōu)解，進入第二階段計算。22第二階段：在第一階段得最優(yōu)解中刪除人工變量得第二階段的初始基可行解；在由第一階段最后一張單純形表中刪去人工變量所在的列，并將價值系數(shù)行換成原問題的價值系數(shù)Cj，如下所示：Cj→0000-1-1θiCBXBbx1x2x3x4X5x60X1311/2-1001/2-0X410-1/2-21-11/21-z00000-1-12-5023Cj→20-50θiCBXBbx1x2x3x42X1311/2-100X410-1/2-21-z－60-1-30

計算Z0、σ值得各σ值均滿足σ≤0得要求，故此解即為原規(guī)劃問題得最優(yōu)解。去掉剩余變量x4得最優(yōu)解為：最優(yōu)值為：

得原規(guī)劃問題得初始單純形表如下所示：242.多最優(yōu)解前面我們在用圖解法求解的時候，曾經(jīng)遇到過多最優(yōu)解的情況，我們知道：當目標函數(shù)的等值線達到最大（或者最?。r且和可行域的某一邊重合，則會出現(xiàn)多最優(yōu)解（任意多最優(yōu)解）的情況。那么，在用單純形法計算的時候，怎樣才能判別出什么時候由唯一最優(yōu)解，什么時候會出現(xiàn)多最優(yōu)解的情形？25在單純形法解的判斷定理中，我們知道：當σ≤0時，的基可行解為最優(yōu)解，那么，就可能出現(xiàn)兩種情況：①所有σ<0,如前面例10中的最后的單純形表：Cj→20-50θiCBXBbx1x2x3x42X1311/2-100X410-1/2-21-z－60-1-30在這種情況下，σ≤0條件滿足，所得的解為最優(yōu)解；26②σ值存在兩種情況，即有σ<0的情況，也有σ＝0的情況，如前面鋼材下料問題中的最終單純形表所得到的σ值：Cj→-1-1-1-1-1-1-1-1θiCBXBBx1x2x3x4x5x6x7X8-1x1401[1]3/503/50-2/5-4/540-1x650011/203/211/2050-1x4200-1-1/51-6/504/58/511000-1/100-1/100-1/10-1/5其中，非基變量x2對應的σ2＝0。取σ2＝0對應的x2作為入基變量，得θ如上表所示，將x1作為出基變量進行旋轉(zhuǎn)迭代得：27得新的基可行解為為：

X＝（0，40，0，60，0，10）T，且所有的σ<0,滿足σ≤0要求，該解也為最優(yōu)解，

Z*＝110不變。Cj→-1-1-1-1-1-1-1-1θiCBXBBx1x2x3x4x5x6x7X8-1X240113/503/50-2/5-4/5-1x610-10-1/1009/1019/104/5-1x460102/51-3/502/54/5110-20-3/100-1/100-1/10-1/528

鋼材下料問題除了前面的最優(yōu)解以外，當σ＝0可以得出在保證使用的鋼材數(shù)為110根不變的情況下的其它最優(yōu)解。由此，我們可以得到線性規(guī)劃問題存在多最優(yōu)解的判斷依據(jù)：

在線性規(guī)劃問題最終單純形表上，至少有一個非基變量的檢驗數(shù)為0。

298.單純形法的矩陣描述

對任意一個線性規(guī)劃，當其約束方程的系數(shù)矩陣能夠按照基和非基來分割的時候，其對應的變量就可以用基變量和非基變量來對應分割，其目標函數(shù)中的價值系數(shù)也能夠分割成基變量對應的系數(shù)和非基變量對應的系數(shù)。設：在約束方程中的系數(shù)矩陣A由基B和非基N組成，A=[AN]；所對應的基變量為XB，非基變量為XN，即：X=[XBXN]T；對應基變量和非基變量的價值系數(shù)分別為CB和CN，C=[CBCN]。則線性規(guī)劃的矩陣表達式：＝>＝>30當適當引進松弛、剩余與人工等輔助變量，將其化為可進行單純形法迭代計算的下列初始標準型時，其約束方程的系數(shù)矩陣則變?yōu)閇AI]，所對應的變量變?yōu)閇XAXI]T。其中，XA由決策變量或加上剩余變量組成，XI由松弛變量或加上人工變量組成；與XA、XI對應，價值向量C分為CA、CI；I為單位陣；b≥0。當取定單位陣I為一個基陣后，其系數(shù)矩陣、解向量、價值向量可按B與N的形式重新分塊，因此對應有：(BN)=>(AI)，(XBXN)T=>

(XAXI)T

，(CBCN)=>(CACI)這樣，就單純形法的矩陣形式又可寫成為：31從而，有：顯然，由于要求XB、XN均滿足非負約束，所以下面討論的均指基可行解。將B-1作用于約束方程，得：代入目標函數(shù)，得：于是，檢驗數(shù)變?yōu)椋簩跏嫉木哂袉挝痪仃嚨南禂?shù)矩陣[AI]：32

注意到B-1I=B-1，所以B-1可在各次迭代表上對照初始單位陣I的位置讀出。0

由于每次迭代只置換一個變量，因此前后兩個基陣只改變一列，而前一基陣恒是單位陣，故后一基陣求逆只須將換入變量的對應列向量化為單位向量即可。至此，完成了單純形法的矩陣描述，從而為下面討論對偶問題與靈敏度分析提供了理論基礎。CICACj→-CBB-