Skip to content
検索結果に戻る

確率的線形計画法 — 不確実なパラメータを持つ不確実性下での最適化

提唱者
George B. Dantzig
年
1955
種類
Stochastic optimization model
系統
Simulation / optimization

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

確率的線形計画法(SLP)は、費用、需要、資源の利用可能性といったモデルパラメータの一部が不確実であり、確率変数としてモデル化される設定に、古典的な線形計画法を拡張したものです。SLPは、シナリオの確率分布に対する期待費用を最適化することで、単一の想定された世界の状態に対してではなく、起こりうる将来の様々な範囲にわたって実行可能かつ準最適な意思決定を生成します。

手法の背後にある直感

古典的な線形計画法では、すべての係数が正確に既知であると仮定します。しかし実際には、将来の需要、価格、収穫量などは不確実です。SLPは、この不確実性をモデルに直接組み込みます。つまり、単一の固定されたシナリオに対して最適化するのではなく、計画者はまず第一段階の行動を現在決定し、どのシナリオが実現するかを観察し、その後、不足や過剰を是正するためのリカバリー行動を取ります。目的は、すべてのシナリオにわたる総期待費用を最小化することであり、コミットメント費用と期待リカバリー費用とのバランスを取ります。これは現実の経営ロジックを反映しています。つまり、今日何を事前注文するかを決定し、明日には追加料金を払ってさらに購入したり、余剰分を割引価格で販売したりすることができます。

歴史学

確率的計画法は、George Dantzigによって開拓され、シンプレックス法を開発した直後の1955年に2段階モデルを導入しました。Beale (1955) も独立して同様のアイデアを提案しました。この分野は、BirgeとLouveauxの1997年の影響力のある教科書と、1960年代から1980年代にかけてのL字型(Benders)分解アルゴリズムの開発によって体系化されました。SLPは現在、世界中のエネルギー、ロジスティクス、金融における運用上の意思決定の基盤となっています。

使うべき場面

SLPを使用する場合:(1) 主要な入力パラメータが真に不確実であり、確率分布または経験的シナリオ集合によって特徴付けられる場合。(2) 不確実性が解消される前に意思決定を行う必要があるが、その後費用を払って修正行動が可能である場合。(3) 目的関数と制約が決定変数に対して線形である場合。典型的な応用例には、生産計画、サプライチェーン設計、エネルギー供給、ポートフォリオ最適化などがあります。SLPを使用しない場合:不確実性を確率的に定量化できない場合(代わりにロバスト最適化を使用)。意思決定と結果の関係が非線形または整数である場合(確率的MIPまたは確率的動的計画法を使用)。シナリオ集合が大きすぎて列挙できず、分解が計算上実行不可能な場合。または、不確実性の影響を理解するのに、より単純な決定論的感度分析で十分な場合。

限界と注意点

  • 不確実なパラメータの確率分布またはシナリオ集合の指定が必要 — この分布仮定は検証が難しいことが多いです。
  • 計算負荷はシナリオ数と第一段階変数の数とともに急速に増加します。大規模な問題には分解とかなりのソルバーリソースが必要です。
  • 線形目的関数と制約に限定されます。非線形または整数構造には、さらなる複雑さを加える拡張が必要です。
  • 期待値目的関数はテールリスクを無視する可能性があります。リスク回避型バリアント(CVaR、チャンス制約)は、モデリングと計算のオーバーヘッドを追加します。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 確率的な不確実性を最適化に直接組み込み、単一の想定された将来ではなく、複数のシナリオにわたってロバストな意思決定を生成します。
  • 2段階フレームワークは、現実の意思決定プロセスを密接に反映しています。今コミットし、後でリカバリーで適応します。
  • 確率的解の価値(VSS)とEVPIは、不確実性をモデル化する利点を伝えるための原則に基づいた指標を提供します。
  • 成熟したアルゴリズム(L字型法 / Benders分解)と商用ソルバー(CPLEX、Gurobi)によって十分にサポートされています。
  • 分解を通じて大規模な実用問題にスケールアップ可能。シナリオ間で並列化可能です。

応用

  • 不確実な再生可能エネルギー発電と需要の下での電力システム計画とユニットコミットメント。
  • 不確実な顧客需要、リードタイム、または輸送費用を伴うサプライチェーンネットワーク設計。
  • 不確実な降雨量と商品価格の下での作物および灌漑計画。
  • 予算および規制制約の下での不確実な資産収益を伴う金融ポートフォリオ最適化。
  • 不確実な乗客需要の下での航空会社の収益管理と乗務員スケジューリング。
  • 不確実な災害シナリオに備えた人道ロジスティクスの救援物資の事前配置。

使い方

使い方

1

2段階モデルを定式化します。第一段階変数 x は、不確実性が解消される前に下される「今ここでの」意思決定を表します。目的は、第一段階費用 c^T x に、確率ベクトル xi にわたる期待リカバリー費用 E[Q(x,xi)] を加えたものを最小化することです。制約 Ax = b は、シナリオに関わらず第一段階の意思決定に対して成立しなければなりません。

数式
\min_{x} c^T x + \mathbb{E}_\xi[Q(x, \xi)] \quad \text{s.t. } Ax = b,\; x \geq 0
2

確率ベクトル xi を、それぞれ確率 p_s を持ち合計が1となる離散シナリオ集合 {xi_1, ..., xi_S} で表現します。シナリオは、過去のデータ、専門家の意見聴取、またはモンテカルロサンプリングから導出できます。シナリオ集合の質は、解の質を決定する上で極めて重要です。問題の規模を扱いやすくするために、シナリオ削減技術(例:Wasserstein距離クラスタリング)が一般的に適用されます。

3

各シナリオ xi_s について、リカバリー部分問題を解きます。第一段階の意思決定 x が与えられたとき、W y_s = h(xi_s) - T(xi_s) x, y_s >= 0 を満たす最も安価な修正行動 y_s を見つけます。もし実行可能なリカバリーが存在しない場合、大きなペナルティ(または非実行可能性)が発生し、第一段階の意思決定が過度に積極的であったことを示します。

数式
Q(x, \xi) = \min_{y} q(\xi)^T y \quad \text{s.t. } W y = h(\xi) - T(\xi) x,\; y \geq 0
4

小規模から中規模のシナリオ集合に対しては、完全な拡張形式(すべてのシナリオを1つの大きな線形計画問題として積み重ねる)を解くか、大規模な集合に対してはBenders分解(L字型法)を適用します。L字型法は、マスター問題に最適性カットと実行可能性カットを収束するまで繰り返し追加し、シナリオ部分問題のブロック対角構造を利用します。

5

解の品質は、確率的解の価値(VSS)— 決定論的平均値解に対する利益 — と、完全情報期待価値(EVPI)— 完全な予知がどれほどの価値を持つかの上限 — を通じて評価します。意思決定者へのリスクプロファイルを伝えるために、第一段階の意思決定 x*、期待総費用、およびシナリオごとのリカバリー費用を報告します。

よくある落とし穴

  • シナリオ数が少なすぎると、サンプル外でパフォーマンスが低い偏った解が生成されます。常にサンプル外シナリオテストで検証してください。
  • 平均値決定論的解(期待値を代入)と確率的解を混同すること — パラメータが安定しているように見えてもVSSは大きくなる可能性があります。
  • リカバリーの実行可能性を無視すること:一部のシナリオで第二段階部分問題が実行不可能になる可能性がある場合、モデルには完全なリカバリー制約または明示的なペナルティが必要です。
  • 特にサプライチェーンや金融の応用において、テールシナリオや敵対的シナリオに対するストレステストなしに、過去のシナリオ分布に過剰適合すること。
  • 意思決定者が期待値中立ではなく、実際には不確実性回避型である場合に、確率的LPをロバスト最適化の代替品として扱うこと。

よくある質問

確率的線形計画法とロバスト最適化の違いは何ですか?

SLPは、シナリオの確率分布に対する期待費用を最小化し、不確実性が解消された後にリカバリー行動を可能にします。一方、ロバスト最適化は、確率分布を仮定せずに不確実性集合に対する最悪ケースを最適化し、通常、すべてのシナリオに対して実行可能な単一の固定解を生成します。確率を推定できる場合はSLPが好ましく、不確実性集合のみが既知の場合やテールリスク保護が最重要である場合はロバスト最適化が好ましいです。

通常、いくつのシナリオが必要ですか?

これは問題の次元と分布の複雑さに依存します。計画問題の場合、賢明に生成されれば(例:モーメントマッチングやシナリオ削減を通じて)、数十から数百のシナリオで十分なことが多いです。モンテカルロ法に基づく標本平均近似(SAA)では、高精度の解を得るために数千のシナリオが必要となる場合があり、信頼区間が収束を導きます。

SLPは整数またはバイナリの決定を扱えますか?

直接は扱えません。整数変数は、計算上はるかに困難な確率的整数計画法(SIP)または確率的混合整数計画法(SMIP)を必要とします。SLPは、すべての決定変数が連続である場合にのみ適用されます。

確率的解の価値(VSS)は何を測定しますか?

VSS = EEV - RP であり、EEVは決定論的平均値解をすべてのシナリオで評価した期待費用、RPは真の確率的最適解(リカバリー問題)です。VSSが高いほど、不確実性を無視して平均パラメータを使用すると、結果が大幅に悪化することを示します。

どのようなソルバーとソフトウェアが確率的線形計画法をサポートしていますか?

CPLEXやGurobiなどの商用ソルバーは、拡張形式を直接解くことができます。オープンソースフレームワークには、SMPS形式リーダー、PySP(Pyomoの一部)、およびJuliaパッケージStochasticPrograms.jlがあります。大規模な問題の場合、研究および産業界ではカスタムのL字型分解実装が一般的です。

関連する手法

参考文献

  1. Dantzig, G. B., & Madansky, A. (1961). On the solution of two-stage linear programs under uncertainty. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1, 165–176.

    出版物の文献を開く
    コピーしました。
  2. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    ISBN:9780387982175
    コピーしました。