運籌學/敏感性分析

敏感性分析是找出我們可以改變輸入資料多少，以便我們的線性規劃模型的輸出保持相對不變。這有助於我們確定我們為問題提供的資料的敏感性。如果輸入的微小變化（例如某些原材料可用性的變化）會對某個模型的最優解產生較大變化，而另一個模型的輸入的相應微小變化卻不會對其最優解產生那麼大的影響，我們可以得出結論，第二個問題比第一個問題更穩健。第二個模型對輸入資料的變化不太敏感。

我們將考慮最優解對資源可用性變化的敏感性情況。（約束的右側。）

如果在任何線性規劃問題中，有 n 個變數和 m 個約束，我們可以認為右側是資源數量的代表。例如，考慮我們之前的化工廠模型

最大化 z = $5x_{1}+4x_{2}$

受制於,

$6x_{1}+4x_{2}\leq 24$,

$x_{1}+2x_{2}\leq 6$,

$x_{2}-x_{1}\leq 1$,

$x_{2}\leq 2$,

$x_{1},x_{2}\geq 0$.

右側代表各種資源：原材料 1 和 2 的數量、市場限制和每日需求。現在，如果這些右側發生變化，整個問題都會發生變化。假設我們想知道任何特定資源的價值。更準確地說，我們想知道第一種原材料可獲得 24 個單位實際上有多重要。如果我們將數量從 24 提高到 25，我們的最優值將變為 21.75，而之前為 21。因此，第一種資源數量的單位增加使最優值（即總利潤）變化了 0.75。因此，這可以被認為是第一種資源的“單位價值”。這個技術術語是第一種資源的“影子價格”。

影子價格的確定

透過逐個增加資源並求解相關的線性模型來單獨確定資源的影子價格非常低效。讓我們研究另一種計算影子價格的方法。

考慮以下線性系統

最大化 z = $3x_{1}+2x_{2}+5x_{3}$

受制於,

$x_{1}+2x_{2}+x_{3}\leq 430$,

$3x_{1}+2x_{3}\leq 460$,

$x_{1}+4x_{2}\leq 420$,

$x_{1},x_{2},x_{3}\geq 0$.

帶有鬆弛變數的最優單純形表$x_{4},x_{5},x_{6}$ 是

基本	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$	$x_{6}$	廣度優先搜尋（BFS）
z	4	0	0	1	2	0	1350
$x_{2}$	${\frac {-1}{4}}$	1	0	${\frac {1}{2}}$	${\frac {-1}{4}}$	0	100
$x_{3}$	${\frac {3}{2}}$	0	1	0	${\frac {1}{2}}$	0	230
$x_{6}$	2	0	0	-2	1	1	20

現在，為了找到影子價格，我們將上述模型的標準形式寫成如下形式

$x_{1}+2x_{2}+x_{3}=430-x_{4}$,

$3x_{1}+2x_{3}=460-x_{5}$,

$x_{1}+4x_{2}=420-x_{6}$.

如果資源 1 增加一個單位，這意味著第一個鬆弛變數減少一個單位，以便左右兩邊的相等性保持不變。所有其他資源也是如此。

從最優單純形表中，我們有以下約束

$z+4x_{1}+x_{4}+2x_{5}+0x_{6}=1350$.

這可以改寫為

$z=1350-4x_{1}+1(-x_{4})+2(-x_{5})+0(-x_{6})=1350$.

鑑於鬆弛變數值的減少等同於其資源的增加，我們得到

$z=1350-4x_{1}$+1（資源 1 的增加）+2（資源 2 的增加）+0（資源 3 的增加）=1350

因此，我們可以看到

• 資源 1 增加一個單位，z 增加 1
• 資源 2 增加一個單位，z 增加 2
• 資源 3 增加一個單位，z 增加 0

因此，影子價格分別為 1、2 和 0。