第三章 靈敏度分析.ppt

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