感度分析#

数理計画問題においては，問題の係数が変化したとき最適解の変化を扱う問題である．

たとえば以下の線形計画問題

(36)#\[\begin{split}(P) \begin{array}{ll} \min & c^\top x \\ \mathrm{s.t.} & Ax=b, \ x \ge 0 \end{array}\end{split}\]

の最適解を係数 \(b\) の関数とみなし \(\varphi(b)\) と表し，\(b\) を \(b + \Delta b\) に変化させたときの変化量 \(\varphi(b) - \varphi(b + \Delta b)\) を考える．このとき

(37)#\[\varphi(b) - \varphi(b + \Delta b) = (w^*)^\top \Delta b\]

という関係がある．ここで \(w^*\) は \((P)\) の最適解における双対変数である．この \(w^*\) は経済学の概念では潜在価格(シャドープライズ)と呼ばれるものである．

感度分析によりどのリソースが結果に大きく関与するのかが分かり，リソースの影響や重要度などを判定することができる．