運籌學(xué)基礎(chǔ)-線性規(guī)劃(3)精彩ppt

1、1單純形法(Simplex Method)是美國人丹捷格(G.Dantzig)1947年創(chuàng)建的這種方法簡捷、規(guī)范，是舉世公認的解決線性規(guī)劃問題行之有效的方法。 表格法 矩陣法改良的單純形法 單純形法的矩陣計算線性規(guī)劃2Cj比值CBXBb檢驗數(shù)j檢驗數(shù)：初始時是目標函數(shù)的系數(shù)（隨基的調(diào)整變化）變量符號基變量符號（隨基的調(diào)整變化）基變量在目標函數(shù)中的系數(shù)（變化）約束方程的常數(shù)項約束方程的變量系數(shù)有一個檢驗數(shù)j=0，此時基解不是最優(yōu)；所有檢驗數(shù)j0 )= k ,則確定xk入基檢驗數(shù)j=Cj Ciaij如果對j，j 0則最優(yōu)，否則到下一步第四步：基變換=min (bi / aik 0 )= bl /

2、alk ,則確定xn+l 出基第五步：以alk為主元素進行迭代，將xn+l換為xk，求新可行解第六步：繼續(xù)判定是否最優(yōu)，如果不是最優(yōu)再求求新可行解第二步：找初始可行基，確定初始可行解第一步：將線性規(guī)劃問題標準化，求出增廣矩陣線性規(guī)劃20 x1 x2 x3 x4x5x6b Max z=2x1+3x2 2x1+2x2+x3 =12 x1+2x2+x4 =8 4x1 +x5 =16 4x2 +x6=12標準型標準型Max z=2x1+3x2 2x1+2x2 12x1+2x2 8 4x1 16 4x2 12 x1, x2, x3 000003216100048010211200122000012000

3、401線性規(guī)劃21x1 x2 x3 x4x5x6b00003216100048010211200122000012000401線性規(guī)劃2200003216100048010211200122000012000401-9000021610004201001600102-3/4 0-1/2-1/23000101/4-130-200081-400020100120-21001/4 2-1/21/23000101/4-14-1/8-3/200041/2-200041/400010-1/4-11000 1002-1/81/20100令非基變量x4=0, x5=0,得到最優(yōu)解：線性規(guī)劃23=0,16242

4、04451021212121xxxxxxxxZMax000510161024200144x1 x2 x3 x4 b化為標準形化為標準形線性規(guī)劃=0,16242044510432142132121xxxxxxxxxxxxZMax24=0,122316423421212121xxxxxxxxZMin=122316420034max4213214321xxxxxxxxxxZ000-3-412-1023160-142x1 x2 x3 x4 b化為標準形化為標準形線性規(guī)劃25maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x

5、2 , x3 0S.t.02134 1216323x1 x2 x3 b已經(jīng)是標準型，不需再劃為標準型線性規(guī)劃26n 用單純形法解題時，需要有一個單位矩陣作為。n 當(dāng)約束條件都是“”時，加入就形成了。n 但如果存在“”或“”型的約束，就的。 采用人造基的辦法：采用人造基的辦法： 處理方法有兩種：處理方法有兩種：線性規(guī)劃27maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x2 , x3 0S.t.沒有單位矩陣，不符合構(gòu)造初始基的條件，沒有單位矩陣，不符合構(gòu)造初始基的條件， 。 maxZ= 3x1 - x2 -2 x3

6、-M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0 人工變量最終必須等于0才能保持原問題性質(zhì)不變。 為保證人工變量為0，在。 M為無限大的正數(shù)，這是一個懲罰項，倘若人工變量不為零，則目標函數(shù)就永遠達不到最優(yōu)，所以必須逐步從基變量中。 如若到，那么這個問題就沒有可行解，當(dāng)然亦。 線性規(guī)劃28按大按大M法構(gòu)造人造基，引入人工變量法構(gòu)造人造基，引入人工變量x4 , x5 的輔助問題如下：的輔助問題如下： 【例例】 maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3

7、x3 =6 x1 - 2 x2 + x3 =4 x1 , x2 , x3 0S.t. maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0線性規(guī)劃290-M-2-13411-2160-323-M0110M0-2-2M-13+4M4 11-216 0-3230 0 1 3+3M -1+2M -2-3M 0 -M 6Mx1 x2 x3 x4 x5 b10M0-2-2M-13+4M411-2160-323001 3+4M -1 -2-2M 0

8、0 10M線性規(guī)劃3010M0-2-2M-13+4M411-2160-323001-6+2M0 1+2M-3-8M/30212-8/3020-12/31-1-4M/3-1/31/3-7-M-1/20-5/3011/21-4/3031/20-2/31-M-5/6-1/61/6線性規(guī)劃31劃為標準型，并按大劃為標準型，并按大M法引入人工變量法引入人工變量x4 , x5 的輔助問題如下：的輔助問題如下：=0,12324112332131321321321xxxxxxxxxxxxxxZMin=0,12324112003717316532143217654321xxxxxxxxxxxxxxMxMxxxx

9、xxZMax松馳變量松馳變量剩余變量剩余變量人工變量人工變量懲罰項懲罰項線性規(guī)劃320-M0-1-1311010-230021-411011-2100-10-M0104M00 -1+3M-1+M3-6M11010-230021-411011-21-M0-10 0010 x1 x2 x3 x4 x5 x6 x7 bx1 x2 x3 x4 x5 x6 x7 b=0,12324112003717316532143217654321xxxxxxxxxxxxxxMxMxxxxxxZMax線性規(guī)劃33M+1-3M+10 0-1+M11100-21-2001010-110-23-M0-1000102-M-10 00111010-21-20001