線形計画法 — 線形制約下での線形目的関数の最適化
- 提唱者
- George B. Dantzig
- 年
- 1947
- 種類
- Mathematical programming / continuous optimization
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
線形計画法(LP)は、1947年にジョージ・B・ダンツィグによって開拓された、線形不等式および等式制約の集合を条件として、線形目的関数(最小コストや最大利益など)の最良の値を見つけるための数学的方法である。これはオペレーションズ・リサーチにおける基礎的な技法であり、生産計画、資源配分、ロジスティクス、食事問題、そして工学、経済学、自然科学にわたる無数の他の意思決定シナリオの根幹をなしている。
手法の背後にある直感
あなたは2つの製品を生産する小規模な工場を経営していると想像してください。各製品は一定の利益をもたらしますが、その生産には限られた原材料と機械時間が必要です。線形計画法は、物理的または契約上の制限を一切違反することなく、固定されたリソースから最大の利益を引き出す製品の正確な組み合わせを見つけ出します。「線形」という言葉は、利益とリソース消費量が生産量に比例して直線的な関係でスケールすることを意味します。実行可能な選択肢は、(2次元では)多角形、(高次元では)多面体を形成し、最適な解は常にその頂点のいずれかに位置します。
歴史学
線形計画法の体系的な開発は、ジョージ・B・ダンツィグが米国空軍に勤務中に、軍事ロジスティクス計画の自動化のためにシンプレックスアルゴリズムを発明した1947年に始まりました。ダンツィグは1963年のモノグラフで基礎理論を発表し、これは依然として標準的な参考文献となっています。ソ連のレオニード・カントロヴィチによる独立かつ並行した研究(1939年)は、同様の数学的概念を用いて生産計画に取り組み、カントロヴィチは1975年にこの貢献の一部として経済学ノーベル賞を受賞しました。多項式時間での解法の理論的な問題は、1979年のカーチャンの楕円体法と、その後1984年のカルマルカーの内点法によって解決され、大規模問題に対して実用的に高速であることが証明されました。今日、商用およびオープンソースのLPソルバーは、世界中のエンタープライズリソースプランニング、航空会社スケジューリング、エネルギーシステムに組み込まれています。
使うべき場面
線形計画法は、線形な意思決定変数のセットに線形に依存する量を最適化する必要があり、かつすべての制約も線形である場合に適切です。分布に関する仮定や最小サンプルサイズを必要とせず、統計的推定値ではなく決定論的な数学モデルです。この方法は、意思決定変数が連続的(分数値が意味を持つ)である場合に適用されます。変数が整数またはバイナリでなければならない場合は、整数計画法が必要です。LPは、生産スケジューリング、サプライチェーンロジスティクス、食事・混合問題、金融ポートフォリオ最適化、輸送・割り当て問題、エネルギー配車などで広く使用されています。
限界と注意点
- 線形性の要件:目的関数または制約のいずれかが非線形である場合、LPモデルは誤って指定されており、解は不正確または実行不可能になる可能性があります。
- 連続変数のみ:意思決定変数が整数値またはバイナリ値を取る必要がある場合、LP緩和は下限値を提供しますが、有効な解は提供しません。整数計画法を使用する必要があります。
- 決定論的:LPはパラメータの不確実性をモデル化しません。データが不確実な場合は、確率計画法またはロバスト最適化が必要です。
- 退化とサイクリング:まれに、シンプレックス法が収束せずに退化した基底間をサイクリングすることがありますが、アンチサイクリング規則(例:Blandの規則)で解決されます。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 保証された大域的最適解:実行可能領域は凸多面体であるため、任意の局所的最適解は大域的最適解でもあり、準最適解に閉じ込められるリスクはありません。
- 高いスケーラビリティ:最新のソルバー(HiGHS、Gurobi、CPLEX)は、数百万の変数と制約を持つモデルを数秒で処理します。
- 豊富な事後解情報:シャドー価格と感度範囲は、追加の実行なしでリソース価値と解の頑健性に関する実行可能な洞察を提供します。
- 分布に関する仮定なし:LPは純粋に代数的なモデルであるため、正規性やデータの統計的性質を必要としません。
応用
- 生産計画:機械能力と原材料の制限を尊重しながら、利益を最大化する最適な製品構成を見つけること。
- サプライチェーンと輸送ロジスティクス:倉庫と顧客のネットワーク全体での輸送コストを最小化すること。
- 食事と混合問題:最小コストで栄養要件を満たす材料の量を選択すること。
- 金融ポートフォリオ最適化:リスクと規制上の制約を条件として、期待リターンを最大化するために資産への資本を配分すること。
- エネルギー配車と電力網スケジューリング:発電機の能力制限と電力需要を満たしながら、燃料コストを最小化すること。
- 人員と労働力スケジューリング:最小の労働コストで需要をカバーするために、作業員にシフトを割り当てること。
使い方
使い方
現実世界の意思決定問題は、数学的な記号に翻訳されます。意思決定変数(制御可能な量)を特定し、目的関数(最大化または最小化したいもの)をそれらの変数の線形結合として記述し、すべての制約(リソース制限、能力上限、需要要件)を線形不等式または等式として記述します。適切に定式化されたLPは、明確な目的、明示的な変数境界、および線形に表現されたすべての構造的制約を持ちます。
モデルは、ソルバーが処理できる標準形または正準形に変換されます。不等式は、非負のスラック変数またはサープラス変数を導入することによって等式に変換され、制約のない変数は2つの非負変数の差に置き換えられます。この機械的なステップにより、アルゴリズムが作用するタブローまたは行列表現が生成され、問題自体は変更されず、計算のために整形されるだけです。
ソルバーは、実行可能な多面体の最適な頂点を探索します。古典的なシンプレックス法は、多面体の辺に沿って頂点から頂点へとピボットし、常に目的関数を改善(または維持)しながら、改善する隣接頂点が存在しなくなるまで進行します。一方、内点法(バリア法)は、実行可能領域の内部を中央経路に沿って移動し、これは特に大規模なモデルに対して効率的です。どちらのファミリも、実行可能領域が凸であるため、解が存在する場合には必ず大域的最適解を見つけることが保証されています。
ソルバーは、意思決定変数の最適値と目的関数の最適値、および双対変数(シャドー価格)と感度範囲を返します。シャドー価格は、拘束条件が1単位緩和された場合に目的関数がどれだけ改善されるかを定量化し、追加リソースが最も価値のある場所を意思決定者に直接伝えます。感度分析は、コスト係数または右辺値が現在の基底が最適でなくなるまでどの程度変化できるかを特定します。
よくある落とし穴
- 制約または目的関数が非線形である場合にLPを適用すること — 解は間違っているか、ソルバーがモデルを拒否します。
- 整数性の要件を無視すること:連続LP解を整数に丸めることは、一般的に実行可能または最適な整数解を生成しません。整数計画法を使用してください。
- 実行不可能または非有界なモデル:実行可能領域が空(制約の競合)であるか、目的関数が非有界(境界制約の欠如)である場合、ソルバーは失敗を報告します。実行前に必ずモデル構造を確認してください。
- LP出力を感度分析なしの推奨として扱うこと:技術的には最適解であっても、データのわずかな変化で推奨が反転するようなぎりぎりの状況にある可能性があります。感度範囲は常に検査されるべきです。
よくある質問
LPの目的で、ある問題が「線形」であるとはどういうことですか?
目的関数とすべての制約は線形である必要があります。つまり、各項は単一の意思決定変数に定数を掛けたものであり、変数の積、指数、非線形関数は含まれません。たとえ1つの制約または目的関数に x * y や x の2乗などが含まれる場合でも、標準的なLPはもはや適用されず、非線形計画法または二次計画法のソルバーが必要になります。
最適な解が常に実行可能領域の角にあるのはなぜですか?
線形制約によって定義される実行可能領域は、凸多面体(またはポリトープ)です。線形目的関数自体が線形であるため、凸集合の内部に向かって「引っ張られる」ことはありません。それは常に境界上で極値を取り、特に頂点(角点)で取ります。これが、シンプレックス法の頂点から頂点への戦略の根底にある幾何学的な洞察です。
LPの代わりに整数計画法を使用すべきなのはいつですか?
1つ以上の意思決定変数が整数値またはバイナリ(0/1)値を取る必要がある場合です。例えば、施設を開設するかどうか(はい/いいえ)、何台のトラックを派遣するか(整数)、または選択にどの項目を含めるかなどです。単にLPを解いて連続解を整数に丸めるだけでは信頼性がありません。丸められた解は実行不可能であったり、最適解からかけ離れていたりする可能性があります。整数計画法は、より大きな計算コストをかけて、整数性を正しく扱います。
シャドー価格は何を教えてくれますか?
拘束条件のシャドー価格(双対変数)は、他のすべてを一定に保った場合に、その制約の右辺値が1単位緩和された場合に、最適目的値がどれだけ改善されるかを示します。例えば、労働時間制約に対するシャドー価格が3である場合、労働時間を1時間追加すると目的値が3単位改善されることを意味します。拘束条件が満たされていない(非拘束)場合、シャドー価格はゼロであり、現在の最適解を制限していません。
関連する手法
参考文献
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
ISBN:9780691059136コピーしました。Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.
DOI 文献を開くコピーしました。