確率計画

【かくりつけいかく (stochastic programming)】

概要

ほとんどの現実問題が確率的であるということから, 1955年にダンツィク (G.B. Dantzig) とビール (M. Beale) によって全く独立に始められたのが確率計画である. 両者とも2段階計画問題を考えたが, その後1959年にチャーンズ (A. Charnes) とクーパー (W.W. Cooper) によって確率制約計画問題が導入された. 一般的には解法が難しいので, 問題固有の構造を利用した特殊解法や近似解法の研究が数多くなされている.

詳説

　数理計画問題において, 目的関数や制約条件の係数の中に確率的要素が含まれているとき, これを確率計画 (stochastic programming)(確率計画法, 確率計画問題)と呼ぶ. いま, 制約条件の係数に確率変数を含む線形計画問題

${\begin{array}{ll}{\mbox{min.}}&c^{\top }x\\{\mbox{s. t.}}&T(\omega )x=h(\omega ),\\&Ax=b,\ x\geq 0,\\\end{array}}\,$

を考える. ここで, $c,b,A\,$はそれぞれ既知のベクトルや行列で, $T(\omega )\,$, $h(\omega )\,$は確率事象$\omega \,$に依存するランダムな行列およびベクトルである. 確率変数を含む制約条件はすべての実現値に対して満たされるとは限らない. そこで, 確率計画問題として2つのアプローチ2段階計画問題 (two-stage programming problem)および確率制約計画問題 (probabilistic constrained programming problem)がある [1], [2].

　まず2段階計画問題では,確率変数の含まれる制約条件$T(\omega )x=h(\omega )\,$においてこの制約条件を成り立たせなくさせている両辺の差 $h(\omega )-T(\omega )x\,$ に対してその外れ具合を矯正するためにリコースというものを考える. 具体的には次のようなリコース行列$W\,$およびリコース変数$y\,$を考える.

$Wy=h-Tx,\ y\geq 0\,$

すなわち, 2段階計画問題は次のように定式化される.

${\begin{array}{ll}{\mbox{min.}}&c^{\top }x+{\mbox{E}}[{\mbox{min}}\ q(\omega )^{\top }y(\omega )]\\{\mbox{s. t.}}&T(\omega )x+Wy(\omega )=h(\omega ),\\&Ax=b,\ x\geq 0,\ y(\omega )\geq 0.\\\end{array}}\,$

　次に確率制約計画問題において, 制約条件が必ずしも満たされなくても, ある確率以上で満たされれば良い場合を考える. 例えば, $T(\omega )x\geq h(\omega )\,$という制約条件の代わりに確率$\alpha \,$以上で成り立つという確率制約条件

$\Pr\{T(\omega )x\geq h(\omega )\}\geq \alpha \,$

を考える. 目的関数の型によってEモデル, Vモデル, Pモデルなど様々なモデルが考えられる.

　2段階計画問題も確率制約計画問題も, 通常は等価な確定問題すなわち非線形計画問題に変換して解く. 一般にはこの変換は非常に複雑な形になる. 通常2段階計画問題の方が確率制約計画問題より等価な確定問題への変換が難しい. そこで確率計画の切除平面法であるL型法のような確率分布の特別な構造を利用した解法や, 様々な近似を利用した解法が研究されている [1], [3].

　確率計画問題において, 通常は確率変数の分布関数は与えられているとするが, 一般には分布関数が完全に分かることは難しい. いま完全情報すなわち確率変数の将来の実現値を知るために決定者が最大どれだけの価値を支払うかを調べる. この価値は完全情報の期待価値 (expected value of perfect information; EVPI)と呼ばれる. 完全情報を得ると実現値に対して, 最適解や最適値を正確に知ることができる. そこで, 最適解や最適値の確率分布を求める問題, すなわち分布問題 (distribution problem)が考えられるが, この問題は通常非常に難しい. 分布問題の近似として確率変数をその期待値で置き換えた問題を考え, このときこの期待値問題と確率の入ったリコース問題との最適値の違いを確率解の価値 (value of the stochastic solution; VSS)と呼ぶ. これは確率計画として解くことの価値を表すものである. EVPIやVSSの上限と下限で挟まれた区間をより厳密に求めることが研究されている[1], [5].

　その他確率計画では推定や近似など統計的な方法を用いたもの [4] やファイナンス, ポートフォリオのような応用面を対象とした研究も多くなってきている.

---

参考文献

[1] J. R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer-Verlag, New York, 1997.

[2] S. Vajda, Probabilistic Programming, Academic Press, New York and London, 1972.

[3] A. Prékopa, "The Use of Discrete Moment Bounds in Probabilistic Constrained Stochastic Programming Models," Annals of Operations Research, 85 (1999), 21-38.

[4] R. J-B Wets, "Stochastic Programming," in Optimization, G. L. Nemhauser, A. H. G. Rinooy Kan and M. J. Todd, eds., North-Holland, 1989. 石井博昭 訳,「確率計画法」, 伊理正夫, 今野浩, 刀根薫監訳,『最適化ハンドブック』, 朝倉書店, 1995.

[5] 塩出省吾,「確率計画法」, 西田俊夫, 田畑吉雄編,『現代OR入門』,現代数学社, 1995.