🗺️ このノートは 第2章「線形計画」のハブ です。
第2章 ── 線形計画（Linear Programming）
線形計画は「目的・制約がすべて線形」な最適化。凸であり多項式時間で解け、最適解は実行可能領域（凸多面体）の 頂点に現れる。この明快な構造が、シンプレックス法・双対性・感度分析という強力な理論を生む。線形計画の双対性は、ネットワーク最適化・整数計画・ゲーム理論まで波及する最適化の背骨。
トピック一覧
- 線形計画の標準形と幾何 — 標準形・実行可能領域＝凸多面体・頂点（基礎）
- シンプレックス法 — 基底解・ピボット・頂点間移動（標準）
- 線形計画の双対性 — 弱双対・強双対・相補性（発展）
- 感度分析 — 影の価格・係数変化・許容範囲（標準）
- 内点法入門 — バリア関数・中心パス・多項式時間（発展）
この章の位置づけ
- 標準形と頂点（線形計画の標準形と幾何）→ シンプレックス法（シンプレックス法）が頂点を渡り歩く理由になる
- 双対性（線形計画の双対性）は感度分析（感度分析）の影の価格に直結し、最大流・最小カット（最大流・最小カット）へ波及
- 適用は operations（生産・配分）・finance（資産配分）へ wikilink
関連章
- 前章：最適化の基礎 章目次 次章：整数計画と組合せ最適化 章目次
- 凸の一般論：凸最適化 章目次
- 全体ハブ：数理最適化・OR 全体目次