第三章 靈敏度分析.ppt

2020 1 30 1 第三章靈敏度分析 前提條件 原線性規(guī)劃問題已取得了最優(yōu)解 每次只討論一種參數(shù)的變化 而參數(shù)之間的變化互不關(guān)聯(lián) 2020 1 30 2 某廠準(zhǔn)備用甲乙兩種原料生產(chǎn)A B C D四種產(chǎn)品 相關(guān)參數(shù)見表 問如何安排生產(chǎn)總利潤為最大 Maxz 9x1 8x2 50 x3 19x4s t 3x1 2x2 10 x3 4x4 182x3 1 2x4 3xj 0 j 1 2 3 4 Maxz 9x1 8x2 50 x3 19x4s t 3x1 2x2 10 x3 4x4 x5 182x3 1 2x4 x6 3xj 0 j 1 2 6 2020 1 30 3 用單純形法對(duì)該線性規(guī)劃進(jìn)行求解 得初始單純行表和最優(yōu)單純形表 Z 88 y1 y2 y3 y4 y5 y6 2020 1 30 4 一 目標(biāo)函數(shù)中cj發(fā)生變化1 非基變量的cj發(fā)生變化x1的利潤值由9變?yōu)? c1則 1 9 c1 2 19 25 4 c1如果 1 4 c1 0 最優(yōu)解不發(fā)生變化 1 4 c1 0 最優(yōu)解將發(fā)生變化 所以當(dāng) c1 4時(shí) 最優(yōu)解不發(fā)生變化 對(duì)于某一非基變量可以看出 它的價(jià)值系數(shù)發(fā)生變化時(shí) 只影響最優(yōu)單純行表中該非基變量的檢驗(yàn)數(shù) 而基變量的檢驗(yàn)數(shù)都不會(huì)發(fā)生變化 所以只需要考慮該非基變量的價(jià)值系數(shù)變化后的檢驗(yàn)數(shù)是否仍然小于等于0 如果仍然小于等于0 則最優(yōu)解不發(fā)生變化 2020 1 30 5 思考 如果x2的系數(shù)發(fā)生變化 c2在什么范圍內(nèi)變化 最優(yōu)解不變 2020 1 30 6 2 基變量的cj發(fā)生變化假設(shè)x4的利潤由19變?yōu)?9 c4 4 2 c4 2 3 4 3 c4 13 3 2 3 c4 10 3 10 3 c4 當(dāng)且僅當(dāng)所有的非基變量的檢驗(yàn)數(shù)都仍然小于等于0則最優(yōu)解不變 2020 1 30 7 當(dāng)目標(biāo)函數(shù)中cj發(fā)生變化 將影響最終單純形表非基變量的檢驗(yàn)數(shù) 如果是非基變量的價(jià)值系數(shù)發(fā)生變化 只影響該非基變量的檢驗(yàn)數(shù) 如果變化后的檢驗(yàn)數(shù)仍然小于等于0 則最優(yōu)解不變 如果是基變量的價(jià)值系數(shù)發(fā)生變化 將影響所有非基變量的檢驗(yàn)數(shù) 只有當(dāng)所有的非基變量檢驗(yàn)數(shù)都仍然小于等于0 最優(yōu)解才不變 2020 1 30 8 二 右端常數(shù)項(xiàng)bi發(fā)生變化X XB 0 T其中XB B 1bZ CBB 1b當(dāng)bi發(fā)生變化時(shí) bi b 0 bi 0 T b b則 XB B 1b B 1 b b B 1b B 1 b XB B 1 b如果XB XB B 1 b 0 則原最終單純形表中的基變量不變 基變量的值將發(fā)生變化如果XB XB B 1 b 0 則需采用對(duì)偶單純形表進(jìn)行重新求解 2020 1 30 9 假設(shè) 甲原材料的供給量從18變?yōu)? 則b 6 3 T 可以看出甲的供給量發(fā)生變化后 x4的值 4 0 所以用對(duì)偶單純形表求新解 2020 1 30 10 2020 1 30 11 2020 1 30 12 2020 1 30 13 2020 1 30 14 2020 1 30 15 當(dāng)右端常數(shù)項(xiàng)發(fā)生變化時(shí) 主要考慮在最優(yōu)單純行表中基變量的值是否仍然大于等于0 如果仍然大于等于0 則線性規(guī)劃問題的基變量不變 但是基變量的值將發(fā)生變化 如果右端常數(shù)項(xiàng)發(fā)生變化時(shí) 最優(yōu)單純行表中基變量的值小于0 則將用對(duì)偶單純形法對(duì)原最優(yōu)單純形表進(jìn)行繼續(xù)求解 2020 1 30 16 三 增加一個(gè)變量假設(shè)用甲乙兩種原材料還可以生產(chǎn)新產(chǎn)品為E 需要甲原料3個(gè)單位 乙原料1個(gè)單位 利潤為10 問該種新產(chǎn)品是否應(yīng)該生產(chǎn) 設(shè)生產(chǎn)E產(chǎn)品x7個(gè) 則線性規(guī)劃方程為 Maxz 9x1 8x2 50 x3 19x4 10 x7s t 3x1 2x2 10 x3 4x4 3x7 182x3 1 2x4 x7 3xj 0 j 1 2 3 4 7 Maxz 9x1 8x2 50 x3 19x4 10 x7s t 3x1 2x2 10 x3 4x4 3x7 x5 182x3 1 2x4 x7 x6 3xj 0 j 1 2 7 2020 1 30 17 P7 3 1 T 7 c7 CBP7 10 19 50 13 4 5 6 T 19 3 0 因?yàn)閤7的檢驗(yàn)數(shù)小于0 所以原最優(yōu)單純形表即為最優(yōu)單純形表 最優(yōu)解不變 考慮影子價(jià)格 y1 13 3 y2 10 3則生產(chǎn)一件E產(chǎn)品所需要的隱含成本為 13 3 3 10 3 1 49 3 10 每件E產(chǎn)品的利潤 所以也不生產(chǎn) 2020 1 30 18 增加一個(gè)變量也就是多生產(chǎn)一種產(chǎn)品 只須考慮該種產(chǎn)品的檢驗(yàn)數(shù)是否大于0 如果大于0則表示應(yīng)該生產(chǎn) 用單純形表進(jìn)行求解 如果小于0則該種產(chǎn)品不用生產(chǎn) 最優(yōu)解不發(fā)生變化 同時(shí)也可以考慮影子價(jià)格 如果該種新產(chǎn)品的利潤大于隱含成本 則應(yīng)該生產(chǎn)用單純形表進(jìn)行求解 如果小于隱含成本則該種產(chǎn)品不用生產(chǎn) 2020 1 30 19 四 增加一個(gè)約束條件假設(shè)原線性規(guī)劃問題變?yōu)?Maxz 9x1 8x2 50 x3 19x4s t 3x1 2x2 10 x3 4x4 182x3 1 2x4 32x1 x2 x3 2x4 8xj 0 j 1 2 3 4 Maxz 9x1 8x2 50 x3 19x4s t 3x1 2x2 10 x3 4x4 x5 182x3 1 2x4 x6 32x1 x2 x3 2x4 x7 8xj 0 j 1 2 7 2020 1 30 20 2020 1 30 21 此時(shí)x7的值 3大于0 所以原問題和對(duì)偶問題都達(dá)到可行解 并分別為最優(yōu)解 不需要進(jìn)行下一步計(jì)算 2020 1 30 22 增加一個(gè)約束條件 可能影響的只是該約束條件的松弛變量的值 如果該松弛變量的值大于等于0 則線性規(guī)劃最優(yōu)解不變 如果該松弛變量的值小于0 則采用對(duì)偶單純形表進(jìn)行計(jì)算 2020 1 30 23 五 aij發(fā)生變化 Maxz 9x1 8x2 50 x3 19x4s t 3x1 2x2 10 x3 4x4 182x3 1 2x4 3xj 0 j 1 2 3 4 3x1 x2 10 x3 4x4 18 則P2 2 0 T P2 1 0 T 2 c2 CBP2 8 19 50 2 3 1 6 T 11 3 0 2020 1 30 24 2020 1 30 25 2020 1 30 26 2020 1 30 27 改變aij只會(huì)