線型計画法のソースを表示

{{参照方法|date=2023年5月}}
'''線型計画法'''（せんけいけいかくほう、{{lang-en|linear programming}}、略称: LP）は、[[数理最適化|数理計画法]]において、いくつかの1次[[不等式]]および1次等式を満たす[[変数 (数学)|変数]]の値の中で、ある1次式を最大化または最小化する値を求める方法である。線形計画法の対象となる[[最適化問題]]を[[線型計画問題]]という。

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

== 線型計画問題 ==
数学的には[[線型計画問題]]は、[[目的関数]]と[[制約条件]]がすべて線型の[[最適化問題]]である。

2変数 <math>x_1 (\geq 0)</math>、<math>x_2 (\geq 0)</math> の場合、与えられた定係数 <math>a_{ij} \ </math> と <math>b_i \ </math>、<math>c_j \ </math>、および不等式制約

:<math>
  \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}
</math>

の下、次式

:<math>
  c_1 x_1 + c_2 x_2 \ 
</math>

の最大値およびそれを実現する <math>x_1 \ </math> と <math>x_2 \ </math> を求める問題が、典型的な線型計画問題である。

3変数  <math>x_1 \ </math>、<math>x_2 \ </math>、<math>x_3 \ </math> の場合、3次元座標空間上に描かれた立体図形を切るような平面のうち、<math>x_3 \ </math> 切片（平面と <math>x_3 \ </math> 軸との交点）の値が最大あるいは最小となるような平面を求めることになる。

最適解の取り得る範囲を[[整数]]に限定した線型計画法は、[[整数計画法]]と呼ばれる。

== 線型計画問題の例 ==
線型計画問題の例として以下の問題をとりあげる。農業を営む人が、小麦と大麦のための<math>A \ </math>平方キロメートルの農地を持っていると仮定する。農家は限度 <math>F \ </math> で肥料、限度 <math>P \ </math> で殺虫剤を使用することができる。これらはそれぞれ単位面積あたり小麦が <math>(F_1, P_1) \ </math>、大麦が <math>(F_2, P_2) \ </math> を必要とする。小麦の販売価格を <math>S_1 \ </math>、大麦の販売価格を <math>S_2 \ </math>、小麦を育てる領域を <math>x_1 \ </math>、大麦を育てる領域を <math>x_2 \ </math> とすると、線型計画問題として大麦と小麦をどれだけ育てればいいかを表すことができる。

{| 
| 最大化：
| <math> S_1 x_1 + S_2 x_2 \ </math>
| (利益の最大化)
|-
| rowspan="4" valign="top" | 制約条件：
| <math> x_1 + x_2 \le A </math>
| (耕作地の制約)
|-
| <math> F_1 x_1 + F_2 x_2 \le F </math>
| (肥料の制約)
|-
| <math> P_1 x_1 + P_2 x_2 \le P </math>
| (殺虫剤の制約)
|-
| <math> x_1 \ge 0,\, x_2 \ge 0 </math>
| (非負制約)
|}

== 理論 ==
[[幾何学]]的には線型（不）等式制約は[[実行可能領域]]と呼ばれる[[凸多面体]]を定義する。目的関数も線型なので、全ての局所最適解はおのずと（大域的）最適解になる。線型な目的関数であることによって、必然的に最適解は実行可能領域の境界上のみに現れる。

最適解が見つからない状況が2つある。1つは互いに矛盾のある制約（例えば、<math>x \ge 2</math> と <math>x \le 1</math>）ならば実行可能領域は空になり、最適解は存在しえない。最適解が得られないのでこの場合はLPは実行不能と呼ばれる。

もう1つの状況は、[[多面体]]が目的関数の向きに境界を持たない場合（例：最大化：<math>x_1 + 3 x_2 \ </math>制約：<math>x_1 \ge 0, x_2 \ge 0, x_1 + x_2 \ge 10</math>）である。この場合、目的関数はいくらでも大きい値を取り得る。

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

== アルゴリズム ==
{{main|シンプレックス法|内点法|カーマーカーのアルゴリズム}}
[[シンプレックス法]]（単体法）は最適解が多面体の頂点に現れることを利用し、最適解に達するまで多面体の辺をたどってより高い目的関数の値を次々にたどることで線型計画問題を解く。この[[アルゴリズム]]は実際にかなり能率のいいもので、巡回していないか（巡回してしまうと最適解に到達することができない）に注意を払えば（大域的）最適解を見つけることが保証される。シンプレックス法は、用いるピボット規則により性能が左右される。有限回のピボットで終了することが保証されている規則として、Blandの提案した最小添字規則が知られている。Dantzigの提案したピボット規則は問題の規模にたいして[[指数関数時間|指数時間]]かかる問題例があることが知られている。現在のところ、線型計画問題を[[多項式時間]]で解くピボット規則の存在性は未解決問題である。

線型計画問題を最悪の場合でも多項式時間で解くアルゴリズムが{{仮リンク|レオニード・カチヤン|en|Leonid Khachiyan|label=}}によって[[1979年]]に初めて提案された。そのアルゴリズムは{{仮リンク|ナウム・ショール|en|Naum Z. Shor|label=}}の[[非線型最適化]]の[[楕円体法]]（これは{{仮リンク|アルカディ・ネミロフスキー|en|Arkadi Nemirovski|label=}}とDmitri Yudinが一般化して、2003年に[[ジョン・フォン・ノイマン理論賞]]を受賞した[[凸最適化]]の楕円体法）をベースにしていた。

しかしカチヤンのアルゴリズムの実用性は期待はずれで、一般にシンプレックス法の方が効率的である。このアルゴリズムの主な重要性は、アルゴリズムの多項式性を示す証明手段を提供した事と、[[内点法]]の研究を促進したことにある。実行可能領域の辺のみを探索するシンプレックス法に対し、内点法は実行可能領域の内部を動くアルゴリズムとなっている。

[[1984年]]に[[ナレンドラ・カーマーカー]]は[[カーマーカーのアルゴリズム|カーマーカー法]]（[[射影変換]]法）を提案した。この方法は理論上でも実際でもいい結果の得られる最初のアルゴリズムで、最悪の場合でも多項式時間で解くことができ、実際の問題ではシンプレックス法と比べてかなり効率的に解くことができることが示されている。それ以降は多くの内点法が提案されて研究されている。よく使われる内点法には[[メロートラの予測子・修正子法]]と小島・水野・吉瀬の主双対内点法がある。

すぐれた実装のシンプレックス法と内点法の効率は、線型計画法の応用としてはっきりした優劣は無いというのが現在の見解である。しかしながら、目的関数や右辺項が僅かに変動した問題の最適化を繰り返し行う際は、シンプレックス法が優れている。

LPのソルバーは、輸送におけるネットワークフロー問題（線型計画問題として定式化できる）のような産業のさまざまな問題の最適化のために広く普及している。

==参考文献==
{{参照方法|date=2023年12月|section=1}}
* 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.
*{{citation | author =水野 眞治 | title =『シンプレックス法の巡回とその回避』| url =http://www.me.titech.ac.jp/~mizu_lab/text/PDF-LP/LP3A-simplex.pdf }}
*{{citation | author =松井 知己 | title =『Bland の最小添字規則の有限性 -単体法の非巡回ピヴォット規則- 』| url =http://tomomi.my.coocan.jp/text/bland7.pdf }}
*[https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.32_01_014.pdf 藤重悟：「線形計画問題の強多項式解法について」,オベレーションズ・リサーチ，1987年1月号，pp.14-18.]
* 室田一雄、杉原正顕：「線形代数II」、東京大学工学教程、丸善出版（2013）.

== 関連項目 ==
* [[線型代数学]]
* [[非線型計画法]]

{{最適化アルゴリズム}}

{{Normdaten}}
{{DEFAULTSORT:せんけいけいかくほう}}
[[Category:線型計画法|*]]
[[Category:数学に関する記事|せんけいけいかくほう]]