基底解が与えられない場合や縮退の場合の対処法: 線形計画入門 7

前章のシンプレックス法の議論では、基底解が与えられることと、非縮退であることを仮定しました。これらが成り立たない場合への対処法を考えます。いずれの場合も、入力例を少し変更することで簡単に対処が可能です。ただし、数値的な誤差については注意が必要です。

基底解が与えられない場合（ビッグM法）

標準形線形計画 $$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad c_1 x_1 + \cdots c_n x_n \\ &\quad \text{s.t.} \qquad a_{11} x_1 + \cdots + a_{1n} x_n = b_1 \\ &\qquad \qquad \qquad \quad \vdots \\ &\qquad \qquad a_{m1} x_1 + \cdots + a_{mn} x_n = b_m \\ &\qquad \qquad x \ge 0\end{align*}$$に対して、補助変数 $s_1, \cdots s_m$ を導入して新たな標準形線形計画 $$\begin{align*}&\underset{(x, s) \in \mathbb{R}^{n+m}}{\text{minimize}} \quad c_1 x_1 + \cdots c_n x_n + M s_1 + \cdots + M s_m \\ &\quad \text{s.t.} \qquad a_{11} x_1 + \cdots + a_{1n} x_n + \text{sign}(b_1) s_1 = b_1 \\ &\qquad \qquad \qquad \quad \vdots \\ &\qquad \qquad a_{m1} x_1 + \cdots + a_{mn} x_n + \text{sign}(b_m) s_m = b_m \\ &\qquad \qquad (x, s) \ge 0\end{align*}$$ を考えます。$\text{sign}(b_i)$ は $b_i \ge 0$ のとき $1$、$b_i < 0$ のとき $-1$ とし、$M \in \mathbb{R}$ は非常に大きな正の数とします。

この新たな線形計画は $x = 0, s_i = |b_i|$ が基底解となるので、シンプレックス法で解くことができます。

十分 $M$ が大きいとすると、$s$ の要素が存在しない方が目的関数が小さくなるので、最適解においては $s = 0$ となるはずです。$(x, 0)$ が実行可能のとき、$Ax = b, x \ge 0$ を満たすのでこの $x$ は元の線形計画の実行可能解であり、$(x, 0)$ が新たな線形計画の最適解なら $x$ は元の線形計画の最適解となります。

しかし、$M$ をどれほど大きくとれば十分かは事前には分かりません。そこで、$M$ に具体的な値を設定するのではなく、記号として扱い、値を $\alpha M + \beta$ の形で保持することにして $(\alpha, \beta)$ の辞書式順序で大小を比較することにすると、無限に大きい $M$ を表現することができます。

$(x, 0)$ の形の解は $s$ に正の要素を含む $(x, s)$ よりも目的関数が小さいので、この線形計画の最適解の $s$ に正の要素が含まれるなら、$Ax = b, x \ge 0, s = 0$ を満たす解が存在しないことを意味します。これはつまり、元の線形計画に実行可能解が存在しないことになります。よって、この方法により元の線形計画に実行可能解が存在するかどうかも判定することができます。

このように、基底解が自明に分かる等価な線形計画に変換する方法をビッグM法といいます。

縮退の場合（摂動法・辞書順法）

シンプレックス法の途中で縮退基底 $x$ と添字集合 $B^{\text{deg}}$ が見つかったとします。これはつまり $x_{B^{\text{deg}}} = A_{B^{\text{deg}}}^{-1} b$ のいくつかの要素がゼロということです。このとき、新しい線形計画問題として、$A, c$ をそのままに、正の微少量 $\varepsilon$ を使って $$b’ = b + A_{B^{\text{deg}}} \begin{pmatrix}\varepsilon \\ \varepsilon^2 \\ \vdots \\ \varepsilon^m\\ \end{pmatrix}$$ とした問題を考えます。この問題における基底は、添字集合を $B$ のとすると $$x_B = A_B^{-1} b’ = A_B^{-1} b + A_B^{-1} A_{B^{\text{deg}}} \begin{pmatrix}\varepsilon \\ \varepsilon^2 \\ \vdots \\ \varepsilon^m\\ \end{pmatrix}$$ です。$\varepsilon$ が十分小さいとき、この $i$ 番目の値が $0$ であるためには $ A_B^{-1} A_{B^{\text{deg}}}$ の $i$ 行目が全て $0$ である必要がありますが、これは $A_B^{-1} A_{B^{\text{deg}}}$ が正則であることからあり得ません。よって、この新しい線形計画は $\varepsilon$ が十分小さいとき非縮退となります。また、$\varepsilon$ を無限に小さく取ることで元の線形計画との最適解の差も無限に小さくなります。

$\varepsilon$ をどれほど小さく取れば十分かは事前には分かりませんが、ここでもビッグM法と同様に $\varepsilon$ に具体的な値を設定するのではなく、記号として扱うことで無限小な $\varepsilon$ を表現することができます。

$\varepsilon$ に具体的に正の微少量を代入して解く方法を摂動法、$\varepsilon$ を記号として扱い解く方法を辞書順法といいます。