線型計画法

線型計画法︵せんけいけいかくほう、英語: linear programming、略称: LP︶は、数理計画法において、いくつかの1次不等式および1次等式を満たす変数の値の中で、ある1次式を最大化または最小化する値を求める方法である。線形計画法の対象となる最適化問題を線型計画問題という。

概要

線型計画法はいくつかの理由で最適化の重要な分野である。オペレーションズリサーチの多くの実際的な問題は線型計画問題として記述できる。ある特殊なケースのネットワークフロー問題︵英語版︶や多品種流問題︵英語版︶といった線型計画問題はこれらを解くために特別なアルゴリズムを考案するに値するほど重要だと考えられている。他のタイプの最適化問題に使われる多くのアルゴリズムは線型計画法を解くことで代用できる。歴史的には、線型計画法の考えによって双対性、分割、凸解析の重要性や一般化のような最適化の主要な理論を引き起こした。

線型計画問題

数学的には線型計画問題は、目的関数と制約条件︵英語版︶がすべて線型の最適化問題である。 2変数

x_{1}(\geq 0)

x_{1}(\geq 0)

、

x_{2}(\geq 0)

x_{2}(\geq 0)

の場合、与えられた定係数

a_{ij}\

a_{ij}\

と

b_{i}\

b_{i}\

、

c_{j}\

c_{j}\

、および不等式制約

{\begin{matrix}a_{11}x_{1}+a_{12}x_{2}\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}\leq b_{2}\\\end{matrix}}

{\begin{matrix}a_{11}x_{1}+a_{12}x_{2}\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}\leq b_{2}\\\end{matrix}}

の下、次式

c_{1}x_{1}+c_{2}x_{2}\

c_{1}x_{1}+c_{2}x_{2}\

の最大値およびそれを実現する

x_{1}\

x_{1}\

と

x_{2}\

x_{2}\

を求める問題が、典型的な線型計画問題である。 3変数

x_{1}\

x_{1}\

、

x_{2}\

x_{2}\

、

x_{3}\

x_{3}\

の場合、3次元座標空間上に描かれた立体図形を切るような平面のうち、

x_{3}\

x_{3}\

切片︵平面と

x_{3}\

x_{3}\

軸との交点︶の値が最大あるいは最小となるような平面を求めることになる。最適解の取り得る範囲を整数に限定した線型計画法は、整数計画法と呼ばれる。

線型計画問題の例

線型計画問題の例として以下の問題をとりあげる。農業を営む人が、小麦と大麦のための

A\

A\

平方キロメートルの農地を持っていると仮定する。農家は限度

F\

F\

で肥料、限度

P\

P\

で殺虫剤を使用することができる。これらはそれぞれ単位面積あたり小麦が

(F_{1},P_{1})\

(F_{1},P_{1})\

、大麦が

(F_{2},P_{2})\

(F_{2},P_{2})\

を必要とする。小麦の販売価格を

S_{1}\

S_{1}\

、大麦の販売価格を

S_{2}\

S_{2}\

、小麦を育てる領域を

x_{1}\

x_{1}\

、大麦を育てる領域を

x_{2}\

x_{2}\

とすると、線型計画問題として大麦と小麦をどれだけ育てればいいかを表すことができる。

最大化：	$S_{1}x_{1}+S_{2}x_{2}\$	(利益の最大化)
制約条件：	$x_{1}+x_{2}\leq A$	(耕作地の制約)
	$F_{1}x_{1}+F_{2}x_{2}\leq F$	(肥料の制約)
	$P_{1}x_{1}+P_{2}x_{2}\leq P$	(殺虫剤の制約)
	$x_{1}\geq 0,\,x_{2}\geq 0$	(非負制約)

理論

幾何学的には線型︵不︶等式制約は実行可能領域︵英語版︶と呼ばれる凸多面体を定義する。目的関数も線型なので、全ての局所最適解はおのずと︵大域的︶最適解になる。線型な目的関数であることによって、必然的に最適解は実行可能領域の境界上のみに現れる。最適解が見つからない状況が2つある。1つは互いに矛盾のある制約︵例えば、

x\geq 2

x\geq 2

と

x\leq 1

x\leq 1

︶ならば実行可能領域は空になり、最適解は存在しえない。最適解が得られないのでこの場合はLPは実行不能と呼ばれる。もう1つの状況は、多面体が目的関数の向きに境界を持たない場合︵例‥最大化‥

x_{1}+3x_{2}\

x_{1}+3x_{2}\

制約‥

x_{1}\geq 0,x_{2}\geq 0,x_{1}+x_{2}\geq 10

x_{1}\geq 0,x_{2}\geq 0,x_{1}+x_{2}\geq 10

︶である。この場合、目的関数はいくらでも大きい値を取り得る。これらの2つの正常ではない条件︵これらは多くの場合は上限を設けるなど問題の不可欠な制約によって除外される︶がなければ、最適解は必ず多面体の頂点︵正確には最小次元面︶にある。しかしながら最適解は唯一とは限らない。多面体の辺や面が最適解の集合となる事があるし、最適解が多面体の全体となる︵目的関数が一律に0に等しいときに現れる︶ことすらある。

アルゴリズム

詳細は「シンプレックス法」、「内点法」、および「カーマーカーのアルゴリズム」を参照

シンプレックス法︵単体法︶は最適解が多面体の頂点に現れることを利用し、最適解に達するまで多面体の辺をたどってより高い目的関数の値を次々にたどることで線型計画問題を解く。このアルゴリズムは実際にかなり能率のいいもので、巡回していないか︵巡回してしまうと最適解に到達することができない︶に注意を払えば︵大域的︶最適解を見つけることが保証される。シンプレックス法は、用いるピボット規則により性能が左右される。有限回のピボットで終了することが保証されている規則として、Blandの提案した最小添字規則が知られている。Dantzigの提案したピボット規則は問題の規模にたいして指数時間かかる問題例があることが知られている。現在のところ、線型計画問題を多項式時間で解くピボット規則の存在性は未解決問題である。線型計画問題を最悪の場合でも多項式時間で解くアルゴリズムがレオニード・カチヤン︵英語版︶によって1979年に初めて提案された。そのアルゴリズムはナウム・ショール︵英語版︶の非線型最適化の楕円体法︵英語版︶︵これはアルカディ・ネミロフスキー︵英語版︶とDmitri Yudinが一般化して、2003年にジョン・フォン・ノイマン理論賞を受賞した凸最適化の楕円体法︶をベースにしていた。しかしカチヤンのアルゴリズムの実用性は期待はずれで、一般にシンプレックス法の方が効率的である。このアルゴリズムの主な重要性は、アルゴリズムの多項式性を示す証明手段を提供した事と、内点法の研究を促進したことにある。実行可能領域の辺のみを探索するシンプレックス法に対し、内点法は実行可能領域の内部を動くアルゴリズムとなっている。 1984年にナレンドラ・カーマーカーはカーマーカー法︵射影変換法︶を提案した。この方法は理論上でも実際でもいい結果の得られる最初のアルゴリズムで、最悪の場合でも多項式時間で解くことができ、実際の問題ではシンプレックス法と比べてかなり効率的に解くことができることが示されている。それ以降は多くの内点法が提案されて研究されている。よく使われる内点法にはMehrotraの予測子・修正子法と小島・水野・吉瀬の主双対内点法がある。すぐれた実装のシンプレックス法と内点法の効率は、線型計画法の応用としてはっきりした優劣は無いというのが現在の見解である。しかしながら、目的関数や右辺項が僅かに変動した問題の最適化を繰り返し行う際は、シンプレックス法が優れている。 LPのソルバーは、輸送におけるネットワークフロー問題︵線型計画問題として定式化できる︶のような産業のさまざまな問題の最適化のために広く普及している。

参考文献

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.
水野眞治, 『シンプレックス法の巡回とその回避』
松井知己, 『Bland の最小添字規則の有限性 -単体法の非巡回ピヴォット規則- 』
藤重悟：「線形計画問題の強多項式解法について」,オベレーションズ・リサーチ，1987年1月号，pp.14-18.
室田一雄、杉原正顕：「線形代数II」、東京大学工学教程、丸善出版（2013）.

概要

線型計画問題

線型計画問題の例

理論

アルゴリズム

関連項目

参考文献