多様化時代の数理計画法 第3回 確率計画法
石井 博昭……m…附……l…………ll……ll…l…l……ll……l………l……………………………‖‖‖＝＝‖‖‖＝‖‖‖＝‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖…l………州…ll…llll…llll…llll……l…lll…llll…llll…lll……l…l……………lI…lllll…lll…ll

行うのが確率計画法である．古くからこのような最適1．はじめに化は，在庫管理，ポートフォリオ，システムの設計・保全等で考えられてきた．しかし，数理計画の1つのまず簡単な例として生産計画の問題を考えよう．S
社はある工場の2つの複合ラインⅠ，ⅠⅠで2種類の製流れとして定着してきたのは，1950年代の後半から品1，2を生産している．各ラインⅠ，ⅠⅠを単位時間で，不確実性に対する態度や考え方による違いに基づ稼働するときの費用はcl，C2であり，この単位時間稼いて，いろいろなモデルが提唱されてきた．この辺り

働のとき，ラインⅠでは製品1がα．1，製品2がα21だをまず2節で述べる．3節では，情報および推定予測

けでき，ラインⅠⅠでは製品1はα12，製品2はα22だけとの関係から確率計面法をみる．4節では，確率的組できる．各ラインⅠ，ⅠⅠの 1ケ月の稼働時間を∬1，裁と合せ最適化の幾つかのモデルについて紹介するとともすると各製品1，2は各々αllズl＋α12ち，亀1ズ1＋亀2鞄だに，現状の問題点や将来の展望について議論する．

けできる．また，1ケ月全体の稼働費用はc．ズ1十c2裁と2．確率計画モデルなる．各製品1，2の需要は確率変動するとして各々勘と技術がすべでと思われていた野球にもデータを吉．，島で表す．通常はこの実現値がわかる前に生産しておかねばな・らないので，生産量と需要量とは一致しな集めることが重要視されるこの頃である．すなわち，い．ここで，厳密さにかけるが吉．，らを確率変数とそ

数理統計ではできるだけ情報（特に，確率変動する要の実現値の両方に用いる．

素に対しては実現値の情報）を基に意思決定する．し2かし，上記の生産計画の例からもわかるように，現実

吉王・＞∑αけちのときは製品才は品不足であり，緊急にJ＝12には実現値を知る前に意思決定しなければならない場製造したり他に頼んだりして不足量ッ‡＝昇一∑αどノち J＝1合が多い．また，そのときにこそ意思決定が重要であを都合しなければならない．一方で，売れ残った場ノ合，2 すなわち，∑恥萌≧古・のときはバーゲンなどの方法で＝1 2

ノ対処して，γ㌻＝∑αゎみ一言〜・だけ処分しなければなら J＝1る．A．M．Madansky［8］は実現値を知った後に意思決定をすることを「待って，よく見，よく聞いて」意ない．品不足の場合の単位当たりかかる費用をみ，売思決定するという意味で，Waitandseeアプローチとれ残りの場合のこの費用を仇・とすると，生産費用，品呼び，そうではなく，実現値を知る前に意思決定をし切れ，売れ残りの期待費用のバランスを考えて，生産なければならない場合を今直ちにという意味でhere

担当者は例えば次のような問題常により，工場の各ラandnowアプローチと呼んだ．前者では意思決定の時インの1ケ月の稼働時間を決めなければならない．

点で実現値がわかっているので，実現値によって最適値や最適解がどう変わるかという分布問題を中心に研

22 昂：最小化∑らみ＋E［∑（食打十qり′J）］ J＝1〜＝1

究が行われてきた．後者では情報がないので，何を基制約条件み≧0，ノ＝1，2，．

準にして意思決定をするかとか，確率変数の実現値との関係で解が実行可能でなくなった場合はどうするか

ここで，Eは期待値をとる汎関数である．
このように確率変動する要素を組み込んで最適化をなどが問題となるので，いろいろなモデルが考えられている．従って以下では後者の場合についてのみ考え
いしい ひろあき 大阪大学ていく．すをわちこの場合は意思決定の方が先である〒565吹田市山田丘2−1ので実際の確率変動要素の実現値との差異によって成© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オ／ヾレーションズ・リサーチ一1▲・．

504（34）

り立たない条件をどうするかが問題である．差異に対異を埋めるための費用）がかかる．もちろん，この他して何らかの行動を起こして埋める（この行動をリコいろいろなタイプがあるが省略する．そのかわりに，ースという）か，そう頻繁でなければ，何回かは我慢

この辺りの状況を上記の生産計画問題に以下の架空のするという2つの態度がある．前者はリコース

数値を当てはめて説明する．

（recourse）を考えるということでリコース問題（sto−Chastic programming with recourse）と言い，最初

例1．単位時間稼働コストcl＝10，ら＝20とし，恥はA・M・Madanskyにより2段階問題として（［18］），さ表1で与えられる数値とする．

らには一般形としてD．W．WalkupandR．J．B．Wets
表1αむ（単位時間当たりの製造数）（［10］）により提唱された．後者は機会制約条件（chance constraint）を考えた機会制約条件問題（chanceconstrainedprogramming）としてA．Char−nesandW．W．Cooper（［13］）により提唱された．

工場Ⅰ

工場ⅠⅠ

製品125

製品254

2段階問題では確率変動要素の実現値がわかる前の●1段階目でまず意思決定を行い，その後わかる実現値

・また，不足の時の費用は♪1＝40，♪2＝20，売れ残りとこの意思決定との適合性のの時の費用は仇＝10，q2＝5，各需要百1，ちは次の図

差異 により制約条件の不成立が生じた場合の差異を埋めるための行動からなる．すなわち1段階目で意思決定をする費用と2段1，図2で与えられるような一様分布とする．
ズ1，鞄は非負条件だけであるので，以下の図3のよう階目でリコースを行う期待費用の和を最小にする最適に実行可能領域を4つの領域に分けて考える．ここで，意思決定を求めるのが2段階問題である．上記の生産

Ⅰは直線2ズ1＋5範＝30を示し，ⅠⅠは直線5二r．十4鞄＝計画問題昂はまさしく2段階問題であり，1段階目40を示す．

での意思決定が各ラインでの稼働時間である．実際の点（ズ1，鞄）が領域αに属する場合

需要が確率変動要素の実現値で，緊急生産やバーゲン

この場合いつも需要より製造量が多いので売れ残りがリコースである．この2段階問題は一般的に示せばの可能性のみあり，Z＝α＋E（Q（ズ，百）〉は以下のよ以下のような形となる．
月：最小化z＝α＋E〈￠（∬，吉）〉

制約条件∂ゴーA㌦≦0，ダ＝1，2，…，∽ズ≧0

ここで，C，ズ，Afは各々横乃ベクトル，縦乃ベクト
ル，横乃ベクトルで占fは定数である．確率変動要素は0

ぎであるが，場合により確率変数あるいはその実現値に用いる．このとき，リコースの費用関数はヴ，ツ，Ⅳ，ん（れ r（百）を適当なべクトル，行列として30

Q（ズ，吉）＝inf〈砂l一物＝ゐ（百）一丁（吉）ズ〉とかける．ニッ≧0の問題はq，Ⅳが確率変動に関係しないので，固定リ

図1 製品1の需要分布コース問題という．この問題では（固定された）制約条件∂∫−Aげ≦0，才＝1，2，…，椚の他に，確率変動要素吉を含む等式制約r（百）ズ＝ゐ（吉）がある．どの実現値を知る前に意思決定，すなわち，ズを決めないといけないので，その等式が成り立たないことがある．このとき，その差ゐ（百）一丁（百）ズを埋めるべくとる行動がリコースッであり，その効果がレり，費用が砂という意味である．従って，意思決定ズにはその直接の費用（生産計画では稼働費用）とそれから発生する可能性のあるリコースによる費用（生産計画では需要との差
1996年9 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（35）505

目的関数値は10小20ち＋÷（2出5鞄）2＋÷（30−2ズ1−5鞄）2・去（5小4名）2＋÷（40−5ズ1−4ズ2）2と1152 なり，最小はズ1＝一頭訂，鞄＝豊でおこる
α，∂，Cどの場合も最小はdとの境界上であるので全1152 体の最小はズ1＝一面−，鞄＝豊でおこり，これが最適解となる．

■

一方，．機会制約条件は確率変動要素をその条件に含んでいるために，その実現値によっては成り立たない場合もあるので，この条件がある確率以上で満たされうに計算される．

ればよいとするものである．通常の制約条件はそれに10小20小10ノ70（2小5ち一島）柏）祐対して常に成り立つことを要求する．例えば遅刻もいつもでなければ，許されるが，頻繁であれば認められ＋5√0（5…4鞄−ら）ム（島鳩ない．このような機会制約条件を含む問題が機会制約＝55ズ1十90ち−250

条件問題であり，例えば，次のような形のものが考えこれの最小はⅠとⅠⅠの交点でおこり，その座標はられる．

80∬1＝，鞄＝である・

残：最小化α宙

乃点（ズ1，ち）が領域∂に属する場合

制約条件Pγ〈∑軋み≧島〉≧αf，f＝1，2，…∽，

この場合は，製品1については品切れと売れ残り

∬≧0．

ノ＝1

が各々2∬1＋5ち≦古1≦30，0≦古1≦2二rl＋5鞄を満たす

ここで，Pγは〈）の中が成り立つ確率を示し，各号iは場合に起こるので，目的関数値は次のように計算され確率変数で，各αgは1≧αど≧0で成り立つべき確率レる．

ベルを示す．この条件が機会制約条件である．上記の10ズl＋20ち＋10 ／；油2賞でcも確率変数のときは，αの期待値を最小にする（2ズ1十5鞄一言1）メ（島）（拷．

モデル（Eモデル）や分散を最小にするモデル（Ⅴモデル），あるいはPγ〈α≧劫〉と表される目的関数を最十40／ご亜2（ぞ1−2ズ1−5鞄）硯）薇

大にする確率最大化モデルなどいろいろ考えられてい＋5∫0（5…4鞄−ち）ム（量鳩る．リコースでは差異の大きさが問題であり，条件が成り立たない確率とかは問題にしない．すなわち，い＝35…40鞄＋÷（2打5栽）2

つもちょっとだけ遅れてくるのとめったにないがめち＋（30−2ズ1−5鞄）2−100ゃくちゃ遅れるのとどっちが許されるかの問題である．
一方，機会制約条件は差異の大きさより成り立たな

この場合の最小はⅠⅠの上でおこり，最小を与えるのはい確率が問題となる．ところが，機会制約条件は次の1884 ズ1＝一宮軒鞄＝窓である・

ようにしてリコース費用関数の形に書くこともできる．

点（ズ1，鞄）が領域cに属する場合

乃

機会制約条件を一番単純なPγ（∑軋み≧古〉≧α，製品2は品切れと売れ残りが各々5ズ1＋4鞄≦ち

ノ＝1

乃≦40，0≦ち≦5ズ1十4ちを満たす場合に起こることか

すなわち，確率分布関数を用いてF（∑q鞄）≧αら∂と同様にして，目的関数値は志（■5小4ち）2−とすると70∬1−10ち＋250となる・また最小はⅠ上のズ1＝面，鞄＝でおこる

ノ＝1

乃

α−1（∑厄晶一首≧0）600

Q（ズ，百）＝．ノ＝l（ α （otherwise）とおけばよい．実際，このとき

点（∬1，鞄）が領域dに属する場合
製品1，2とも品切れと売れ残りの可能性があり，506（36）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ●・00

柚，距／蓬￠ち（α一躍（材量。みα併ほ）乃

実現値について全く情報がない場合の最適意思決定の価値の差の期待値である．EVPIは，まさしく，2章で＝α−F（∑肪）ノ＝1

JJ となり，ダ（∑ム晶）≧αを満たす∬が存在する条件とJ＝1

述べた・Waitandseeとhereandnowのア70ローチによる最適意思決定の差異に対応している．これらの概g［Q（∬，吉）］の最小値が0以下となる条件は同値とな

念は統計的決定理論において以前から考えられていたる．

ものであるが，数理計画問題では，）．BrackenandR．
2段階問題も機会制約条件問題も通常解くためにはM．Soland（［2］）の論文で初めて使われた．彼らの基等価な確定問題，すなわち，非線形計画問題に変換しにしたモデルはcのみを確率変動要素とする次の線て解くことになるが，この等価確定問題への変換が難形計画問題ろであった．

しい上，変換できたとしてもとても複雑な形となる。
一般的に言って，2段階問題の方が変換が困難であり，●は実現値がわかっている場合の最適意思決定の価値と

汽：最小化α
制約条件AJ＝∂，J≧0形もより複雑である．どちらにしても最低限確率変動

ここで，A，∂は各々∽×乃行列，∽次元縦ベクトル，要素の分布関数が必要である．この辺りを機会制約条

ズは乃次元縦ベクトルで決定変数，0は成分が零のみ

乃件Pγ〈∑￠ち≧霞）≧αを使って説明する．確率変数∈ J＝1からなる乃次元縦ベクトルである．cは乃次元横ベクが平均仏 分散♂2の正規分布Ⅳ（〃，♂2）に従うとするとトルで成分が確率変動すると仮定する．貧の制約条件

皇二妻を満たすズ全体の集合，すなわち，実行可能解の集合♂

が標準正規分布に従うことからこの機会制約条
乃件は簡単な計算で，等価確定条件∑彿≧〃＋靡 −1（α）

を5で示す．価値については最小化であるから，このノ＝1に変形される．ここで，F（ズ）は標準正規分布の確率分布関数で，F￣1（∬）はその逆関数である．

しかし，確率変動要素の分布関数が完全にわかるこ

場合EVSIおよびEVPIは以下のようになる．
EVSI＝minE，。［cxトE′。［minE′′c（cx）］∫∈5

EVPI＝minE c［cx］，E′c［mincx］
J∈5とは一般には難しい．また，わかるとしても莫大な費用がかかることも多い．第3節でこの点を議論する．

∫∈S

∫∈5

ここで，且′。は事前分布を用いた場合の期待値であり，E′′。はサンプルから得られる何らかの統計量から求め3．情報と確率計画法られる事後分布を用いた場合の期待値を表す．上記の確率変動する対象の確率分布や実現値を確実に知ることができないような不完全情報下での確率計画問題
に対して，実現値に関する情報を得ることの価値について考えてみよう．例えば，確率変動要素がある確率分布のクラスに従って変動していることがわかっているが，確率分布を規定する母数が既知でないとする．
未知の母数が含まれている場合は，通常サンプルを集めて推定を行う．そこで，まず問題となるのは，費用をかけてサンプルを集めることの価値があるのかどうかである．もし，それだけの価値がなければ，サンプルを集める意味がない．その1つの基準が情報の価値である．ここでは，サンプル情報の期待価値（ExpectedValueofSampleInformation，EVSIと略す）と完全情報の期待価値（Expected Value of PerfectInformation，EVPIと略す）について考える．EVSIとは，事前分布あるいはその情報がない場合の最適意思決定の価値とサンプル情報からの事後分布を用いた場ような目的関数にのみ確率変動要素が現れる場合でも，EVSIやEVPIを求めることは一般に非常に困難である．通常，確率計画モデルに対する情報の価値は，その上界や下界を追求するのがやっとである．このためには，以下の関係は有用である．
」ensenの不等式（［7］）

￠（ズ）をズの凸関数とすると，Eを確率変数∈に関する期待値とし，E［ぞ］の存在を仮定するとE［￠ほ）］≧￠咋ほ］）が成り立つ．

■

このJensenの不等式を用いると2段階問題に関連する次の関係が示せる．

定理11段階目の目的関数がα，2段階目のリコー
ス費用関数が0（∬，ぞ），決定変数ズのとり得る実行可能解の集合5をもつ2段階問題を考える．このとき，次の不等式が成り立つ．

E［C（x（盲），E）］≧minE［C（x，E）］≧E［minC（x，E）］
∫∈5

∫∈5

≧minC（J，亨）
エ∈5合の最適意思決定の価値の差の期待値である．EVPI
ここで，∈が確率変動要素，且をこの引こ関する期待値© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

1996年9月号（37）507

とし，C（J，∈）＝α＋Q（∬，ど）とおき，ぞ＝Eほ］の存在をがわかっているが，その平均，分散は未知とする．こ

仮定した．また，J（盲）はC（ェ，盲）を最小にするズ∈5をの未知パラメータを大きさ〃のサンプルから信頼領示す．

■

域Sにより推定する．すなわち，

E［C（x，E）］＝CX＋E［Q（x，E）］なることおよびminm 5＝（（〃f，♂雪），才＝1，2，…，∽け（〃i一読）2／ざ号とEの順番に注意すれば，定理1のようなhere and∽（Ⅳ−1）

nowたる2段階問題では，EVPIは，この最適値
minE［C（x，E）］（定理1の不等式の第2辺）からwait

Ⅳ（〃一研）

andseeの場合の最適値の期待値E［minC（x，E）］（定理ズ芸′2（Ⅳ−1）

F霊▼椚（α／2），≦♂写

ズ芸′2（Ⅳ−1）（〃−1）5亨J∈5f＝1（〃−1）5ヲ

才＝1，2，…椚）エ∈51の第3辺）を引き算したものになる．従って，このここで，〃わ♂引ま∂の各要素∂fに対する平均と分散〃で，場合のEVPIの1つの上界として且［C（J（亨），∈）

石f，ポはそのサンプル平均とサンプル分散，ダ雲（γ）は自−minC（x，盲）を得る．決定変数，確率変数を各々平均に由度（れヴ）のダ分布の上側100γ％点，妨（♪）は自由関するもので代用して得られていることに注意したい．

度♪のカイ2乗分布の上側100γ％点であり，Sは，厳

一方，機会制約条件問題に対しては情報の価値を評

密には信頼係数100（1−α）％の信頼域の近似である

価すること自身いろいろな考え方があり，Blauのジレ（分散の推定は厳密には各成分の分散についての様なンマ［1］は有名である．すなわち，当然成り立つべき分離型にはならない）．Sにより限定された正規分布のだと思われるEVPI≧EVSIやEVPI，EVSIの非負性部分クラスを斤で示し，以下のミニマックスモデル賞が成り立たないとする例を示している．この辺りになを考える．

J∈5ってくると統計的意思決定理論と深くかかわってきて，1％：最小化Maximize cxF∈斤

いわゆるBayes派，非Bayes派の間の論争が避けて制約条件A∬＝∂，∬≧0通れないようである．

ところで，確率計画法というぐらいで，従来は 確

ここで，Fは∂の確率分布関数である．

率的 接近法が中心であった．しかし，確率変動要素

最小化Maximizeαは意思決定としてxをとったときの確率分布が既知であることは稀である．一方で，実の部分クラス斤の中で最悪の場合を想定したもので，際に解くには，確率分布が必要である．確率分布が全それを最小にするというゲーム理論的考え方に基づいくわからなければ，等価確定問題に変換することすらている．さらに，確率変動要素についてはhere andできない．従って，何らかの確率分布の推定，あるいnowの立場から2次リコースをもつ2段階問題鳥をは分布のクラスがわかっているのなら，その母数の推考えることになる．

定が必要である．このためには，サンプルを用いて，

島：最小化

F∈斤m

統計的推定・検定，さらには，多変量解析の理論を駆使することが必須となるであろう．この 統計的Maximize（諾（cx＋／…／∑u）t（AiX−ti）2i＝1
F∈斤なddF（Jl，ち，…′m））

確率計面法の取り扱いのはしりには既出の］．Braken
andR．M．Soland［2］やR．Jagannathan［6］があるが，本格的研究は最近であり，JatikaDupacovaやその一派のT．Cipraおよび森田等によるものがある（森日引こよる本誌での紹介［9］が詳しい）．

制約条件∬≧0

ここで，ぴfは2次リコースを規定する定数である．
この他のミニマックスモデルとしては，もっと条件が簡単な連続型ナップサック問題，目的関数の係数を推定する問題なども考えている（詳しくは［9］参確率分布の母数が未知の場合の森田等によるモデル

についてここで紹介する．次の線形計画問題昂を考える．

照）．

この連続型ナップサック問題は以下のように機会制
約条件問題吾が基になっており，0（乃2log乃）の計算手汽：・最′j、化α間で解くことができる．

制約条件Aェ＝∂，J≧0
ここで，A，∂，Cは各々椚×犯行列，∽次元縦ベクト
ル乃次元横ベクトル，∬は乃次元縦ベクトルで決定変賞：最小化 ′／I

制約条件 Pr（∑cJみ≦／）≧αノ＝1／J

数，0は成分が零のみからなる乃次元縦ベクトルとし，∑αJ∬ノ＝占，0≦JJ≦∂J，ノ＝1，2，…乃
l■＝l∂のみが確率変動要素で，多変量正規分布に従うこと
508（38）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

ただし，C＝（cJ）は正規分布に従う確率変数である．

ものにしておられる．

さらには，逐次的にサン70ルが得られ，問題自身お最後にこれからの研究課題，応用課題であるが，なよび最適解も変化するadaptiveな確率計画モデルもんといっても実際の解法が問題で，離散近似やシナリ考えられている［9］．推定や予測を用いるモデルではオ統合とかいろいろ考えられているが，もっと工夫が対応する確定問題として，非線形問題のあらゆるタイいる．

プのものがと1＿iてくる．従って，実際に解く段になると参考文献

非線形計画の手法を駆使する必要がある．例えば，条件式を回帰を用いて推定する問題では，確定問題とし［1］Blau，R．A． Stochastic programming and deci−ては逆凸計画問題となる．一方で，等価確定問題に変sion analysis：An apparent dillemma， Man．Sci．

換しないで解く試みもあり，その場合は確率的劣勾配，21（1974）271−276．

確率的準勾配（stochastic subgradient，StOChastic［2］Braken，］．B．andR．M．Soland， Statisticaldeci−quasi−gradient）を用いる方法が一般的であるが，このSion analysIS Of■ stochasticlinear programmlng

ときは確率近似法との関連憎三が出てくる．

problems， Nav．Res．Log．Quart．13（1966）205−225．
［3］Charnes，A．and W．W．Cooper，

4．おわりにChance con−strainedprogramming：Man．Sci．6（1959）73−79．

確率計画法では離散決定変数の方が連続決定変数よ［4］Freund，R．），， Theintroduction of riskinto a

りも確率計算がやりやすいことがある．バブルがはじprogramming model，

けて，最近は投資熱ももう1つのようであるが，投資263．

Econometrica，24（1956）253−［5］Ishii，H．et al．，の問題も確率計画法，特に確率的組合せ最適化の応用

1em，の1つと考えられる．もちろん，投資にはいろいろな接近法があI），確率計画がすべてではないが，情報がstochastic spanning tree prob−

Discrete AppliedMathematics3（1981）76−85．

［6］Jagannathan，R．，

Use of sampleinformationin

重要である点から，少なくとも3節での話が有用では

StOChastic recourse and chance constrained pro−ないかと思っている．実際，経済の分野でのこれまで

grammingmodels，Man．Sci．31（1985）96108．

［7］Jensen，］．L．W．Ⅴ．， Surlesfonctionsconvexesetのポートフォリオ問題は確率計画問題として考えられてきたものも多い．また，一見意外かもしれないが，lesinさgalitさs entreles valeurs moyennes，農業問題への応用もある．有名なFreundのモデル［4］Math．30（1906）175193．
［8］Madansky，A．M．， Inequalities for stochastic

は米国北カロライナ州東部のある典型的な穀物最適生産問題を確率計画問題として取り上げている．

じゃがいも，とうもろこし，肉牛，秋キャベツの4種類について，期間1から期間3まで考え，土地制約，労働力制約，資金制約の下，期待効用関数を最大にする作付けを求めている．農業こそはお天気まかせの動確率変に左右されるからであろうか？ また，我が国でも，農林水産省の南石氏が盛んに農業問題への応用を

Acta・

linear programming problem，Man．Sci．6（1960）

197−204．

［9］森臼l浩 確率計画法とサンプル情報， オペレー
ションズ・リサーチ，37（1992）88−92．

［10］Walkup，D．W．and R．］．B．Wets，
programmingwith recourse，

siam．J．on Applied

Math．15（1967）12991314．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

1996年9 月号

stochas（39）509