📂最適化理論

線形計画問題の方程式フォーム

定義 ¹

行列 $A \in \mathbb{R}^{m \times n}$、$\mathbf{b} \in \mathbb{R}^{m \times 1}$、そして $\mathbf{c} \in \mathbb{R}^{n}$に関して、以下の線形計画問題を標準形^{standard form}または方程式フォーム^{equational form}と呼ぶ。 $$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$

---

• $\mathbf{c}^{T}$は転置を意味する。
• 最適化は最大化あるいは最小化を指す。

説明

標準形への変換

原則として、どんな線形計画問題も標準形に変換できる。例えば、以下のような最大化問題が与えられたとする。

$$ \begin{matrix} \text{Maximize} & 3 x_{1} - 2 x_{2} \\ \text{subject to} & 2 x_{1} - x_{2} \le 4 \\ & x_{1} + 3 x_{2} \ge 5 \\ & x_{2} \ge 0 \end{matrix} $$

変換の基本的なアイディアは「不等式をまとめること」である。最初の制約 $$ 2 x_{1} - x_{2} \le 4 $$ は実際、何らかの $x_{3} \ge 0$について $$ 2 x_{1} - x_{2} + x_{3} = 4 $$ と表現しても全く問題ない。$2 x_{1} - x_{2}$が$4$より小さい量を$x_{3} > 0$が補う役割をするからである。このように方程式を緩める役割をする変数をスラック変数^{slack variable}と呼ぶ。二番目の制約 $$ x_{1} + 3 x_{2} \ge 5 $$ は両辺に$-1$を掛け、最初の制約で行ったように新しいスラック変数$x_{4}$を導入すれば $$ - x_{1} - 3 x_{2} + x_{4} = - 5 $$ である。ここまで見ると $$ \begin{matrix} \text{Maximize} & 3 x_{1} - 2 x_{2} \\ \text{subject to} & 2 x_{1} - x_{2} + x_{3} = 4 \\ & - x_{1} - 3 x_{2} + x_{4} = - 5 \\ & x_{2}, x_{3}, x_{4} \ge 0 \end{matrix} $$ は方程式フォームの条件を満たしたように見えるが、まだ$x_{1} \ge 0$という制約がないので、これを形式に合わせなければならない。与えられた問題で$x_{1}$は実数全体で許されているので、これを二つの正数の差$x_{1} = y_{1} - z_{1}$に分解すれば$x_{1}$は式から消え、次のような方程式フォームで表現できる。 $$ \begin{matrix} \text{Maximize} & 3 \left( y_{1} - z_{1} \right) - 2 x_{2} \\ \text{subject to} & 2 \left( y_{1} - z_{1} \right) - x_{2} + x_{3} = 4 \\ & - \left( y_{1} - z_{1} \right) - 3 x_{2} + x_{4} = - 5 \\ & y_{1}, z_{1}, x_{2}, x_{3}, x_{4} \ge 0 \end{matrix} $$

方程式フォームの幾何

方程式$A \mathbf{x} = \mathbf{b}$は一般的な平面、超平面を形成し、$\mathbf{x} \ge \mathbf{0}$という条件によってユークリッド空間で円錐形の部分だけを取ることができるようになる。スラック変数が導入されることで次元は増えるが、最適化のために探索しなければならない空間自体は大幅に単純化される。

一方、この解空間は他ならぬシンプレックスであり、ここからシンプレックスメソッドのアイデアにつながる。