📂最適化理論

基底可溶性の一意性の証明

定理 ¹

$$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$

行列 $A \in \mathbb{R}^{m \times n}$ と $\mathbf{b} \in \mathbb{R}^{m \times 1}$ と $\mathbf{c} \in \mathbb{R}^{n}$ が与えられたとき、線形計画問題が上記のように方程式の形で表される場合、基底可能解は基底 $B$ に従って一意に決まる。

---

• $\mathbf{c}^{T}$ は 転置を意味する。
• 可能解は最適化とは無関係に、とりあえず制約条件を満たす解をいう。
• $[n] = \left\{ 1, \cdots , n \right\}$ は $1$ から $n$ までの自然数の集合だ。
• $A_{B}$ は行列 $A$ から集合 $B$ に記された列だけを取った正方行列だ。
• 可能解 $\mathbf{x} \in \mathbb{R}^{n}$ について、基数 $m$ を持つ集合 $B \subseteq [n]$ が存在して $\exists A_{B}^{-1}$ であり $x_{j} = 0 \forall j \notin B$ の $\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ を基底可能解という。この集合 $B$ を基底と呼ぶ。

証明

可能解 $\mathbf{x}$ が $A \mathbf{x} = \mathbf{b}$ を満たすとする。基底ではないインデックスの集合 $N := [n] \setminus B$ を定義することによって、$A \mathbf{x}$ を以下のように表現できる。 $$ A \mathbf{x} = A_{B} \mathbf{x}_{B} + A_{N} \mathbf{x}_{N} $$ 基底 $B$ の条件 (ii) に従い、$\mathbf{x}_{N}$ の全ての成分は $0$ であり、$$ \mathbf{b} = A \mathbf{x} = A_{B} \mathbf{x}_{B} $$ になる。ベクトル $\mathbf{x}_{B}$ は $A_{B} \mathbf{x}_{B} = \mathbf{b}$ を満たすが、基底 $B$ の条件 (i) で $A_{B}^{-1}$ の存在が保証されているため、方程式 $A_{B} \mathbf{x}_{B} = \mathbf{b}$ は唯一の解を持つ。

• もしその唯一の解の全ての成分が $0$ より大きいか等しければ、$B$ による正確に一つの基底可能解を持つことになる。
• それ以外の場合、その解は $\mathbf{x} \ge 0$ を満たさない。

結論として、与えられた線形計画問題と基底 $B$ に従った基底可能解は存在しないか、存在しても唯一の解を持つ。

説明

要約で確認したように、基底は一つの基底可能解を決定するものであるが、一つの基底可能解は異なる複数の基底からそれぞれ得ることができる。

参照

線形計画法の基本定理

この定理は線形計画法の基本定理の証明に使用される。