線形計画法【LP】 Linear Programming / リニアプログラミング

概要

線形計画法（LP）とは、様々な制約条件のもとで目的関数を最適化(最大化あるいは最小化)する解を求める数理計画法のうち、制約も目的関数もすべて一次式(一次不等式、一次等式)で表されるもの。

複数の変数の関係について、不等式で表される制約条件が複数与えられ、等式で与えられる目的関数があるとき、目的関数の値が最大あるいは最小となるような変数の値の組み合わせを求める。

制約条件は、例えば「x+2y<12」「2x+y<12」といった形で一次不等式の形で与えられ、目的関数は「x+y」のようにやはり一次式として表される。この例の場合、制約条件を満たすxとyの値の組み合わせの中で「x=4,y=4」という組み合わせの場合に目的関数の値が最大値である8を取る。

解が存在するような問題設定の場合、2変数ならば制約条件を満たす値が含まれる領域を平面に図示すると多角形（多変数の場合は凸多面体）となり、そのうちの頂点のいずれかが解となる。多変数や多条件の場合に効率良く解を探索する計算手順（アルゴリズム）にはシンプレックス法や内点法などがある。

線形計画法のうち、解を整数に限定したものを「整数計画法」という。条件や目的関数に線形（一次式）ではないものを含む手法は「非線形計画法」（NLP：Non-Linear Programming）という。現実世界では様々な制約の下で最大の効用を得る問題は多くあり、生産や輸送、人員配置の計画などに広く応用されている。

(2021.8.3更新)