数学における線形計画法(LP) 問題は、目的関数と制約がすべて線形である最適化問題です。ただし、ここで示した結果のほとんどは、目的が考慮されている各変数の単調増加関数である場合にも当てはまります。線形計画法は、 LP 問題を解決する方法も指します。
LP 問題は最も簡単な最適化問題であり、すべての制約が線形であるため、線形計画法は最適化の中心領域です。実際の オペレーションズ リサーチの問題の多くは、PL 問題として表現できます。このため、他の最適化問題を解決するための多数のアルゴリズムは、線形問題の解決に基づいています。
線形計画法という用語は、求められる解が実数変数で表現されなければならないことを前提としています。問題のモデル化に離散変数を使用する必要がある場合、それは整数線形計画法 (ILP) と呼ばれます。後者は連続変数を使用した PL よりも解決が大幅に難しいことを知っておくことが重要です。
例
Hヘクタールに等しい面積の土地を所有し、小麦やトウモロコシを植えることができる農家を考えてみましょう。農家は量Eの肥料とIの殺虫剤を持っています。小麦には、1 ヘクタールあたりE 1の量の肥料と、1 ヘクタールあたりI 1の殺虫剤が必要です。トウモロコシの対応する量はE 2およびI 2で示されます。
P 1 を小麦の販売価格、 P 2 をトウモロコシの販売価格とします。小麦とトウモロコシを植えるヘクタールの数をx 1とx 2で表すと、小麦とトウモロコシを植える最適なヘクタール数は線形プログラムとして表すことができます。
| 最大化する | D1 × 1 + D2 × 2 | （純利益の最大化） |
| 制約の下で | $$ {x_1 + x_2 \le H} $$ | （総ヘクタール数の制限） |
$$ {E_1 x_1 + E_2 x_2 \le E} $$ | （肥料の量の制限） | |
$$ {I_1 x_1 + I_2 x_2 \le I} $$ | （殺虫剤の使用量制限） | |
$$ {x_1 \ge 0,\, x_2 \ge 0} $$ | (負のヘクタール数を植えることはできません) |
理論
幾何学的観点から見ると、線形拘束は凸多面体を形成します。目的関数も線形の場合、すべての局所最適値は大域最適値でもあります。これは、考慮される各変数で単調増加する場合に当てはまります。線形ケースは、プロパティが使用されない特定のケースのみを表します。
最適な解決策が存在しないケースが 2 つあります。 1 つ目は、制約が互いに矛盾する場合です (例:
多面体は、目的関数で定義された方向に無制限にすることもできます (たとえば、次のようなx 1 + 3 x 2) 。
これら 2 つのケース (実際の問題では究極的にはまれです) を除けば、最適値は常に多面体の頂点で達成されます。ただし、最適解は必ずしも一意であるとは限りません。ポリトープのエッジや面、あるいはポリトープ全体に対応する最適解のセットを持つことも可能です。
二元性
すべての線形プログラムは次の形式で記述できます。
ここで、c と x はサイズ n のベクトル、b はサイズ m のベクトル、A はサイズ mXn の行列です。この表現を「主形式」という用語で表すと、次の問題を「双対形式」という用語で表すことができます。
ここで、A、b、c は同じで、y はサイズ m のベクトルです。 (注: 2 つの表現の正確な詳細は作品ごとに大きく異なります)
2 つの問題は非常に強く関連しています。そのうちの 1 つが最適な解決策を持っている場合、もう一方も最適な解決策を持っています。さらに、2 つの解は同じ値になります (w*=z*)。そのうちの 1 つが制限されていない場合、もう 1 つは解決策がありません。
双対問題には、理論的な面白さに加えて、非常に興味深い経済的応用もあります。各主制約は二重変数に対応します。最適解におけるこの変数の値は、主制約に関連付けられた限界費用を表します。
アルゴリズム
シンプレックスアルゴリズムでは、最初に多面体の頂点である実行可能な解を構築し、次に多面体のエッジに沿って移動して目的の値がどんどん大きくなる頂点に到達し、最適解に到達することで、LP 問題を解くことができます。 。このアルゴリズムは実際には効率的であり、最適なアルゴリズムを見つけることが保証されていますが、最悪の場合の動作は悪くなる可能性があります。したがって、シンプレックス法では問題のサイズが指数関数的に増加するステップ数を必要とする PL を構築することが可能です。したがって、数年間、LP が NP 完全問題なのか多項式問題なのかは未解決の問題のままでした。
PL の最初の多項式アルゴリズムは、1979 年に Leonid Khachiyan によって提案されました。これは、Naum Shor によって以前に提案された非線形最適化の楕円体法に基づいています。この手法自体は、Arkadi Nemirovski (2003 年ジョン フォン ノイマン賞) と D. Yudin による凸最適化における楕円体手法を一般化したものです。
しかし、Khachiyan のアルゴリズムの実際の有効性は残念です。ほとんどの場合、シンプレックス アルゴリズムの方が効率的です。一方、この結果は内点法の研究を促進しました。制約によって定義された多面体の境界のみを考慮するシンプレックス アルゴリズムとは対照的に、内点法は多面体内部で進化します。
1984 年に、N. Karmarkar は射影法を提案しました。これは、理論的にも実践的にも効果的な最初のアルゴリズムです。その最悪の場合の複雑さは多項式であり、実際の問題に関する実験では、この方法がシンプレックス アルゴリズムと合理的に比較できることが示されています。それ以来、いくつかの内点法が提案され、研究されてきました。最も有名な方法の 1 つは、理論的研究がまだ不完全であるにもかかわらず、実際には非常にうまく機能する予測/修正方法です。
通常の LP 問題を実際に解決するには、シンプレックスまたは内点から導出された方法に基づいて同等の (良い) コードと考えるのが現在一般的です。さらに、大きな問題を解決するには、列生成のような手法が非常に効果的です。
LP ベースのソルバーは、輸送フローの最適化や生産計画など、さまざまな産業上の問題の最適化に使用されることが増えています。ただし、PL モデルは多くの問題を表現するには不十分であることが判明したため、整数の線形計画法を使用すると、多数の追加の問題をモデル化することができます。
整数線形計画法
整数線形計画問題 (ILLP) は、線形計画法、つまり線形制約の下で最大化または最小化される線形目的関数であり、変数が整数であるという追加の制約があります。変数のサブセットのみが整数で、その他は実数でなければならない場合、混合線形プログラムについて話します。
多くの NP 完全問題は PLNE として表現できるため、PLNE が NP 完全問題であることを示すのは簡単です。もちろん、PL について上で説明したアルゴリズムは PLNE の問題を解決しません。一方、PLNE (整合性制約のない PLNE) の継続的な緩和は、効率的に解決できる PL です。分離および評価アルゴリズムやセカント平面生成アルゴリズムなどの PLNE 解決アルゴリズムは、多くの場合、この連続緩和に基づいています。
アプリケーション
線形計画法は基本的に、中長期の最適化問題 (オペレーションズ リサーチの用語でいう戦略的および戦術的問題) を解決するために適用されます。これらの問題の適用分野は、対処する問題の性質 (ネットワークにおける生産、流通の計画と制御) と、製造業、エネルギー(石油、ガス、電気、原子力)、輸送などの産業分野の両方で非常に多岐にわたります。 (航空、道路、鉄道)、電気通信、林業、金融。
石油分野での応用
線形計画法は石油業界で一般的に適用されています。メインではないにしても、PL（線形計画法）を日常的に使用している業界の1つです。これは、精製業者が製油所の生産量を最適に決定できるようにするツールです。これを行うには、プログラムは次のような特定の数の制約を考慮する必要があります。
- 利用可能な原材料、その収量、カットの品質、
- 製造される製品の仕様、
- 一部商品のアウトレット制限、
- ユニットの能力、
- 設置調整モード、
- 利用可能なストレージ容量。
PL は、次のような精製の他の分野でも使用できます。
- 仕様を考慮した製品混合物（燃料、ディーゼル、燃料油）の最適な組成の計算。
- 施設利用の最適化、
- 原油の最適な予熱と使用料を取得するための計算、
- 製油所にとって最適な「蒸気と電気」のバランスを決定します。
製油所以外では、LP は次のような運用研究に使用できます。
- 石油会社の長期・中期・短期計画を立てる、
- タンカー艦隊の運航と製品の導入を最適化します。
参考文献
- クリステル・ゲレ、クリスチャン・プリンス、マルク・セヴォー：「線形計画法」。 Eyrolles、2000 年。ISBN 2-212-09202-4、365 ページ。
- エリック・ジャケ＝ラグレーズ。 線形計画法 – コンピューターのモデリングと実装コレクション: PIQ Poche – 出版社: Economya
