ジャパンネット バンク 線形計画法

線形とは？

線形計画法はいくつかの理由で最適化の重要な分野である。オペレーションズリサーチの多くの実際的な問題は線形計画問題として記述できる。ある特殊なケースのネットワークフロー問題や多品種流問題といった線形計画問題はこれらを解くために特別なアルゴリズムを考案するに値するほど重要だと考えられている。他のタイプの最適化問題に使われる多くのアルゴリズムはLPを解くことで代用できる。歴史的には、線形計画法の考えによって双対性、分割、凸解析の重要性や一般化のような最適化の主要な理論を引き起こした。
3変数 、、 の場合、3次元座標空間上に描かれた立体図形を切るような平面のうち、 切片（平面と 軸との交点）の値が最大あるいは最小となるような平面を求めることになる。
線形計画問題の例として以下の問題をとりあげる。農業を営む人が、小麦と大麦のための平方キロメートルの農地を持っていると仮定する。農家は限度 で肥料、限度 で殺虫剤を使用することができる。これらはそれぞれ単位面積あたり小麦が 、大麦が を必要とする。小麦の販売価格を 、大麦の販売価格を 、小麦を育てる領域を 、大麦を育てる領域を とすると、線形計画問題として大麦と小麦をどれだけ育てればいいかを表すことができる。
幾何学的には線形(不）等式制約は実行可能領域と呼ばれる凸多面体を定義する。目的関数も線形なので、全ての局所最適解はおのずと（大域的）最適解になる。線形な目的関数であることによって、必然的に最適解は実行可能領域の境界上のみに現れる。
最適解が見つからない状況が2つある。1つは互いに矛盾のある制約（例えば、 と ）ならば実行可能領域は空になり、最適解は存在しえない。最適解が得られないのでこの場合はLPは実行不能と呼ばれる。
これらの2つの正常ではない条件（これらは多くの場合は上限を設けるなど問題の不可欠な制約によって除外される）がなければ、最適解は必ず多面体の頂点（正確には最小次元フェイス）にある。しかしながら最適解は唯一とは限らない。多面体の辺や面が最適解の集合となる事があるし、最適解が多面体の全体となる（目的関数が一律に0に等しいときに現れる）ことすらある。
シンプレックス法（単体法）は最適解が多面体の頂点に現れることを利用し、最適解に達するまで多面体の辺をたどってより高い目的関数の値を次々にたどることで線形計画問題を解く。このアルゴリズムは実際にかなり能率のいいもので、巡回していないか（巡回してしまうと最適解に到達することができない）に注意を払えば（大域的）最適解を見つけることが保証される。シンプレックス法は、用いるピボット規則により性能が左右されるが、Dantzigの提案したピボット規則は問題の規模にたいして指数時間かかる問題例があることが知られている。現在のところ、線形計画問題を多項式時間で解くピボット規則の存在性は未解決問題である。
しかしKhachiyanのアルゴリズムの実用性は期待はずれで、一般にシンプレックス法の方が効率的である。このアルゴリズムの主な重要性は、アルゴリズムの多項式性を示す証明手段を提供した事と、内点法の研究を促進したことにある。実行可能領域の辺のみを探索するシンプレックス法に対し、内点法は実行可能領域の内部を動くアルゴリズムとなっている。
1984年にN. Karmarkarは射影変換法を提案した。この方法は理論上でも実際でもいい結果の得られる最初のアルゴリズムで、最悪の場合でも多項式時間で解くことができ、実際の問題ではシンプレックス法と比べてかなり効率的に解くことができることが示されている。それ以降は多くの内点法が提案されて研究されている。よく使われる内点法にはMehrotraの予測子・修正子法と小島・水野・吉瀬の主双対内点法がある。
すぐれた実装のシンプレックス法と内点法の効率は、線形計画法のアプリケーションとしてはっきりした優劣は無いというのが現在の見解である。しかしながら、目的関数や右辺項が僅かに変動した問題の最適化を繰り返し行う際は、シンプレックス法が優れている。