01運(yùn)籌學(xué)-靈敏度分析目標(biāo)規(guī)劃

1、運(yùn)籌學(xué) 靈敏度分析n價(jià)值系數(shù)價(jià)值系數(shù)C發(fā)生變化：發(fā)生變化： m考慮檢驗(yàn)數(shù) j = cj - cri arij j = 1,2,n i = 1 1、若 ck 是非基變量的系數(shù)： 設(shè) ck 變化為 ck + ck k= ck + ck - cri arik = k+ ck 只要 k 0 ，即 ck - k ，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗(yàn)數(shù) k 用 k取代，繼續(xù)單純形法的表格計(jì)算。 例: Max Z = - 2x1 - 3x2 - 4x3 S.t. - x1 - 2x2 - x3 + x4 = - 3 - 2x1 + x2 - 3x3 + x5 = - 4 x1 , x2 , x3 ,

2、 x4 , x5 02 2、線性規(guī)劃問題的進(jìn)一步研究（、線性規(guī)劃問題的進(jìn)一步研究（2.32.3） 進(jìn)一步理解最優(yōu)單純性表中各元素的含義進(jìn)一步理解最優(yōu)單純性表中各元素的含義考慮問題考慮問題 Max Max z = c1 x1 + c2 x2 + + cn xn s.t. a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . . am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 03.3.靈敏度分析靈敏度分析3 3、靈敏度分析、靈敏度分析無防設(shè)，無防設(shè)，xj = 0 j = m+1, , n ;

3、 xi = bi i = 1 , , m 是基本可行解, 對(duì)應(yīng)的目標(biāo)函數(shù)典式為：z = -f + m+1xm+1+ nxn以下是初始單純形表： m m其中：f = - ci bi j = cj - ci aij 為檢驗(yàn)數(shù)。 向量 b = B-1 b i = 1 i = 1 A= p1, p2, , pn , pj = B-1 pj, pj = ( a1j , a2j , , amj )T ， j = m+1, , nc1cmcm+1cnCBXBx1xmxm+1xnic1x1b110a1m+1a1n1c2x2b200a2m+1a2n2cmxmbm01amm+1amnm-zf00m+1nc ci

4、, b bj發(fā)生變化 本段重點(diǎn) 增加一約束或變量及A中元素發(fā)生變化通過例題學(xué)會(huì)處理 對(duì)于表格單純形法，通過計(jì)算得到最優(yōu)單純形表。 應(yīng)能夠找到最優(yōu)基 B B 的逆矩陣 B B-1 ， B B-1b b 以及 B B-1N N，檢驗(yàn)數(shù) j 等。3.3.靈敏度分析靈敏度分析 價(jià)值系數(shù)c發(fā)生變化： m 考慮檢驗(yàn)數(shù) j = cj - cri arij j =1,2,n i = 1 1. 若ck是非基變量的系數(shù)： 設(shè)ck變化為 ck + ck k= ck + ck -cri arik = k+ ck 只要 k 0 ,即 ck - k ，則 最優(yōu)解不變；否則，將最優(yōu)單純形表 中的檢驗(yàn)數(shù) k 用 k取代，繼續(xù)

5、單 純形法的表格計(jì)算。 3.3.靈敏度分析靈敏度分析例3.3: Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 03.3.靈敏度分析靈敏度分析 例：最優(yōu)單純形表 CI-2-3-400CBXBbX1X2X3X4X5-3 X22 /501-1 /5-2 /51 /5-2 X11 1 /5107 /5-1 /5-2 /5j00-9 /5-8 /5-1 /5CI-2-3-4+c300CBXBbX1X2X3X4X5-3 X22/501-1/5-2/51/5-2 X111/5

6、107/5-1/5-2/5j00-9/5+c3-8/5-1/5 從表中看到3= c3+c3-(c2a13+c1a23 ) 可得到c3 9/5 時(shí)，原最優(yōu)解不變。3.3.靈敏度分析靈敏度分析 2、若 cs 是基變量的系數(shù)： 設(shè) cs 變化為 cs + cs ，那么 j= cj -cri arij - ( cs + cs ) asj = j - cs asj ， i s 對(duì)所有非基變量，只要對(duì)所有非基變量 j 0 ，即 j cs asj ，則最優(yōu)解 不變；否則，將最優(yōu)單純形表中的檢驗(yàn)數(shù) j 用 j取代，繼續(xù)單純形法的表格計(jì)算。 Maxj/asjasj0csMinj/asjasj0brMin-bi/

7、airair03.3.靈敏度分析靈敏度分析 例3.5: 上例最優(yōu)單純形表如下 C i23000CBX BBX 1X 2X 3X 4X 52 X 141001/400 X 5400-21/213 X 22011/2-1/80j00-1.5-1/803.3.靈敏度分析靈敏度分析 0 0.25 0 這里 B B-1 = -2 0.5 1 0.5 -0.125 0 各列分別對(duì)應(yīng) b1、b2、b3 的單一變化因此，設(shè) b1 增加 4，則 x1 ,x5 ,x2分別變?yōu)椋?+04=4, 4+(-2)4=-40, d-=0; 當(dāng)實(shí)際值未達(dá)到目標(biāo)值時(shí)：當(dāng)實(shí)際值未達(dá)到目標(biāo)值時(shí)： d+=0, d-0; 當(dāng)實(shí)際值同目

8、標(biāo)值恰好一致時(shí)：當(dāng)實(shí)際值同目標(biāo)值恰好一致時(shí)： d+=0, d-=0;故恒有故恒有d+d-=0目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型2. 統(tǒng)一處理目標(biāo)和約束。統(tǒng)一處理目標(biāo)和約束。 對(duì)有嚴(yán)格限制的資源使用建立系統(tǒng)約束，數(shù)學(xué)形式同線性規(guī)劃對(duì)有嚴(yán)格限制的資源使用建立系統(tǒng)約束，數(shù)學(xué)形式同線性規(guī)劃中的約束條件。如中的約束條件。如C和和D設(shè)備的使用限制。設(shè)備的使用限制。12416421 xx 對(duì)不嚴(yán)格限制的約束，連同原線性規(guī)劃建模時(shí)的目標(biāo)，均通過對(duì)不嚴(yán)格限制的約束，連同原線性規(guī)劃建模時(shí)的目標(biāo)，均通過目標(biāo)約束來表達(dá)。目標(biāo)約束來表達(dá)。1）例如要求甲、乙兩種產(chǎn)品保持）例如要求甲、乙兩種產(chǎn)品保持1:1的比例，系統(tǒng)約束表達(dá)為：的比

9、例，系統(tǒng)約束表達(dá)為：x1=x2。由于這個(gè)比例允許有偏差，。由于這個(gè)比例允許有偏差，當(dāng)當(dāng)x1x2時(shí)，出現(xiàn)正偏差時(shí)，出現(xiàn)正偏差d+，即：，即： x1-d+ =x2或或x1x2-d+ =0目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型n正負(fù)偏差不可能同時(shí)出現(xiàn)，故總有：nx1x2+d-d+ =0 0min21ddxxd 若希望甲的產(chǎn)量不低于乙的產(chǎn)量，即不希望若希望甲的產(chǎn)量不低于乙的產(chǎn)量，即不希望d-0,用目標(biāo)約束可用目標(biāo)約束可表為表為: 若希望甲的產(chǎn)量低于乙的產(chǎn)量，即不希望若希望甲的產(chǎn)量低于乙的產(chǎn)量，即不希望d0,用目標(biāo)約束可用目標(biāo)約束可表為表為: 0min21ddxxd 若希望甲的產(chǎn)量恰好等于乙的產(chǎn)量，即不希望若希望甲的

10、產(chǎn)量恰好等于乙的產(chǎn)量，即不希望d0,也不希望也不希望d-0用目標(biāo)約束可表為用目標(biāo)約束可表為: 0min21ddxxdd目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型n3）設(shè)備B必要時(shí)可加班及加班時(shí)間要控制，目標(biāo)約束表示為： 82min21ddxxdn2）力求使利潤(rùn)指標(biāo)不低于12元，目標(biāo)約束表示為： 1232min21ddxxdn4）設(shè)備A既要求充分利用，又盡可能不加班，目標(biāo)約束表示為： 1222min21ddxxdd目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型3. 目標(biāo)的優(yōu)先級(jí)與權(quán)系數(shù)目標(biāo)的優(yōu)先級(jí)與權(quán)系數(shù)在一個(gè)目標(biāo)規(guī)劃的模型中，為達(dá)到某一目標(biāo)可犧牲其他一些在一個(gè)目標(biāo)規(guī)劃的模型中，為達(dá)到某一目標(biāo)可犧牲其他一些目標(biāo)，稱這些目標(biāo)是屬于不同層

11、次的優(yōu)先級(jí)。優(yōu)先級(jí)層次的高低目標(biāo)，稱這些目標(biāo)是屬于不同層次的優(yōu)先級(jí)。優(yōu)先級(jí)層次的高低可分別通過優(yōu)先因子可分別通過優(yōu)先因子P1,P2,表示。對(duì)于同一層次優(yōu)先級(jí)的不同表示。對(duì)于同一層次優(yōu)先級(jí)的不同目標(biāo)，按其重要程度可分別乘上不同的權(quán)系數(shù)。權(quán)系數(shù)是一個(gè)個(gè)目標(biāo)，按其重要程度可分別乘上不同的權(quán)系數(shù)。權(quán)系數(shù)是一個(gè)個(gè)具體數(shù)字，乘上的權(quán)系數(shù)越大，表明該目標(biāo)越重要。具體數(shù)字，乘上的權(quán)系數(shù)越大，表明該目標(biāo)越重要。現(xiàn)假定：現(xiàn)假定： 第第1優(yōu)先級(jí)優(yōu)先級(jí)P1企業(yè)利潤(rùn)；企業(yè)利潤(rùn)； 第第2優(yōu)先級(jí)優(yōu)先級(jí)P2甲乙產(chǎn)品的產(chǎn)量保持甲乙產(chǎn)品的產(chǎn)量保持1:1的比例的比例 第第3優(yōu)先級(jí)優(yōu)先級(jí)P3設(shè)備設(shè)備A,B盡量不超負(fù)荷工作。其中設(shè)備盡

12、量不超負(fù)荷工作。其中設(shè)備A的重要性的重要性比設(shè)備比設(shè)備B大三倍。大三倍。目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型n上述目標(biāo)規(guī)劃模型可以表示為： )4,.,1(0,82122201232124164.)(3)(min214421332122211121214333322211iddxxddxxddxxddxxddxxxxtsdPddPddPdPzii目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式 )2 .1( 0 .n)1.2(j 0)2 .1( ).()2 .1( )(min1111KkddxmibxaKkgddxcddPZkkjnjijijnjkkkjkjLlKkklkklkl

13、達(dá)成函數(shù)達(dá)成函數(shù)目標(biāo)約束目標(biāo)約束其中：其中：g gk k為第為第k k個(gè)目標(biāo)約束的預(yù)期目標(biāo)值，個(gè)目標(biāo)約束的預(yù)期目標(biāo)值， 和和 為為p pl l 優(yōu)先因子優(yōu)先因子對(duì)應(yīng)各目標(biāo)的權(quán)系數(shù)。對(duì)應(yīng)各目標(biāo)的權(quán)系數(shù)。 lk lk目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型明確問題，列出明確問題，列出目標(biāo)的優(yōu)先級(jí)和目標(biāo)的優(yōu)先級(jí)和權(quán)系數(shù)權(quán)系數(shù)構(gòu)造目標(biāo)規(guī)構(gòu)造目標(biāo)規(guī)劃模型劃模型求出滿意解求出滿意解滿意否？滿意否？分析各項(xiàng)目標(biāo)分析各項(xiàng)目標(biāo)完成情況完成情況據(jù)此制定出決策方案據(jù)此制定出決策方案NY目標(biāo)規(guī)劃的圖解分析法適用兩個(gè)變量的目標(biāo)規(guī)劃問題，但其操作簡(jiǎn)單，原理一目了然。適用兩個(gè)變量的目標(biāo)規(guī)劃問題，但其操作簡(jiǎn)單，原理一目了然。同時(shí)，也有助于理

14、解一般目標(biāo)規(guī)劃的求解原理和過程。同時(shí)，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。1. 將所有約束條件（包括目標(biāo)約束和絕對(duì)約束，暫不考慮正負(fù)偏將所有約束條件（包括目標(biāo)約束和絕對(duì)約束，暫不考慮正負(fù)偏差變量）的直線方程分別標(biāo)示于坐標(biāo)平面上。差變量）的直線方程分別標(biāo)示于坐標(biāo)平面上。2. 確定系統(tǒng)約束的可行域。確定系統(tǒng)約束的可行域。3. 在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向增大的方向目標(biāo)規(guī)劃的圖解分析法n3. 求滿足最高優(yōu)先等級(jí)目標(biāo)的解n4. 轉(zhuǎn)到下一個(gè)優(yōu)先等級(jí)的目標(biāo)，再不破壞所有較高優(yōu)先等級(jí)目標(biāo)的前提下，求出該優(yōu)先等級(jí)目

15、標(biāo)的解n5. 重復(fù)4，直到所有優(yōu)先等級(jí)的目標(biāo)都已審查完畢為止n6. 確定最優(yōu)解和滿意解。目標(biāo)規(guī)劃的圖解分析法n例5.2 用圖解法求解下列目標(biāo)規(guī)劃問題 )4 , 1(0,)1 . 4(82)1 . 4(1222)1 . 4(0)1 . 4(1232)1 . 4(124)1 . 4(164)(3)min214421332122211121214433322211iddxxfddxxeddxxdddxxcddxxbxaxdPddPddPdPzii（目標(biāo)規(guī)劃的圖解分析法(a)(b)(c)(d )x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+滿意解滿意解(3,3) )4 , 1(0

16、,)1 . 4(82)1 . 4(1222)1 . 4(0)1 . 4(1232)1 . 4(124)1 . 4(16421442133212221112121iddxxfddxxeddxxdddxxcddxxbxaxii 4433322211)()mindPddPddPdPz（04683462 2目標(biāo)規(guī)劃的圖解分析法 )3 , 2 , 1( 0,)4(56108)3(102)2(0) 1 (112)min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii（x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d3+GD滿意解是線段

17、滿意解是線段GD上任意點(diǎn)上任意點(diǎn)其中其中G點(diǎn)點(diǎn)X(2,4),D點(diǎn)點(diǎn)X(10/3,10/3)05.51055.6112,410/3,10/35107例例5.3目標(biāo)規(guī)劃的圖解分析法 )4 , 1(0,)(30)(24)(50)(40)2(min21442331222111214332211iddxxdddxcddxbddxxaddxxddPdPdPziiOx1x22040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)滿意解滿意解X=(24，26)例例5.4目標(biāo)規(guī)劃應(yīng)用舉例n例5.5 已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型如下，其中目標(biāo)函數(shù)為總利潤(rùn)，x1,x2

18、 為產(chǎn)品A、B產(chǎn)量。 0)( 100 )( 60 )( 14021230max21212121xxxxxxxZ丙丙資資源源乙乙資資源源甲甲資資源源現(xiàn)有下列目標(biāo)：現(xiàn)有下列目標(biāo)：1. 要求總利潤(rùn)必須超過要求總利潤(rùn)必須超過 2500 元；元；2. 考慮產(chǎn)品受市場(chǎng)影響，為避免積壓，考慮產(chǎn)品受市場(chǎng)影響，為避免積壓，A、B的生產(chǎn)量不超過生產(chǎn)量不超過 60 件和件和 100 件；件；3. 由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。目標(biāo)規(guī)劃應(yīng)用舉例解：以產(chǎn)品解：以產(chǎn)品 A,B 的單件利潤(rùn)比的單件利潤(rùn)比 2.5 :1 為權(quán)系數(shù)，模型如下：為權(quán)系數(shù)，模型如下： )4 . 3 . 2 . 1( 0, 0100 60 100 60 140 2 250012305 .