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

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

2、基變量基變量基變量111110BCNBCCzcBNBIbBXCXXXBBNjjBBsNB基變量基變量非基變量非基變量【例】0,44222326max32131321321xxxxxxxxxxxz0,4422200326max321531432154321xxxxxxxxxxxxxxxz加入松弛變量x4、x5，對(duì)上述模型進(jìn)行標(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如何而來(lái)？知識(shí)點(diǎn)1 目標(biāo)函數(shù)為max時(shí)，判斷最優(yōu)的準(zhǔn)則為0； 目標(biāo)函數(shù)為min時(shí)，迭代過(guò)程與max一樣，判斷最優(yōu)的準(zhǔn)則為0。 性質(zhì)6：線性規(guī)劃的原問(wèn)題與其對(duì)偶問(wèn)題之間存在一對(duì)互補(bǔ)的基解；其中原問(wèn)題的松弛變量對(duì)應(yīng)對(duì)偶問(wèn)題的變量，對(duì)偶問(wèn)題的剩余變量對(duì)應(yīng)原問(wèn)題的變量；這些互相對(duì)應(yīng)的變量如果在一個(gè)問(wèn)題的解中是基變量，則在另一個(gè)問(wèn)題的解中是非基變量；將這對(duì)互補(bǔ)的基解分別代入原問(wèn)題和對(duì)偶問(wèn)題的目標(biāo)函數(shù)有z=。知識(shí)點(diǎn)2【例】線性規(guī)劃問(wèn)題為)5 , 1(0155164122200032max524132154321jxxxxxxxxxxxxxzj23000CBXBbx1x2x3x

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

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

6、純形法繼續(xù)迭代用對(duì)偶單純形法繼續(xù)迭代非可行解非可行解 非可行解非可行解 編制新的單純形表重新計(jì)算編制新的單純形表重新計(jì)算【例】某家電廠家利用現(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)試工序利潤(rùn)（元）利潤(rùn)（元）0612521115時(shí)時(shí)24時(shí)時(shí) 5時(shí)時(shí)0, 5 2426 155 2max 212121221xxxxxxxs.t.xxz32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/1500012yyyyyxxxxxxxxjjzc 原問(wèn)題最優(yōu)解對(duì)偶問(wèn)題

7、最優(yōu)解（相差負(fù)號(hào)）最終單純形表分析 的變化 的變化僅影響 的變化。jcjcjjjzc 設(shè)備設(shè)備A 設(shè)備設(shè)備B調(diào)試工序調(diào)試工序利潤(rùn)（元）利潤(rùn)（元）0612521115時(shí)時(shí)24時(shí)時(shí) 5時(shí)時(shí)D1.52問(wèn)題1：當(dāng) 該公司最優(yōu)生 產(chǎn)計(jì)劃有何變化？2, 5 . 121cc最終單純形表變?yōu)椋?/98/10002/34/10102/322/14/10012/75 . 12/154/51002/15000025 . 121354321xxxxxxxxbXCBBjcjjzc jjBjjBjjPYcPCcPBCc 1對(duì)變化后的單純形表繼續(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)解 問(wèn)題2：設(shè)產(chǎn)品II利潤(rùn)為 ， 求原最優(yōu)解不變時(shí) 的范圍。)1 ( 的變化僅影響的變化僅影響 的變化；的變化；在最后一張單純形表中求出變化后在最后一張單純形表中求出變化后的的 ；原最優(yōu)解不變，需滿足原最優(yōu)解不變，需滿足 ；由由 確定的不等式可求出確定的不等式可求出 的范的范圍。圍。2cjj0j0j2321414

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

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

11、3)1 (2/ )7(2/15)1 (524152/34/ 102/ 14/ 102/154/511bBb11,0b原最優(yōu)解保持不變，則原最優(yōu)解保持不變，則增加一個(gè)變量 的分析 增加一個(gè)變量相當(dāng)于增加一種產(chǎn)品。分析步驟：1、計(jì)算2、計(jì)算3、若 ，原最優(yōu)解不變； 若 ，則按單純形表繼續(xù)迭代 計(jì)算找出最優(yōu)解。jxjjjjjPYczcjjPBP10j0j問(wèn)題5：設(shè)生產(chǎn)第三種產(chǎn)品，產(chǎn)量為 件， 對(duì)應(yīng)的 求最優(yōu)生產(chǎn)計(jì)劃。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如果某個(gè)系數(shù)aij發(fā)生變化，如何進(jìn)行分析？最終單純形表中，xj對(duì)應(yīng)的系數(shù)列向量發(fā)生了變化，即Pj發(fā)生了變化。jjPBP1增加一個(gè)約束條件的分析 增加一個(gè)約束條件相當(dāng)于增添一道工序或一種資源。分析方法：將最優(yōu)解代入新的約束中（1 1）若滿足要求，則原最優(yōu)解不變；）若滿足要求，則原最優(yōu)解不變；（2 2）若不滿足要求，則原最優(yōu)解改變，）若不滿足要求，則原最優(yōu)解改變，將新增的約束條件添入最終的單純形表將新增的約束條件添入最終的單純形表中繼續(xù)分析。中繼續(xù)分析。靈敏度分析的步驟歸納如下：（1）將參數(shù)的改變計(jì)算反映到最終 單純形表上；（2）檢查原問(wèn)題是否仍為可行解；（3）檢查對(duì)偶問(wèn)題是否仍為可行解；（4）按下表所列情況得出結(jié)論