線形計画の定式化と等価な変種: 線形計画入門 3

この章では線計画を定式化し、いくつもある線形計画が等価であることをみていきます。

線形計画の定式化

目的関数と制約関数が全て一次関数である場合を線形計画といいます。

等式制約や不等式制約の有無によっていくつかの変種があるのでそれらを紹介します。

標準形線形計画

定義: 標準形線形計画

行列 $A \in \mathbb{R}^{m \times n}$、ベクトル $b \in \mathbb{R}^m$、ベクトル $c \in \mathbb{R}^n$ により表される最適化問題

$$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad A x = b \\ &\qquad \qquad x \ge 0\end{align*}$$

を標準形線形計画という。

ここで、ベクトル $x, y$ について $x \ge y$ は全ての要素で $x_i \ge y_i$ が成り立っていることを表します。また、標準形では最大化は考えず最小化問題だけが含まれることに注意してください。

不等式型線形計画

定義: 不等式型線形計画

行列 $A \in \mathbb{R}^{m \times n}$、ベクトル $b \in \mathbb{R}^m$、ベクトル $c \in \mathbb{R}^n$ により表される最適化問題

$$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad A x \le b \\ & \qquad \qquad x \ge 0\end{align*}$$

を不等式型線形計画という。

定式化の等価性

線形計画には、上述の標準形と不等式形や、最大化と最小化の組み合わせで様々な定式化が考えられます。しかし、様々な定式化は実は全て等価なのです。

たとえば、最大化問題 $$\begin{align*}&\underset{x \in \mathbb{R}^d}{\text{maximize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad A x = b \\ &\qquad \qquad x \ge 0\end{align*}$$ は目的関数の符号を反転させた最小化問題 $$\begin{align*}&\underset{x \in \mathbb{R}^d}{\text{minimize}} \quad (-c)^\top x \\ &\quad \text{s.t.} \qquad A x = b \\ &\qquad \qquad x \ge 0\end{align*}$$ と等価（最適解が同じ）です。

また、不等式型線形計画は、補助的な決定変数 $s \in \mathbb{R}^m$ を導入し、不等式の「余り量」を表すことにすると、$$\begin{align*}&\underset{x \in \mathbb{R}^n, s \in \mathbb{R}^m}{\text{minimize}} \quad c^\top x \\ &\quad \text{s.t.} \qquad A x + s = b \\ & \qquad \qquad x \ge 0, s \ge 0 \end{align*}$$ と等価です。

つまり、標準形線形計画を解くアルゴリズムさえ設計してしまえば、不等式型線形計画を解きたいときにも、等価な標準形線形計画に変換してやりアルゴリズムに入力することで、もとの不等式型線形計画が解けることになります。

よって、これから先は、ターゲットを標準形線形計画に絞ってアルゴリズムの設計を考えます。具体的には $A, b, c$ が与えられたとき、最適な $x$ を計算するアルゴリズムです。

ただし、他の定式化が標準形と等価だからといって他の定式化が無駄なのではありません。よりシンプルにモデリングできたり、図形的に考えるときに便利であったりするので、今後も他の定式化を使っていきます。そのような場合でも常に標準形に変換して解けることを覚えておいてください。