この記事について
PuLPやGurobiを使っていると、なんとなく「線形計画問題（LP）」を解いているのは分かるのですが、「内部でどんな構造を扱っているのか？」を意識する機会は少ない気がします。
この記事では、単体法を理解するための土台として、線形計画問題の幾何的なイメージを整理します。標準形・実行可能領域・凸多面体の頂点という3つのキーワードを押さえると、構造の見通しが良くなるかなと思います。
線形計画問題とは
線形計画問題（Linear Program: LP） は、目的関数と全ての制約条件が線形の式で表される最適化問題です。
| 要素 | 性質 |
|---|---|
| 目的関数 | 線形（$c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$） |
| 制約条件 | 線形の等式または不等式 |
| 変数 | 連続値（整数条件はなし） |
標準形（不等式標準形）
LPにはいくつかの書き方がありますが、理論的に扱いやすい書き方として不等式標準形を使うことが多いです。
\text{maximize} \quad c_1 x_1 + c_2 x_2 + \cdots + c_n x_n
\text{subject to} \quad \sum_{j=1}^{n} a_{ij} x_j \leq b_i, \quad i = 1, \ldots, m
x_j \geq 0, \quad j = 1, \ldots, n
行列形式では：
\text{maximize} \quad \mathbf{c}^\top \mathbf{x} \quad \text{s.t.} \quad \mathbf{A}\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq \mathbf{0}
と書きます。
標準形のポイント：
- 目的関数は最大化
- 制約条件は 「左辺 ≤ 右辺」
- 各変数は非負
すべてのLPは標準形に変形できます（最小化なら符号反転、等式制約なら ≤ と ≥ の2本に分割、自由変数なら $x = x^+ - x^-$ に分解、など）。
実行不能・非有界の例
LPには必ず最適解があるわけではなく、以下の2つの最適解の存在しない状況が発生します。
実行不能（Infeasible）
制約条件を満たす解（実行可能解）がひとつも存在しない状態です。
\text{maximize} \quad 3x_1 + 4x_2 + x_3
\text{subject to} \quad -x_1 + x_2 + x_3 = -5,\quad 2x_1 + x_2 - x_3 = 7,\quad x_1, x_2, x_3 \geq 0
1本目を2倍して2本目を足すと $3x_2 + x_3 = -3$ になりますが、$x_2, x_3 \geq 0$ なので左辺は非負。矛盾しているので解なしとなります。
非有界（Unbounded）
実行可能解は存在するものの、目的関数を無限に改善できる状態です。
\text{maximize} \quad x_1 + x_2 \quad \text{s.t.} \quad x_1 + 3x_2 \geq 3,\ 3x_1 + x_2 \geq 3,\ x_1, x_2 \geq 0
この問題では $x_1, x_2$ をどちらも好きなだけ大きくできるので目的関数値が $\infty$ になります。
実務では「実行不能になった！」「非有界になった！」というケースに遭遇することがあるので、それぞれの意味を押さえておくと良いかと思います。
実行可能領域は凸多面体になる
ここからが本記事のメインです。LPの実行可能領域（制約条件を満たす点の集合）は、必ず凸多面体（Convex Polyhedron） になります。
「制約条件 ≤ b」というのは1枚の超平面より下側の半空間を表します。LPでは
- $m$ 本の不等式制約 → $m$ 枚の超平面
- $n$ 個の非負制約 → $n$ 枚の超平面（座標軸）
合計で $m + n$ 枚の超平面に囲まれた領域が実行可能領域になります。
具体例
\text{maximize} \quad x_1 + 2x_2
\text{subject to} \quad x_1 + x_2 \leq 6,\quad x_1 + 3x_2 \leq 12,\quad 2x_1 + x_2 \leq 10,\quad x_1, x_2 \geq 0
実行可能領域を描くと以下のような五角形になります。
参考に上記図のソースコードです。
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Polygon
plt.rcParams['font.family'] = 'Yu Gothic'
fig, ax = plt.subplots(figsize=(7, 6))
# 実行可能領域の頂点（手計算で求めた）
vertices = np.array([
[0, 0], # (a)
[5, 0], # (b)
[4, 2], # (d)
[3, 3], # (e) 最適解
[0, 4], # (c)
])
poly = Polygon(vertices, alpha=0.3, facecolor='#3498db', edgecolor='#2980b9', linewidth=2)
ax.add_patch(poly)
# 制約条件の直線
x = np.linspace(-1, 7, 100)
ax.plot(x, 6 - x, label=r'$x_1 + x_2 = 6$', color='#7f8c8d')
ax.plot(x, (12-x)/3, label=r'$x_1 + 3x_2 = 12$', color='#7f8c8d')
ax.plot(x, 10 - 2*x, label=r'$2x_1 + x_2 = 10$', color='#7f8c8d')
# 頂点と最適解
labels = ['(a) (0,0)', '(b) (5,0)', '(d) (4,2)', '(e) (3,3) 最適', '(c) (0,4)']
for (vx, vy), label in zip(vertices, labels):
color = '#e74c3c' if '最適' in label else '#27ae60'
ax.scatter(vx, vy, c=color, s=120, zorder=5, edgecolors='white', linewidths=2)
ax.annotate(label, (vx, vy), xytext=(8, 8), textcoords='offset points', fontsize=10)
# 目的関数の等高線
for z in [3, 6, 9]:
ax.plot(x, (z - x)/2, '--', color='#e74c3c', alpha=0.4, linewidth=1)
ax.annotate('最大化', xy=(4.5, 3.0), xytext=(5.5, 4.5),
arrowprops=dict(arrowstyle='<-', color='#e74c3c'),
color='#e74c3c', fontsize=12)
ax.set_xlim(-0.5, 7); ax.set_ylim(-0.5, 5.5)
ax.set_xlabel('$x_1$', fontsize=12); ax.set_ylabel('$x_2$', fontsize=12)
ax.set_title('LP の実行可能領域（凸多面体）と最適解', fontsize=13)
ax.legend(loc='upper right', fontsize=9)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('lp_feasible_region.png', dpi=150)
頂点の座標：(0,0), (5,0), (4,2), (3,3), (0,4)
目的関数 $x_1 + 2x_2$ を最大化するため、等高線（赤い破線）を右上に押し上げていきます。実行可能領域の境界に接するギリギリの位置が最適解で、この問題では頂点 (3, 3) が最適解（目的関数値 9）になります。
なぜ最適解は頂点にあるのか
これがLPの最も重要な性質です。
線形計画問題の最適解は、実行可能領域（凸多面体）の頂点のいずれかにある。
直感的には、目的関数の等高線を「動かしながら実行可能領域に押し付ける」と、最後に接するのは凸多面体の頂点になるからです（辺や面で接するケースもありますが、その場合でも頂点に最適解が存在します）。
ただし、実行可能領域が非有界の場合には頂点を持たない凸多面体になることもある点には注意が必要です（例：$\max{x_1 + x_2 \mid x_1 + x_2 \leq 1}$）。
頂点全列挙は無理ゲー
「じゃあ頂点を全部調べればいいじゃん！」と思いますよね。実はこれが現実的に無理なのです。
各頂点は「$m + n$ 本の超平面のうち $n$ 枚が交わる点」として特徴付けられます。よって頂点の候補数は組み合わせ
\binom{m + n}{n} = \frac{(m + n)!}{m!\,n!}
の数だけあります。ここで、具体的な数を見てみます。
| 制約数 $m$ | 変数数 $n$ | 頂点候補数 $\binom{m+n}{n}$ |
|---|---|---|
| 5 | 5 | 252 |
| 10 | 10 | 184,756 |
| 20 | 20 | 約 1.38 × 10¹¹ |
| 50 | 50 | 約 1.01 × 10²⁹ |
| 100 | 100 | 約 9.05 × 10⁵⁸ |
100変数100制約の小さな問題でも、頂点候補数がとんでもない数です。。。
実務的なLPは数千〜数百万変数になることもあるので、全列挙は完全に不可能です。
だから単体法が必要
頂点全列挙は無理だが、最適解は頂点にあることは分かっている。
このギャップを埋めるのが 単体法（Simplex Method） です。
単体法のアイデア：
① ある頂点（実行可能解）から出発
② 目的関数が改善する隣接頂点へ移動
③ もう改善できなくなったら最適解
全頂点を見るのではなく、「目的関数が改善する隣接頂点」だけを辿って最適解まで到達する戦略です。
凸多面体の構造（凸性）のおかげで、「目的関数を改善する隣接頂点がなければ、現在の頂点が大域最適解」という性質が保証されます。これがLPの最大の魅力かと思います。
PuLPで実際に解いてみる
紹介した例題をPuLPで解いてみます。
import pulp
prob = pulp.LpProblem("LP_example", pulp.LpMaximize)
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)
prob += x1 + 2*x2 # 目的関数
prob += x1 + x2 <= 6 # 制約1
prob += x1 + 3*x2 <= 12 # 制約2
prob += 2*x1 + x2 <= 10 # 制約3
prob.solve(pulp.PULP_CBC_CMD(msg=0))
print(f"x1 = {pulp.value(x1):.2f}")
print(f"x2 = {pulp.value(x2):.2f}")
print(f"目的関数値 = {pulp.value(prob.objective):.2f}")
print(f"Status: {pulp.LpStatus[prob.status]}")
x1 = 3.00
x2 = 3.00
目的関数値 = 9.00
Status: Optimal
予想通り頂点 (3, 3) で最大値 9 となりました。PuLPのデフォルトソルバーCBCは内部で単体法を実行していて、ちゃんと最適頂点に辿り着いてくれています。
まとめ
- 線形計画問題（LP）は目的関数と制約条件がすべて線形な最適化問題
- 標準形は最適化問題定義の統一的な書き方
- 実行可能領域は凸多面体になり、最適解は頂点のいずれかにある
- 頂点候補数は $\binom{m+n}{n}$ で爆発するので全列挙は不可能
- だから「改善する隣接頂点へ移動を繰り返す」単体法が必要