logo

線形計画問題において最適解が存在する場合、そのうちの一つは基底実行可能解である 📂最適化理論

線形計画問題において最適解が存在する場合、そのうちの一つは基底実行可能解である

定理 1

MaximizecTxsubject toAx=bx≥0 \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∈Rm×nA \in \mathbb{R}^{m \times n} および b∈Rm×1\mathbf{b} \in \mathbb{R}^{m \times 1} と c∈Rn\mathbf{c} \in \mathbb{R}^{n} について、線形計画問題が上のように方程式の形で表されるとする。もし最適解が存在するならば、最適基底実行可能解も存在する。

  • cT\mathbf{c}^{T} は転置を意味する。
  • 実行可能解とは、最適化とは関係なく制約条件を満たす解のことである。

証明

戦略：この証明は本質的に最適解の存在証明と同じである。

基底実行可能解の定義：実行可能解 x∈Rn\mathbf{x} \in \mathbb{R}^{n} に対して、集合 B⊆[n]B \subseteq [n] が存在してその濃度が mm であり、∃AB−1\exists A_{B}^{-1} であり、xj=0∀j∉Bx_{j} = 0 \forall j \notin B であるx=(x1,⋯ ,xn)\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right) を基底実行可能解という。この集合 BB を基底と呼ぶ。

任意の実行可能解 x0\mathbf{x}_{0} に対して cTx0≤cTx \mathbf{c}^{T} \mathbf{x}_{0} \le \mathbf{c}^{T} \mathbf{x} x\mathbf{x} を満たす中で00 の成分が最も多い解をx~\tilde{\mathbf{x}} とする。

  • x~\tilde{\mathbf{x}} が基底実行可能解であることを示せれば、基底実行可能解が有限に多く存在するので、最適解の存在を示すことができる。
  • したがって、どんな最適解も最適である前に実行可能解であるため、最適解と同じ目的関数の値を持つ（最適）基底実行可能解が存在するはずである。従って、少なくとも1つの最適解は基底実行可能解である。

今、インデックスの集合 K={k∈[n]:(x~)k>0} K = \left\{ k \in [n] : \left( \tilde{\mathbf{x}} \right)_{k} > 0 \right\} を定義したときに AKA_{K} の列ベクトルが線形独立かどうかによって、場合を分けて考えよう。

ケース1. 線形独立

基底実行可能解の定義に従えば、x~\tilde{\mathbf{x}} は自然に基底実行可能解であり、これ以上証明することはない。

ケース2. 線形従属

線形独立ではなく線形従属である場合、ある∣K∣|K|次元ベクトルv∈R∣K∣\mathbf{v} \in \mathbb{R}^{|K|}が次を満たす存在する。 AKv=0 A_{K} \mathbf{v} = \mathbf{0} 例えば、K={2,3,5}K = \left\{ 2,3,5 \right\} が v=(−2,1,7)\mathbf{v} = (-2,1,7) であれば、w\mathbf{w} は 2,3,52,3,5 番目の成分が v\mathbf{v} と同じで他が 00 のベクトルw=(0,−2,1,0,7)\mathbf{w}= (0,-2,1,0,7) になるなど、wK=v\mathbf{w}_{K} = \mathbf{v} と Aw=AKv=0A \mathbf{w} = A_{K} \mathbf{v} = \mathbf{0} を満たすように拡張したベクトルw∈Rn\mathbf{w} \in \mathbb{R}^{n} を考えることができる。このとき、w\mathbf{w} は元のv\mathbf{v} の成分の符号を再調整することで cTw>0 \mathbf{c}^{T} \mathbf{w} > 0 も満たすことができる。これから言及されるw\mathbf{w} は、上記の不等式を満たすベクトルとして考えよう。

これから、w\mathbf{w} について、t≥0t \ge 0 に従属する次のベクトルx(t)\mathbf{x}(t) を考えよう。 x(t)=x~+tw \mathbf{x} (t) = \tilde{\mathbf{x}} + t \mathbf{w} まず、x~\tilde{\mathbf{x}} は実行可能解であり、Aw=AKv=0A \mathbf{w} = A_{K} \mathbf{v} = \mathbf{0} を満たすようにしたw\mathbf{w} の定義により、全てのt≥0t \ge 0 に対して Ax(t)=Ax~+tAw=Ax~=b \begin{align*} A \mathbf{x} (t) =& A \tilde{\mathbf{x}} + t A \mathbf{w} \\ =& A \tilde{\mathbf{x}} \\ =& \mathbf{b} \end{align*} である。つまり、x(t)\mathbf{x} (t) もx(t)≥0\mathbf{x}(t) \ge 0 を除く全ての制約を満たしている。一方、x(t)\mathbf{x} (t) の jj番目の成分xj(t)x_{j}(t) を考えると、xj(t)=x~j+twjx_{j}(t) = \tilde{x}_{j} + t w_{j} のように表され、これらの少なくとも1つはwj<0w_{j} < 0 でなければならない。もし全てのjj に対してwj>0w_{j} > 0 であれば、全てのtt に対してx(t)=x~+tw≥0\mathbf{x} (t) = \tilde{\mathbf{x}} + t \mathbf{w} \ge 0 となり全てのx(t)\mathbf{x} (t) も実行可能解であるが、これは目的関数が上界を持つという仮定に矛盾するので、 cTx(t)=cTx~+tcTw→∞ \mathbf{c}^{T} \mathbf{x} (t) = \mathbf{c}^{T} \tilde{\mathbf{x}} + t \mathbf{c}^{T} \mathbf{w} \to \infty したがって、少なくとも1つのwj0w_{j_{0}} が負であれば、いずれ xj0(t0)=xj0~+t0wj0=0 x_{j_{0}} \left( t_{0} \right) = \tilde{x_{j_{0}}} + t_{0} w_{j_{0}} = 0 を初めて満たすt0≥0t_{0} \ge 0 が存在するはずである。そうすると、x(t0)\mathbf{x} \left( t_{0} \right) はx~\tilde{\mathbf{x}} に比べて00 の成分を1つ多く持ちながらも cTx(t0)=cTx~+t0cTw≥cTx0+t0cTw≥cTx0 \begin{align*} \mathbf{c}^{T} \mathbf{x} \left( t_{0} \right) =& \mathbf{c}^{T} \tilde{\mathbf{x}} + t_{0} \mathbf{c}^{T} \mathbf{w} \\ \ge & \mathbf{c}^{T} \mathbf{x}_{0} + t_{0} \mathbf{c}^{T} \mathbf{w} \\ \ge & \mathbf{c}^{T} \mathbf{x}_{0} \end{align*} も満たす。これは、cTx0≤cTx\mathbf{c}^{T} \mathbf{x}_{0} \le \mathbf{c}^{T} \mathbf{x} を満たしながら00 の成分が最も多くなるようにしたx~\tilde{\mathbf{x}} の定義に矛盾する。

基底実行可能解の一意性：基底実行可能解は、基底 BB によって一意に決定される。

結果的に、AKA_{K} は線形従属になることができないため、x~\tilde{\mathbf{x}} は基底実行可能解でなければならず、基底の選択によって決まる基底実行可能解が一意であることから、基底実行可能解と最適解が有限に多く存在し、したがって、いくつかの最適解に対しては、同じ目的関数の値を持つ基底実行可能解が存在し、それらもまた最適解であるため、最適解の中で少なくとも1つは基底実行可能解でなければならない。

■

参照

線形計画法の基本定理

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

  1. Matousek. (2007). Understanding and Using Linear Programming: p46. ↩︎