基底解: 線形計画入門 5 - コンピュータフリーク

この章では、線形計画を解く際に非常に重要な概念である基底解について学びます。まずは、制約が少ない標準形の問題を用いてなぜ基底解を考える必要があるかについて考えます。

基底解を考えるモチベーション

制約が一つの場合

以下の制約が一つしかない正規形線形計画問題を考えます。$$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b \\ &\qquad \qquad x \ge 0\end{align*}$$

等式制約より、$x_1 = \frac{1}{a_1}(b – a_2 x_2 – \cdots – a_n x_n)$ と表されます。$x_1$ は $x_2, \cdots, x_n$ を決めると一意に決まるので、$n$ 個ある決定変数のうち、自由に動けるのは実質 $n-1$ 個となります。ただし、$x_1$ を計算した結果が負であれば実行可能でないことに注意してください。

制約が二つの場合

では制約が二つの場合はどうでしょう。$$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1 \\ & \qquad \qquad a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 \\ &\qquad \qquad x \ge 0\end{align*}$$

これも等式制約より、$$\begin{pmatrix} x_1 \\ x_2 \\ \end{pmatrix} = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{pmatrix}^{-1} \begin{pmatrix} b_1 – a_{13} x_3 – \cdots – a_{1n} x_n \\ b_2 – a_{23} x_3 – \cdots – a_{2n} x_n \\ \end{pmatrix}$$

となります。$x_1, x_2$ は $x_3, \cdots, x_n$ を決めると一意に決まるので、$n$ 個ある決定変数のうち、自由に動けるのは実質 $n-2$ 個となります。

一般の場合

一般に、制約が $m$ 個ある場合を考えます。行列 $A \in \mathbb{R}^{m \times n}$、ベクトル $b \in \mathbb{R}^m$、ベクトル $c \in \mathbb{R}^n$ を用いて以下の線形計画を考えます。$$\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*}$$

行列 $A$ の最初の $m$ 列を並べた行列を $A_B \in \mathbb{R}^{m \times m}$, 残りの $n-m$ 列を並べた行列を $A_N \in \mathbb{R}^{m \times (n-m)}$ とおくと、等式制約より、 $$\begin{pmatrix} x_1 \\ \vdots \\ x_m \\ \end{pmatrix} = A_B^{-1} \left( b – A_N \begin{pmatrix} x_{m+1} \\ \vdots \\ x_n \\ \end{pmatrix} \right)$$

なります。$x_1, \cdots, x_m$ は $x_{m+1}, \cdots, x_n$ を決めると一意に決まるので、$n$ 個ある決定変数のうち、自由に動けるのは実質 $n-m$ 個となります。

基底解の考え方

このように、制約等式を使って一部の変数を消去することによって、決定変数の数を減らし、制約式を扱う煩わしさも軽減します。上記では消去する変数を $x_1, x_2, \cdots, x_m$ としましたが、一般にどの $m$ 個の組み合わせでも同様に消去できることに注意してください。ただし、上述の議論では $A_B$ が正則であることを暗黙的に仮定し、非負制約については無視していました。これらの可能性を考慮する必要から、以下の基底解の定義に繋がります。

基底解の定義

一次独立の仮定

以下では制約条件の係数行列 $A$ の行は全て一次独立であると仮定します。一次独立ではない場合は、制約を満たす解が存在しないか、冗長な制約が含まれます。なので事前に冗長な行を削除しておくことで、一般性を失うことなくこの仮定を置くことができます。解の存在判定や冗長な行の判定は、たとえばガウスの消去法を用いて行うことができます。

基底解の定義

定義: 基底解

標準形線形計画問題 $$\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*}$$ について、ベクトル $x \in \mathbb{R}^n$ はある添字集合 $B \subset \{1, 2, \cdots, n\}$ について以下の 4 つの条件を満たすとき、基底解と呼ばれる。

$x$ は実行可能解である (= 制約条件を満たす）
$|B| = m$
任意の $i \not \in B$ について $x_i = 0$
$A$ のうち、$B$ に含まれる番号の列を並べた行列 $A_B$ は正則である

すなわち、基底解とは、適当に $m$ 個の決定変数を選んだのち、それらを上述の要領で消去したあと、残った自由に動ける変数を全て $0$ で代入した解になります。ただし、対応する解は実行可能でなければなりません。

上述の変数削除の議論より、$B$ が定まると、$x_B = A_B^{-1} b$ かつ $x_i = 0 \quad \forall i \not \in B$ より、対応する基底解 $x$ は存在すれば一意に定まります。ここで $x_B$ は $x$ の添字 $B$ に対応する部分ベクトルです。

基底解の性質

まず、基底解が必ず存在することを示します。

定理: 基底解の存在

実行可能領域が空集合でないならば基底解が存在する

証明

$A$ の列ベクトルを $A = [a_1 \cdots a_n]$ とおく。

実行可能解のうち、非ゼロ要素の最小個数を $p$ とおき、非ゼロ要素が $p$ 個である解 $x$ を適当に 1 つとる。このとき、一般性を失うことなく、非ゼロ要素の添字は $1, 2, \cdots, p$ であると仮定する。

$x$ は実行可能なので、$\sum_{i = 1}^p a_i x_i = b$ が成り立つ。

$a_1, \cdots, a_p$ が一次従属であると仮定すると、$\sum_{i = 1}^p a_i z_i = 0$ となる $z \in \mathbb{R}^n, z \neq 0, z_{p+1} = \cdots = z_{n} = 0$ が存在する。線形性より任意の $\theta \in \mathbb{R}$ について $A(x + \theta z) = b$ である。適当に $\theta$ を取ることで非負性を保ちつつ $x + \theta z$ の非ゼロ要素を $p-1$ 個以下にできるので、$p$ の最小性に反する。よって、$a_1, \cdots, a_p$ は一次独立。

基底の補充定理より、適当に添字 $B’ \subset \{p+1, \cdots, n\}$ を選んで $A$ のうち $B = \{1, \cdots, p\} \cup B’$ に含まれる番号の列ベクトルが基底であるようにできる。

$x$ は実行可能、$|B| = m$ であり、非ゼロ要素は $\{1, \cdots, p\} \subset B$ のみ、$A_B$ は正則なので、$x$ は基底解である。

次に、最適解が存在するときにはそのうち一つは基底解であることを示します。この証明は上記の証明とかなり似ています。

定理: 最適な基底解の存在

最適解が存在するならば、最適解かつ基底解である解が存在する。

証明

$A$ の列ベクトルを $A = [a_1 \cdots a_n]$ とおく。

最適解のうち、非ゼロ要素の最小個数を $p$ とおき、非ゼロ要素が $p$ 個である最適解 $x^*$ を適当に 1 つとる。このとき、一般性を失うことなく、非ゼロ要素の添字は $1, 2, \cdots, p$ であると仮定する。

$x^*$ は実行可能なので、$\sum_{i = 1}^p a_i x^*_i = b$ が成り立つ。

$a_1, \cdots, a_p$ が一次従属であると仮定すると、$\sum_{i = 1}^p a_i z_i = 0$ となる $z \in \mathbb{R}^n, z \neq 0, z_{p+1} = \cdots = z_{n} = 0$ が存在する。線形性より任意の $\theta \in \mathbb{R}$ について $A(x^* + \theta z) = b$ である。また、$x^*_1, \cdots, x^*_p$ は正なので、$\theta$ の絶対値が十分小さければ $x^* + \theta z$ は非負であり実行可能である。このときの目的関数の値は $c^\top x^* + \theta c^\top z$。ここで $c^\top z \neq 0$ であれば $\theta$ を正の微少量または負の微少量と取ることで目的関数を $c^\top x^*$ から改善できてしまい $x^*$ の最適性に反するので、$c^\top z = 0$ である。よって、適当に $\theta$ を取ることで、非負性を保ちつつ、目的関数の値も保ちつつ、 $x^* + \theta z$ の非ゼロ要素を $p-1$ 個以下にできるので、$p$ の最小性に反する。よって、$a_1, \cdots, a_p$ は一次独立。

基底の補充定理より、適当に添字 $B’ \subset \{p+1, \cdots, n\}$ を選んで $A$ のうち $B = \{1, \cdots, p\} \cup B’$ に含まれる番号の列ベクトルが基底であるようにできる。よって $x^*$ は基底解である。

この定理から基底解が線形計画において非常に重要な役割をすることが分かります。

たとえば、最適解が存在すると分かっているとき、以下の単純なアルゴリズムによって線形計画を解くことができます。

全ての添字 $m$ 個の組み合わせ $B \subset \{1, \cdots, n\}, |B| = m$ について
1. $A_B$ が正則かチェックする。正則でなければスキップ。
2. $x_B = A_B^{-1} b$ により基底解を求める
3. $x$ が非負かどうかチェックする。非負でなければスキップ。
4. 目的関数の値 $c^\top x$ を評価する
評価した目的関数値のうち、最も値が小さかったときの $x$ を最適解として出力

解の候補 $\mathcal{C}$ は無限集合だったので、有限個の候補に絞り込めたことは大きな進歩です。しかし、これだとメインループを $_nC_m$ 回ループするので効率的ではありません。次章で学ぶシンプレックス法では、明らかに最適解でない基底解を考慮せず、効率よく基底解を探索することでより効率的に線形計画を解くことができます。