🗺️ このノートは 第8章「ネットワーク最適化」のハブ です。
第8章 ── ネットワーク最適化
グラフ（ノードと枝）の上で「最短・最大・最小費用」を求める問題群。これらは整数計画（整数計画と組合せ最適化 章目次）の特殊例だが、制約行列が 全ユニモジュラなので、LP 緩和を解くだけで整数最適が出る ── 整数なのに多項式時間で解ける、最適化の美しい一角。双対性（線形計画の双対性）が最大流・最小カットとして幾何的に現れる。
トピック一覧
- 最短経路問題（ダイクストラ・ベルマンフォード） — 最短路・緩和・負辺（基礎）
- 最大流・最小カット — フロー・カット・双対の好例（標準）
- 最小費用流・輸送問題 — 需給バランス・輸送・最小費用（標準）
- 割当問題（ハンガリアン法） — 二部マッチング・全ユニモジュラ（標準）
この章の位置づけ
- 全ユニモジュラ性（整数計画とは・LP緩和 のギャップ0）が「整数なのに易しい」を生む
- 最大流・最小カット（最大流・最小カット）は LP 双対（線形計画の双対性）の最も美しい実例
- 最短路（最短経路問題（ダイクストラ・ベルマンフォード））は動的計画法（動的計画法とベルマンの原理）の応用
- 適用（配送・スケジューリング）は operations へ wikilink（スケジューリング・配送のモデル化）
関連章
- 前章：不確実性下の最適化 章目次 次章：応用とモデリング 章目次
- 全体ハブ：数理最適化・OR 全体目次