線形計画法（最適化問題）

Q: 線形計画法（最適化問題）とは何ですか？

線形計画問題（Linear Programming）とは、複数の変数 x, y, \ldots に関する一次不等式の制約条件のもとで、一次式である目的関数を最大化（または最小化）する問題である。標準形は次のように書ける。 \text{maximize} \quad z = c_1 x + c_2 y \qquad \text{subject to} \quad \begin{cases} a_{i1} x + a_{i2} y \le b_i & (i = 1, \ldots, m) \\ x \ge 0, \; y \ge 0 \end{cases} これらの不等式（半平面）すべての共通部分を「実行可能領域（feasible region）」と呼び、各半平面は凸集合であるためその共通部分である実行可能領域も必ず凸多角形（凸多面体）になる。

Q: 線形計画法（最適化問題）は社会やプログラミングでどのように使われていますか？

配送ルート・資源配分の最適化（線形計画ソルバーの基本ロジック）: 工場の生産計画や配送トラックの積載最適化など「限られた資源（時間・材料・積載量）の中で利益を最大化する」実務問題の多くは線形計画問題として定式化できる。ここでは2変数の小規模なLP問題を、実行可能領域の頂点をすべて列挙してから目的関数値を比較する素朴な方法で解くTypeScript実装を示す（大規模問題では単体法や内点法を使う）。

一次不等式が作る実行可能領域から、目的関数を最大化する頂点を探す最適化理論

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 線形計画法（LP）は、いくつかの一次不等式（制約条件）を満たす領域の中で、一次式（目的関数）を最大化・最小化する変数の値を求める最適化手法
2: 制約条件が作る「実行可能領域」は必ず凸多角形（凸多面体）になり、線形の目的関数の最適解は領域の内部ではなく必ずどこかの「頂点」で達成される（頂点定理）
3: この頂点を効率よく巡って最適解を見つけるアルゴリズムが単体法（シンプレックス法）であり、配送ルートの最適化や工場の生産計画など資源配分問題に広く使われている

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

線形計画法（LP）は、いくつかの一次不等式（制約条件）を満たす領域の中で、一次式（目的関数）を最大化・最小化する変数の値を求める最適化手法

身につく武器・思考力

制約条件が作る「実行可能領域」は必ず凸多角形（凸多面体）になり、線形の目的関数の最適解は領域の内部ではなく必ずどこかの「頂点」で達成される（頂点定理）

実社会・ITでの活躍現場

•配送ルート・資源配分の最適化（線形計画ソルバーの基本ロジック）
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

目的関数 $z = c_1 x + c_2 y$ の係数 $c_1, c_2$ をスライダーで変えてみよう。実行可能領域（水色の多角形）の中で、目的関数の値が最大になる頂点が自動的にハイライトされ、その頂点を通る目的関数の等高線（点線）が表示される。係数を変えるたびに「勝つ頂点」が切り替わる様子を確認できる。

係数 c₁ = 4.0係数 c₂ = 3.0

目的関数: $z = c_1 x + c_2 y$ = 4.0x + 3.0y

最適頂点 (x, y) = (4, 3) 最大値 z = 25.0

制約条件: x ≥ 0, y ≥ 0, x + 2y ≤ 10, 3x + y ≤ 15（水色の実行可能領域）

↑ 赤い矢印は目的関数の係数ベクトル (c₁, c₂) の向き。赤い点線はその向きに垂直な等高線で、最適頂点（赤い点）を通っている。 c₁, c₂ を変えると「勝つ頂点」が切り替わる様子を確認しよう。

直感チェック！ミニクイズ

実行可能領域が凸多角形であるとき、一次式の目的関数 $z = c_1 x + c_2 y$ の最大値はどこで達成されるか？

Layer 2 — 定義・受験・証明

定義

線形計画問題（Linear Programming）とは、複数の変数 $x, y, \ldots$ に関する一次不等式の制約条件のもとで、一次式である目的関数を最大化（または最小化）する問題である。標準形は次のように書ける。

\text{maximize} \quad z = c_1 x + c_2 y \qquad \text{subject to} \quad \begin{cases} a_{i1} x + a_{i2} y \le b_i & (i = 1, \ldots, m) \\ x \ge 0, \; y \ge 0 \end{cases}

これらの不等式（半平面）すべての共通部分を「実行可能領域（feasible region）」と呼び、各半平面は凸集合であるためその共通部分である実行可能領域も必ず凸多角形（凸多面体）になる。

公式・数理モデル

z = c_1 x + c_2 y, \quad \text{各半平面 } a_{i1}x + a_{i2}y \le b_i \text{ の共通部分は凸多角形}, \quad z^* = \max_{(x,y) \in \text{頂点集合}} z(x,y)

証明・導出

頂点定理（Extreme Point Theorem）の証明（背理法）：実行可能領域 $S$ は凸多角形であり、目的関数 $z(x,y) = c_1 x + c_2 y$ は線形（アフィン）関数である。

仮に最適解 $\mathbf{p}^*$ が $S$ の頂点ではなく、内部または辺の途中の点であったとする。凸多角形の性質より、 $\mathbf{p}^*$ はある2つの頂点 $\mathbf{v}_1, \mathbf{v}_2$ （あるいはより一般に頂点の凸結合）を用いて

\mathbf{p}^* = \lambda \mathbf{v}_1 + (1-\lambda)\mathbf{v}_2, \qquad 0 < \lambda < 1

と表せる。 $z$ は線形なので

z(\mathbf{p}^*) = \lambda z(\mathbf{v}_1) + (1-\lambda) z(\mathbf{v}_2)

これは $z(\mathbf{v}_1)$ と $z(\mathbf{v}_2)$ の間（加重平均）の値であるため、 $z(\mathbf{p}^*) \le \max(z(\mathbf{v}_1), z(\mathbf{v}_2))$ が成り立つ。すなわち $\mathbf{v}_1$ か $\mathbf{v}_2$ のどちらかは $\mathbf{p}^*$ 以上の値を持つ頂点となり、 $\mathbf{p}^*$ が「内部点で唯一の最適解」であるという仮定に矛盾する。したがって、線形の目的関数の最大値は必ずいずれかの頂点で達成される。

押さえておきたいポイント

実行可能領域は複数の半平面（一次不等式）の共通部分であり、凸集合どうしの共通部分は必ず凸集合になる
目的関数の等高線（ $z=$ 一定の直線）は係数 $c_1, c_2$ によって傾きが決まり、この直線を平行移動させて領域から最後に離れる点が最適頂点である
単体法（シンプレックス法）は、この性質を利用して頂点から隣接する頂点へと目的関数値が改善する方向にだけ移動を繰り返し、効率的に最適解へ到達するアルゴリズム
変数や制約が数百万に達する大規模な線形計画問題は、内点法（interior-point method）など別のアルゴリズムで解かれることが多い

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

配送ルート・資源配分の最適化（線形計画ソルバーの基本ロジック）

工場の生産計画や配送トラックの積載最適化など「限られた資源（時間・材料・積載量）の中で利益を最大化する」実務問題の多くは線形計画問題として定式化できる。ここでは2変数の小規模なLP問題を、実行可能領域の頂点をすべて列挙してから目的関数値を比較する素朴な方法で解くTypeScript実装を示す（大規模問題では単体法や内点法を使う）。

1type Point = { x: number; y: number };
2type Constraint = { a: number; b: number; c: number }; // a*x + b*y <= c
3
4// 2本の直線 a1*x + b1*y = c1 と a2*x + b2*y = c2 の交点を求める
5function intersect(l1: Constraint, l2: Constraint): Point | null {
6  const det = l1.a * l2.b - l2.a * l1.b;
7  if (Math.abs(det) < 1e-9) return null; // 平行で交点なし
8  return {
9    x: (l1.c * l2.b - l2.c * l1.b) / det,
10    y: (l1.a * l2.c - l2.a * l1.c) / det,
11  };
12}
13
14// 候補点がすべての制約を満たすか（実行可能かどうか）を判定
15function isFeasible(p: Point, constraints: Constraint[]): boolean {
16  return constraints.every((c) => c.a * p.x + c.b * p.y <= c.c + 1e-6);
17}
18
19// 実行可能領域の頂点をすべて列挙し、目的関数を最大化する頂点を返す
20function solveLP(
21  constraints: Constraint[], // x>=0, y>=0 も Constraint として含める
22  objective: (p: Point) => number
23): { optimal: Point; value: number } {
24  const vertices: Point[] = [];
25
26  for (let i = 0; i < constraints.length; i++) {
27    for (let j = i + 1; j < constraints.length; j++) {
28      const p = intersect(constraints[i], constraints[j]);
29      if (p && isFeasible(p, constraints)) vertices.push(p);
30    }
31  }
32
33  let best = vertices[0];
34  let bestValue = objective(best);
35  for (const v of vertices) {
36    const value = objective(v);
37    if (value > bestValue) {
38      best = v;
39      bestValue = value;
40    }
41  }
42  return { optimal: best, value: bestValue };
43}
44
45// 例: 配送計画で x=商品A個数, y=商品B個数、積載量と時間の制約下で利益を最大化
46const constraints: Constraint[] = [
47  { a: -1, b: 0, c: 0 },  // x >= 0 (-x <= 0 として Constraint 形式に変換)
48  { a: 0, b: -1, c: 0 },  // y >= 0 (-y <= 0 として Constraint 形式に変換)
49  { a: 1, b: 2, c: 10 },  // 積載量制約: x + 2y <= 10
50  { a: 3, b: 1, c: 15 },  // 稼働時間制約: 3x + y <= 15
51];
52const result = solveLP(constraints, (p) => 4 * p.x + 3 * p.y); // 利益 = 4x + 3y
53console.log(`最適点: (${result.optimal.x.toFixed(2)}, ${result.optimal.y.toFixed(2)}), 利益: ${result.value.toFixed(2)}`);