線型計画法

線形計画法とは

線形計画法（Linear Programming, LP）は、数理計画法の一分野であり、与えられた制約条件のもとで、ある目的関数を最大化または最小化する変数の値を求める手法です。ここで、制約条件と目的関数はすべて線形（一次式）で表されることが特徴です。線形計画法は、オペレーションズリサーチにおいて非常に重要な役割を果たしており、多くの現実的な問題を解決するために利用されています。

線形計画問題

線形計画問題は、目的関数と制約条件がすべて線形である最適化問題です。例えば、2つの変数 \(x_1\) と \(x_2\) があり、以下の制約条件と目的関数が与えられたとします。

制約条件:


a₁₁x₁ + a₁₂x₂ ≤ b₁
a₂₁x₁ + a₂₂x₂ ≤ b₂
x₁ ≥ 0, x₂ ≥ 0


目的関数:


c₁x₁ + c₂x₂ (最大化)


このとき、目的関数を最大化する \(x_1\) と \(x_2\) の値を求めるのが線形計画問題です。3変数以上の場合も同様に考えることができます。

線形計画法の重要性

線形計画法が重要視される理由としては、以下の点が挙げられます。

1. 現実的な問題への応用: オペレーションズリサーチにおける多くの現実的な問題が、線形計画問題として記述できます。
2. 特殊なケースの存在: ネットワークフロー問題や多品種流問題など、特定の線形計画問題は、専用のアルゴリズムを開発する価値があるほど重要です。
3. 他の最適化問題への応用: 他のタイプの最適化問題を解くために、線形計画法が利用されることがあります。
4. 理論的な発展への貢献: 線形計画法の研究は、双対性、分割、凸解析といった最適化の重要な理論を発展させるきっかけとなりました。

線形計画問題の例

例えば、農業を営む人が、小麦と大麦を栽培するために、限られた農地、肥料、殺虫剤をどのように配分すれば、利益を最大化できるかを考えます。この問題を線形計画問題としてモデル化し、最適な栽培面積を決定できます。

理論的背景

幾何学的には、線形不等式制約は実行可能領域と呼ばれる凸多面体を定義します。目的関数が線形であるため、すべての局所最適解は大域的最適解となります。また、最適解は実行可能領域の境界上に必ず存在します。ただし、制約条件が矛盾していたり、目的関数が無限に増加したりする場合は、最適解が存在しないこともあります。

線形計画法のアルゴリズム

線形計画問題を解くための代表的なアルゴリズムとしては、以下のものがあります。

1. シンプレックス法: 多面体の頂点をたどりながら、目的関数の値を改善していく方法です。効率的なアルゴリズムですが、最悪の場合には指数時間かかることがあります。
2. 内点法: 実行可能領域の内部を探索し、最適解に近づいていく方法です。多項式時間で解くことができ、実際の問題でもシンプレックス法と同等以上に効率的であることが多いです。カーマーカー法はその代表例です。

線形計画法の応用

線形計画法は、以下のような様々な分野で応用されています。

輸送問題
資源配分問題
生産計画問題
ポートフォリオ最適化

まとめ

線形計画法は、現実世界の問題を解決するための強力なツールです。その理論とアルゴリズムは、数理計画法の重要な基礎となっています。線形計画法の理解は、様々な分野での問題解決能力の向上に繋がります。

参考資料

Hodges, S. M. （1977年）, "A Model for Bond Portfolio Improvement," Journal of Financial and Quantitative Analysis, June 1977, pp.243-260.
Ronn, E. I. （1987年）, "A New Linear Programming Approach to Bond Portfolio Management," Journal of Financial and Quantitative Analysis, December 1987, pp. 439-466.
V. Chv'atal: Linear Programming, W. H. Freeman, New York, 1983.
G. B. Dantzig: Linear Programming and Extensions, Princeton University Press, Princeton, 1963.
Y. E. Nesterov and A. S. Nemirovskii: Interior-Point Polynomial Algorithms in Convex Programming, SIAM, Philadelphia, 1994.
A. Schrijver: Theory of Linear and Integer Programming, John Wiley and Sons, New York, 1986.
水野 眞治, 『シンプレックス法の巡回とその回避』, http://www.me.titech.ac.jp/~mizu_lab/text/PDF-LP/LP3A-simplex.pdf
松井 知己, 『Bland の最小添字規則の有限性 -単体法の非巡回ピヴォット規則- 』, http://tomomi.my.coocan.jp/text/bland7.pdf
藤重悟：「線形計画問題の強多項式解法について」,オベレーションズ・リサーチ，1987年1月号，pp.14-18.
室田一雄、杉原正顕：「線形代数II」、東京大学工学教程、丸善出版（2013）.

もう一度検索