單純形法解法的矩陣描述及靈敏度分析

1、單純形解法的矩陣描述單純形解法的矩陣描述 線性規(guī)劃問題0.maxXbAXtsCXz 引入松弛變量Xs,化為標(biāo)準(zhǔn)型：0, 0. .0maxsssXXbIXAXtsXCXz 用單純形法求解以上模型，初始單純形表為：單純形解法的矩陣描述單純形解法的矩陣描述00NBjjssNBCCzcINBbXXXX非基變量非基變量基變量基變量當(dāng)基變量為 時，新的單純形表BX111110BCNBCCzcBNBIbBXCXXXBBNjjBBsNB基變量基變量非基變量非基變量當(dāng)當(dāng)11; 0BCNBCCBBN時，得到時，得到最優(yōu)解最優(yōu)解001*bBXXB比較兩個單純形表00NBjjssNBCCzcINBbXXXX非基變量非

2、基變量基變量基變量111110BCNBCCzcBNBIbBXCXXXBBNjjBBsNB基變量基變量非基變量非基變量【例】0,44222326max32131321321xxxxxxxxxxxz0,4422200326max321531432154321xxxxxxxxxxxxxxxz加入松弛變量x4、x5，對上述模型進行標(biāo)準(zhǔn)化處理初始單純形表6-2300CBXBbx1x2x3x4x50 x422-12100 x54104016-23006-2300CBXBbx1x2x3x4x56x1410401-2x26016-1200-9-2-2B矩陣矩陣N矩陣矩陣I單位陣單位陣B的逆陣的逆陣B-1最終單

3、純形表I單位陣單位陣B-1 N如何而來？知識點1 目標(biāo)函數(shù)為max時，判斷最優(yōu)的準(zhǔn)則為0； 目標(biāo)函數(shù)為min時，迭代過程與max一樣，判斷最優(yōu)的準(zhǔn)則為0。 性質(zhì)6：線性規(guī)劃的原問題與其對偶問題之間存在一對互補的基解；其中原問題的松弛變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問題的變量；這些互相對應(yīng)的變量如果在一個問題的解中是基變量，則在另一個問題的解中是非基變量；將這對互補的基解分別代入原問題和對偶問題的目標(biāo)函數(shù)有z=。知識點2【例】線性規(guī)劃問題為)5 , 1(0155164122200032max524132154321jxxxxxxxxxxxxxzj23000CBXBbx1x2x3x

4、4x52x13101/20-1/50 x4400-214/53x2301001/5cj-zj00-10-1/5原問題變量原問題變量原問題松弛變量原問題松弛變量對偶問題變量對偶問題變量對偶問題剩余變量對偶問題剩余變量 其中XB=B-1b為原問題的基解；而YS=CBB-1為對偶問題的基解。111110BCNBCCzcBNBIbBXCXXXBBNjjBBsNB基變量基變量非基變量非基變量知識點知識點3 3：單純形法與對偶單純形法的對比單純形法與對偶單純形法的對比 單純形法求解的基本思想：保持原問題為可行解，通過迭代，增大目標(biāo)函數(shù)，當(dāng)其對偶問題的解也為可行解時，就達到了目標(biāo)函數(shù)的最優(yōu)值。 對偶單純形法

5、的基本思想：保持對偶問題為可行解，通過迭代，減小目標(biāo)函數(shù)，當(dāng)原問題也達到可行解時，即得到了目標(biāo)函數(shù)的最優(yōu)值。靈敏度分析 所謂靈敏度分析，就是考察當(dāng)線性規(guī)劃問題中的參數(shù)aij、bi、cj等發(fā)生變化時，線性規(guī)劃問題最優(yōu)解如何變化的問題。jjjBjjPYcPBCcPBPPBPbBbbBb11111,某一個參數(shù)發(fā)生變化時，通過計算，原最終單純形表會出現(xiàn)以下幾種情況：原問題原問題 對偶問題對偶問題 結(jié)論或繼續(xù)計算的步驟結(jié)論或繼續(xù)計算的步驟可行解可行解 可行解可行解 問題的最優(yōu)解不變問題的最優(yōu)解不變可行解可行解 非可行解非可行解 用單純形法繼續(xù)迭代用單純形法繼續(xù)迭代非可行解非可行解 可行解可行解 用對偶單

6、純形法繼續(xù)迭代用對偶單純形法繼續(xù)迭代非可行解非可行解 非可行解非可行解 編制新的單純形表重新計算編制新的單純形表重新計算【例】某家電廠家利用現(xiàn)有資源生產(chǎn)兩種產(chǎn)品某家電廠家利用現(xiàn)有資源生產(chǎn)兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：，有關(guān)數(shù)據(jù)如下表： 設(shè)備設(shè)備A 設(shè)備設(shè)備B調(diào)試工序調(diào)試工序利潤（元）利潤（元）0612521115時時24時時 5時時0, 5 2426 155 2max 212121221xxxxxxxs.t.xxz32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/1500012yyyyyxxxxxxxxjjzc 原問題最優(yōu)解對偶問題

7、最優(yōu)解（相差負號）最終單純形表分析 的變化 的變化僅影響 的變化。jcjcjjjzc 設(shè)備設(shè)備A 設(shè)備設(shè)備B調(diào)試工序調(diào)試工序利潤（元）利潤（元）0612521115時時24時時 5時時D1.52問題1：當(dāng) 該公司最優(yōu)生 產(chǎn)計劃有何變化？2, 5 . 121cc最終單純形表變?yōu)椋?/98/10002/34/10102/322/14/10012/75 . 12/154/51002/15000025 . 121354321xxxxxxxxbXCBBjcjjzc jjBjjBjjPYcPCcPBCc 1對變化后的單純形表繼續(xù)迭代4/98/10002/34/10102/322/14/10012/75 .

8、 12/154/51002/15000025 . 121354321xxxxxxxxbXCBBjcjjzc 新的最終單純形表為2/3010/100005/11032105/10125 . 1615/4006000025 . 121454321xxxxxxxxbXCBBjcjjzc 最優(yōu)解 問題2：設(shè)產(chǎn)品II利潤為 ， 求原最優(yōu)解不變時 的范圍。)1 ( 的變化僅影響的變化僅影響 的變化；的變化；在最后一張單純形表中求出變化后在最后一張單純形表中求出變化后的的 ；原最優(yōu)解不變，需滿足原最優(yōu)解不變，需滿足 ；由由 確定的不等式可求出確定的不等式可求出 的范的范圍。圍。2cjj0j0j2321414

9、10002/34/ 10102/312/ 14/ 10012/722/154/51002/1500001221354321xxxxxxxxbXCBBjcjjzc 13102321, 04141即即產(chǎn)品產(chǎn)品IIII利潤為利潤為 時的最終單純形表時的最終單純形表)1 (分析 的變化 的變化僅影響 ，即原最優(yōu)解的可行性可能會變化：可行性不變，則原最優(yōu)解不變?？尚行圆蛔?，則原最優(yōu)解不變。可行性改變，則原最優(yōu)解改變，可行性改變，則原最優(yōu)解改變，用對偶單純形法，找出最優(yōu)解。用對偶單純形法，找出最優(yōu)解。ibibib問題3：設(shè)備B的能力從24增加到32小時，原最優(yōu)解如何變化？2/12/112/35532152

10、/34/102/14/102/154/511bBb出現(xiàn)負值，為不可行解，用對偶單純形法繼續(xù)求解2/14/10002/34/10102/112/14/10012/1122/154/51002/3500001221354321xxxxxxxxbXCBBjcjjzc 把計算結(jié)果代入原最終單純形表中把計算結(jié)果代入原最終單純形表中可行性改變，用對偶單純形法換基求解。主元主元2001061040201001152001501500001241354321xxxxxxxxbXCBBjcjjzc 新的最優(yōu)解新的最優(yōu)解經(jīng)過迭代得經(jīng)過迭代得：問題4：設(shè)調(diào)試工序可用時間為 小時，求 ，原最優(yōu)解保持不變。)5(?2/

11、3)1 (2/ )7(2/15)1 (524152/34/ 102/ 14/ 102/154/511bBb11,0b原最優(yōu)解保持不變，則原最優(yōu)解保持不變，則增加一個變量 的分析 增加一個變量相當(dāng)于增加一種產(chǎn)品。分析步驟：1、計算2、計算3、若 ，原最優(yōu)解不變； 若 ，則按單純形表繼續(xù)迭代 計算找出最優(yōu)解。jxjjjjjPYczcjjPBP10j0j問題5：設(shè)生產(chǎn)第三種產(chǎn)品，產(chǎn)量為 件， 對應(yīng)的 求最優(yōu)生產(chǎn)計劃。6xTPc)2 , 4 , 3(, 3661243)2/1 , 4/1 , 0(362072432/34/102/14/102/154/516P解：解：代入最終原單純形表中2/ 14/

12、10002/34/ 10102/312/ 14/ 10012/722/154/51002/1500001221354321xxxxxxxxbXCBBjcjjzc 120736x主元主元迭代后，得：4/58/ 102/ 104/38/ 102/ 104/332/ 14/ 10012/724/98/312/704/300001261354321xxxxxxxxbXCBBjcjjzc 010036x如果某個系數(shù)aij發(fā)生變化，如何進行分析？最終單純形表中，xj對應(yīng)的系數(shù)列向量發(fā)生了變化，即Pj發(fā)生了變化。jjPBP1增加一個約束條件的分析 增加一個約束條件相當(dāng)于增添一道工序或一種資源。分析方法：將最優(yōu)解代入新的約束中（1 1）若滿足要求，則原最優(yōu)解不變；）若滿足要求，則原最優(yōu)解不變；（2 2）若不滿足要求，則原最優(yōu)解改變，）若不滿足要求，則原最優(yōu)解改變，將新增的約束條件添入最終的單純形表將新增的約束條件添入最終的單純形表中繼續(xù)分析。中繼續(xù)分析。靈敏度分析的步驟歸納如下：（1）將參數(shù)的改變計算反映到最終 單純形表上；（2）檢查原問題是否仍為可行解；（3）檢查對偶問題是否仍為可行解；（4）按下表所列情況得出結(jié)論