日本大百科全書(ニッポニカ) 「リニア・プログラミング」の意味・わかりやすい解説
リニア・プログラミング
りにあぷろぐらみんぐ
linear programming
一次の不等式または一次式で表される制約条件のもとで、一次式で表される目的関数あるいは評価関数を最大（または最小）にする最適化技法の一つ。一次式はグラフにすると直線（線形）になるので、線形計画法ともいう。略称LP。たとえば、ある工場で2種類の製品（AとB）を2台の機械（M1とM2）を使って生産する場合に、最大の利益（z）をあげるには各製品をどのくらい生産するかを決定する問題は、次の例で示すように、リニア・プログラミングの問題として定式化できる。いま、に示すような各製品を生産するために必要な時間および制約と利益が与えられている場合を考える。製品Aの生産量をxA、また製品Bの生産量をxBとすれば、リニア・プログラミングの問題は
という制約条件のもとで、次に示す目的関数
z=2xA+xB (3)
を最大になるような決定変数xAとxBを求めることである。ここで、式(2)を非負条件という。
ここでのLP問題のように、決定変数が2個（xA,xB）の場合には、平面上に式(1)のグラフを書くことができ、のようになる。この図で、斜線部分が制約条件(1)と非負条件(2)を満足するxA、xBの範囲を表し、実行可能域とよんでいる。LP問題の実行可能域は、一般にのような凸多角形の内部とその辺上になる。したがって、実行可能域内の点（xA,xB）で目的関数(3)を最大にするのは、点BすなわちxA=24,xB=48であり、その利益は96万円となる。このように、線形計画問題では、目的関数値は凸多面体の端点で最大または最小値をとることが知られている。このようなLP問題を解くおもな手法としては、1950年代の後半に、ダンツィグGeorge B. Danzig（1914―2005）が開発したシンプレックス法（単体法ともいう）や改訂シンプレックス法などがある。これらの手法のコンピュータ・プログラムが開発されて以来、リニア・プログラミングは広く生産管理、経営計画、在庫管理、石油の混合問題、栄養問題などによく使用されるようになった。
［玄 光男］
『玄光男・井田憲一著『BASICによる線形計画』（1988・共立出版）』▽『小山昭雄著『線形計画入門』（日経文庫）』
