📘

シンプレックス法の手順と直感的な理解

2025/05/27に公開

シンプレックス法を解説！

この記事ではシンプレックス法という最適化手法について、できるだけ直感的に理解できるよう解説します。記事中に誤り等ありましたら、コメント等でお知らせください。

想定読者

大学の講義等でシンプレックス法を習っている人
大学の講義等でシンプレックス法を習ったが結局何をやっているのかわからなかった人

シンプレックス法とは？

線形計画問題を解くためのアルゴリズムです。

まず、線形計画問題とは、以下のような形式の問題です。

\text{maximize} \quad c^T x \\\text{subject to} \quad Ax \leq b, \quad x \geq 0

ここで、

$x$ ：変数ベクトル（求める値）
$c$ ：目的関数の係数ベクトル
$A$ 、 $b$ ：制約条件を構成する行列とベクトル

をそれぞれ表します。

シンプレックス法の手順（簡略版）

問題の定式化
スラック変数を追加して不等式制約を標準形に変換
目的関数を改善するようにピポット操作を行う
改善できなくなるまで3-4を繰り返す

具体例で完全理解！生産量最大化問題

実際にシンプレックス法を使って解いてみましょう。

問題設定

あなたは工場の経営者です。商品1は価値が3円、商品2は価値が5円です。これらの商品を売って利益を最大化したいと考えています。ただし、商品1を作るためには機械Aを2時間、機械Bを4時間使う必要があり、商品2を作るためには機械Aを3時間、機械Bを2時間使う必要があります。また、メンテナンスのため、機械Aは1週間に32時間、機械Bは1週間に24時間しか稼働できません。この制約の中で、どのように利益を最大化すればよいでしょうか？

まず、問題を定式化しましょう。商品1の生産量を $x_1$ 、商品2の生産量を $x_2$ とすると、以下のように表現できます。

目的：利益Zを最大化
$Z = 3x_1 + 5x_2$
制約：

機械Aの使用時間： $2x_1 + 4x_2 ≤ 32\text{時間}$
機械Bの使用時間： $3x_1 + 2x_2 ≤ 24\text{時間}$
$x₁ \geq 0, x₂ \geq 0$ (商品生産量を負にすることはできないものとします)

ステップ1：標準形への変換

制限が不等式というのは扱いづらいため、スラック変数 $s_1, s_2$ を追加して制約を等式に変換しましょう。スラック変数を導入すると、以下のように変形できます。

標準形：
最大化： $Z = 3x_1 + 5x_2 + 0s_1 + 0s_2$
制約条件：

$2x_1 + 4x_2 + s_1 = 32$
$3x_1 + 2x_2 + s_2 = 24$
$x_1, x_2, s_1, s_2 \geq 0$

ステップ2: 初期シンプレックスタブローの作成

標準系の係数をタブロー形式にしましょう。

基底	$x_1$	$x_2$	$s_1$	$s_2$	右辺
$s_1$	2	4	1	0	32
$s_2$	3	2	0	1	24
$Z$	-3	-5	0	0	0

ただし、 $Z$ の係数だけはマイナスをかけておく必要があります。

現在の状態は、 $x_1=0, x_2=0, s_1=32, x_2 =24, Z= 0$ です。

ここまでは難しくないと思います。問題はここからです。

ステップ3: ピボット操作（1回目）

ピポット列の決定:
Z行の係数が負であるもの中から一番最小のものを選択します。ここでは $x_2$ の列（係数 -5）がピボット列です。
ピボット行の決定:
右辺の値をピボット列の係数で割り、最小比を求めます。
$s_1$ 行： $32 / 4 = 8$ , $s_2$ 行： $24 / 2 = 12$
→ $s_1$ 行がピボット行です（最小値 8）。
ピボット要素を1に変換:
$s_1$ 行を 4 で割ります。
$x_2$ 行： $(0.5, \, 1, \, 0.25, \, 0, \, 8)$
他の行の更新:
そのほかの行が0になるようにピポット行を適用します。
- $s_2$ 行： $3 - 2 \times 0.5 = 2$ , $2 - 2 \times 1 = 0$ , $24 - 2 \times 8 = 8$
  → $(2, \, 0, \, -0.5, \, 1, \, 8)$
- $Z$ 行： $-3 + 5 \times 0.5 = -0.5$ , $0 + 5 \times 8 = 40$
  → $(-0.5, \, 0, \, 1.25, \, 0, \, 40)$

更新後のタブロー：

基底	$x_1$	$x_2$	$s_1$	$s_2$	右辺
$x_2$	0.5	1	0.25	0	8
$s_2$	2	0	-0.5	1	8
$Z$	-0.5	0	1.25	0	40

いきなり意味のわからない操作を始めたように見えるかもしれませんが、これからその内容を詳しく解説します。

今回行ったピボット操作では、何をしたのでしょうか？まず、操作前の状態は $x_1 = 0, x_2 = 0$ でした。このとき、目的関数 $Z$ の式を見ると、 $x_1$ を1だけ増やすと $Z$ は3増加し、 $x_2$ を1だけ増やすと $Z$ は5増加することがわかります。そこで、増加率の大きい $x_2$ を増やせるだけ増やしてみることにします。

このとき注意すべきなのが制約条件です。たとえば制約式の一つは次のようになっています。

2x_1 + 4x_2 + s_1 = 32

$x_1 = 0$ のままでこの式を満たすためには、 $x_2$ を最大まで増やすと次のような制限がかかります。

4x_2 \leq 32 \Rightarrow x_2 \leq 8

したがって、

x_2 = 8

が限界となります。このとき、

Z = 5 \times 8 = 40

となります。

一方で、もう一つの制約条件

3x_1 + 2x_2 + s_2 = 24

は

x_2

を12まで増やすことができるので、一つ目の制約条件だけ考えればいいことがわかります。

この一連の流れを、ピボット操作によって機械的に処理しました。

「Zの中で最小値を選ぶ」というステップは、「 $x_2$ を1増やすと $Z$ が5増えるので、 $x_2$ を変化させてみる」という判断に対応しています。
「ピボット行の決定」は、「 $x_2$ を最大どこまで増やせるかを判定する」操作に相当します。
「ピボット要素を1にし、他の要素を更新する」ことで、「実際に $x_2$ を最大まで増加させる」処理を実行しました。

この操作によって、状態は次のように変化しました：
$x_1 = 0,\ x_2 = 8,\ s_1 = 0,\ s_2 = 8,\ Z = 40$

ステップ4: ピボット操作（2回目）

ピボット列の選択:
Z行の係数が負であるもの中から一番最小のものを選択します。ここではZ行の係数が負の $x_1$ 列（係数 -0.5）がピボット列です。
ピボット行の決定:
$x_2$ 行： $8 / 0.5 = 16$ , $s_2$ 行： $8 / 2 = 4$
→ $s_2$ 行がピボット行です（最小値 4）。
ピボット要素を1に変換:
$s_2$ 行を 2 で割ります。
$x_1$ 行： $(1, \, 0, \, -0.25, \, 0.5, \, 4)$
他の行の更新:
- $x_2$ 行： $0.5 - 0.5 \times 1 = 0$ , $8 - 0.5 \times 4 = 6$
  → $(0, \, 1, \, 0.375, \, -0.25, \, 6)$
- $Z$ 行： $-0.5 + 0.5 \times 1 = 0$ , $40 + 0.5 \times 4 = 42$
  → $(0, \, 0, \, 1.125, \, 0.25, \, 42)$

最終タブロー：

基底	$x_1$	$x_2$	$s_1$	$s_2$	右辺
$x_2$	0	1	0.375	-0.25	6
$x_1$	1	0	-0.25	0.5	4
$Z$	0	0	1.125	0.25	42

さて、この操作も「何をやっているのか」を詳しく見ていきましょう。

前回のステップでは、 $x_2$ を増やして利益（Z）を増加させました。今回は、次に利益を増やせる変数として $x_1$ に注目します。Zの式（ $Z = 3x_1 + 5x_2$ ）から、 $x_1$ を1増やせば3の利益が得られます。ところが、注意が必要です。前のステップで $x_2 = 8$ にしたため、制約式

2x_1 + 4x_2 \leq 32

がすでに限界であり、自由に $x_1$ を増やせるわけではありません。しかし、 $s_2$ を1減らせば $x_1$ を2増やすことができます。この操作は割に合うか考えてみましょう。 $Z = 3x₁ + 5x₂$ から、 $x_2$ を1減らして $x_1$ を2つ増やすことで、1の利益を上げることができます。そのため、この操作を行うことで利益が増加するので実行する価値があることがわかります。次に、この操作を何回行えるかを考えます。制約式2を思い出しましょう。

3x_1 + 2x_2 + s_2 = 24

において、今は

x_1 = 0, x_2 = 8

のため、

3 \cdot 0 + 2 \cdot 8 = 16 \Rightarrow s_2 = 8

まだ8の余裕があります。実際にこの制約の範囲で、どこまで

x_2

を減らして

x_1

を増やせるかを確認してみましょう。たとえば、

x_1 = 4

にすれば、

3 \cdot 4 + 2 \cdot 6 = 12 + 12 = 24 \Rightarrow s_2 = 0

このとき

x_2 = 6

に下がってはいますが、

x_1 = 4

に増やせるため、制約を満たしつつ利益を最大化できます。これ以上、例えば

x_1=6, x_2=5

とかにしてしまうと、

3x_1 + 2x_2 = 28

であり制約である24をオーバーして

s_2

が0以下になってしまいます。

「Zの中で最小値を選ぶ」ステップは、「 $x_1$ を1つ増やすことで( $x_2$ が0.5減る代わりに)全体の利益 $Z$ を0.5あげられる」という判断に該当します。
「ピボット行の決定」ステップは「 $x_1$ を最大何回まで増加させられるか(今回は4)を判断すること」に対応します。
「ピボット要素を1にし、他の要素を更新する」ことで、「実際に $x_1$ を最大まで増加させる」処理を実行しました。

この操作を行うことで、

x_1 = 4,\ x_2 = 6, s_1=0 ,s_2=0,\ Z = 42

という新たな最適解にたどり着きました。

ステップ5: 最適解の確認

Z行の係数がすべて非負になったため、これ以上値を増やす操作はありません。最適解が得られました。

$x_1 = 4$ , $x_2 = 6$
最大値 $Z = 3 \times 4 + 5 \times 6 = 42$

このような手順で最大値を求めることができました。

なぜ頂点移動で最大値が求まるのか？幾何的解説

この問題を図的にとらえると、以下のようになります。制約条件によって定まる範囲内で、最もZの値（図中の斜め方向の破線はZの等高線）を高くする点を探す問題です。

答えは必ず「角」にある
制約が線形であることがから、制約範囲が作る図形は、へこみのない多角形（凸多面体）です。このような形では、「一番高い場所」は必ず角にあります。シンプレックス法は、この性質を利用して「角」だけを調べます。
局所解は存在しない
凸多面体の構造上、各頂点は局所解にはなりません。一度下へ行かなければ最適解へ行けないということは無く、常に目的関数の値が大きくなる方向を目指していけば、いずれ最適解へたどり着けます。逆に言うと、もし今いる頂点よりも良い頂点が周辺に無ければ、その頂点が最適解ということになります。
有限回で必ず答えにたどり着く
角の数は有限なので、同じ角をウロウロしなければ必ず終わります。シンプレックス法は「同じ角を二度通らない」というルールを組み込んでおり、最悪の場合でも全ての角を調べる前に最適解が見つかります。

以上の三点の理由から、今の頂点から移動できる最も良い頂点に移動することを繰り返すことで必ず最適解が得られます。

立体では以下のように表すことができます。直感的には「途中で下り坂にならない坂を登っていく」イメージでとらえると理解しやすいと思います。初期頂点から出発し、目的関数Zを最も大きく改善する隣接頂点へ移動を繰り返すと、凸多面体の構造上必ず最適頂点に到達します。

この記事を友人に捧げます。中間テスト頑張ってください！