線形計画の感度分析 - コンピュータフリーク

線形計画問題は一度解いて終わりではなく、問題のパラメータを変えたときに最適解がどのように振る舞うかを調べたいときがしばしばあります。

例えば、以下のような工場の生産計画の最適化を考えましょう。

例: 工場の生産計画

あなたは薬品工場のオーナーだとします。この工場では薬品 A, B を生産しており、それぞれの薬品をどれだけ生産するかを決定したいと考えています。それぞれの薬品は、過去の経験から、1kg 作るごとに 80, 50 万円の利益が見込めます。ただし、これらの薬品を作るには希少材料 X, Y を消費してしまいます。材料の消費量は以下の表で表されます。

	材料 X	材料 Y
製品 A	20 g	40 g
製品 B	30 g	20 g

いま、工場には材料 X は 100 g、材料 Y は 120 gあります。材料が不足しないように利益を最大化するには、薬品をそれぞれ何kgずつ作ればよいでしょう。

これは典型的な線形計画問題です。薬品を作る量が決定変数、材料の上限が制約条件になります。具体的には以下のように定式化できます。

$$\begin{align*}&\underset{(x_A, x_B) \in \mathbb{R}^2}{\text{maximize}} \quad 80 x_A + 50 x_B \\ &\quad \text{s.t.} \qquad 20 x_A + 30 x_B \le 100 \\ &\qquad \qquad 40 x_A + 20 x_B \le 120 \\ &\qquad \qquad (x_A, x_B) \ge 0\end{align*}$$

これを解くと、薬品 A を $x^*_A = 2$ kg、薬品 B を $x^*_B = 2$ kg生産するのが最適で、その時の利益は $f(x^*) = 260$ 万円となります。

感度分析

さて、上の問題では材料 X, Y の量は固定でしたが、在庫としてある分だけでなく、これらの材料を仕入れるような問題設定も考えらます。どの材料をどのように仕入れるのが良いでしょうか。

新しい在庫量 $b’$ を定めて線形計画を解くことを繰り返すと解くことができるかもしれませんが、これでは線形計画を何度も解き直す必要があり効率的ではありません。

そこで役立つのが感度分析というテクニックです。感度分析とは、制約ベクトル $b$ が微少量変化したときの最適値の変化量を求めることを指します。感度分析ができたとすると、上述の工場の問題の場合、変化量が大きくなるような制約に対応する材料を仕入れれば良いということになります。

感度分析は、以下でみていくように線形計画を一度解くだけで求めることができます。

感度分析の定式化

以下の標準形線形計画を考えます。$$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad A x = b \\ &\qquad \qquad x \ge 0\end{align*}$$ 感度分析では、微少量 $\Delta b \in \mathbb{R}^m$ について、以下の摂動を加えた線形計画の最適値を考えます。$$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad A x = b + \Delta b \\ &\qquad \qquad x \ge 0\end{align*}$$

この問題の最適値を $\psi(\Delta b)$ と置きましょう。$\psi(0)$ が摂動のない元の問題の最適値となります。

感度分析においては双対問題が重要な役割を果たします。摂動を加えた問題の双対問題は以下のようになります。$$\begin{align}&\underset{\lambda \in \mathbb{R}^{m}}{\text{maximize}} \quad (b + \Delta b)^\top \lambda \\ &\quad \text{s.t.} \qquad A^\top \lambda \le c\end{align}$$ となります。

つまり、主問題においては制約条件に入っていた摂動が、双対問題においては目的関数に入るように移り変わります。

仮に双対問題の最適解が微小摂動によって変わらなかったとすると、最適値は $(b + \Delta b)^\top \lambda^* = g(\lambda^*) + (\Delta b)^\top \lambda^*$ となります。ここで $\lambda^*$ は双対問題の最適解、$g$ は摂動のない双対問題の目的関数です。強双対定理より、主問題と双対問題の目的関数値は同じなので、このとき $\psi(\Delta b) = \psi(0) + (\Delta b)^\top \lambda^*$ となります。

実際、主問題の最適解が縮退していなければ、微小摂動によって双対問題の最適解変わらないことが示せます。

命題: 微小摂動により双対問題の最適解は変わらない

摂動のない主問題の最適な基底解が縮退していと仮定する。このとき、十分小さい摂動 $\Delta b$ について、摂動のない場合と同じ双対問題の最適解が存在する。

証明

摂動のない主問題の最適な基底解を $x^*$、非ゼロ要素を $B\subset \{1, \cdots, n\}$、それ以外の添字を $N\subset \{1, \cdots, n\}$ とおく。シンプレックス法の証明より、最適性から $c_N^\top – c_B^\top A_B^{-1} A_N \ge 0$ が成り立つ。また、非縮退性から全ての基底要素において $x^*_B = A_B^{-1} b > 0$ が成り立つ。このとき強双対定理の証明より、双対問題の最適解は $A_B^{-\top} c_B$ と表せるのであった。摂動 $\Delta b$ を加えた問題を考える。摂動が十分小さいと $A_B^{-1} (b + \Delta b) > 0$ が成り立つので、この基底 $B$ は摂動がある問題に置いても実行可能。また、最適性の式 $c_N^\top – c_B^\top A_B^{-1} A_N \ge 0$ には $b$ は登場しないので、摂動によらずこの条件は成り立つので、$A_B^{-1} (b + \Delta b)$ は摂動がある問題においても最適な基底解となる。よって、$A_B^{-\top} c_B$ は摂動がある双対問題においても最適解となる。

よって、摂動が微小な領域においては $\psi(\Delta b) = \psi(0) + (\Delta b)^\top \lambda^*$ となり、最適値は摂動に対して線形に振る舞います。勾配を使って表すと $$\frac{\partial \psi(0)}{\partial \Delta b} = \lambda^*$$ ということになります。

つまり、感度分析は双対問題を一度解くだけで求めることができるということです。

主問題の解が縮退している場合は議論がややこしくなるのでここでは省略します。縮退の場合は双対問題の最適解が定まらず、よって勾配も存在せず、劣勾配により記述する必要が生じてきます。ただし、そのような場合であっても、基本的には双対問題の最適解が感度を表していると思って差し支えありません。

例: 工場の生産計画の感度分析

冒頭で導入した工場の生産計画の感度分析を行ってみましょう。双対問題は $$\begin{align*}&\underset{(\lambda_X, \lambda_Y) \in \mathbb{R}^2}{\text{minimize}} \quad 100 \lambda_X + 120 \lambda_Y \\ &\quad \text{s.t.} \qquad 20 \lambda_X + 40 \lambda_Y \ge 80 \\ &\qquad \qquad 30 \lambda_X + 20 \lambda_Y \le 50 \\ &\qquad \qquad (\lambda_X, \lambda_Y) \ge 0\end{align*}$$ であり、最適解は $(\lambda^*_X, \lambda^*_Y) = (0.50, 1.75)$ です。すなわち、材料 X の在庫が 1g 増えるごとに $0.50$ 万円、材料 Y の在庫が 1g 増えるごとに $1.75$ 万円利益を増やすことができます。

冒頭の定式化は標準形ではないですが、等価な標準形への変形を（暗黙的に）行うことで、標準形の議論が適用できます。