キーワード
» 2009年01月13日 00時00分 公開

情報マネジメント用語辞典:線形計画法(せんけいけいかくほう)

LP / linear programming / 線型計画法 / ライナープログラミング

[@IT情報マネジメント編集部,@IT]

 いくつかの1次式で表わされる制約条件を満たし、かつ1次式で表わされる目的関数を最適化(最大化・最小化)する解を求める数学的手法のこと。主に限られた資源を最大限に利用したい場合、あるいは最小の費用で目的を達成したいような場合、すなわち最適資源配分問題に用いられる。

 経済主体(もしくは経済以外の目的を持つ行動主体)は、一般にさまざまな制約条件の下に利益や効果を最大にしたり、費用や時間を最小にしたりすることを目指す。このとき、各種の制約条件(設備能力や原材料、時間、人員、工程、資金など)の相互関係を1群の1次不等式・等式に、活動目的(利益や生産量、費用や生産要素の消費量など)の達成度を評価する関数を1次式に定式化し、この数式モデル(線形計画モデル)を解くことにより、操作可能な資源や要素の量(変数)についての最適な配分を導き出す計算技術が線形計画法である。

 線形計画法の“線形”とは、条件式と目的関数がすべて1次式であることを意味する。1次式はグラフに描くと直線、すなわち線形(リニア)になるもので、変数(例えば投入量と産出量)が比例・反比例の関係(比例性)にあることを仮定している。ほかにも線形計画法では変数(各活動の結果)は独立で交互作用は加法的であること(加法性)、変数は連続的値となること(連続性)、変数は負の値を取らないこと(非負性)などを前提としている。

 解法には大別して単体法(シンプレックス法)と内点法がある。前者は幾何学的イメージで考えた場合に実行可能領域を示す凸多面体を、原点から稜線に沿って最適解となる頂点に移動する代数的方法、後者は凸多面体の内部から中心曲線を辿って最大解となる頂点に到達する解析的方法である。

 初学者向けの教科書などでは縦横2軸の図を用いて手計算する方法が紹介されているが、これは変数が2つである場合にのみ通用する方法であって、実務的な線形計画問題の場合はコンピュータの利用が不可欠である。

 その応用分野は、生産計画、原料購入計画、混合問題、人員配置、輸送計画、在庫計画、スケジューリング、ネットワークフロー、クラス編成、資産運用、エネルギー計画、サプライチェーン最適化など、幅広い分野に及んでいる。線形計画法が生まれてすぐの1950年代から石油業界や鉄鋼業界での応用事例が多数報告され、これら業界における早期のコンピュータ導入を誘引した。

 線形計画法の創始者は、米国人応用数学者のジョージ・B・ダンツィク(George Bernard Dantzig)である。彼は1947年、米空軍の物資補給・要員育成の計画(プログラム)に関する研究プロジェクト――のちにSCOOP(Scientific Computation of Optimum Programs)と名付けられた――にリーダーの1人として参加した。ここで経済学の投入産出モデル(レオンチェフモデル)を線形計画モデルに一般化し、その解法として単体法を提案した。

 なお当初、ダンツィクは「Programming in a Linear Structure」(線形構造における計画)と呼んでいたが、経済学者のチャリング・C・クープマンス(Tjalling Charles Koopmans)に示唆されて「Linear Programming」という名称になったという。

 ダンツィクの単体法によって生み出された線形計画法は、すぐに経済学者や応用数学者、政府機関の関心を集め、理論や応用、計算手法、計算用プログラムなどでさまざまな拡張が行われた。解法では1984年に、インド出身の数学者であるナレンドラ・カーマーカー(Narendra Karmarkar)が新たな内点法を発表して、以後しばらくの間、単体法と内点法のアルゴリズム競争が展開された。これら数学的解法とソフトウェア・アルゴリズムの進化、そしてコンピュータ・ハードウェアの高速化によって、当初は計算不能と考えられた大型の線形計画問題も、今日ではパソコンで扱えるようになっている。

 線形計画法のソフトウェアは数多くがあるが、商用製品としては「ILOG CPLEX」(仏アイログ)、「Xpress-MP」(米フェアアイザック)※が有名である。小規模の問題ならば、Microsoft Excelのソルバー機能で解くことができる。


※現在、両製品とも線形計画法以外に数理計画法の各種解法に対応している。


参考文献

▼『リニアー・プログラミングによる経営計画』 河部守弘=著/産業図書/1956年8月

▼『線型計画法入門』 森口繁一=著/日本科学技術連盟/1957年8月

▼『線型計画法とその周辺』 ジョージ・B・ダンツィーク=著/小山昭雄=訳/ホルト・サウンンダース・ジャパン/1983年10月(『Linear Programming and Extensions』の邦訳)

▼『オペレーションズ・リサーチ読本〈増補版〉』 刀根薫=著/日本評論社/1991年3月

▼『カーマーカー特許とソフトウェア――数学は特許になるか』 今野浩=著/中央公論社・中公新書/1995年12月

▼『内点法』 小島政和、土谷隆、水野眞治、矢部博=著/朝倉書店/2001年9月

▼『役に立つ一次式――整数計画法「気まぐれな王女」の50年』 今野浩=著/日本評論社/2005年12月


Copyright © ITmedia, Inc. All Rights Reserved.

注目のテーマ