線形計画問題の定義
定義 1
目的関数objective functionと制約constraintが線形な最適化問題を線形計画問題linear Programming Problem、略してLP問題という。簡単に言うと、線形問題とは、与えられた目的関数 $f: \mathbb{R}^{n} \to \mathbb{R}$ がベクトル $\mathbf{c} \in \mathbb{R}^{n}$ に対して $$ f \left( \mathbf{x} \right) := \mathbf{c}^{T} \mathbf{x} $$ であり、与えられた行列 $A \in \mathbb{R}^{m \times n}$ と $\mathbf{b} \in \mathbb{R}^{m \times 1}$ に対して $$ A \mathbf{x} \le \mathbf{b} $$ を満たしながら $f$ の関数値が最適化される $\mathbf{x} \in \mathbb{R}^{n}$ を見つける問題である。主に以下のように表される。 $$ \begin{matrix} \text{Optimize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} \le \mathbf{b} \end{matrix} $$ このような問題では、まず、制約条件を満たす解を実行可能解feasible solutionとし、その中で目的関数を最大化または最小化する解を最適解optimal solutionという。
説明
語り
線形とは、与えられた目的関数と制約条件が線形であるために付けられた言葉だ。式に$\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$の二乗項やログなどの非線形関数型が入らず、制約も行列（不等）式の形で現れなければならない点から、適切な表現である。主に行列代数、線形代数でこのように等式で表された問題を解決することと対比される。 $$ A \mathbf{x} = \mathbf{b} $$
計画は、我々が一般的に理解しているコンピュータのアプリケーションではなく、スケジュールやタスクを意味する。実際の線形計画法の応用では、各変数 $x_{1} , \cdots , x_{n}$ は時間、エネルギー、資源など様々な要素を表すことができる。
例えば、経済学や経営学では、これらの要素を最大化することは恐らく有用性、最小化することはコストに相当するだろう。出退勤時間と効率が異なる従業員をどの仕事に割り当てるかによる最適な勤務表を作成する場合、線形計画法が最も優先される方法となるだろう。
例 2
$$ \begin{matrix} \text{Optimize} & x_{1} + x_{2} \\ \text{subject to} & x_{1} \ge 0 \\ & x_{2} \ge 0 \\ & x_{2} - x_{1} \le 1 \\ & x_{1} + 6 x_{2} \le 15 \\ & 4 x_{1} - x_{2} \le 10 \end{matrix} $$
上記のような線形問題を考えてみよう。条件が五つもあるため、一見複雑に見えるが、実際に扱う変数は$x_{1}$と$x_{2}$の二つだけなので、これを$2$次元の平面に表示すれば、以下の図のように条件を満たす領域を確認できる。
この領域に属する全ての点は、少なくとも制約条件を満たしている実行可能解である。ここから、目的関数$\Lambda \left( x_{1} , x_{2} \right) = x_{1} + x_{2}$が最大になる点を見つければいい。幾何学的に言うと、実行可能解の領域と$x_{1} + x_{2} = \lambda$が交差する部分の中で$\lambda$が最も大きくなる場所、つまり直線の$y$切片が最も大きくなる点を見つければいいのだ。
実際の例の解答は$\lambda = 5$になるような$\left( x_{1} , x_{2} \right) = (3,2)$である。しかし、この解法はどこか見覚えがあるはずだ。一般的な教育課程を経ていれば、恐らく高校一年生ぐらいの時に教科書でこのような問題を見たことがあるだろう。このように基本的なアイデアは中学校を卒業したばかりの子供たちでも理解できるほどシンプルだ。元々「線形」が付いているということは、実際の解法がどうであれ、概念自体は簡単であるということだ。