➣ Reading Time: 5 minutes

Duality & Postoptimality Analysis (敏感度分析)

forms

primal form

原題

Cononical form

統一大小於,做符號轉換(大於、等於、小於)

Dual form

以係數來重新檢視問題(有點類似做轉置矩陣)

Theorems

Theorem 4-1

objective function primal form 與 Dual form 會相等

Theorem 4-2

slack variables(除了目標式變數之外,我們自己加的變數(非人工變數))
slack variables = 0 時,dual variable 會對應必有值
反之,slack variables 有值 時,dual variable 必為 0

Theorem 4-3

slack variables所對應的Zj那個row(final table),會正好是dual variables的解

Postoptimality Analysis

  • 對於”目標變數”來說,可變動範圍表示”不影響最佳解的值”,但object function得到的值會變

換句話說就是 X1=5 X2=10 這種不會變,但Min Max會隨著你調整係數改變

  • 對於”constraints的值”來說,可變動範圍”會影響最佳解的值”,且object function得到的值也會變

邊濟效益(經濟學) shadow price: 正是指我們在上方所求得的 dual variables
而 dual prices 也正對應 constraints的值

  • 想想一個問題:如何使 Max f = 12×1+8×2 能夠再增加?
1. 改變係數:我們去動12跟8 
    -> 改變係數,X1,X2不變,dual price改變,值增加
2. 改變限制:我們讓你有更多的資源 (造成X1,X2增加)
    -> 改變右邊資源,X1,X2改變,dual price不變,值增加 

第四章末 Postoptimality Analysis

找B^(-1)的方法

BI -> IB^(-1)

Analysis of the coefficient

改設係數為C final table Cj-Zj<=0 看範圍

Analysis of the right-hand sides

設原限制右側值為b 透過B^(-1)運算得到新b >=0看範圍

100 percent rule

單一變化的總和相加小於100%時,結果不受影響

add new decision variable

一樣設係數為C,透過B^(-1)運算得到final table 判斷 Cj-Zj需要>=0,表示生產新東西更有價值。

⭐管理科學/作業研究 MS/OR – 相關文章連結整理⭐:
1.【管理科學】 LP 問題, LP problem, LP solution procedure 第一次期中考筆記
2.【管理科學】 IP problem, 條件式 IP problems (either-or, if-then problem) 第一次期中考筆記
3.【管理科學】 solve LP problems, simplex method 詳細步驟與觀念 圖文說明講解 第二次期中考筆記
4.【管理科學】 simplex method 變形, two-phase method 二階解(另解) 第二次期中考筆記
5.【管理科學】 Duality & Postoptimality Analysis (敏感度分析) 期末考筆記
6.【管理科學】 運輸問題 (Transportation problem) 期末考筆記
⭐【喜歡我的文章嗎? 幫忙按讚除了鼓勵外,我也會將部分所得捐出!
如果喜歡我的文章,請幫我在下方【按五下Like】 (Google, Facebook 免費註冊),會由 「LikeCoin」 贊助作者鼓勵繼續創作,扣除掉網站本身經營的成本 (可惜目前還是虧本的),我會將 【50% 收益全部捐出】 並公開發文,讀者們「只需幫忙按讚,完全不用出錢」哦!

likecoin-steps