第三章 對(duì)偶理論和靈敏度分析(第7-8節(jié))

1、第第1頁頁以前討論線性規(guī)劃問題時(shí)，假定以前討論線性規(guī)劃問題時(shí)，假定aij , bi , cj 都是常數(shù)。都是常數(shù)。 市場條件變化市場條件變化 cj 值發(fā)生變化值發(fā)生變化 工藝技術(shù)條件變化工藝技術(shù)條件變化 a i j 值發(fā)生變化值發(fā)生變化 資源投入后產(chǎn)生的經(jīng)濟(jì)效果的變化資源投入后產(chǎn)生的經(jīng)濟(jì)效果的變化 bi 值發(fā)生變化值發(fā)生變化 實(shí)際上，這些系數(shù)往往都是估計(jì)值和預(yù)測值，而不是實(shí)際上，這些系數(shù)往往都是估計(jì)值和預(yù)測值，而不是已知數(shù)。已知數(shù)。第第2頁頁因此提出以下問題：因此提出以下問題：當(dāng)這些參數(shù)中的一個(gè)或幾個(gè)發(fā)生變化時(shí)，問題的當(dāng)這些參數(shù)中的一個(gè)或幾個(gè)發(fā)生變化時(shí)，問題的最優(yōu)解會(huì)發(fā)生什么變化。最優(yōu)解會(huì)發(fā)生

2、什么變化。這些參數(shù)在多大范圍內(nèi)變化時(shí)，問題的最優(yōu)解不這些參數(shù)在多大范圍內(nèi)變化時(shí)，問題的最優(yōu)解不變。變。 上述問題就是靈敏度分析所要研究解決的內(nèi)容。上述問題就是靈敏度分析所要研究解決的內(nèi)容。 第第3頁頁解決上述問題的方法：解決上述問題的方法：1. 用單純形法從頭計(jì)算，求得新的最優(yōu)解。用單純形法從頭計(jì)算，求得新的最優(yōu)解。2. 只計(jì)算發(fā)生變化的個(gè)別系數(shù)，并直接填入最只計(jì)算發(fā)生變化的個(gè)別系數(shù)，并直接填入最終單純形表中。終單純形表中。 第第4頁頁靈敏度分析的步驟靈敏度分析的步驟1. 將參數(shù)的改變直接反映到最終單純形表上來：將參數(shù)的改變直接反映到最終單純形表上來：按下列公式分別計(jì)算參數(shù)按下列公式分別計(jì)算參

3、數(shù) bi、cj、aij、的變化而引、的變化而引起的最終單純形表的變化：起的最終單純形表的變化： bBbb 1njaccccaccmiijiijjmiijij,.,1,)()(11 jjPBP 1第第5頁頁2. 檢驗(yàn)原問題是否仍然為可行解（檢驗(yàn)最終單純形檢驗(yàn)原問題是否仍然為可行解（檢驗(yàn)最終單純形表的表的 b 列）；列）；3. 檢驗(yàn)對(duì)偶問題是否仍然為可行解（檢驗(yàn)最終單純檢驗(yàn)對(duì)偶問題是否仍然為可行解（檢驗(yàn)最終單純形表的檢驗(yàn)數(shù)行）；形表的檢驗(yàn)數(shù)行）；4. 按下表繼續(xù)計(jì)算步驟：按下表繼續(xù)計(jì)算步驟： 第第6頁頁原問題原問題對(duì)偶問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解可行解可行解問題

4、的最優(yōu)解或最優(yōu)基不變問題的最優(yōu)解或最優(yōu)基不變可行解可行解非可行解非可行解用用單純形法單純形法繼續(xù)跌代求出最優(yōu)解繼續(xù)跌代求出最優(yōu)解非可行解非可行解可行解可行解用用對(duì)偶單純形法對(duì)偶單純形法繼續(xù)跌代求出最繼續(xù)跌代求出最優(yōu)解優(yōu)解非可行解非可行解非可行解非可行解引入引入人工變量人工變量，編制新的單純形，編制新的單純形表，求出最優(yōu)解表，求出最優(yōu)解第第7頁頁將右端常數(shù)將右端常數(shù) bi 的變化反映到最終單純形表上：的變化反映到最終單純形表上：bBbb 1b 列數(shù)字的變化：列數(shù)字的變化： 最終單純形表出現(xiàn)的情況：最終單純形表出現(xiàn)的情況：1. 第一種情況出現(xiàn)：問題的最優(yōu)基不變，變化后的第一種情況出現(xiàn)：問題的最優(yōu)基

5、不變，變化后的 b 列列為最優(yōu)解。為最優(yōu)解。2. 第三種情況出現(xiàn)：用對(duì)偶單純形法繼續(xù)找出最優(yōu)解。第三種情況出現(xiàn)：用對(duì)偶單純形法繼續(xù)找出最優(yōu)解。 第第8頁頁 0,1241648232max21212121xxxxxxxxz例例 原問題的初始單純形表：原問題的初始單純形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j z j23000第第9頁頁cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/80（1）b1在什么范

6、圍變化時(shí)，問題的最優(yōu)基不發(fā)生變化。在什么范圍變化時(shí)，問題的最優(yōu)基不發(fā)生變化。（2）若）若b1增加增加4，其他不變，求該廠的最優(yōu)生產(chǎn)方案。，其他不變，求該廠的最優(yōu)生產(chǎn)方案。 原問題的最終單純形表：原問題的最終單純形表： 第第10頁頁解：解：（1）當(dāng)）當(dāng) 01 bBb時(shí)，最優(yōu)基不發(fā)生變化時(shí)，最優(yōu)基不發(fā)生變化 1 B1410004201 08/12/112/1204/10 001bb 1112/120bbbB第第11頁頁 bBb1 112/120244bb02/1224411 bb241 b即即 b1 可以在可以在 4，10 之間變化，而不影響最優(yōu)基。之間變化，而不影響最優(yōu)基。 第第12頁頁（2）

7、1 B1410004201 08/12/112/1204/10 004b 2801bB，將其反映到最終單純形表中：，將其反映到最終單純形表中： 第第13頁頁cj23000iCBXBbx1x2x3x4x52x141001/400 x5-400 -2 1/213x24011/2-1/80c j z j00-3/2-1/80即出現(xiàn)了第三種情況（原問題不可行，對(duì)偶問題可即出現(xiàn)了第三種情況（原問題不可行，對(duì)偶問題可行）利用對(duì)偶單純形法：行）利用對(duì)偶單純形法： 第第14頁頁cj23000iCBXBbx1x2x3x4x52x141001/400 x32001-1/4-1/23x2401001/4c j z

8、j000-1/2-3/4出現(xiàn)了第一種情況（原問題可行，對(duì)偶問題也可行出現(xiàn)了第一種情況（原問題可行，對(duì)偶問題也可行），問題達(dá)到最優(yōu)。），問題達(dá)到最優(yōu)。 第第15頁頁將目標(biāo)函數(shù)系數(shù)將目標(biāo)函數(shù)系數(shù) cj 的變化反映到最終單純形表上：的變化反映到最終單純形表上： 檢驗(yàn)數(shù)行（檢驗(yàn)數(shù)行（cj - zj）的變化：）的變化： njaccccaccmiijiijjmiijij,.,1,)()(11 最終單純形表出現(xiàn)的情況：最終單純形表出現(xiàn)的情況：1. 第一種情況出現(xiàn)：問題的最優(yōu)解不變。第一種情況出現(xiàn)：問題的最優(yōu)解不變。2. 第二種情況出現(xiàn)：用單純形法繼續(xù)跌代求出最優(yōu)解。第二種情況出現(xiàn)：用單純形法繼續(xù)跌代求出最優(yōu)

9、解。 第第16頁頁 0,1241648232max21212121xxxxxxxxz例例 原問題的初始單純形表：原問題的初始單純形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j z j23000第第17頁頁cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/80原問題的最終單純形表：原問題的最終單純形表： （1）c2 在什么范圍變化時(shí)，問題的最優(yōu)解不發(fā)生變化。在什么范圍變化時(shí)，問題的最優(yōu)解不發(fā)生變化。（2）若）

10、若 c2 增加增加2，其他不變，求該廠的最優(yōu)生產(chǎn)方案。，其他不變，求該廠的最優(yōu)生產(chǎn)方案。 第第18頁頁解：解：（1）當(dāng)）當(dāng) njaccmiijij,.,1, 01 時(shí)，最優(yōu)解不發(fā)生變化時(shí)，最優(yōu)解不發(fā)生變化 cj23+c2000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213+c2x22011/2-1/80c j z j00022123c 28181c 第第19頁頁021232 c081812 c132 c即即 c2 可以在可以在0，4之間變化，而不影響最優(yōu)解。之間變化，而不影響最優(yōu)解。 （2） cj25000iCBXBbx1x2x3x4x52x141001/4

11、00 x5400-2 1/2 15x22011/2-1/80c j z j00-5/21/80第第20頁頁cj25000iCBXBbx1x2x3x4x52x121010-1/20 x4800-4125x2301001/4c j z j00-20-1/4即出現(xiàn)了第二種情況（原問題可行，對(duì)偶問題不可行即出現(xiàn)了第二種情況（原問題可行，對(duì)偶問題不可行）利用單純形法：）利用單純形法： 第第21頁頁1. 增加一個(gè)新變量增加一個(gè)新變量 xj 的變化分析的變化分析 將增加一個(gè)新變量將增加一個(gè)新變量 xj 的變化反映到最終單純形表上：的變化反映到最終單純形表上： （1）增加一列）增加一列 （2）該列的檢驗(yàn)數(shù)）該

12、列的檢驗(yàn)數(shù) （3）按下表進(jìn)行：）按下表進(jìn)行： jPB1 jBjjPBCc1 第第22頁頁原問題原問題對(duì)偶問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解可行解可行解問題的最優(yōu)解或最優(yōu)基不變問題的最優(yōu)解或最優(yōu)基不變可行解可行解非可行解非可行解用單純形法繼續(xù)跌代求出最優(yōu)解用單純形法繼續(xù)跌代求出最優(yōu)解非可行解非可行解可行解可行解用對(duì)偶單純形法繼續(xù)跌代求出最用對(duì)偶單純形法繼續(xù)跌代求出最優(yōu)解優(yōu)解非可行解非可行解非可行解非可行解引入人工變量，編制新的單純形引入人工變量，編制新的單純形表，求出最優(yōu)解表，求出最優(yōu)解第第23頁頁 0,1241648232max21212121xxxxxxxxz例

13、例 原問題的初始單純形表：原問題的初始單純形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j z j23000第第24頁頁cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/80原問題的最終單純形表：原問題的最終單純形表： 如果增加變量如果增加變量 x6 ，其對(duì)應(yīng)目標(biāo)函數(shù)系數(shù)，其對(duì)應(yīng)目標(biāo)函數(shù)系數(shù) c6 =5 , 其對(duì)應(yīng)約束條件系數(shù)列向量為其對(duì)應(yīng)約束條件系數(shù)列向量為P6= ( 2 , 6 , 3 )T。問題的最優(yōu)解

14、為多少？問題的最優(yōu)解為多少？ 第第25頁頁解：解：x6 為新變量。為新變量。 （1） 11410004201 B 08 / 12/ 112/ 1204 / 10 3626P61PB 4/122/3 第第26頁頁（2） 6166PBCcB 36208/12/112/1204/103025 45/ 第第27頁頁（3） cj230005iCBXBbx1x2x3x4x5x62x141001/403/28/30 x5400-21/21 2 23x22011/2-1/801/48c j z j00-3/2-1/805/4即出現(xiàn)了第二種情況（原問題可行，對(duì)偶問題不可即出現(xiàn)了第二種情況（原問題可行，對(duì)偶問題不

15、可行）利用單純形法：行）利用單純形法： 第第28頁頁cj230005iCBXBbx1x2x3x4x5x62x11103/2-1/8-3/405x6200-11/41/213x23/2013/4-3/16-1/80c j z j00-1/4-7/16-5/80出現(xiàn)了第一種情況（原問題可行，對(duì)偶問題也可行出現(xiàn)了第一種情況（原問題可行，對(duì)偶問題也可行），問題達(dá)到最優(yōu)。），問題達(dá)到最優(yōu)。 第第29頁頁2. 原變量原變量 xj（ xj 在最終單純形表中為非基變量）在最終單純形表中為非基變量）參數(shù)參數(shù) aij 的變化分析的變化分析 將變量將變量 xj 的變化反映到最終單純形表上：的變化反映到最終單純形表上

16、： （1）增加一列）增加一列 （2）該列的檢驗(yàn)數(shù)）該列的檢驗(yàn)數(shù) jPB 1jBjjPBCc 1 第第30頁頁（3）在最終單純形表中用）在最終單純形表中用 列替代列替代 xj 列，將列，將 xj 列列從最終單純形表中刪除（并不影響基矩陣），并按從最終單純形表中刪除（并不影響基矩陣），并按下表進(jìn)行：下表進(jìn)行： jx 原問題原問題對(duì)偶問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解可行解可行解問題的最優(yōu)解或最優(yōu)基不變問題的最優(yōu)解或最優(yōu)基不變可行解可行解非可行解非可行解用單純形法繼續(xù)跌代求出最優(yōu)解用單純形法繼續(xù)跌代求出最優(yōu)解非可行解非可行解可行解可行解用對(duì)偶單純形法繼續(xù)跌代求出最用對(duì)偶

17、單純形法繼續(xù)跌代求出最優(yōu)解優(yōu)解非可行解非可行解非可行解非可行解引入人工變量，編制新的單純形引入人工變量，編制新的單純形表，求出最優(yōu)解表，求出最優(yōu)解第第31頁頁例例 max z = 2x1 + 3x2 0,12 4 16 452 .32121321xxxxxxxxts原問題的初始單純形表：原問題的初始單純形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j z j23000第第32頁頁cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z

18、j00-3/2-1/80原問題的最終單純形表：原問題的最終單純形表： 如果變量如果變量 x3 的目標(biāo)函數(shù)系數(shù)變?yōu)榈哪繕?biāo)函數(shù)系數(shù)變?yōu)?2523P變量變量 x3 對(duì)應(yīng)的約束條件系數(shù)列向量變?yōu)閷?duì)應(yīng)的約束條件系數(shù)列向量變?yōu)?3 c問題的最優(yōu)解為多少？問題的最優(yōu)解為多少？ 第第33頁頁解：解：x3 在最終單純形表中為非基變量。在最終單純形表中為非基變量。 （1） 11410004201 B 08 / 12/ 112/ 1204 / 10 2523P31PB 8/32/14/5 第第34頁頁（2） 25208/12/112/1204/103024 83/ 3133PBCcB （3）在最終單純形表中用）在最

19、終單純形表中用 列替代列替代 x3列，并不再列，并不再保留保留 x3 ： 3x 第第35頁頁cj23400iCBXBbx1x2x4x52x14105/41/408/50 x54001/21/2183x22013/8-1/8016/3c j z j003/8-1/80即出現(xiàn)了第二種情況（原問題可行，對(duì)偶問題不可即出現(xiàn)了第二種情況（原問題可行，對(duì)偶問題不可行）利用單純形法：行）利用單純形法： 3x 第第36頁頁cj23400iCBXBbx1x2x4x5416/54/5011/500 x512/5 -2/5 002/513x24/5-3/1010-1/50c j z j-3/1000-1/503x

20、出現(xiàn)了第一種情況（原問題可行，對(duì)偶問題也可行出現(xiàn)了第一種情況（原問題可行，對(duì)偶問題也可行），問題達(dá)到最優(yōu)。），問題達(dá)到最優(yōu)。 3x 第第37頁頁3. 原變量原變量 xj（ xj 在最終單純形表中為基變量）參在最終單純形表中為基變量）參數(shù)數(shù) aij 的變化分析的變化分析 將變量將變量 xj 的變化反映到最終單純形表上：的變化反映到最終單純形表上： （1）增加一列）增加一列 jPB 1（2）在最終單純形表中用）在最終單純形表中用 列替代列替代 xj 列，將列，將 xj 列列從最終單純形表中刪除（基矩陣受影響）；從最終單純形表中刪除（基矩陣受影響）；jx 第第38頁頁原問題原問題對(duì)偶問題對(duì)偶問題結(jié)論

21、或繼續(xù)計(jì)算的步驟結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解可行解可行解問題的最優(yōu)解或最優(yōu)基不變問題的最優(yōu)解或最優(yōu)基不變可行解可行解非可行解非可行解用單純形法繼續(xù)跌代求出最優(yōu)解用單純形法繼續(xù)跌代求出最優(yōu)解非可行解非可行解可行解可行解用對(duì)偶單純形法繼續(xù)跌代求出最用對(duì)偶單純形法繼續(xù)跌代求出最優(yōu)解優(yōu)解非可行解非可行解非可行解非可行解引入人工變量，編制新的單純形引入人工變量，編制新的單純形表，求出最優(yōu)解表，求出最優(yōu)解（3）將）將變?yōu)榛兞?，并將變?yōu)榛兞?，并?列變?yōu)閱挝痪仃?，列變?yōu)閱挝痪仃?，重新?jì)算各變量的檢驗(yàn)數(shù)，并按下表進(jìn)行：重新計(jì)算各變量的檢驗(yàn)數(shù)，并按下表進(jìn)行： jx jx 第第39頁頁例例 0,12416

22、482 .32max21212121xxxxxxtsxxz原問題的初始單純形表：原問題的初始單純形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j z j23000第第40頁頁如果變量如果變量 x1 的目標(biāo)函數(shù)系數(shù)變?yōu)榈哪繕?biāo)函數(shù)系數(shù)變?yōu)?2521P變量變量 x1 對(duì)應(yīng)的約束條件系數(shù)列向量變?yōu)閷?duì)應(yīng)的約束條件系數(shù)列向量變?yōu)?1 c問題的最優(yōu)解為多少？問題的最優(yōu)解為多少？ cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2

23、-1/80原問題的最終單純形表：原問題的最終單純形表： 第第41頁頁解：解：x1 在最終單純形表中為基變量。在最終單純形表中為基變量。 （1） 11410004201 B 08 / 12/ 112/ 1204 / 10 2521P11PB 8/32/14/5 第第42頁頁cj43000iCBXBbx2x3x4x52x145/4001/400 x541/20-21/213x223/811/2-1/80c j z j1x （2）在最終單純形表中用）在最終單純形表中用 列替代列替代 x1列，并不再列，并不再保留保留 x1 ： 1x 第第43頁頁cj43000iCBXBbx2x3x4x5416/510

24、01/500 x512/500-22/513x24/5011/2-1/50c j z j00-3/2-1/50出現(xiàn)了第一種情況（原問題可行，對(duì)偶問題也可行出現(xiàn)了第一種情況（原問題可行，對(duì)偶問題也可行），問題達(dá)到最優(yōu)。），問題達(dá)到最優(yōu)。 （3）將）將列變換為單位向量，并重新計(jì)算檢驗(yàn)數(shù)：列變換為單位向量，并重新計(jì)算檢驗(yàn)數(shù)： 1x 1x 1x 第第44頁頁例例 0,12416482 .32max21212121xxxxxxtsxxz原問題的初始單純形表：原問題的初始單純形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j

25、 z j23000第第45頁頁如果變量如果變量 x1 的目標(biāo)函數(shù)系數(shù)變?yōu)榈哪繕?biāo)函數(shù)系數(shù)變?yōu)樽兞孔兞?x1 對(duì)應(yīng)的約束條件系數(shù)列向量變?yōu)閷?duì)應(yīng)的約束條件系數(shù)列向量變?yōu)?1 c問題的最優(yōu)解為多少？問題的最優(yōu)解為多少？ cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/80原問題的最終單純形表：原問題的最終單純形表： 2541P第第46頁頁解：解：x1 在最終單純形表中為基變量。在最終單純形表中為基變量。 （1） 11410004201 B 08 / 12/ 112/ 1204 / 10 2541P

26、11PB 8/112/74/5 第第47頁頁cj43000iCBXBbx2x3x4x52x145/4001/408/50 x54-7/20-21/2183x2211/811/2-1/8016/3c j z j（2）在最終單純形表中用）在最終單純形表中用 列替代列替代 x1列，并不再列，并不再保留保留 x1 ： 1x 1x 第第48頁頁cj43000iCBXBbx2x3x4x5416/51001/500 x576/500-26/513x2-12/5011/2-2/50c j z j00-3/22/50出現(xiàn)了第四種情況（原問題不可行，對(duì)偶問題也不出現(xiàn)了第四種情況（原問題不可行，對(duì)偶問題也不可行），

27、需引入人工變量?？尚校?，需引入人工變量。 （3）將）將列變換為單位向量，并重新計(jì)算檢驗(yàn)數(shù)：列變換為單位向量，并重新計(jì)算檢驗(yàn)數(shù)： 1x 1x 1x 第第49頁頁因?yàn)橐驗(yàn)?x2 為不可行解，故需要在為不可行解，故需要在 x2 所在行引入人工變量。所在行引入人工變量。 x2 + 1/2x3 - 2/5x4 = - 12/5 為了確保原問題的解為可行解，需要使約束條件右端為了確保原問題的解為可行解，需要使約束條件右端常數(shù)為正，從而必須常數(shù)為正，從而必須 將將 x2 所在行的等式兩邊乘以所在行的等式兩邊乘以 - 1： -x2 - 1/2x3 + 2/5x4 = 12/5 為湊出基變量來替換為湊出基變量來

28、替換 x2（因此此時(shí)（因此此時(shí) x2 的列向量已經(jīng)的列向量已經(jīng)不是單位向量），從而需引入人工變量不是單位向量），從而需引入人工變量 x6： -x2 - 1/2x3 + 2/5x4 +x6 = 12/5 第第50頁頁cj43000-MiCBXBbx2x3x4x5x6416/51001/500-0 x576/500-26/510-Mx612/50-1-1/2 2/5 016c j z j03-M -1/2M 2/5M-4/5 001x 即出現(xiàn)了第二種情況（原問題可行，對(duì)偶問題不可即出現(xiàn)了第二種情況（原問題可行，對(duì)偶問題不可行）利用單純形法：行）利用單純形法： 1x 第第51頁頁cj43000-Mi

29、CBXBbx2x3x4x5x64211/21/4001/240 x580 3 -1/201-38/30 x460-5/2-5/4105/2-c j z j01-1 0 02-M 1x 仍然是第二種情況（原問題可行，對(duì)偶問題不可行仍然是第二種情況（原問題可行，對(duì)偶問題不可行），繼續(xù)利用單純形法：），繼續(xù)利用單純形法： 1x 第第52頁頁cj43000-MiCBXBbx2x3x4x5x642/3101/30-1/603x28/30 1 -1/601/3-10 x438/300-5/315/60c j z j00-5/6 0-1/3 3-M 出現(xiàn)了第一種情況（原問題可行，對(duì)偶問題也可行出現(xiàn)了第一種情

30、況（原問題可行，對(duì)偶問題也可行），問題達(dá)到最優(yōu)。），問題達(dá)到最優(yōu)。 1x 1x 第第53頁頁4. 增加一個(gè)約數(shù)條件的變化分析增加一個(gè)約數(shù)條件的變化分析 將增加的一個(gè)約數(shù)條件的變化反映到最終單純形表將增加的一個(gè)約數(shù)條件的變化反映到最終單純形表上：上：（1）將原問題最終單純形表中得出的最優(yōu)解帶入新）將原問題最終單純形表中得出的最優(yōu)解帶入新增加的約束條件；增加的約束條件；（2）如滿足：則說明新增加的約束條件未起到限制）如滿足：則說明新增加的約束條件未起到限制作用，原最優(yōu)解不變；作用，原最優(yōu)解不變； （3）如不滿足：）如不滿足：第第54頁頁引入松弛變量或剩余變量將該約束條件化為等式；引入松弛變量或剩余

31、變量將該約束條件化為等式；將該等式加入到原最終單純形表的最后一行，重新將該等式加入到原最終單純形表的最后一行，重新計(jì)算檢驗(yàn)數(shù)，并按下表進(jìn)行：計(jì)算檢驗(yàn)數(shù)，并按下表進(jìn)行： 原問題原問題對(duì)偶問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解可行解可行解問題的最優(yōu)解或最優(yōu)基不變問題的最優(yōu)解或最優(yōu)基不變可行解可行解非可行解非可行解用單純形法繼續(xù)跌代求出最優(yōu)解用單純形法繼續(xù)跌代求出最優(yōu)解非可行解非可行解可行解可行解用對(duì)偶單純形法繼續(xù)跌代求出最用對(duì)偶單純形法繼續(xù)跌代求出最優(yōu)解優(yōu)解非可行解非可行解非可行解非可行解引入人工變量，編制新的單純形引入人工變量，編制新的單純形表，求出最優(yōu)解表，求出最優(yōu)解

32、第第55頁頁 0,524261552max212121221xxxxxxxxxz例例 第第56頁頁原問題的最終單純形表：原問題的最終單純形表： cj21000iCBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2c j z j000-1/4-1/2如果增加約束條件如果增加約束條件 3x1 + 2x2 12，求最優(yōu)解？，求最優(yōu)解？ 第第57頁頁解：解： 原問題最優(yōu)解為原問題最優(yōu)解為 x1 =7/2，x2=3/2，代入約束條件代入約束條件 3x1+2x212 不滿足，故原問題不滿足，故原問題最優(yōu)解發(fā)生變化。最優(yōu)解發(fā)生變

33、化。引入松弛變量引入松弛變量 x6 將約束條件化為等式：將約束條件化為等式： 3x1 + 2x2 + x6 = 12將其加入到最優(yōu)單純形表的最后一行。將其加入到最優(yōu)單純形表的最后一行。第第58頁頁cj210000iCBXBbx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x612320001c j z j第第59頁頁將將x1、x2列變?yōu)閱挝幌蛄?，并重新?jì)算檢驗(yàn)數(shù)：列變?yōu)閱挝幌蛄浚⒅匦掠?jì)算檢驗(yàn)數(shù)： cj210000iCBXBbx1x2x3x4x5x60 x315/20015/4-15/202x17/2100

34、1/4-1/201x23/2010-1/43/200 x6-3/2000-1/4-3/21c j z j000-1/4-1/20即出現(xiàn)了第三種情況（原問題不可行，對(duì)偶問題可即出現(xiàn)了第三種情況（原問題不可行，對(duì)偶問題可行）利用對(duì)偶單純形法：行）利用對(duì)偶單純形法： 第第60頁頁cj210000iCBXBbx1x2x3x4x5x60 x3150015/20-52x141001/30-1/31x20010-1/2010 x510001/61-2/3c j z j000-1/60-1/3出現(xiàn)了第一種情況（原問題可行，對(duì)偶問題也可行出現(xiàn)了第一種情況（原問題可行，對(duì)偶問題也可行），問題達(dá)到最優(yōu)。），問題達(dá)到

35、最優(yōu)。 第第61頁頁參數(shù)線性規(guī)劃是研究參數(shù)（參數(shù)線性規(guī)劃是研究參數(shù)（C、b）中某一參數(shù)連續(xù)變）中某一參數(shù)連續(xù)變化時(shí)，使最優(yōu)解發(fā)生變化的各臨界點(diǎn)的值。即把某一化時(shí)，使最優(yōu)解發(fā)生變化的各臨界點(diǎn)的值。即把某一參數(shù)作為參變量：參數(shù)作為參變量：目標(biāo)函數(shù)在某區(qū)間內(nèi)是這個(gè)參變量的線性函數(shù)。目標(biāo)函數(shù)在某區(qū)間內(nèi)是這個(gè)參變量的線性函數(shù)。約束條件在某區(qū)間內(nèi)是這個(gè)參變量的線性不等式。約束條件在某區(qū)間內(nèi)是這個(gè)參變量的線性不等式。第第62頁頁若若 C 按按(C+ C*) 或或 b 按按(b+b*)連續(xù)變化，而目標(biāo)函數(shù)值連續(xù)變化，而目標(biāo)函數(shù)值 z 是參數(shù)是參數(shù)的線性函數(shù)時(shí)，下式稱為參數(shù)線性規(guī)劃：的線性函數(shù)時(shí)，下式稱為參數(shù)線

36、性規(guī)劃： 0.) ( max*XbAXtsXCCz 0.max*XbbAXtsCXz 第第63頁頁參數(shù)線性規(guī)劃問題的分析步驟：參數(shù)線性規(guī)劃問題的分析步驟：（1）令）令= 0 求解得最終單純形表；求解得最終單純形表；（2）將）將C* 或或b* 項(xiàng)反映到最終單純形表中去；項(xiàng)反映到最終單純形表中去；（3）隨）隨值的增大或減小，觀察原問題或?qū)ε紗栴}：值的增大或減小，觀察原問題或?qū)ε紗栴}： 確定表中現(xiàn)有解（基）允許確定表中現(xiàn)有解（基）允許的變動(dòng)范圍。的變動(dòng)范圍。 當(dāng)當(dāng)變動(dòng)超出該范圍時(shí)，用單純形法或?qū)ε紗渭冏儎?dòng)超出該范圍時(shí)，用單純形法或?qū)ε紗渭冃畏ㄇ笕⌒碌慕狻Ｐ畏ㄇ笕⌒碌慕?。?）重復(fù)步驟（）重復(fù)步驟（3

37、），直到繼續(xù)增大或減小時(shí)，表中），直到繼續(xù)增大或減小時(shí)，表中的解（基）不再出現(xiàn)變化為止。的解（基）不再出現(xiàn)變化為止。第第64頁頁 0,52426155)21()2( max212121221xxxxxxxxxz 例例 分析分析值變化時(shí)，下述參數(shù)線性規(guī)劃問題最優(yōu)值變化時(shí)，下述參數(shù)線性規(guī)劃問題最優(yōu)解得變化。解得變化。 第第65頁頁解解：（：（1）令）令=0，求出最終單純形表，如下所示。，求出最終單純形表，如下所示。cj21000iCBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2c j z j000-1/4-1/2第

38、第66頁頁（2）將）將C* 項(xiàng)反映到最終單純形表中去項(xiàng)反映到最終單純形表中去cj2+1+2000iCBXBbx1x2x3x4x50 x315/20015/4-15/22+x17/21001/4-1/21+x23/2010-1/43/2c j z j000-1/4+1/4 -1/2-5/2 0252104141 151 時(shí)表中解為最優(yōu)。時(shí)表中解為最優(yōu)。第第67頁頁（3）當(dāng)）當(dāng) 1 時(shí)，變量時(shí)，變量 x4 的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) 0，需將，需將 x4 換入換入，利用單純形法繼續(xù)跌代。，利用單純形法繼續(xù)跌代。cj2+1+2000iCBXBbx1x2x3x4x50 x315/2001 5/4 -15/262

39、+x17/21001/4-1/2141+x23/2010-1/43/2-c j z j000-1/4+1/4 -1/2-5/2 第第68頁頁cj2+1+2000iCBXBbx1x2x3x4x50 x46004/51-62+x1210-1/5011+x23011/500c j z j001/5-1/50-2- 0205151 1 時(shí)表中解為最優(yōu)。時(shí)表中解為最優(yōu)。第第69頁頁（4）當(dāng)）當(dāng) 0，需將，需將 x5 換換入，利用單純形法繼續(xù)跌代。入，利用單純形法繼續(xù)跌代。cj2+1+2000iCBXBbx1x2x3x4x50 x315/20015/4-15/2-2+x17/21001/4-1/2-1+x

40、23/2010-1/4 3/2 1c j z j000-1/4+1/4 -1/2-5/2 第第70頁頁cj2+1+2000iCBXBbx1x2x3x4x50 x315051002+x1411/301/600 x5102/30-1/61c j z j01/3+5/30-1/3-1/60 0613103531 512 時(shí)表中解為最優(yōu)。時(shí)表中解為最優(yōu)。第第71頁頁（5）當(dāng)）當(dāng) 0，需將，需將 x4 換入換入，利用單純形法繼續(xù)跌代。，利用單純形法繼續(xù)跌代。cj2+1+2000iCBXBbx1x2x3x4x50 x31505100-2+x1411/30 1/6 0240 x5102/30-1/61-c

41、j z j01/3+5/30-1/3-1/60第第72頁頁 02102 2 時(shí)表中解為最優(yōu)。時(shí)表中解為最優(yōu)。cj2+1+2000iCBXBbx1x2x3x4x50 x315051000 x4246201 00 x5511001c j z j2+1+2000第第73頁頁2 512 151 1 （x1 ， x2）=（2，3）（x1 ， x2）=（7/2，3/2）（x1 ， x2）=（4，0）（x1 ， x2）=（0，0）z =7+8z =17/2+13/2z =8+4z =0第第74頁頁 0,524261552 max212121221xxxxxxxxxz 例例 分析分析值變化時(shí)，下述參數(shù)線性規(guī)劃

42、問題最優(yōu)值變化時(shí)，下述參數(shù)線性規(guī)劃問題最優(yōu)解得變化。解得變化。 第第75頁頁解解：（：（1）令）令=0，求出最終單純形表，如下所示。，求出最終單純形表，如下所示。cj21000iCBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2c j z j000-1/4-1/2第第76頁頁1 B 2/34/102/14/102/154/51 00 b 4/14/14/51bB（2）將）將b* 項(xiàng)反映到最終單純形表中去項(xiàng)反映到最終單純形表中去第第77頁頁 bBb1 4/14/14/52/32/72/15 4/12/34/12/74/52/15cj21000iCBXBbx1x2x3x4x50 x315/2+5/40015/4-15/22x17/2+1/41001/4-1/21x23/2-1/