コトバンクはYahoo!辞書と技術提携しています。

リニア・プログラミング

ブリタニカ国際大百科事典 小項目事典の解説

リニア・プログラミング

線形計画法」のページをご覧ください。

出典 ブリタニカ国際大百科事典 小項目事典ブリタニカ国際大百科事典 小項目事典について 情報

日本大百科全書(ニッポニカ)の解説

リニア・プログラミング
りにあぷろぐらみんぐ
linear programming

一次の不等式または一次式で表される制約条件のもとで、一次式で表される目的関数あるいは評価関数を最大(または最小)にする最適化技法の一つ。一次式はグラフにすると直線(線形)になるので、線形計画法ともいう。略称LP。たとえば、ある工場で2種類の製品(AとB)を2台の機械(M1とM2)を使って生産する場合に、最大の利益(z)をあげるには各製品をどのくらい生産するかを決定する問題は、次の例で示すように、リニア・プログラミングの問題として定式化できる。いま、に示すような各製品を生産するために必要な時間および制約と利益が与えられている場合を考える。製品Aの生産量をxA、また製品Bの生産量をxBとすれば、リニア・プログラミングの問題は

という制約条件のもとで、次に示す目的関数
  z=2xA+xB (3)
を最大になるような決定変数xAxBを求めることである。ここで、式(2)を非負条件という。
 ここでのLP問題のように、決定変数が2個(xA,xB)の場合には、平面上に式(1)のグラフを書くことができ、のようになる。この図で、斜線部分が制約条件(1)と非負条件(2)を満足するxAxBの範囲を表し、実行可能域とよんでいる。LP問題の実行可能域は、一般にのような凸多角形の内部とその辺上になる。したがって、実行可能域内の点(xA,xB)で目的関数(3)を最大にするのは、点BすなわちxA=24,xB=48であり、その利益は96万円となる。このように、線形計画問題では、目的関数値は凸多面体の端点で最大または最小値をとることが知られている。このようなLP問題を解くおもな手法としては、1950年代の後半に、G・B・ダンツィグGeorge B. Danzig(1914―2005)が開発したシンプレックス法(単体法ともいう)や改訂シンプレックス法などがある。これらの手法のコンピュータ・プログラムが開発されて以来、リニア・プログラミングは広く生産管理、経営計画、在庫管理、石油の混合問題、栄養問題などによく使用されるようになった。[玄 光男]
『小山昭雄著『線形計画入門』(日経文庫) ▽玄光男・井田憲一著『BASICによる線形計画』(1988・共立出版)』

出典 小学館 日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について 情報 | 凡例

リニア・プログラミングの関連キーワードクリティカル・パス・メソッドリニア・プログラミングメディア・ミックスカントロビチシステム工学最大・最小動的計画法管理会計活動分析

今日のキーワード

コペルニクス的転回

カントが自己の認識論上の立場を表わすのに用いた言葉。これまで,われわれの認識は対象に依拠すると考えられていたが,カントはこの考え方を逆転させて,対象の認識はわれわれの主観の構成によって初めて可能になる...

続きを読む

コトバンク for iPhone

コトバンク for Android