線形計画法 — シンプレックス法と図式解法

線形計画法は、最大利益や最小費用のような線形の目的を、線形の制約条件のもとで最もよい値にする方法です。2変数の問題では、図式解法によって実行可能領域を求め、その頂点を調べます。より大きな問題では、シンプレックス法が同じ頂点の考え方を代数的に使います。

線形計画法が使えるのは、目的関数と制約条件がどちらも線形である場合だけです。関係が曲がっていたり、曲線になっていたり、$xy$ のような積に依存したりするなら、そのモデルは線形計画ではありません。

線形計画法の定義

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

制約条件はたとえば

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

のように表され、これに同様の線形不等式や、負の値に意味がないときの $x_i \ge 0$ のような条件が加わります。

すべての制約を満たす点の集合を実行可能領域といいます。線形計画法が問うのは、その実行可能な点の中で、どれが最もよい目的関数値を与えるかということです。

図式解法のしくみ

意思決定変数が2つだけなら、各制約条件を $xy$ 平面上に描けます。許される領域どうしの重なりが実行可能領域です。

その領域内の各点は、どれも有効な解です。目的関数は、それぞれの点に値を対応させます。

線形計画法では、重要な事実があります。最適解が存在するなら、少なくとも1つの最適解は実行可能領域の頂点で生じます。だから図式解法では、塗られた領域のすべての点を調べるのではなく、頂点に注目します。

例題：図式解法で線形計画問題を解く

ある工場が2種類の製品 $A$ と $B$ を作るとします。

• 製品 $A$ の1単位あたりの利益: $3$
• 製品 $B$ の1単位あたりの利益: $5$
• 機械時間の制限: 製品 $A$ は1単位あたり $1$ 時間、製品 $B$ は1単位あたり $2$ 時間使い、使える時間は最大 $8$ 時間
• 組立時間の制限: 製品 $A$ は1単位あたり $1$ 時間、製品 $B$ も1単位あたり $1$ 時間使い、使える時間は最大 $5$ 時間

$A$ の生産量を $x$、$B$ の生産量を $y$ とします。

最大化するのは

$$P = 3x + 5y$$

制約条件は

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

頂点を求める

座標軸と制約直線から、実行可能領域の頂点は次の通りです。

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

点 $(2,3)$ は、境界の方程式

$$x + 2y = 8,\quad x + y = 5$$

を連立して求めます。

引き算すると $y = 3$ となり、そこから $x = 2$ です。

各頂点で目的関数を調べる

各頂点で利益を計算します。

• $(0,0)$ では、$P = 0$
• $(5,0)$ では、$P = 15$
• $(0,4)$ では、$P = 20$
• $(2,3)$ では、$P = 21$

したがって最大利益は

$$P = 21$$

であり、そのとき

$$(x,y) = (2,3)$$

です。

これが図式解法を一言で言ったものです。実行可能領域を描き、頂点を見つけ、そこで目的関数を評価します。

シンプレックス法の直感

図式解法が実用的なのは、変数が2つの場合だけです。3つでも立体としてイメージできるなら可能なことがありますが、現実の最適化問題には多くの変数があることが普通です。その場合、実行可能領域を描くのは現実的ではありません。

シンプレックス法は、同じ頂点の考え方を保ったまま、それを代数的に行います。大まかに言えば、目的関数を改善する実行可能な頂点から別の頂点へ移動し、隣接する移動でこれ以上よくならなくなったところで止まります。

したがって、イメージとしては次のように考えるとよいです。

• 図式解法: 頂点を目で見る
• シンプレックス法: 描かずに頂点をたどる

この説明は直感的なイメージであって、完全なアルゴリズムではありません。実際のシンプレックス法では、各段階でどの変数を入れ、どの変数を外すかを決めるために、単体表やそれと同等の代数的な形を使います。

なぜ頂点が重要なのか

線形の目的関数は、たとえば

$$3x + 5y = k$$

のような等値線を作ります。

この直線を、利益が大きくなる方向へ平行移動していくと、実行可能領域に最後に接する点で最大値が生じます。

多くの図では、その最後の接点は1つの頂点です。もし目的関数の直線が境界の辺と平行なら、その辺上の複数の点がすべて最適になることもあります。その場合でも、少なくとも1つの最適な頂点は存在します。

よくあるミス

実行可能と最適を混同する

ある点がすべての制約を満たしていても、目的関数を最大化または最小化しているとは限りません。実行可能とは、単に条件を満たしているという意味です。

非負条件を忘れる

$x$ や $y$ が生産量や輸送量を表すなら、通常は負の値に意味がありません。$x \ge 0$ や $y \ge 0$ を入れ忘れると、問題そのものが変わってしまいます。

答えは必ず整数だと思い込む

通常の線形計画法では、分数の値も許されます。トラックの台数や作業員の人数のように、変数が整数でなければならないなら、整数計画法のモデルや整数条件を追加する必要があります。

どの問題にも最適解があると思い込む

線形計画問題の中には、どの点もすべての制約を満たさない実行不可能なものがあります。また、目的関数が際限なく改善できる非有界なものもあります。制約条件が十分に問題を囲い込んでいるときにだけ、有限の最適値が得られます。

変数が多いのに図式解法を使おうとする

変数が多くなると、グラフで解くのはもはや適切ではありません。そこでシンプレックス法や他の最適化手法が必要になります。

線形計画法が使われる場面

線形計画法は、限られた資源をめぐって意思決定が競合し、しかも目標と制約の両方を線形にモデル化できるときに使われます。典型例としては、生産計画、輸送、要員配置、配合、スケジューリング、予算配分などがあります。

ただし、モデルの良し悪しは前提に左右されます。現実の関係が線形に近くない場合や、変数が整数でなければならない場合には、通常の線形計画法は出発点にすぎないこともあります。

類題に挑戦してみよう

2つの製品、2つの資源制約、そして利益関数をもつ小さな文章題を1つ作ってみましょう。変数を定め、制約をグラフに描き、自分で頂点を調べてみてください。この考え方がつかめると、シンプレックス法は同じ論理を高次元に拡張したものだとわかり、ずっと理解しやすくなります。