第二章線性規(guī)劃的靈敏度分析

1、線性規(guī)劃靈敏度分析5.1 5.1 目標(biāo)函數(shù)系數(shù)的靈敏度分析目標(biāo)函數(shù)系數(shù)的靈敏度分析5.2 5.2 右端項(xiàng)的靈敏度分析右端項(xiàng)的靈敏度分析5.3 5.3 約束系數(shù)的靈敏度分析約束系數(shù)的靈敏度分析線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式(1)、參數(shù)、參數(shù)A，b，C在什么范圍內(nèi)變動，對當(dāng)前方案無影響？在什么范圍內(nèi)變動，對當(dāng)前方案無影響？(2)、參數(shù)、參數(shù)A，b，C中的一個(gè)中的一個(gè)(幾個(gè)幾個(gè))變動，對當(dāng)前方案影響？變動，對當(dāng)前方案影響？(3)、如果最優(yōu)方案改變，如何用簡便方法求新方案？、如果最優(yōu)方案改變，如何用簡便方法求新方案？ 0XbAXs.tCXzMax當(dāng)線性規(guī)劃問題中的一個(gè)或幾個(gè)參數(shù)變化時(shí)，可以用單純當(dāng)線

2、性規(guī)劃問題中的一個(gè)或幾個(gè)參數(shù)變化時(shí)，可以用單純形法從頭計(jì)算，看最優(yōu)解有無變化，但這樣做既麻煩又沒形法從頭計(jì)算，看最優(yōu)解有無變化，但這樣做既麻煩又沒有必要。有必要。靈敏度分析一詞的含義是指對系統(tǒng)或事物因周圍條件變化靈敏度分析一詞的含義是指對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。顯示出來的敏感程度的分析。5.1 目標(biāo)函數(shù)系數(shù)的靈敏度分析j1Bjj1BPBCCABCC 考慮檢驗(yàn)數(shù)考慮檢驗(yàn)數(shù)(1) 若若ck是非基變量的系數(shù)：是非基變量的系數(shù)： 解。解。，用單純形法求解最優(yōu)，用單純形法求解最優(yōu)代替代替否則，用否則，用原最優(yōu)解不變；原最優(yōu)解不變；時(shí)時(shí)即即當(dāng)當(dāng)則則設(shè)設(shè)kkkkkkkkkk1Bkk

3、kkkkc0ccPBCcc,ccc 解：最優(yōu)單純形表解：最優(yōu)單純形表 0 xx4x3xx2x3xx2xxs.t4x3x2xzMax5153214321321例例試求試求 c3 在多大范圍內(nèi)變動時(shí)，原最優(yōu)解保持不變。在多大范圍內(nèi)變動時(shí)，原最優(yōu)解保持不變。cj-2-3-400B-1bcBxBx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5j00-9/5-8/5-1/5-28/5從表中看到從表中看到3= c3+c3-(c2a13+c1a23 ) 可得到可得到c3 9/5 時(shí)，原最優(yōu)解不變。時(shí)，原最優(yōu)解不變。cj-2-3-4+c300B-1bcBx

4、Bx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5j00-9/5+c3-8/5-1/5-28/5(2) 若若 ck 是基變量的系數(shù)是基變量的系數(shù) 解。解。，用單純形法求解最優(yōu)，用單純形法求解最優(yōu)代替代替否則，用否則，用原最優(yōu)解不變；原最優(yōu)解不變；時(shí)時(shí)即所有即所有所有的所有的當(dāng)當(dāng)則則為基變量的價(jià)值系數(shù)，為基變量的價(jià)值系數(shù)，設(shè)設(shè)jjrjrjjkrjkjjrjkjjkjjkBjjBjj1BjjkBkk1Bkkk,0aac0acacPc0Pc0CcPCcPBCcc0CcccC,ccc 例例 0,xx124x164x82xxs.t3x2xZMax21

5、212121求求c c2 2在什么范圍在什么范圍內(nèi)變動時(shí)，原最內(nèi)變動時(shí)，原最優(yōu)解保持不變。優(yōu)解保持不變。 下表為最優(yōu)單純形表下表為最優(yōu)單純形表,考慮基變量系數(shù)考慮基變量系數(shù)c2發(fā)生變化發(fā)生變化C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2 -1/8014從表中看到從表中看到可得到可得到 -3c21 時(shí)，原最優(yōu)解不變。時(shí)，原最優(yōu)解不變。1c08c813c02c232222即即即即C i23+c3000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143

6、+c3 x2 011/2-1/802j00-3/2-c3/2 -1/8+ c3 /8014+2 c3 設(shè)分量設(shè)分量 br 變化為變化為 br + br ，根據(jù)前面的討論：，根據(jù)前面的討論： 最優(yōu)解的基變量最優(yōu)解的基變量 xB = B-1b，那么只要保持，那么只要保持 B-1(b + b) 0 ， 則最優(yōu)基不變，即基變量保持，只有值的變化；則最優(yōu)基不變，即基變量保持，只有值的變化； 否則，需要利用對偶單純形法繼續(xù)計(jì)算。否則，需要利用對偶單純形法繼續(xù)計(jì)算。 5.2 右端項(xiàng)的靈敏度分析例例 0,xx124x164x82xxs.t3x2xzMax21212121求當(dāng)求當(dāng)b b1 1在由在由8 8變動為

7、變動為1212時(shí)，原最優(yōu)解是否保時(shí)，原最優(yōu)解是否保持不變，若變動求出持不變，若變動求出新的最優(yōu)解。新的最優(yōu)解。解解: 下表為最優(yōu)單純形表下表為最優(yōu)單純形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2 -1/8014 4-44224-80428-02440040812112120410244bBXbBbBbbBbBX0812112120410B111111則則由最優(yōu)單純形表可知：由最優(yōu)單純形表可知：將將b代入原最優(yōu)單純形表中，運(yùn)用對偶單純形法計(jì)算最優(yōu)解。代入原最優(yōu)單純形表中，運(yùn)用對偶單純形

8、法計(jì)算最優(yōu)解。經(jīng)一次迭代后，求得新的最優(yōu)解經(jīng)一次迭代后，求得新的最優(yōu)解: ( 4 3 2 0 0 )TC i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/21-43 x2 011/2-1/804j00-3/2 -1/80143/42 x1 1001/4040 x3 001-1/4-1/223 x2 01001/43j000-1/2-3/417(1) (1) 增加一個(gè)變量增加一個(gè)變量 增加一個(gè)變量，相當(dāng)于系數(shù)矩陣增加一列。增加一個(gè)變量，相當(dāng)于系數(shù)矩陣增加一列。 增加變量增加變量 xn+1 則有相應(yīng)的則有相應(yīng)的pn+1 ,cn+1 。 那么那么 計(jì)算

9、出計(jì)算出B-1pn+1 , n+1=cn+1-cB pn+1 填入最優(yōu)單純形表填入最優(yōu)單純形表, 若若 n+1 0 則則 最優(yōu)解不變；最優(yōu)解不變； 否則，進(jìn)一步用單純形法求解。否則，進(jìn)一步用單純形法求解。5.3 約束系數(shù)的靈敏度分析例例 0,xx124x164x82xxs.t3x2xzMax21212121求當(dāng)增加求當(dāng)增加x6 , p6=( 2, 6, 3 )T, c6=5時(shí)，原最優(yōu)解是否保時(shí)，原最優(yōu)解是否保持不變，若變動求出新的持不變，若變動求出新的最優(yōu)解。最優(yōu)解。解解: 下表為最優(yōu)單純形表下表為最優(yōu)單純形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x

10、5 00-21/2143 x2 011/2-1/802j00-3/2 -1/80146666161p5c412233620812112120410pBp0812112120410B 算算代入最優(yōu)單純形表，計(jì)代入最優(yōu)單純形表，計(jì)與與將將則則由最優(yōu)單純形表可知：由最優(yōu)單純形表可知：用單純形法進(jìn)一步求解，可得：用單純形法進(jìn)一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5C i230005B-1bCBXBx1x2x3x4x5x62 x1 1001/403/248/30 x5 00-21/212423 x2 011/2-1/801/428j00-3/2 -1/805/4

11、142 x1 103/2-1/8-3/4015 x6 00-11/41/2123 x2 013/4-3/16-1/403/2j00-1/4 -7/160033/2(2) (2) 增加一個(gè)約束條件增加一個(gè)約束條件 增加一個(gè)約束條件相當(dāng)于系數(shù)矩陣中增加一行。增加一個(gè)約束條件相當(dāng)于系數(shù)矩陣中增加一行。 增加一個(gè)約束條件之后，應(yīng)把最優(yōu)解帶入新的增加一個(gè)約束條件之后，應(yīng)把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入一個(gè)新的非負(fù)變量純形表作為新的一行，引入一個(gè)新的非負(fù)變量（原約束若是小于等于形式可引入非負(fù)松弛變（原約束若是小于等于形

12、式可引入非負(fù)松弛變量，否則引入非負(fù)人工變量），并通過矩陣行量，否則引入非負(fù)人工變量），并通過矩陣行變換把對應(yīng)基變量的元素變?yōu)樽儞Q把對應(yīng)基變量的元素變?yōu)? 0，進(jìn)一步用單純，進(jìn)一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼?。形法或?qū)ε紗渭冃畏ㄇ蠼狻＠?0,xx124x164x82xxs.t3x2xzMax21212121求當(dāng)增加求當(dāng)增加3x1+ 2x215時(shí)，時(shí)，原最優(yōu)解是否保持不變，原最優(yōu)解是否保持不變，若變動求出新的最優(yōu)解。若變動求出新的最優(yōu)解。解解: 下表為最優(yōu)單純形表下表為最優(yōu)單純形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2

13、011/2-1/802j00-3/2 -1/8014將將3x1+ 2x2+ x6=15 代入原最優(yōu)單純形表。代入原最優(yōu)單純形表。經(jīng)對偶單純形法迭代一步，可得：經(jīng)對偶單純形法迭代一步，可得：最優(yōu)解為最優(yōu)解為(3.5, 2.25, 0, 0, 3, 2 )T，最優(yōu)值為，最優(yōu)值為 13. 75C i230000B-1bCBXBx1x2x3x4x5x62 x1 1001/40040 x5 00-21/21043 x2 011/2-1/80020 x632000115j00-3/2 -1/800142 x1 1001/40040 x5 00-21/21043 x2 011/2-1/80020 x600-

14、1-1/201-1j00-3/2 -1/80014(3) (3) 技術(shù)系數(shù)改變技術(shù)系數(shù)改變(計(jì)劃生產(chǎn)的產(chǎn)品工藝結(jié)構(gòu)改變計(jì)劃生產(chǎn)的產(chǎn)品工藝結(jié)構(gòu)改變) 非基變量非基變量xj工藝改變工藝改變只影響單純形表只影響單純形表Pj 列列， j .關(guān)鍵看關(guān)鍵看 j 0? 還是還是0? . 用增加新變量類似方用增加新變量類似方法解決。法解決。 基變量基變量xj工藝改變，復(fù)雜，在此暫不予討論。工藝改變，復(fù)雜，在此暫不予討論。最優(yōu)單純形表為最優(yōu)單純形表為問：當(dāng)問：當(dāng)P3由由(-1 3)T改為改為(-1 2)T時(shí)最優(yōu)解是否變化？時(shí)最優(yōu)解是否變化？0 x,x,x,x,x4x3xx2x3xx2xxt . s4x3x2xz

15、Max5432153214321321例例C i-2-3-400B-1bCBXBx1x2x3x4x5-3 x2 01-1/5-2/51/52/5-2 x1 107/5-1/5-2/511/5j00-9/5 -8/5-1/5-28/5解：解：P P3 3由由(-1 (-1 3)3)T T改為改為(-1 (-1 2)2)T T 由最由單純形表可知由最由單純形表可知 32CB 51525251B1 022151525251324PBCc31B33 4c3 所以原最優(yōu)解不變所以原最優(yōu)解不變（2 2）P P1 1由由(-1 (-1 2)2)T T改為改為(1 (1 1)1)T T 由最優(yōu)單純形表可知由最

16、優(yōu)單純形表可知 51525251B1代入最優(yōu)單純形表，用代入最優(yōu)單純形表，用P1代替代替P1 53511151525251PBP111C i-2-3-400B-1bCBXBx1x2x3x4x5-3 x2 -3/51-1/5-2/51/52/5-2 x1 1/507/5-1/5-2/511/5j-28/5-3 x2 014-1-177/4-2 x1 107-1-21111/7j0022 -5-7-43-3 x2 -4/710-3/71/75/7-4 x3 1/701-1/7-2/711/7j-22/700-13/7-5/7-59/7所以，新的最優(yōu)解為所以，新的最優(yōu)解為:(0,5/7,11/7,0

17、,0)T 最優(yōu)值為：最優(yōu)值為：-59/7參數(shù)線性規(guī)劃5.4 參數(shù)線性規(guī)劃n在線性規(guī)劃的實(shí)際應(yīng)用中，由于某種原因，線性規(guī)劃在線性規(guī)劃的實(shí)際應(yīng)用中，由于某種原因，線性規(guī)劃問題的目標(biāo)函數(shù)的價(jià)值系數(shù)問題的目標(biāo)函數(shù)的價(jià)值系數(shù)C和約束條件的右端常數(shù)和約束條件的右端常數(shù)b會隨著某個(gè)參數(shù)而連續(xù)變動。會隨著某個(gè)參數(shù)而連續(xù)變動。n當(dāng)數(shù)據(jù)隨著某個(gè)參數(shù)連續(xù)變化時(shí)，研究其對最優(yōu)解的當(dāng)數(shù)據(jù)隨著某個(gè)參數(shù)連續(xù)變化時(shí)，研究其對最優(yōu)解的影響，即為參數(shù)線性規(guī)劃問題。影響，即為參數(shù)線性規(guī)劃問題。v目標(biāo)函數(shù)的價(jià)值系數(shù)含有參數(shù)的線性規(guī)劃問題目標(biāo)函數(shù)的價(jià)值系數(shù)含有參數(shù)的線性規(guī)劃問題v右端常數(shù)含有參數(shù)的線性規(guī)劃問題右端常數(shù)含有參數(shù)的線性規(guī)劃

18、問題(1)目標(biāo)函數(shù)的價(jià)值系數(shù)含有參數(shù)的線性規(guī)劃問題目標(biāo)函數(shù)的價(jià)值系數(shù)含有參數(shù)的線性規(guī)劃問題 0XbAXt . sXCCZMax ABCCABCCABCABCCCABCCCC1B1B1B1B1BB bBCbBCbBCCZ1B1B1BB 求解步驟：求解步驟： 令令= 0，求得最優(yōu)解與最優(yōu)基，求得最優(yōu)解與最優(yōu)基 B； 根據(jù)根據(jù) 求得求得的區(qū)間；的區(qū)間； 運(yùn)用單純形法求得其余區(qū)間的最優(yōu)解。運(yùn)用單純形法求得其余區(qū)間的最優(yōu)解。 0 例例 0 x,x,x420 x4x460 x2x3430 xx2xt . sx25x52x63zMax3212131321321 解：解： 化為標(biāo)準(zhǔn)形；求化為標(biāo)準(zhǔn)形；求= 0

19、的最優(yōu)解與最優(yōu)基的最優(yōu)解與最優(yōu)基 B 6 ,2 ,1j0 x420 xx4x460 xx2x3430 xxx2xt . sx25x52x63ZMaxj6215314321321 則則= 0 時(shí)最優(yōu)解為時(shí)最優(yōu)解為(0 100 230 0 0 20)T C i325000B-1bCBXBx1x2x3x4x5x62x2 -1/4101/2-1/401005x33/20101/202300 x6 200-21120j-400-1-201350 根據(jù)根據(jù) 求得求得的區(qū)間的區(qū)間 0 0492025104414541 52411698524116 即當(dāng)即當(dāng)時(shí)最優(yōu)解為時(shí)最優(yōu)解為 401350Z20002301

20、000XT C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52 x2 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-40 運(yùn)用單純形法求得其余區(qū)間的最優(yōu)解運(yùn)用單純形法求得其余區(qū)間的最優(yōu)解當(dāng)當(dāng)52時(shí)時(shí)C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9

21、/40-4000 x4 -1/2201-1/2020025x33/20101/2023000 x6 140001420j-9/2200-5/201150j-9-500-10460最優(yōu)解為最優(yōu)解為 4601150Z420020023000XT 當(dāng)當(dāng)時(shí)時(shí)4116 C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-40-52x2 0101/4-1/81/8205/225x30013/2-1/4-3

22、/4215-63x1 100-11/21/210j0005001310j000-31/423/80-285/222851310Z000215220510X41163120T 時(shí)，時(shí)，則當(dāng)則當(dāng)當(dāng)當(dāng)時(shí)時(shí)1320 C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2 0101/4-1/81/8205/225x30013/2-1/4-3/4215-63x1 100-11/21/210j0005001310j000-31/423/80-285/2-52x2 01-1/60-1/121/4200/300 x4002/31-1/6-1/2430/3-63x1 102

23、/301/30460/3j0010/30-5/6-1/21780/3j0031/6019/125/4-3760/33376031780Z003430032003460X3120T ，時(shí)，時(shí)，則當(dāng)則當(dāng) 4601150Z23000X52401350Z2301000X52411622851310Z215220510X411631203376031780Z032003460X3120 參變量的取值范圍與最優(yōu)解為參變量的取值范圍與最優(yōu)解為（2）右端常數(shù)含有參數(shù)的線性規(guī)劃問題）右端常數(shù)含有參數(shù)的線性規(guī)劃問題 0XbbAXt . sCXZMax XXbBbBbbBX111 求解步驟：求解步驟： 令令= 0，

24、求得最優(yōu)解與最優(yōu)基，求得最優(yōu)解與最優(yōu)基B； 根據(jù)根據(jù) 求得求得的區(qū)間；的區(qū)間； 運(yùn)用對偶單純形法求得其余區(qū)間的最優(yōu)解。運(yùn)用對偶單純形法求得其余區(qū)間的最優(yōu)解。 0XXX 例例 0 x,x,x4420 x4x4460 x2x3430 xx2xt . sx5x2x3ZMax3212131321321 解：解： 化為標(biāo)準(zhǔn)形；求化為標(biāo)準(zhǔn)形；求= 0 的最優(yōu)解與最優(yōu)基的最優(yōu)解與最優(yōu)基 B 6 ,2 , 1j0 x4420 xx4x4460 xx2x3430 xxx2xt . sx5x2x3ZMaxj6215314321321 根據(jù)根據(jù) 求得求得的區(qū)間；的區(qū)間；則則= 0 時(shí)最優(yōu)解為時(shí)最優(yōu)解為(0 100

25、230 0 0 20)T 0XXX C i325000B-1bCBXBx1x2x3x4x5x62x2 -1/4101/2-1/401005x33/20101/202300 x6 200-21120j-400-1-201350 201020b2320011502230b3200023100b321 71350Z1020002230231000XT 最優(yōu)解為最優(yōu)解為C i325000B-1bb*CBXBx1x2x3x4x5x62x2 -1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-7當(dāng)當(dāng)時(shí)最優(yōu)單純形表為時(shí)最

26、優(yōu)單純形表為2 運(yùn)用單純形法求得其余區(qū)間的最優(yōu)解。運(yùn)用單純形法求得其余區(qū)間的最優(yōu)解。C i325000B-1bb*CBXBx1x2x3x4x5x62x2 -1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-72x2 1/410001/4105-15x33/20101/20230-20 x4 -1001-1/21/2-105j-5000-5/2-1/21360-12時(shí)，最優(yōu)解為時(shí)，最優(yōu)解為 121360Z0051022301050XT 1052 當(dāng)當(dāng)當(dāng)當(dāng)時(shí)最優(yōu)單純形表為時(shí)最優(yōu)單純形表為3200430 C i3

27、25000B-1bb*CBXBx1x2x3x4x5x62x2 -1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-70 x5 1-40-210-400-65x312110043010 x6 140-3/201420-4j-2-80-50021505最優(yōu)解為最優(yōu)解為 52150Z44206400043000XT 參變量的取值范圍與最優(yōu)解為參變量的取值范圍與最優(yōu)解為 無可行解無可行解無可行解無可行解105121360Z00510-2-230-1050X105271350Z10-20002-230231000X2

28、320052150Z4-4206-400-043000X3200430430TTT 第五章作業(yè)題第五章作業(yè)題1、5、7、9、10（選（選2） 時(shí)的最優(yōu)單純形表為時(shí)的最優(yōu)單純形表為當(dāng)當(dāng)已知線性規(guī)劃已知線性規(guī)劃00 x,x,x,x,x325x5x2x6x210 x3xxxt . s54x2x2xzMax200503205432153214321321 求所有最優(yōu)解。求所有最優(yōu)解。是否唯一？如果不唯一是否唯一？如果不唯一。并判斷最優(yōu)解。并判斷最優(yōu)解線性規(guī)劃問題的最優(yōu)解線性規(guī)劃問題的最優(yōu)解求當(dāng)求當(dāng)。，并求，并求填空完成上面單純形表填空完成上面單純形表02B11 CBXBx1x2x3x4x5b2x213100 x50-1-2100 。完成單純形表如下所示完成單純形表如下所示解：解： 1CBXBx1x2x3x4x5b2x2-11310100 x580-1-21500-2-2020 知：知：量。由最優(yōu)單純形表可量。由最優(yōu)單純形表可，就相當(dāng)于增加一個(gè)變，就相當(dāng)于增加一個(gè)變當(dāng)當(dāng)