logo

線形計画問題の方程式フォーム 📂最適化理論

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

定義 1

行列 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}に関して、以下の線形計画問題を標準形standard formまたは方程式フォームequational formと呼ぶ。 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}

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

説明

標準形への変換

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

Maximize3x1−2x2subject to2x1−x2≤4x1+3x2≥5x2≥0 \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}

変換の基本的なアイディアは「不等式をまとめること」である。最初の制約 2x1−x2≤4 2 x_{1} - x_{2} \le 4 は実際、何らかの x3≥0x_{3} \ge 0について 2x1−x2+x3=4 2 x_{1} - x_{2} + x_{3} = 4 と表現しても全く問題ない。2x1−x22 x_{1} - x_{2}が44より小さい量をx3>0x_{3} > 0が補う役割をするからである。このように方程式を緩める役割をする変数をスラック変数slack variableと呼ぶ。二番目の制約 x1+3x2≥5 x_{1} + 3 x_{2} \ge 5 は両辺に−1-1を掛け、最初の制約で行ったように新しいスラック変数x4x_{4}を導入すれば −x1−3x2+x4=−5 - x_{1} - 3 x_{2} + x_{4} = - 5 である。ここまで見ると Maximize3x1−2x2subject to2x1−x2+x3=4−x1−3x2+x4=−5x2,x3,x4≥0 \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} は方程式フォームの条件を満たしたように見えるが、まだx1≥0x_{1} \ge 0という制約がないので、これを形式に合わせなければならない。与えられた問題でx1x_{1}は実数全体で許されているので、これを二つの正数の差x1=y1−z1x_{1} = y_{1} - z_{1}に分解すればx1x_{1}は式から消え、次のような方程式フォームで表現できる。 Maximize3(y1−z1)−2x2subject to2(y1−z1)−x2+x3=4−(y1−z1)−3x2+x4=−5y1,z1,x2,x3,x4≥0 \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}

方程式フォームの幾何

20211004_220856.png

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

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

  1. Matousek. (2007). 線形プログラミングを理解して使う: p41. ↩︎