線形計画法（せんけいけいかくほう）
最終更新：2026/4/25
線形計画法は、制約条件のもとで線形な目的関数を最大化または最小化する問題を解く数学的最適化手法である。
別名・同義語 線形最適化リニアプログラミング
ポイント
線形計画法は、資源配分や生産計画など、現実世界の様々な問題を効率的に解決するために広く用いられている。シンプレックス法が代表的な解法である。
線形計画法の概要
線形計画法（Linear Programming, LP）は、オペレーションズ・リサーチ（OR）の分野で発展した、最も基本的な最適化手法の一つです。目的関数と制約条件がすべて線形である場合に適用でき、資源の効率的な配分や、生産計画、輸送問題など、幅広い分野で利用されています。
歴史的背景
線形計画法の基礎は、19世紀に数学者ジョゼフ・ルイ・ラグランジュによって築かれました。しかし、実用的な手法として確立されたのは、1947年にジョージ・B・ダンツィグがシンプレックス法を開発したことがきっかけです。シンプレックス法は、線形計画問題を効率的に解くことができるアルゴリズムであり、その後のORの発展に大きく貢献しました。
基本的な構成要素
線形計画問題は、以下の3つの要素で構成されます。
- 目的関数: 最大化または最小化したい量を示す線形関数。
- 制約条件: 問題を解決する上で満たすべき線形不等式または線形等式。
- 変数: 決定すべき変数を表す。
代表的な解法
線形計画問題を解くための代表的な解法としては、以下のものがあります。
- シンプレックス法: 最も一般的な解法であり、効率的に最適解を探索できます。
- 内点法: シンプレックス法に比べて計算量が大きい場合がありますが、大規模な問題に対して有効です。
応用例
線形計画法は、以下のような様々な分野で応用されています。