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 = 12x1+8x2 能夠再增加?

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，表示生產新東西更有價值。