(57)【特許請求の範囲】
【請求項１】
問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定手段と、数式１で表される確率計画問題Ｐ０を用いて前記問題集合Ｐ＝{Ｐ０}に設定する問題設定手段と、前記問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断手段と、前記問題集合Ｐから問題ＰＭを選択すると共に前記問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択手段と、前記問題ＰＭの求解を行うと共に実行可能解がない場合に前記空集合判断手段に処理を移行させる最適解求解手段と、前記問題ＰＭの最適解をχｉ＊，θｉ＊（ただし、ｉ＝１，２，…，ｍ２）とする最適解設定手段と、全ての変数ｉについてθｉ＊≧Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]の場合に前記空集合判断手段に処理を移行させる最適解判断手段と、入札変数χｉの定義域χｉ∈[ξｉｊ，ξｉｋ＋１]においてθｉ＊＜Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]を満たす前記変数ｉを選択する第一の探索手段と、前記選択された変数ｉの下でχｉ＊∈[ξｉｓ，ξｉｓ＋１]を満たす最大のｓ（ただし、ｊ≦ｓ≦ｋ）を求める第二の探索手段と、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定手段と、前記問題ＰＭに制約θｉ≧Ｌｉｊ，ｓ＋１(χｉ)及びχｉ≦ξｉｓ＋１を追加した問題を問題ＰＮ＋１とすると共に前記問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，前記問題番号Ｎ＝Ｎ＋１とする第一の子問題設定手段と、前記問題ＰＭに制約ξｉｓ＋１≦χｉを追加すると共にｋ＜|Ξｉ|の場合にはθｉ≧Ｌｉｓ＋１，ｋ＋１(χｉ)を更に追加した問題を問題ＰＮ＋１とすると共に前記問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，前記問題番号Ｎ＝Ｎ＋１とする第二の子問題設定手段とを有することを特徴とする確率計画問題求解装置。
【数１】
0004981559.tif 000069
ただし、Ａ：ｍ１×ｎ１次元行列，ｃ：ｎ１次元列ベクトル，ｂ：ｍ１次元列ベクトル，
ｘ：第一段階変数であってｎ１次元変数ベクトル，Ｔ：ｍ２×ｎ１次元行列，
ξ'：確率変数であってｌ次元列ベクトル，ξ：確率変数ξ'の実現値，
Ξ：確率変数ξ'の台，ｑ：ｎ２次元列ベクトル，
ｙ(ξ)：第二段階変数であってｎ２次元変数ベクトル，
χ：入札変数，θｉ：Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]の上界，
ψ'：リコース関数，ｐｉｓｉ：確率変数ξ'ｉがξｉｓｉとなる確率，
ｍ１：第一段階の制約個数，ｎ１：第一段階変数の個数，
ｍ２：第二段階の制約個数，ｎ２：第二段階変数の個数，
ｌ：確率変数ベクトルの次元，
ｉ：第二段階制約のいずれであるかを表す識別子である添字，
ｓｉ：第二段階制約ｉに含まれる確率変数ξ'のとり得る値の数
をそれぞれ表す。
また、問題Ｐ０に分枝操作を加えることによって得られる子問題ＰＭにおいて、
入札変数χｉの定義域に関する制約χｉ∈[ξｉｊ，ξｉｋ＋１]と
分散に対する下界制約θｉ≧Ｌｉｊ，ｋ＋１(χｉ)とが与えられている。
ｊ，ｋ：第二段階制約ｉに含まれる確率変数ξ'のとり得る値の番号，
Ｌ：下界を与える凸関数  をそれぞれ表す。
なお、上付の┬：ベクトルの転置，
ｍｉｎ：最小値の関数，Ｖａｒ：分散  をそれぞれ意味する。
【請求項２】
確率計画問題の最適解を求める際に、少なくとも、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定手段、数式１で表される確率計画問題Ｐ０を用いて前記問題集合Ｐ＝{Ｐ０}に設定する問題設定手段、前記問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断手段、前記問題集合Ｐから問題ＰＭを選択すると共に前記問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択手段、前記問題ＰＭの求解を行うと共に実行可能解がない場合に前記空集合判断手段に処理を移行させる最適解求解手段、前記問題ＰＭの最適解をχｉ＊，θｉ＊（ただし、ｉ＝１，２，…，ｍ２）とする最適解設定手段、全ての変数ｉについてθｉ＊≧Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]の場合に前記空集合判断手段に処理を移行させる最適解判断手段、入札変数χｉの定義域χｉ∈[ξｉｊ，ξｉｋ＋１]においてθｉ＊＜Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]を満たす前記変数ｉを選択する第一の探索手段、前記選択された変数ｉの下でχｉ＊∈[ξｉｓ，ξｉｓ＋１]を満たす最大のｓ（ただし、ｊ≦ｓ≦ｋ）を求める第二の探索手段、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定手段、前記問題ＰＭに制約θｉ≧Ｌｉｊ，ｓ＋１(χｉ)及びχｉ≦ξｉｓ＋１を追加した問題を問題ＰＮ＋１とすると共に前記問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，前記問題番号Ｎ＝Ｎ＋１とする第一の子問題設定手段、前記問題ＰＭに制約ξｉｓ＋１≦χｉを追加すると共にｋ＜|Ξｉ|の場合にはθｉ≧Ｌｉｓ＋１，ｋ＋１(χｉ)を更に追加した問題を問題ＰＮ＋１とすると共に前記問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，前記問題番号Ｎ＝Ｎ＋１とする第二の子問題設定手段としてコンピュータを機能させることを特徴とする確率計画問題求解プログラム。
【請求項３】
電源計画問題求解装置における電源計画問題求解方法であって、電源計画問題求解装置のコンピュータが、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定ステップと、数式２で表される電源計画問題を問題Ｐ０として前記問題集合Ｐ＝{Ｐ０}に設定する問題設定ステップと、前記問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断ステップと、前記問題集合Ｐから問題ＰＭを選択すると共に前記問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択ステップと、前記問題ＰＭの求解を行うと共に実行可能解がない場合に前記空集合判断ステップに処理を移行させる最適解求解ステップと、前記問題ＰＭの最適解をχｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）とする最適解設定ステップと、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の場合に前記空集合判断ステップに処理を移行させる最適解判断ステップと、入札変数χｊの定義域χｊ∈[ξｊｒ，ξｊｋ＋１]においてθｊ＊＜Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]を満たす前記変数ｊを選択する第一の探索ステップと、前記選択された変数ｊの下でχｊ＊∈[ξｊｓ，ξｊｓ＋１]を満たす最大のｓ（ただし、ｒ≦ｓ≦ｋ）を求める第二の探索ステップと、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定ステップと、前記問題ＰＭに制約θｊ≧Ｌｊｒ，ｓ＋１(χｊ)及びχｊ≦ξｊｓ＋１を追加した問題を問題ＰＮ＋１とすると共に前記問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，前記問題番号Ｎ＝Ｎ＋１とする第一の子問題設定ステップと、前記問題ＰＭに制約ξｊｓ＋１≦χｊを追加すると共にｋ＜|Ξｊ|の場合にはθｊ≧Ｌｊｓ＋１，ｋ＋１(χｊ)を更に追加した問題を問題ＰＮ＋１とすると共に前記問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，前記問題番号Ｎ＝Ｎ＋１とする第二の子問題設定ステップとを有することを特徴とする電源計画問題求解方法。
【数２】
0004981559.tif 000070
ただし、ｉ：新設発電所の識別子（ｉ＝１，２，…，ｎ１），
ｊ：負荷領域又は需要領域の識別子（ｊ＝１，２，…，ｍ１），
ｇｉ：新設発電所ｉを建設するための容量当たりの費用（円／ＭＷ），
ｗｉ：第一段階変数であって新設発電所ｉの容量（ＭＷ）
ｃｉ：新設発電所ｉの運転費用（円／ＭＷｈ），
ｔｊ：負荷領域ｊの持続時間（ｈ），
ｘｉｊ：新設発電所ｉの需要領域ｊにおける出力（ＭＷ），
ｑｊ：既存発電所の需要領域ｊにおける運転費用（円／ＭＷｈ），
ｙｊ(ξｊ)：第二段階変数であって既存発電所の需要領域ｊにおける出力
（ＭＷ）
ξ'ｊ：確率変数であって需要領域ｊの需要量（ＭＷ）
（ξ'＝(ξ'１，ξ'２，…，ξ'ｍ１)と表す），
ξ：確率変数である需要量ξ'の実現値であって需要量のシナリオ
（ξ＝(ξ１，ξ２，…，ξｍ１)と表す），
Ξｊ：確率変数である需要量ξ'ｊのとり得る値の集合
（ξ'の台ΞはΞ＝Ξ１×Ξ２×…×Ξｍ１），
λ：リスク尺度パラメータ，ψ：リコース関数
をそれぞれ表す。
また、電源計画問題に分枝操作を加えることによって得られる子問題ＰＭにおいて、
入札変数χｊの定義域に関する制約χｊ∈[ξｊｒ，ξｊｋ＋１]と
分散に対する下界制約θｊ≧Ｌｊｒ，ｋ＋１(χｊ)とが与えられている。
χｊ：ｘｉｊのｊ＝１からｍ１までの合計，
ｒ，ｋ：第二段階制約ｊに含まれる確率変数ξ'のとり得る値の番号，
Ｌ：下界を与える凸関数  をそれぞれ表す。
θｊ：λＶａｒ[ψ(ｗ，ξ')]を表し、θｊ≧０である。
なお、ｍｉｎ：最小値の関数，Ｅ：期待値，Ｖａｒ：分散  をそれぞれ意味する。
【請求項４】
問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定手段と、数式２で表される電源計画問題を問題Ｐ０として前記問題集合Ｐ＝{Ｐ０}に設定する問題設定手段と、前記問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断手段と、前記問題集合Ｐから問題ＰＭを選択すると共に前記問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択手段と、前記問題ＰＭの求解を行うと共に実行可能解がない場合に前記空集合判断手段に処理を移行させる最適解求解手段と、前記問題ＰＭの最適解をχｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）とする最適解設定手段と、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の場合に前記空集合判断手段に処理を移行させる最適解判断手段と、入札変数χｊの定義域χｊ∈[ξｊｒ，ξｊｋ＋１]においてθｊ＊＜Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]を満たす前記変数ｊを選択する第一の探索手段と、前記選択された変数ｊの下でχｊ＊∈[ξｊｓ，ξｊｓ＋１]を満たす最大のｓ（ただし、ｒ≦ｓ≦ｋ）を求める第二の探索手段と、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定手段と、前記問題ＰＭに制約θｊ≧Ｌｊｒ，ｓ＋１(χｊ)及びχｊ≦ξｊｓ＋１を追加した問題を問題ＰＮ＋１とすると共に前記問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，前記問題番号Ｎ＝Ｎ＋１とする第一の子問題設定手段と、前記問題ＰＭに制約ξｊｓ＋１≦χｊを追加すると共にｋ＜|Ξｊ|の場合にはθｊ≧Ｌｊｓ＋１，ｋ＋１(χｊ)を更に追加した問題を問題ＰＮ＋１とすると共に前記問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，前記問題番号Ｎ＝Ｎ＋１とする第二の子問題設定手段とを有することを特徴とする電源計画問題求解装置。
【請求項５】
電源計画問題の最適解を求める際に、少なくとも、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定手段、数式２で表される電源計画問題を問題Ｐ０として前記問題集合Ｐ＝{Ｐ０}に設定する問題設定手段、前記問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断手段、前記問題集合Ｐから問題ＰＭを選択すると共に前記問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択手段、前記問題ＰＭの求解を行うと共に実行可能解がない場合に前記空集合判断手段に処理を移行させる最適解求解手段、前記問題ＰＭの最適解をχｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）とする最適解設定手段、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の場合に前記空集合判断手段に処理を移行させる最適解判断手段、入札変数χｊの定義域χｊ∈[ξｊｒ，ξｊｋ＋１]においてθｊ＊＜Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]を満たす前記変数ｊを選択する第一の探索手段、前記選択された変数ｊの下でχｊ＊∈[ξｊｓ，ξｊｓ＋１]を満たす最大のｓ（ただし、ｒ≦ｓ≦ｋ）を求める第二の探索手段、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定手段、前記問題ＰＭに制約θｊ≧Ｌｊｒ，ｓ＋１(χｊ)及びχｊ≦ξｊｓ＋１を追加した問題を問題ＰＮ＋１とすると共に前記問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，前記問題番号Ｎ＝Ｎ＋１とする第一の子問題設定手段、前記問題ＰＭに制約ξｊｓ＋１≦χｊを追加すると共にｋ＜|Ξｊ|の場合にはθｊ≧Ｌｊｓ＋１，ｋ＋１(χｊ)を更に追加した問題を問題ＰＮ＋１とすると共に前記問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，前記問題番号Ｎ＝Ｎ＋１とする第二の子問題設定手段としてコンピュータを機能させることを特徴とする電源計画問題求解プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、確率計画問題求解装置及びプログラム、並びに、電源計画問題求解方法、装置及びプログラムに関する。さらに詳述すると、本発明は、最適値の分散を目的関数に含む確率計画問題の最適解を求める技術に関する。
【背景技術】
【０００２】
不確実な状況下であって最適値が分散を有する場合の最適化即ち最適解を求める従来の方法として確率計画法がある（非特許文献１）。そして、確率計画法で扱う代表的モデルに、確率変数の値によって制約侵犯が起こった場合の罰金に対する償還請求（リコースとも呼ばれる）を有する確率計画問題（二段階モデルとも呼ばれる）がある。
【０００３】
このモデルでは、定式化に確率変数を含み二段階の意思決定を行う。例えば、確率変数として与えられる不確定の需要量を満たす生産計画を立てる場合には、需要確定前に生産する量を第一段階決定変数とし、需要の値が確定した後に需要の変動に応じて不足分を追加で生産する量を第二段階決定変数とする。すなわち、第一段階決定変数は確率変数の値によらないのに対し、第二段階決定変数は確率変数の値に応じて第二段階の追加費用最適化問題を解くことによって決定される。したがって、全体として数式１に示す目的関数を最小化する解を求めることになる。
【０００４】
（数１）  最小化：(第一段階費用)＋(第二段階費用の期待値)
【０００５】
【非特許文献１】Ｇ.Ｂ.Ｄantzig：Ｌinear  Ｐrogramming  under  uncertainty，Ｍanagement  Ｓcience，Vol.１，pp.197−206，1955年．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来のように期待値を基準とする最適化では、第二段階費用のばらつきを考慮した最適解を求めることはできない。このため、確率変数のとり得る値によっては需要の変動のために費用が非常に大きくなってしまうリスクが存在することになり、どのような状況に対しても適切な解を求めることができるとは言えない。
【０００７】
そこで、ばらつきの小さい解を求めるためにばらつきによるペナルティを目的関数に加えた最適化モデルを用いることが望ましい。
【０００８】
ここで、ばらつきの指標として分散を用いた場合は、単なる確率変数の分散を考慮するのではなく第二段階問題の最適値関数の分散を考慮するので、目的関数を第一段階変数の関数として表すと非凸関数になる。すなわち、第二段階問題の最適値の分散を目的関数に含めると、目的関数は区分的には第一段階変数の凸二次関数であるが全体としては非凸関数となるので解を求めることが困難になる。
【０００９】
ここで、目的関数が区分的には第一段階変数の凸二次関数であって全体としては非凸関数である場合には、目的関数が凸二次関数になるように決定変数を全ての区間に分割して各区間での最適値を列挙する方法が考えられる。しかしながら、問題に含まれる確率変数の個数や確率変数がとり得る値が大きくなると列挙すべき個数が膨大となり、列挙法は効率的でなく有効とは言えない。
【００１０】
そこで、本発明は、確率計画問題において最適値の分散を考慮して目的関数が全体として非凸関数である場合に効率的に厳密解を求めることができる確率計画問題求解装置及びプログラムを提供することを目的とする。また、本発明は、電源計画問題において最適値の分散を考慮して目的関数が全体として非凸関数である場合に効率的に厳密解を求めることができる電源計画問題求解方法、装置及びプログラムを提供することを目的とする。
【００１１】
なお、本発明において、厳密解とは、確率計画問題において、実行可能解のうち最も適切な値を与える解のことを指す。具体的には、従来の解法で与えられる解よりも、標準偏差が同じ場合に期待値が小さい解のことを、また、期待値が同じ場合に標準偏差が小さい解のことを指す。
【課題を解決するための手段】
【００１２】
以下、本明細書では、数式中の一部の文字を本文中においては表１に示すとおりに置き換える。
【００１３】
【表１】
0004981559.tif 000002
【００１４】
本発明者は、確率計画問題において最適値の分散を考慮して目的関数が全体として非凸関数である場合に効率的に厳密解を求める方法を開発するために以下の検討を行った。
【００１５】
罰金の償還請求への期待値を含む目的関数を最小化する確率計画問題ＳＰＲ（Ｓtochastic  Ｐrogramming  with  Ｒecourse の略）を数式２の通りに定義する。
【００１６】
【数２】
0004981559.tif 000003
なお、上付の┬：ベクトルの転置，Ｅ：期待値の関数，ｍｉｎ：最小値の関数をそれぞれ意味する。
【００１７】
ｍ１×ｎ１次元行列Ａ，ｎ１次元列ベクトルｃ，ｍ１次元列ベクトルｂは確定値として与えられている。これらに関連するｎ１次元変数ベクトルｘは第一段階変数と呼ばれる。
【００１８】
また、ｌ次元列ベクトルξ'は確率変数であり、その台をΞとし、ξをξ'の実現値とする。ξ'の実現値ξに対し、ｎ２次元列ベクトルｑ(ξ)，ｍ２×ｎ１次元行列Ｔ(ξ)，ｍ２次元列ベクトルｈ(ξ)の値が定まる。
【００１９】
また、ｎ２次元変数ベクトルｙ(ξ)は第二段階変数と呼ばれる。ｍ２×ｎ２次元行列Ｗはリコース行列と呼ばれる。
【００２０】
リコース関数Ｑ(ｘ，ξ)を定義する線形計画問題は第二段階問題或いはリコース問題と呼ばれる。関数Ｑ_(ｘ)はリコース関数Ｑ(ｘ，ξ)の期待値を表す。
【００２１】
上記確率計画問題ＳＰＲの決定においては、まず、第一段階として変数ｘを決定し、その後、確率変数ξ'の実現値ξを観測する。
【００２２】
確率変数ξ'の変動に応じて制約条件Ｗｙ(ξ)＝ｈ(ξ)−Ｔ(ξ)ｘを満足させるように第二段階変数ｙ(ξ)（≧０）を決定する。列ベクトルｑ(ξ)は第二段階変数ｙ(ξ)に対する罰金である。
【００２３】
第一段階で決定ｘを行い、確率変数の実現値ξを観測したときの罰金への償還請求を表すリコース関数Ｑ(ｘ，ξ)の値は線形計画問題を解くことによって求められる。確率計画問題ＳＰＲの目的関数は、第一段階で生じる費用ｃ┬ｘと数式３で表されるリコース関数の期待値Ｑ_(ｘ)との総和となる。
【００２４】
【数３】
0004981559.tif 000004
【００２５】
確率変数ξ'が有限な離散分布に従うと仮定し、そのとり得る値をシナリオと呼ぶ。シナリオの集合をΞ＝{ξ１，ξ２，…，ξＳ}とし、ξ１，ξ２，…，ξＳ＞０が成り立つものとする。なお、変数Ｓはすなわちシナリオの数である。
【００２６】
確率変数ξ'がξ'＝ξｓとなる確率をｐｓ＝Ｐｒｏｂ[ξ'＝ξｓ]（ただし、ｓ＝１，２，…，Ｓ）とする。このとき、確率計画問題ＳＰＲは数式４に示す確率計画問題ＳＰＲ’のように表される。
【００２７】
【数４】
0004981559.tif 000005
【００２８】
そして、第二段階変数ｙ(ξｓ)をｙｓに置き換え、リコース問題に含まれるｑ(ξｓ)，Ｔ(ξｓ)，ｈ(ξｓ)をそれぞれｑｓ，Ｔｓ，ｈｓに置き換え、目的関数に含まれるリコース関数Ｑ(ｘ，ξｓ)を数式５に置き換えることにより、確率計画問題ＳＰＲ’は数式６に示す確率計画問題ＤＥＰ−ＳＰＲに再定式化される。
【００２９】
【数５】
0004981559.tif 000006
【００３０】
【数６】
0004981559.tif 000007
【００３１】
確率計画問題ＳＰＲ’から確率計画問題ＤＥＰ−ＳＰＲへの変換は等価であり、確率計画問題ＤＥＰ−ＳＰＲの最適解ｘ＊，ｙ１＊，ｙ２＊，…，ｙＳ＊において、ｙｓ＊（ただし、ｓ＝１，２，…，Ｓ）はリコース問題Ｑ(ｘ＊，ξｓ)＝ｍｉｎ{ｑ(ξｓ)┬ｙ(ξｓ)｜Ｗｙ(ξｓ)＝ｈ(ξｓ)−Ｔ(ξｓ)ｘ，ｙ(ξｓ)≧０}の最適解となる。なお、確率計画問題ＤＥＰ−ＳＰＲは確率計画問題ＳＰＲ’の等価確定問題と呼ばれる。
【００３２】
ここで、リコース費用のリスクを考慮したモデルとして、第二段階費用のばらつきに対する罰金を目的関数に含めたモデルが提案されている（Ｊ.Ｍ.Ｍulvey，Ｒ.Ｊ.Ｖanderbei  and  Ｓ.Ａ.Ｚenios：Ｒobust optimization of large-scale systems，Ｏperations Ｒesearch，Vol.43，pp.264−281，1995年）。
【００３３】
このモデルは全体として数式７に示す目的関数を最小化する解を求める。
【００３４】
（数７）  最小化：(第一段階費用)＋(第二段階費用の期待値)
＋λ×(第二段階費用のばらつき)
【００３５】
このモデルでは、ばらつきに対する罰金に正の値のパラメータλ(＞０)を掛けて目的関数に組み込むことにより、パラメータλの値によってはばらつきが抑制されることが期待される。ばらつきを考慮した二段階確率計画モデルＳＰＲ−Ｖを数式８に示す。
【００３６】
【数８】
0004981559.tif 000008
【００３７】
ｆ：ＲＳ→Ｒはリコース費用のばらつきを表す関数である。ばらつきを示すリスク尺度ｆとしては、分散，平均絶対偏差，上方半分散などが考えられる。Ｑｓ(ｘ)をｑｓ┬ｙｓに置き換えると二段階確率計画モデルＳＰＲ−Ｖは数式９に示す緩和問題ＲＳＰＲ−Ｖに変換される。
【００３８】
【数９】
0004981559.tif 000009
【００３９】
二段階費用の期待値のみを含む従来の確率計画モデルとは異なり、ばらつきを考慮したモデルの場合は、二段階確率計画モデルＳＰＲ−Ｖと緩和問題ＲＳＰＲ−Ｖとは等価ではなく、緩和問題ＲＳＰＲ−Ｖは二段階確率計画モデルＳＰＲ−Ｖの緩和問題となる。緩和問題ＲＳＰＲ−Ｖの最適解をｘ＊，ｙ１＊，…，ｙＳ＊とすると、ｙｓ＊が数式１０に示すリコース問題Ｑ(ｘ＊，ξｓ)の最適解にならない可能性がある。
【００４０】
【数１０】
0004981559.tif 000010
【００４１】
なお、解が一致しないのは、ばらつきの指標ｆによってはリコース問題の目的関数値を増やした方がばらつきの抑制につながる場合があるためである。すなわち、リコース問題で最小費用の解ではなく敢えて費用の高い解にした方がばらつきが抑えられ、その結果緩和問題ＲＳＰＲ−Ｖの全体としての目的関数がより改善されるという現象が起き、数式１０に示すリコース問題Ｑ(ｘ＊，ξｓ)の最適解と一致しないということが起こり得る。
【００４２】
そして、本発明は、単純リコース型の確率計画問題に対して分散を考慮した二段階モデルを対象とする。
【００４３】
上述の確率計画問題ＳＰＲにおいて、リコース問題に含まれる目的関数係数と一段階変数に関する制約行列とが確率変数ξ'によらない場合、すなわち、ｑ(ξ)≡ｑ(＞０)，Ｔ(ξ)≡Ｔであり且つｈ(ξ)≡ｈであってリコース行列Ｗが条件Ｗ＝(Ｉ，−Ｉ)を満たす場合を考える。
【００４４】
このとき、確率変数ξ'はｍ２次元ベクトルであり、リコース問題に含まれる第二段階変数の個数はｎ２＝２×ｍ２となる。
【００４５】
第二段階変数ベクトルｙ(ξ)をｙ(ξ)┬＝(ｙ(ξ)＋┬，ｙ(ξ)−┬)とすると、非負条件ｙ(ξ)≧０はｙ(ξ)＋≧０，ｙ(ξ)−≧０となる。リコース問題の目的関数の係数ベクトルｑ＞０はｑ┬＝(ｑ＋┬，ｑ−┬)と表すことができる。
【００４６】
前述と同様に確率変数ξ'の分布の台をΞとすると、確率計画問題ＳＰＲを数式１１に示す単純リコース型の確率計画問題ＳＰＲＳとして表すことができる。
【００４７】
【数１１】
0004981559.tif 000011
【００４８】
特にｑ−＝０であるとき、リコース変数ｙ(ξ)−は第二段階問題から消去できるので、リコース関数Ｑ(ｘ，ξ)は数式１２に示す通りに書くことができる。
【００４９】
【数１２】
0004981559.tif 000012
【００５０】
この場合、確率変数ξ'と第一段階の決定Ｔｘの大小関係のみが問題となり、ｑ＋＞０より、ξ−Ｔｘ＜０の場合はｙ(ξ)＋＝０が第二段階問題の最適解となり、ξ−Ｔｘ≧０の場合はｙ(ξ)＋＝ξ−Ｔｘが第二段階問題の最適解となる。
【００５１】
このとき、新たな変数χ＝Ｔｘを導入する。変数χは入札変数と呼ばれ、リコース関数Ｑ(ｘ，ξ)は入札変数χを変数とする関数ψ(χ，ξ)の形式で数式１３のように表すことができる。
【００５２】
【数１３】
0004981559.tif 000013
【００５３】
同様に、数式３で表されるリコース関数の期待値Ｑ_(ｘ)も入札変数χを変数とする関数Ψ(χ)として数式１４のように表すことができる。
【００５４】
【数１４】
0004981559.tif 000014
【００５５】
また、数式１５に示すとおり、数式１３で表される入札変数χを変数とするリコース関数はχ┬＝(χ１，χ２，…，χｍ２)┬の成分毎に分離可能である。
【数１５】
0004981559.tif 000015
【００５６】
そして、確率変数ベクトルξ'＝(ξ'１，ξ'２，…，ξ'ｍ２)の各成分ξ'ｉ（ただし、ｉ＝１，２，…，ｍ２）が有限な離散分布に従うものとし、確率変数ξ'ｉの分布の台をΞｉ＝{ξｉ１，ξｉ２，…，ξｉ|Ξｉ|}（ただし、|Ξｉ|＜∞）とする。
【００５７】
そして、次の仮定Ｉ及び仮定IIを仮定する。
仮定Ｉ）確率変数ベクトルξ'の各成分ξ'ｉ（ただし、ｉ＝１，２，…，ｍ２）は有限な離散分布に従い、互いに独立であるものとする。
【００５８】
仮定II）ξ'ｉ＝ξｉｓｉとなる確率をＰｒｏｂ[ξ'ｉ＝ξｉｓｉ]＝ｐｉｓｉ＞０（ただし、ｓｉ＝１，２，…，|Ξｉ|）とする。確率変数ξ'ｉのとり得る値は全て正であり、上に有界である。すなわち、０＜ξｉ１，ξｉ２，…，ξｉ|Ξｉ|＜∞とする。
【００５９】
確率変数ベクトルξ'の台ΞはΞ＝Ξ１×Ξ２×…×Ξｍ２と示すことができる。仮定Ｉ及び仮定IIより、確率変数ベクトルξ'がξ'＝ξｓとなる確率は、ξｓを数式１６に示す通りとすると、各確率変数ξ'ｉがξｉｓｉとなる確率を掛け合わせることによって、具体的には数式１７によって求められる。
【００６０】
【数１６】
0004981559.tif 000016
【００６１】
【数１７】
0004981559.tif 000017
【００６２】
数式１７より、入札変数χを変数とするリコース関数の期待値Ψ(χ)も数式１８に示すようにχ┬＝(χ１，χ２，…，χｍ２)の成分毎に分離可能である。
【００６３】
【数１８】
0004981559.tif 000018
【００６４】
以上より、確率計画問題ＳＰＲＳは仮定Ｉ及び仮定IIの下でｑ−＝０の場合、数式１９に示す確率計画問題ＳＰＲＳＴへと変換することができる。
【００６５】
【数１９】
0004981559.tif 000019
なお、ｙ(ξ)ｉ≡ｙ(ξ)ｉ＋，ｑｉ≡ｑｉ＋と書き直している。
【００６６】
そして、仮定Ｉ及び仮定IIの下でｑ−＝０の場合において確率計画問題ＳＰＲより導かれた確率計画問題ＳＰＲＳＴを基に、リコース関数の分散を考慮した場合の定式化を行う。
【００６７】
入札変数χを変数とするリコース関数ψ(χ，ξ)はχｉ（ただし、ｉ＝１，２，…，ｍ２）毎に分離可能であって数式２０に示すように表されるので、ψｉ(χｉ，ξｉ)（ただし、ｉ＝１，２，…，ｍ２）の分散を目的関数に含む確率計画問題ＳＰＲＳＴ−Ｖを数式２１に示すように定義する。
【００６８】
【数２０】
0004981559.tif 000020
【数２１】
0004981559.tif 000021
【００６９】
上述の緩和問題ＲＳＰＲ−Ｖと同様に確率計画問題ＳＰＲＳＴ−Ｖの凸二次計画緩和問題ＲＳＰＲＳＴ−Ｖを数式２２のように定義することができる。
【００７０】
【数２２】
0004981559.tif 000022
【００７１】
続いて、入札変数χｉと確率変数ξ'ｉとに関するリコース関数ψｉ(ｘｉ，ξｉ)＝ｍｉｎ{ｑｉｙ(ξｓ)ｉ｜ｙ(ξｉｓ)ｉ≧ξｉｓ−χｉ，ｙ(ξｉｓ)ｉ≧０}（ただし、ｉ＝１，２，…，ｍ２）の期待値と分散とを導出する。
【００７２】
まず、ψｉ(χｉ，ξｉ)においてｑｉ＝１として数式２３が導出される。
【００７３】
【数２３】
0004981559.tif 000023
【００７４】
第二段階問題の目的関数の係数が正である（１と定めた）ので、数式２３で表されるリコース問題の最適解ｙ(ξｉｓ)ｉ＊は数式２４のようになる。
【００７５】
【数２４】
0004981559.tif 000024
【００７６】
数式２３で表されるリコース問題は、確率計画問題ＳＰＲＳＴ及びＳＰＲＳＴ−Ｖにおいて、需要に相当する確率変数ξｓに対して入札変数χｉの値を供給と考えると、需要に対する供給の不足分を第二段階変数によって補うものと解釈することができる。数式２３で表されるリコース関数の期待値は数式２５のように表される。
【００７７】
【数２５】
0004981559.tif 000025
【００７８】
また、リコース関数ψ'ｉ(χｉ，ξｉ)の分散は数式２６の通りに求められる。
【００７９】
【数２６】
0004981559.tif 000026
【００８０】
数式２６から数式２７が成り立つ。
【００８１】
【数２７】
0004981559.tif 000027
【００８２】
また、数式２８が成り立つ。
【００８３】
【数２８】
0004981559.tif 000028
【００８４】
また、確率変数ξ'ｉのとり得る値ξｉｓ（ただし、ｓ＝１，２，…，|Ξｉ|）について、一般性を失うことなしに、或いはシナリオの添字を付け替えることによって、ξｉ１≦ξｉ２≦…≦ξｉ|Ξｉ|が成立するものとする。これより、ξｉｓ≧χｉを満たすシナリオの集合｛ｓ｜ξｉｓ≧χｉ｝が固定される範囲即ちχｉ∈(ξｉｓ，ξｉｓ＋１]（ただし、ｓ＝１，２，…，|Ξｉ|−１）においてリコース関数ψ'ｉ(χｉ，ξｉ)の分散Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]はχｉの凸二次関数になる。
【００８５】
続いて、χｉ∈[０，∞)におけるＶａｒ[ψ'ｉ(χｉ，ξ'ｉ)]の形状を検証する。
【００８６】
まず、χｉ∈[０，ξｉ１]の場合は、Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]＝Ｖａｒ[ξｉ１−χｉ，ξｉ２−χｉ，…，ξｉ|Ξｉ|−χｉ]＝Ｖａｒ[ξｉ１，ξｉ２，…，ξｉ|Ξｉ|]＝Ｖａｒ[ξ'ｉ]（これは定数）となる。
【００８７】
また、χｉ∈(ξｉｓ，ξｉｓ＋１]（ただし、ｓ＝１，２，…，|Ξｉ|−１）の場合は、｛ｓ｜ξｉｓ≧χｉ｝＝｛ｊ｜ｓ＋１≦ｊ≦|Ξｉ|｝であるので数式２９のようにおくと、Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]＝ａｉｓ(χｉ−ｇｉｓ)２＋ｈｉｓとなり、これは凸二次関数となる。
【００８８】
【数２９】
0004981559.tif 000029
【００８９】
さらに、χｉ∈(ξｉ|Ξｉ|，∞)の場合は、Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]＝Ｖａｒ[０，０，…，０]＝０となる。
【００９０】
以上より、Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]は区分的に数式３０のように定められる。
【００９１】
【数３０】
0004981559.tif 000030
【００９２】
また、Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]の連続性を検証する。
【００９３】
まず、区間χｉ∈(ξｉｓ−１，ξｉｓ]（ただし、ｓ＝２，３，…，|Ξｉ|）における右端の値Ｖｉｓ−１(ξｉｓ)を求めると数式３１の通りとなる。
【００９４】
【数３１】
0004981559.tif 000031
【００９５】
ｓ＝|Ξｉ|の場合は｛ｊ｜|Ξｉ|＋１≦ｊ≦|Ξｉ|｝を満たすシナリオｊは存在しないので、Ｖｉ|Ξｉ|−１(ξｉ|Ξｉ|)＝０となり、これはＶｉ|Ξｉ|(χｉ)のχｉ∈(ξｉ|Ξｉ|，∞)における値と等しい。
【００９６】
次に、区間χｉ∈(ξｉｓ，ξｉｓ＋１]（ただし、ｓ＝１，２，…，|Ξｉ|−１）におけるＶｉｓ(χｉ)のξｉｓへの右極限の値を求めると数式３２に示す通りになる。
【００９７】
【数３２】
0004981559.tif 000032
【００９８】
ｓ＝１の場合は数式３３の通りとなる。
【００９９】
【数３３】
0004981559.tif 000033
【０１００】
数式３１と数式３２とからＶｉｓ−１(ξｉｓ)＝ｌｉｍΔ→＋０Ｖｉｓ(ξｉｓ＋Δ)（ただし、ｓ＝１，２，…，|Ξｉ|）となって両者が一致することから、Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]はχｉ∈[０，∞)において連続であることが示された。
【０１０１】
Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]はχｉ∈[０，∞)において連続であることから、半開区間(ξｉｓ，ξｉｓ＋１]（ただし、ｓ＝１，２，…，|Ξｉ|−１）における分散を表す関数Ｖｉｓ(χ)は閉区間[ξｉｓ，ξｉｓ＋１]（ただし、ｓ＝１，２，…，|Ξｉ|−１）を定義域とする関数とみなすことができる。そして、ξｉ０≡０，ξｉ|Ξｉ|＋１≡∞と便宜的に定めると、[ξｉｓ，ξｉｓ＋１]（ただし、ｓ＝０，１，…，|Ξｉ|）上の関数へと拡張することができる。
【０１０２】
数式２９、及び、Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]はχｉ∈[０，∞)において連続であることから、数式３４に示す系が成り立つ。
【０１０３】
【数３４】
0004981559.tif 000034
【０１０４】
なお、数式３４に示す系が成り立つことは、まず、ｓ＝０の場合はａｉｓ＝０，ｈｉｓ＝Ｖａｒ[ξ'ｉ]となるのでＶｉ０＝ａｉ０(χｉ−ｇｉ０)２＋ｈｉ０が成り立つことから確かである。
【０１０５】
また、ｓ＝１，２，…，|Ξｉ|−１の場合は数式２６から明らかである。
【０１０６】
続いて、ｇｉｓ，ｈｉｓについては数式３５に示す関係が成り立ち、この関係から、ｇｉｓ≦ｇｉｓ＋１，ｈｉｓ≧ｈｉｓ＋１（ただし、ｓ＝０，１，…，|Ξｉ|−１）が得られる。
【０１０７】
【数３５】
0004981559.tif 000035
【０１０８】
確率計画問題ＳＰＲＳＴ−Ｖと凸二次計画緩和問題ＲＳＰＲＳＴ−Ｖとにおいて、制約Ａｘ＝ｂを含まず、Ｔ＝Ｉである場合を考える。この場合、第一段階変数ｘは消去され、入札変数χと第二段階変数とを有する問題に変換される。第一段階費用をｃ＝１、確率変数のとり得る値をΞ＝{２，４，６，８}、ｐ１＝ｐ２＝ｐ３＝ｐ４＝１／４、第二段階費用をｑ＝０．５、λ＝４とする。
【０１０９】
図３に示すように、期待値Ｅ[ψ'(χ，ξ')]のグラフは区分的線形の凸関数となる。一方、分散Ｖａｒ[ψ'(χ，ξ')]のグラフは、区間[２，８]においては区分的二次凸関数であるが、χの定義域全体[０，∞)では非凸関数になる。Ξに含まれる要素２，４，６，８の値を境界として分割してみると定義式からそれぞれの区間で数式３６を軸とする凸二次関数となる。
【０１１０】
【数３６】
0004981559.tif 000036
【０１１１】
また、図４に示すように、確率計画問題ＳＰＲＳＴ−Ｖの目的関数は非凸関数である。一方、凸二次計画緩和問題ＲＳＰＲＳＴ−Ｖの目的関数は凸関数であり、確率計画問題ＳＰＲＳＴ−Ｖの目的関数に対する下界を与えている。そして、凸二次計画緩和問題ＲＳＰＲＳＴ−Ｖの目的関数は、χ＜７では確率計画問題ＳＰＲＳＴ−Ｖの目的関数と一致しない。
【０１１２】
上述のとおり、確率計画問題ＳＰＲＳＴ−Ｖの目的関数は一般的には凸関数ではないが、変数のとり得る区間を制限することによって元問題を複数の凸二次計画問題へと分割することができる。
【０１１３】
入札変数χｉ（ただし、ｉ＝１，２，…，ｍ２）について区間χｉ∈[ξｓ，ξｓ＋１]（ただし、ｓ＝１，２，…，|ξｉ|）を全て列挙し、それぞれの区間でＶａｒ[ψ'ｉ(χｉ，ξ'ｉ)]＝Ｖｉｓ(χｉ)と与えることにより、確率計画問題ＳＰＲＳＴ−Ｖはχｉ∈[ξｓ，ξｓ＋１]において凸二次計画となる。
【０１１４】
したがって、全ての区間χｉ∈[ξｓ，ξｓ＋１]（ただし、ｓ＝１，２，…，|ξｉ|、及び、ｉ＝１，２，…，ｍ２）において確率計画問題ＳＰＲＳＴ−Ｖを解いて解を求めて比較することによって厳密解を求めることが可能になる。
【０１１５】
しかしながら、このような全列挙によると、列挙すべき区間の総数は数式３７で示す数になるので、計算の手間が非常に大きくなってしまう。
【０１１６】
【数３７】
0004981559.tif 000037
【０１１７】
そこで、入札変数のとり得る定義域を分割することによって全列挙と比べて少ない子問題を解くことにより、元問題の最適解を求めることができる。具体的には、入札変数χｉがとり得る定義域がχｉ∈[ξｉｊ，ξｉｋ＋１]（ただし、ｊ≦ｋ）に限定された子問題を解くことにより元問題の最適解を求める。
【０１１８】
この場合、確率計画問題ＳＰＲＳＴ−Ｖにおける分散項は、Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]＝Ｖｉｓ(χｉ)（ただし、χｉ∈[ξｓ，ξｓ＋１]、及び、ｓ＝ｊ，…，ｋ）となり、区間χｉ∈[ξｓ，ξｓ＋１]ではχｉの凸二次関数であるが、区間χｉ∈[ξｉｊ，ξｉｋ＋１]ではχｉの区分的二次関数であり、全体として非凸関数となる。そのため、確率計画問題ＳＰＲＳＴ−Ｖのχｉ∈[ξｉｊ，ξｉｋ＋１]（ただし、ｊ≦ｋ）における緩和問題を解く。
【０１１９】
緩和問題の条件は、元問題の実行可能解が緩和問題の実行可能解となること、及び、緩和問題の目的関数が元問題の目的関数の下界を与えることである。したがって、区間χｉ∈[ξｉｊ，ξｉｋ＋１]（ただし、ｊ≦ｋ）においてＶａｒ[ψ'ｉ(χｉ，ξ'ｉ)]＝Ｖｉｓ(χｉ)（ただし、χｉ∈[ξｓ，ξｓ＋１]、及び、ｓ＝ｊ，…，ｋ）の下界を与える関数を求める。
【０１２０】
関数Ｌｉｊ，ｋ＋１(χｉ)を以下のように定義する。
１）関数Ｌｉｊ，ｋ＋１(χｉ)は点(ξｉｊ，Ｖｉｊ(ξｉｊ))と(ｇｉｋ，Ｖｉｋ(ｇｉｋ))とを通る凸二次関数である。
２）関数Ｌｉｊ，ｋ＋１(χｉ)の軸はχｉ＝ｇｉｊである。
【０１２１】
関数Ｌｉｊ，ｋ＋１(χｉ)のχｉ２に対する係数をａ'ｉｊ，ｋ＋１とすると共に定数項をｈ'ｉｊ，ｋ＋１とすると、関数Ｌｉｊ，ｋ＋１(χｉ)は数式３８のように表すことができる。
【０１２２】
【数３８】
0004981559.tif 000038
【０１２３】
係数ａ'ｉｊ，ｋ＋１と定数項ｈ'ｉｊ，ｋ＋１とを数式３９のように定める。関数Ｌｉｊ，ｋ＋１(χｉ)は点(ξｉｊ，Ｖｉｊ(ξｉｊ))と(ｇｉｋ，Ｖｉｋ(ｇｉｋ))とを通るので数式３９を満たす。
【０１２４】
【数３９】
0004981559.tif 000039
【０１２５】
ｇｉｊ−ξｉｊ＝ｇｉｋ−ｇｉｊとなる場合には(ξｉｊ−ｇｉｊ)２＝(ｇｉｋ−ｇｉｊ)２となり、Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]の単調減少性よりＶｉｊ(ξｉｊ)＞Ｖｉｋ(ｇｉｋ)であるので、数式３９を満たすａ'ｉｊ，ｋ＋１とｈ'ｉｊ，ｋ＋１とは存在しない。したがって、ｇｉｊ−ξｉｊ≠ｇｉｋ−ｇｉｊの場合を考える。この場合には、数式３９を満たすａ'ｉｊ，ｋ＋１とｈ'ｉｊ，ｋ＋１とは数式４０及び数式４１によって求められる。
【０１２６】
【数４０】
0004981559.tif 000040
【数４１】
0004981559.tif 000041
【０１２７】
ｋ＝ｊの場合には、Ｌｉｊ，ｋ＋１はＶｉｊ(χｉ)と一致する。そして、数式４２及び数式４３が成り立つ。
【０１２８】
【数４２】
0004981559.tif 000042
【数４３】
0004981559.tif 000043
【０１２９】
ｇｉｊ−ξｉｊ＞ｇｉｋ−ｇｉｊの場合には数式４０よりａ'ｉｊ，ｋ＋１＞０となるので、関数Ｌｉｊ，ｋ＋１(χｉ)は凸関数になる。逆に、ｇｉｊ−ξｉｊ＜ｇｉｋ−ｇｉｊの場合には関数Ｌｉｊ，ｋ＋１(χｉ)は凸関数になる。よって、ｇｉｊ−ξｉｊ＞ｇｉｋ−ｇｉｊが成り立つ場合の関数Ｌｉｊ，ｋ＋１(χｉ)を考える。
【０１３０】
図５に示すように、関数Ｖｉｊ(χｉ)，Ｖｉｋ(χｉ)と関数Ｌｉｊ，ｋ＋１(χｉ)との間の関係において、ｇｉｊ−ξｉｊ＞ｇｉｋ−ｇｉｊが成り立つ場合は関数Ｌｉｊ，ｋ＋１(χｉ)が分散Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]＝Ｖｉｓ(χｉ)（ただし、χｉ∈[ξｓ，ξｓ＋１]、及び、ｓ＝ｊ，…，ｋ）の下界を与えることが期待される。以下に検証する。
【０１３１】
まず、ｋ＝ｊの場合にはＶｉｊ(χｉ)とＬｉｊ，ｋ＋１(χｉ)とは一致する。
【０１３２】
続いて、ｊ＜ｋ＜|Ξｉ|の場合にＬｉｊ，ｋ＋１(χｉ)≦Ｖｉｓ(χｉ)（ただし、χｉ∈[ξｓ，ξｓ＋１]、及び、ｓ＝ｊ，…，ｋ）であることを背理法を用いて証明する。
【０１３３】
区間[ξｉｐ，ξｉｐ＋１]（ただし、ｊ≦ｐ≦ｋ）においてＬｉｊ，ｋ＋１(ξｉｐ)≦Ｖｉｊ(ξｉｐ)且つＬｉｊ，ｋ＋１(ξｉｐ＋１)＞Ｖｉｊ(ξｉｐ＋１)が成り立つと仮定する。すなわち、χｉ∈[ξｉｐ，ξｉｐ＋１]においてＬｉｊ，ｋ＋１(χｉ)とＶｉｊ(χｉ)とが交わると仮定する。
【０１３４】
このとき、ｇｉｊ−ξｉｊ＞ｇｉｋ−ｇｉｊであるので、関数Ｌｉｊ，ｋ＋１(χｉ)は凸関数であり、数式４４が成り立つ。
【０１３５】
【数４４】
0004981559.tif 000044
【０１３６】
また、ｇｉｊ＜ｇｉｐであるので、数式４５が成り立つ。
【０１３７】
【数４５】
0004981559.tif 000045
【０１３８】
これより、Ｌｉｊ，ｋ＋１(χｉ)の最小値Ｌｉｊ，ｋ＋１(ｇｉｊ)はＶｉｐ(χｉ)の最小値Ｖｉｐ(ｇｉｐ)より大きい。したがって、数式４６が成り立つ。
【０１３９】
【数４６】
0004981559.tif 000046
【０１４０】
数式４６における不等式ｈｉｐ＜ｈｉｋは数式３４に示す系に反する（図６）。よって、上述の仮定を満たすｐは存在せず、区間[ξｉｊ，ξｉｋ]において下界を与えることが示された。
【０１４１】
確率変数のとり得る値がΞ＝{２，４，６，８}、ｐ１＝ｐ２＝ｐ３＝ｐ４＝１／４の場合を考える。下界を与える関数Ｌ(χ)は図７，８，９に示すようになる。
【０１４２】
この場合は、区間[ξｉｊ，ξｉｋ＋１]のｊ及びｋ（ただし、ｊ≦ｋ）のとり方を変えることで、５Ｃ２＝１０通りの組み合わせに対して[０,２]，[０,４]，[０,６]，[０,８]，[２,４]，[２,６]，[２,８]，[４,６]，[４,８]，[６,８]の１０通りの区間での下界を与えることができる。
【０１４３】
なお、区間[０,２]では、Ｌ０，１(χ)＝Ｖ０(χ)＝Ｖａｒ(ξ')であり、Ｖ０(χ)におけるχ２の係数がａ０＝０となるので、Ｌ０，１(χ)＝５と定数値になる。
【０１４４】
しかしながら、すべての区間に対してこのような下界が必ず与えられるとは限らない。Ｌｉｊ，ｋ＋１(χｉ)が凸二次関数となるためには、ｊ＝ｋの場合を除くとａ'ｉｊ，ｋ＋１が正でなければならない。ａ'ｉｊ，ｋ＋１＜０ならば凹関数となるために下界を与えない可能性がある。
【０１４５】
ａ'ｉｊ，ｋ＋１の分子は、Ｖｉｊ(χｉ)，Ｖｉｋ(χｉ)がχｉの単調減少関数でξｉｊ＞ｇｉｋであることから常にＶｉｊ(ξｉｊ)−Ｖｉｋ(ｇｉｋ)＞０となる。したがって、分母について(ξｉｊ−ｇｉｊ)２−(ｇｉｋ−ｇｉｊ)２＞０の条件を満たすときのみａ'ｉｊ，ｋ＋１の値が正になる。このことから、ｇｉｊ−ξｉｊ＞ｇｉｋ−ｇｉｊが成り立つときのみ下界を与える凸関数Ｌｉｊ，ｋ＋１(χｉ)を定義することが可能である。
【０１４６】
以上のことを踏まえ、本発明者は、不確実な状況下での最適化を行う方法であって目的関数に分散を含む確率計画問題ＳＰＲＳＴ−Ｖの最適解を求める方法の着想に至った。
【０１４７】
具体的には、確率計画問題ＳＰＲＳＴ−Ｖにおける分散項（数式４７に示す）を数式４８に示す項に置き換えた問題Ｐ０（数式４９に示す）を解く。新たな変数θｉはＶａｒ[ψ'ｉ(χｉ，ξ'ｉ)]の上界を表すが、問題Ｐ０においては制約θｉ≧Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]を緩和する。
【０１４８】
【数４７】
0004981559.tif 000047
【数４８】
0004981559.tif 000048
【０１４９】
【数４９】
0004981559.tif 000049
【０１５０】
そして、本発明の解法においては、入札変数χｉ（ただし、ｉ＝１，２，…，ｍ２）の定義域を分割することによって分枝操作を行う。
【０１５１】
問題Ｐ０に分枝操作を加えることによって得られた子問題ＰＭにおいて、入札変数χｉの定義域に関する制約χｉ∈[ξｉｊ，ξｉｋ＋１]と分散に対する下界制約θｉ≧Ｌｉｊ，ｋ＋１(χｉ)とが与えられているものとする。
【０１５２】
ここで、ｋ＝ｊならば関数Ｌｉｊ，ｊ＋１(χｉ)は正確な分散の値を与えるので、ｊ＜ｋの場合を考える。また、ｋ＝|Ξｉ|ならばχｉ∈[ξｉｊ，ξｉｋ＋１]における分散の下界としてθｉ≧０が与えられているものとする。
【０１５３】
問題ＰＭを解いてχｉ＊（ただし、ｉ＝１，２，…，ｍ２）を求める。このとき、あるｉについてθｉ＜Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]という関係が得られたとする。続いて、χｉ＊∈[ξｉｓ，ξｉｓ＋１]を満たす最大のｓ（ただし、ｊ≦ｓ≦ｋ）を求める。ｓ＝ｋの場合は、ｓ＝ｋ−１とする。問題ＰＭを問題ＰＭ＋１と問題ＰＭ＋２とに更に分解する。
【０１５４】
問題ＰＭ＋１に対しては、制約θｉ≧Ｌｉｊ，ｓ＋１(χｉ)及びχｉ≦ξｉｓ＋１を追加する。
【０１５５】
問題ＰＭ＋２に対しては、ｋ＜|Ξｉ|の場合には制約θｉ≧Ｌｉｓ＋１，ｋ＋１(χｉ)及びξｉｓ＋１≦χｉを追加し、ｋ＝|Ξｉ|の場合にはχｉ∈[ξｉｓ＋１，ξｉ|Ξｉ|＋１]での分散の下界は０であることから制約ξｉｓ＋１≦χｉのみを追加する。
【０１５６】
そして、変数χｉの区間の分割を続けていくと、最終的にχｉ∈[ξｉｊ，ξｉｋ＋１]という制約においてｊ＝ｋとなるので、最適性カットがリコース関数に対する正確な近似となる。よって、ξ'の各成分の最大値が有限であり、さらに、とり得る値の総数も有限であるとき、分枝操作が無限に繰り返されることはないので、上記の処理は有限回の反復で終了する。
【０１５７】
請求項１記載の確率計画問題求解装置は、上述の発明者独自の新たな着想に基づくものであり、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定手段と、数式５０で表される確率計画問題Ｐ０を用いて問題集合Ｐ＝{Ｐ０}に設定する問題設定手段と、問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断手段と、問題集合Ｐから問題ＰＭを選択すると共に問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択手段と、問題ＰＭの求解を行うと共に実行可能解がない場合に空集合判断手段に処理を移行させる最適解求解手段と、問題ＰＭの最適解をχｉ＊，θｉ＊（ただし、ｉ＝１，２，…，ｍ２）とする最適解設定手段と、全ての変数ｉについてθｉ＊≧Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]の場合に空集合判断手段に処理を移行させる最適解判断手段と、入札変数χｉの定義域χｉ∈[ξｉｊ，ξｉｋ＋１]においてθｉ＊＜Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]を満たす変数ｉを選択する第一の探索手段と、前記選択された変数ｉの下でχｉ＊∈[ξｉｓ，ξｉｓ＋１]を満たす最大のｓ（ただし、ｊ≦ｓ≦ｋ）を求める第二の探索手段と、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定手段と、問題ＰＭに制約θｉ≧Ｌｉｊ，ｓ＋１(χｉ)及びχｉ≦ξｉｓ＋１を追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第一の子問題設定手段と、問題ＰＭに制約ξｉｓ＋１≦χｉを追加すると共にｋ＜|Ξｉ|の場合にはθｉ≧Ｌｉｓ＋１，ｋ＋１(χｉ)を更に追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第二の子問題設定手段とを有するようにしている。
【０１５８】
【数５０】
0004981559.tif 000050
ただし、Ａ：ｍ１×ｎ１次元行列，ｃ：ｎ１次元列ベクトル，ｂ：ｍ１次元列ベクトル，
ｘ：第一段階変数であってｎ１次元変数ベクトル，Ｔ：ｍ２×ｎ１次元行列，
ξ'：確率変数であってｌ次元列ベクトル，ξ：確率変数ξ'の実現値，
Ξ：確率変数ξ'の台，ｑ：ｎ２次元列ベクトル，
ｙ(ξ)：第二段階変数であってｎ２次元変数ベクトル，
χ：入札変数，θｉ：Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]の上界，
ψ'：リコース関数，ｐｉｓｉ：確率変数ξ'ｉがξｉｓｉとなる確率，
ｍ１：第一段階の制約個数，ｎ１：第一段階変数の個数，
ｍ２：第二段階の制約個数，ｎ２：第二段階変数の個数，
ｌ：確率変数ベクトルの次元，
ｉ：第二段階制約のいずれであるかを表す識別子である添字，
ｓｉ：第二段階制約ｉに含まれる確率変数ξ'のとり得る値の数
をそれぞれ表す。
また、問題Ｐ０に分枝操作を加えることによって得られる子問題ＰＭにおいて、
入札変数χｉの定義域に関する制約χｉ∈[ξｉｊ，ξｉｋ＋１]と
分散に対する下界制約θｉ≧Ｌｉｊ，ｋ＋１(χｉ)とが与えられている。
ｊ，ｋ：第二段階制約ｉに含まれる確率変数ξ'のとり得る値の番号，
Ｌ：下界を与える凸関数  をそれぞれ表す。
なお、上付の┬：ベクトルの転置，
ｍｉｎ：最小値の関数，Ｖａｒ：分散  をそれぞれ意味する。
【０１５９】
また、請求項２記載の確率計画問題求解プログラムは、確率計画問題の最適解を求める際に、少なくとも、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定手段、数式５０で表される確率計画問題Ｐ０を用いて問題集合Ｐ＝{Ｐ０}に設定する問題設定手段、問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断手段、問題集合Ｐから問題ＰＭを選択すると共に問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択手段、問題ＰＭの求解を行うと共に実行可能解がない場合に空集合判断手段に処理を移行させる最適解求解手段、問題ＰＭの最適解をχｉ＊，θｉ＊（ただし、ｉ＝１，２，…，ｍ２）とする最適解設定手段、全ての変数ｉについてθｉ＊≧Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]の場合に空集合判断手段に処理を移行させる最適解判断手段、入札変数χｉの定義域χｉ∈[ξｉｊ，ξｉｋ＋１]においてθｉ＊＜Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]を満たす変数ｉを選択する第一の探索手段、前記選択された変数ｉの下でχｉ＊∈[ξｉｓ，ξｉｓ＋１]を満たす最大のｓ（ただし、ｊ≦ｓ≦ｋ）を求める第二の探索手段、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定手段、問題ＰＭに制約θｉ≧Ｌｉｊ，ｓ＋１(χｉ)及びχｉ≦ξｉｓ＋１を追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第一の子問題設定手段、問題ＰＭに制約ξｉｓ＋１≦χｉを追加すると共にｋ＜|Ξｉ|の場合にはθｉ≧Ｌｉｓ＋１，ｋ＋１(χｉ)を更に追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第二の子問題設定手段としてコンピュータを機能させるようにしている。
【０１６０】
したがって、この確率計画問題求解装置及びプログラムによると、最適値の分散を目的関数に含めるようにしているので、期待値を基準とする最適化ではなく、ばらつきを考慮した最適化を行って最適解が求められる。また、最適値の分散が目的関数に含められているので目的関数は全体としては非凸関数になるが、目的関数の形状に注目して変数の区間を制限することによって下界を与える凸二次関数を求めてこれを用いて凸二次計画問題を解くようにしているので、最適目的関数値に対する下界が算出される。
【０１６１】
また、請求項３記載の電源計画問題求解方法は、電源計画問題求解装置における電源計画問題求解方法であって、電源計画問題求解装置のコンピュータが、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定ステップと、数式５１で表される電源計画問題を問題Ｐ０として問題集合Ｐ＝{Ｐ０}に設定する問題設定ステップと、問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断ステップと、問題集合Ｐから問題ＰＭを選択すると共に問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択ステップと、問題ＰＭの求解を行うと共に実行可能解がない場合に空集合判断ステップに処理を移行させる最適解求解ステップと、問題ＰＭの最適解をχｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）とする最適解設定ステップと、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の場合に空集合判断ステップに処理を移行させる最適解判断ステップと、入札変数χｊの定義域χｊ∈[ξｊｒ，ξｊｋ＋１]においてθｊ＊＜Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]を満たす変数ｊを選択する第一の探索ステップと、前記選択された変数ｊの下でχｊ＊∈[ξｊｓ，ξｊｓ＋１]を満たす最大のｓ（ただし、ｒ≦ｓ≦ｋ）を求める第二の探索ステップと、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定ステップと、問題ＰＭに制約θｊ≧Ｌｊｒ，ｓ＋１(χｊ)及びχｊ≦ξｊｓ＋１を追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第一の子問題設定ステップと、問題ＰＭに制約ξｊｓ＋１≦χｊを追加すると共にｋ＜|Ξｊ|の場合にはθｊ≧Ｌｊｓ＋１，ｋ＋１(χｊ)を更に追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第二の子問題設定ステップとを有するようにしている。
【０１６２】
【数５１】
0004981559.tif 000051
ただし、ｉ：新設発電所の識別子（ｉ＝１，２，…，ｎ１），
ｊ：負荷領域又は需要領域の識別子（ｊ＝１，２，…，ｍ１），
ｇｉ：新設発電所ｉを建設するための容量当たりの費用（円／ＭＷ），
ｗｉ：第一段階変数であって新設発電所ｉの容量（ＭＷ）
ｃｉ：新設発電所ｉの運転費用（円／ＭＷｈ），
ｔｊ：負荷領域ｊの持続時間（ｈ），
ｘｉｊ：新設発電所ｉの需要領域ｊにおける出力（ＭＷ），
ｑｊ：既存発電所の需要領域ｊにおける運転費用（円／ＭＷｈ），
ｙｊ(ξｊ)：第二段階変数であって既存発電所の需要領域ｊにおける出力
（ＭＷ）
ξ'ｊ：確率変数であって需要領域ｊの需要量（ＭＷ）
（ξ'＝(ξ'１，ξ'２，…，ξ'ｍ１)と表す），
ξ：確率変数である需要量ξ'の実現値であって需要量のシナリオ
（ξ＝(ξ１，ξ２，…，ξｍ１)と表す），
Ξｊ：確率変数である需要量ξ'ｊのとり得る値の集合
（ξ'の台ΞはΞ＝Ξ１×Ξ２×…×Ξｍ１），
λ：リスク尺度パラメータ，ψ：リコース関数
をそれぞれ表す。
また、電源計画問題に分枝操作を加えることによって得られる子問題ＰＭにおいて、
入札変数χｊの定義域に関する制約χｊ∈[ξｊｒ，ξｊｋ＋１]と
分散に対する下界制約θｊ≧Ｌｊｒ，ｋ＋１(χｊ)とが与えられている。
χｊ：ｘｉｊのｊ＝１からｍ１までの合計，
ｒ，ｋ：第二段階制約ｊに含まれる確率変数ξ'のとり得る値の番号，
Ｌ：下界を与える凸関数  をそれぞれ表す。
θｊ：λＶａｒ[ψ(ｗ，ξ')]を表し、θｊ≧０である。
なお、ｍｉｎ：最小値の関数，Ｅ：期待値，Ｖａｒ：分散  をそれぞれ意味する。
【０１６３】
また、請求項４記載の電源計画問題求解装置は、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定手段と、数式５１で表される電源計画問題を問題Ｐ０として問題集合Ｐ＝{Ｐ０}に設定する問題設定手段と、問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断手段と、問題集合Ｐから問題ＰＭを選択すると共に問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択手段と、問題ＰＭの求解を行うと共に実行可能解がない場合に空集合判断手段に処理を移行させる最適解求解手段と、問題ＰＭの最適解をχｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）とする最適解設定手段と、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の場合に空集合判断手段に処理を移行させる最適解判断手段と、入札変数χｊの定義域χｊ∈[ξｊｒ，ξｊｋ＋１]においてθｊ＊＜Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]を満たす変数ｊを選択する第一の探索手段と、前記選択された変数ｊの下でχｊ＊∈[ξｊｓ，ξｊｓ＋１]を満たす最大のｓ（ただし、ｒ≦ｓ≦ｋ）を求める第二の探索手段と、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定手段と、問題ＰＭに制約θｊ≧Ｌｊｒ，ｓ＋１(χｊ)及びχｊ≦ξｊｓ＋１を追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第一の子問題設定手段と、問題ＰＭに制約ξｊｓ＋１≦χｊを追加すると共にｋ＜|Ξｊ|の場合にはθｊ≧Ｌｊｓ＋１，ｋ＋１(χｊ)を更に追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第二の子問題設定手段とを有するようにしている。
【０１６４】
また、請求項５記載の電源計画問題求解プログラムは、電源計画問題の最適解を求める際に、少なくとも、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定手段、数式５１で表される電源計画問題を問題Ｐ０として問題集合Ｐ＝{Ｐ０}に設定する問題設定手段、問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断手段、問題集合Ｐから問題ＰＭを選択すると共に問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択手段、問題ＰＭの求解を行うと共に実行可能解がない場合に空集合判断手段に処理を移行させる最適解求解手段、問題ＰＭの最適解をχｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）とする最適解設定手段、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の場合に空集合判断手段に処理を移行させる最適解判断手段、入札変数χｊの定義域χｊ∈[ξｊｒ，ξｊｋ＋１]においてθｊ＊＜Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]を満たす変数ｊを選択する第一の探索手段、前記選択された変数ｊの下でχｊ＊∈[ξｊｓ，ξｊｓ＋１]を満たす最大のｓ（ただし、ｒ≦ｓ≦ｋ）を求める第二の探索手段、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定手段、問題ＰＭに制約θｊ≧Ｌｊｒ，ｓ＋１(χｊ)及びχｊ≦ξｊｓ＋１を追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第一の子問題設定手段、問題ＰＭに制約ξｊｓ＋１≦χｊを追加すると共にｋ＜|Ξｊ|の場合にはθｊ≧Ｌｊｓ＋１，ｋ＋１(χｊ)を更に追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第二の子問題設定手段としてコンピュータを機能させるようにしている。
【０１６５】
したがって、この電源計画問題求解方法、装置及びプログラムによると、最適値の分散を目的関数に含めるようにしているので、期待値を基準とする最適化ではなく、ばらつきを考慮した最適化を行って最適解が求められる。また、最適値の分散が目的関数に含められているので目的関数は全体としては非凸関数になるが、目的関数の形状に注目して変数の区間を制限することによって下界を与える凸二次関数を求めてこれを用いて凸二次計画問題を解くようにしているので、最適目的関数値に対する下界が算出される。
【発明の効果】
【０１６６】
本発明の確率計画問題求解装置及びプログラム、並びに、電源計画問題求解方法、装置及びプログラムによれば、期待値を基準とする最適化ではなくばらつきを考慮した最適化を行って最適解を求めることができるので、確率変数の変動に対して変動の小さい強固な最適解を得ることが可能になる。しかも、目的関数が全体としては非凸関数になるにもかかわらず、目的関数の形状に注目して変数の区間を制限することによって下界を与える凸二次関数を求めてこれを用いて凸二次計画問題を解くことにより、最適目的関数値に対する下界を算出することができるので、例えばバックトラック法による全列挙法と比べて効率的に厳密解を得ることが可能になる。
【発明を実施するための最良の形態】
【０１６７】
以下、本発明の構成を図面に示す最良の形態に基づいて詳細に説明する。
【０１６８】
図１及び図２に、本発明の確率計画問題求解装置及びプログラムの実施形態の一例を示す。本発明の確率計画問題求解装置は、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定手段と、数式５２で表される確率計画問題Ｐ０を用いて問題集合Ｐ＝{Ｐ０}に設定する問題設定手段と、問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断手段と、問題集合Ｐから問題ＰＭを選択すると共に問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択手段と、問題ＰＭの求解を行うと共に実行可能解がない場合に空集合判断手段に処理を移行させる最適解求解手段と、問題ＰＭの最適解をχｉ＊，θｉ＊（ただし、ｉ＝１，２，…，ｍ２）とする最適解設定手段と、全ての変数ｉについてθｉ＊≧Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]の場合に空集合判断手段に処理を移行させる最適解判断手段と、入札変数χｉの定義域χｉ∈[ξｉｊ，ξｉｋ＋１]においてθｉ＊＜Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]を満たす変数ｉを選択する第一の探索手段と、前記選択された変数ｉの下でχｉ＊∈[ξｉｓ，ξｉｓ＋１]を満たす最大のｓ（ただし、ｊ≦ｓ≦ｋ）を求める第二の探索手段と、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定手段と、問題ＰＭに制約θｉ≧Ｌｉｊ，ｓ＋１(χｉ)及びχｉ≦ξｉｓ＋１を追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第一の子問題設定手段と、問題ＰＭに制約ξｉｓ＋１≦χｉを追加すると共にｋ＜|Ξｉ|の場合にはθｉ≧Ｌｉｓ＋１，ｋ＋１(χｉ)を更に追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第二の子問題設定手段とを有する。
【０１６９】
【数５２】
0004981559.tif 000052
ただし、Ａ：ｍ１×ｎ１次元行列，ｃ：ｎ１次元列ベクトル，ｂ：ｍ１次元列ベクトル，
ｘ：第一段階変数であってｎ１次元変数ベクトル，Ｔ：ｍ２×ｎ１次元行列，
ξ'：確率変数であってｌ次元列ベクトル，ξ：確率変数ξ'の実現値，
Ξ：確率変数ξ'の台，ｑ：ｎ２次元列ベクトル，
ｙ(ξ)：第二段階変数であってｎ２次元変数ベクトル，
χ：入札変数，θｉ：Ｖａｒ[ψ'ｉ(χｉ，ξ'ｉ)]の上界，
ψ'：リコース関数，ｐｉｓｉ：確率変数ξ'ｉがξｉｓｉとなる確率，
ｍ１：第一段階の制約個数，ｎ１：第一段階変数の個数，
ｍ２：第二段階の制約個数，ｎ２：第二段階変数の個数，
ｌ：確率変数ベクトルの次元，
ｉ：第二段階制約のいずれであるかを表す識別子である添字，
ｓｉ：第二段階制約ｉに含まれる確率変数ξ'のとり得る値の数
をそれぞれ表す。
また、問題Ｐ０に分枝操作を加えることによって得られる子問題ＰＭにおいて、
入札変数χｉの定義域に関する制約χｉ∈[ξｉｊ，ξｉｋ＋１]と
分散に対する下界制約θｉ≧Ｌｉｊ，ｋ＋１(χｉ)とが与えられている。
ｊ，ｋ：第二段階制約ｉに含まれる確率変数ξ'のとり得る値の番号，
Ｌ：下界を与える凸関数  をそれぞれ表す。
なお、上付の┬：ベクトルの転置，
ｍｉｎ：最小値の関数，Ｖａｒ：分散  をそれぞれ意味する。
【０１７０】
そして、上記確率計画問題求解装置は、図１に示すように、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定ステップ（Ｓ１）と、数式５２で表される確率計画問題Ｐ０を用いて問題集合Ｐ＝{Ｐ０}に設定する問題設定ステップ（Ｓ２）と、問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断ステップ（Ｓ３）と、問題集合Ｐから問題ＰＭを選択すると共に問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択ステップ（Ｓ４）と、問題ＰＭの求解を行うと共に実行可能解がない場合に空集合判断ステップに処理を移行させる最適解求解ステップ（Ｓ５）と、問題ＰＭの最適解をχｉ＊，θｉ＊（ただし、ｉ＝１，２，…，ｍ２）とする最適解設定ステップ（Ｓ６）と、全ての変数ｉについてθｉ＊≧Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]の場合に空集合判断ステップに処理を移行させる最適解判断ステップ（Ｓ７）と、入札変数χｉの定義域χｉ∈[ξｉｊ，ξｉｋ＋１]においてθｉ＊＜Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]を満たす変数ｉを選択する第一の探索ステップ（Ｓ８）と、前記選択された変数ｉの下でχｉ＊∈[ξｉｓ，ξｉｓ＋１]を満たす最大のｓ（ただし、ｊ≦ｓ≦ｋ）を求める第二の探索ステップ（Ｓ９）と、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定ステップ（Ｓ１０，Ｓ１１）と、問題ＰＭに制約θｉ≧Ｌｉｊ，ｓ＋１(χｉ)及びχｉ≦ξｉｓ＋１を追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第一の子問題設定ステップ（Ｓ１２−１）と、問題ＰＭに制約ξｉｓ＋１≦χｉを追加すると共にｋ＜|Ξｉ|の場合にはθｉ≧Ｌｉｓ＋１，ｋ＋１(χｉ)を更に追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第二の子問題設定ステップ（Ｓ１２−２）とからなる処理構成を実行することにより、最適値が分散を有する確率計画問題の最適解を求める。
【０１７１】
また、上記確率計画問題求解装置は、本発明の確率計画問題求解プログラムをコンピュータ上で実行することによっても実現される。本実施形態では、確率計画問題求解プログラムをコンピュータ上で実行する場合を例に挙げて説明する。
【０１７２】
確率計画問題求解プログラム１６を実行するための本実施形態の確率計画問題求解装置１０の全体構成を図２に示す。この確率計画問題求解装置１０は、制御部１１、記憶部１２、入力部１３、表示部１４及びメモリ１５を備え相互にバス等の信号回線により接続されている。
【０１７３】
制御部１１は記憶部１２に記憶されている確率計画問題求解プログラム１６により確率計画問題求解装置１０全体の制御並びに確率計画問題の最適解の求解に係る演算を行うものであり、例えばＣＰＵである。記憶部１２は少なくともデータやプログラムを記憶可能な装置であり、例えばハードディスクである。入力部１３は少なくとも作業者の命令を制御部１１に与えるためのインターフェイスであり、例えばキーボードである。表示部１４は制御部１１の制御により文字や図形等の表示を行うものであり、例えばディスプレイである。メモリ１５は制御部１１が各種制御や演算を実行する際の作業領域であるメモリ空間になる。また、確率計画問題設定データ１７は記憶部１２に記憶されているデータファイルであり、確率計画問題求解装置１０によって最適解の求解が行われる確率計画問題の各種の設定データを格納するものである。
【０１７４】
確率計画問題求解装置１０の制御部１１には、確率計画問題求解プログラム１６を実行することにより、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定部１１ａと、数式５２で表される確率計画問題Ｐ０を用いて問題集合Ｐ＝{Ｐ０}に設定する問題設定部１１ｂと、問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断部１１ｃと、問題集合Ｐから問題ＰＭを選択すると共に問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択部１１ｄと、問題ＰＭの求解を行うと共に実行可能解がない場合に空集合判断部１１ｃに処理を移行させる最適解求解部１１ｅと、問題ＰＭの最適解をχｉ＊，θｉ＊（ただし、ｉ＝１，２，…，ｍ２）とする最適解設定部１１ｆと、全ての変数ｉについてθｉ＊≧Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]の場合に空集合判断部１１ｃに処理を移行させる最適解判断部１１ｇと、入札変数χｉの定義域χｉ∈[ξｉｊ，ξｉｋ＋１]においてθｉ＊＜Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]を満たす変数ｉを選択する第一の探索部１１ｈと、前記選択された変数ｉの下でχｉ＊∈[ξｉｓ，ξｉｓ＋１]を満たす最大のｓ（ただし、ｊ≦ｓ≦ｋ）を求める第二の探索部１１ｉと、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定部１１ｊと、問題ＰＭに制約θｉ≧Ｌｉｊ，ｓ＋１(χｉ)及びχｉ≦ξｉｓ＋１を追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第一の子問題設定部１１ｋと、問題ＰＭに制約ξｉｓ＋１≦χｉを追加すると共にｋ＜|Ξｉ|の場合にはθｉ≧Ｌｉｓ＋１，ｋ＋１(χｉ)を更に追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第二の子問題設定部１１ｍとが構成される。
【０１７５】
確率計画問題求解装置１０による確率計画問題の最適解の求解処理の実行にあたっては、まず、制御部１１の初期設定部１１ａは、以降の処理に用いる変数の初期値の設定を行う（Ｓ１）。
【０１７６】
具体的には、初期設定部１１ａは、問題集合Ｐを空集合φに設定し、目的関数の上界ＵＢを＋∞に下界ＬＢを−∞に設定し、問題番号Ｎをゼロに設定する。本実施形態では、変数の初期値は確率計画問題求解プログラム１６上に規定されており、初期設定部１１ａは確率計画問題求解プログラム１６から読み込むことにより変数の初期値の設定を行う。
【０１７７】
なお、問題集合Ｐは、各問題が添字を有している個別問題の集合を表す。本実施形態では、添字Ｍを用いて個別問題をＰＭと表す。
【０１７８】
そして、初期設定部１１ａは、問題集合Ｐと上界ＵＢ及び下界ＬＢと問題番号Ｎとの設定をメモリ１５に記憶させる。
【０１７９】
次に、制御部１１の問題設定部１１ｂは、数式５２で表される確率計画問題Ｐ０を用いて問題集合Ｐ＝{Ｐ０}に設定する（Ｓ２）。
【０１８０】
数式５２で表される確率計画問題Ｐ０は確率計画問題求解プログラム１６上に予め規定しておく。なお、確率計画問題Ｐ０に係るｍ１，ｎ１，ｍ２，ｎ２，ｓｉ，ξ'ｉの設定については、確率計画問題求解プログラム１６上に予め規定しておくようにしても良いし、記憶部１２に記憶されているデータファイルである確率計画問題設定データ１７の中に格納しておくようにしても良い。
【０１８１】
そして、問題設定部１１ｂは、数式５２で表される確率計画問題Ｐ０を用いて問題集合Ｐ＝{Ｐ０}に設定し、新たな問題集合Ｐの設定をメモリ１５に記憶させる。
【０１８２】
次に、制御部１１の空集合判断部１１ｃは、問題集合Ｐが空集合φか否かを判断する（Ｓ３）。
【０１８３】
具体的には、空集合判断部１１ｃは、メモリ１５に記憶されている問題集合Ｐの設定をメモリ１５から読み込み、問題集合Ｐが空集合φであるか否かを判断する。
【０１８４】
そして、問題集合Ｐが空集合φである場合には（Ｓ３；Ｙｅｓ）、空集合判断部１１ｃは確率計画問題求解装置１０による最適解の求解処理を終了させる（ＥＮＤ）。
【０１８５】
一方、問題集合Ｐが空集合φでない場合には（Ｓ３；Ｎｏ）、空集合判断部１１ｃは確率計画問題求解装置１０による最適解の求解処理をＳ４の処理に移行させる。
【０１８６】
次に、制御部１１の問題選択部１１ｄは、問題集合Ｐから問題ＰＭを選択すると共に問題集合ＰをＰ＼{ＰＭ}に設定する（Ｓ４）。
【０１８７】
具体的には、問題選択部１１ｄは、メモリ１５に記憶されている問題集合Ｐの設定をメモリ１５から読み込み、問題集合Ｐの中から任意の問題ＰＭを選択する。本実施形態では、問題選択部１１ｄは、問題集合Ｐの問題ＰＭの中から添字Ｍの値が最も大きい問題を選択する（奥行優先規則と呼ばれる）。なお、問題集合Ｐの中から任意の問題ＰＭを選択する処理を問題選択操作という。
【０１８８】
さらに、問題選択部１１ｄは、問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する。すなわち、問題集合Ｐから個別の問題ＰＭを削除する。
【０１８９】
そして、問題選択部１１ｄは、新たな問題集合Ｐの設定をメモリ１５に記憶させる。また、問題選択部１１ｄは、問題ＰＭをメモリ１５に記憶させる。
【０１９０】
次に、制御部１１の最適解求解部１１ｅは、問題ＰＭの求解を行うと共に問題ＰＭが解けるか否かを判断する（Ｓ５）。
【０１９１】
具体的には、最適解求解部１１ｅは、Ｓ４の処理においてメモリ１５に記憶された問題ＰＭをメモリ１５から読み込み、二次計画問題の解法に従って問題ＰＭを解く。なお、二次計画問題の解法自体は周知の技術であるのでここでは詳細については省略する。
【０１９２】
本実施形態では、最適解求解部１１ｅとして、アイログ株式会社製・ＩＬＯＧ  ＣＰＬＥＸの求解プログラムである二次計画法ソルバが用いられる。なお、最適解求解部１１ｅとして用いられるものはこれに限られるものではなく、二次計画問題を解くことができるものであればどのようなものであっても構わない。
【０１９３】
そして、問題ＰＭの実行可能解がある場合には（Ｓ５；Ｙｅｓ）、最適解求解部１１ｅは確率計画問題求解装置１０による最適解の求解処理をＳ６の処理に移行させる。
【０１９４】
一方、問題ＰＭの実行可能解がない場合には（Ｓ５；Ｎｏ）、最適解求解部１１ｅは確率計画問題求解装置１０による最適解の求解処理をＳ３の処理に移行させる。
【０１９５】
なお、Ｓ４の処理において問題集合Ｐから問題ＰＭを選択すると共に当該問題ＰＭを問題集合Ｐから削除するようにしているので、Ｓ５の処理において当該問題ＰＭの実行可能解がない場合（Ｓ５；Ｎｏ）にＳ３の処理に戻る処理を繰り返していくと問題集合Ｐが空集合φになる場合（Ｓ３；Ｙｅｓ）があり、その場合には、空集合判断部１１ｃが確率計画問題求解装置１０による最適解の求解処理を終了させる（ＥＮＤ）ことになる。そして、問題集合Ｐが空集合φになった時にメモリ１５に記憶されている暫定の最適解χｉ＊，θｉ＊（ただし、ｉ＝１，２，…，ｍ２）が第二段階制約ｉ毎の最終的な確定最適解になる。制御部１１はこれらの確定最適解χｉ＊，θｉ＊を表示部１４に表示する。
【０１９６】
次に、制御部１１の最適解設定部１１ｆは、問題ＰＭの最適解をχｉ＊，θｉ＊（ただし、ｉ＝１，２，…，ｍ２）とする（Ｓ６）。
【０１９７】
具体的には、最適解設定部１１ｆは、Ｓ５の処理において最適解求解部１１ｅによって導出された実行可能解を問題ＰＭの暫定の最適解χｉ＊，θｉ＊（ただし、ｉ＝１，２，…，ｍ２）としてメモリ１５に記憶させる。
【０１９８】
次に、制御部１１の最適解判断部１１ｇは、全ての変数ｉについてθｉ＊≧Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]か否かを判断する（Ｓ７）。
【０１９９】
具体的には、最適解判断部１１ｇは、全ての変数ｉについて、Ｓ６の処理においてメモリ１５に記憶された最適解χｉ＊の値をメモリ１５から読み込むと共に確率変数ξ'ｉの値を確率計画問題設定データ１７から読み込み、読み込んだ最適解χｉ＊の値と確率変数ξ'ｉの値とを用いてＶａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]の値を求める。そして、最適解判断部１１ｇは、求めたＶａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]の値をメモリ１５に記憶させる。
【０２００】
続いて、最適解判断部１１ｇは、Ｓ６の処理においてメモリ１５に記憶された最適解θｉ＊の値をメモリ１５から読み込むと共に上述の処理によってメモリ１５に記憶されたＶａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]の値をメモリ１５から読み込み、全ての変数ｉについてθｉ＊≧Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]が成り立つか否かを判断する。
【０２０１】
そして、全ての変数ｉについてθｉ＊≧Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]が成り立つ場合には（Ｓ７；Ｙｅｓ）、最適解判断部１１ｇは確率計画問題求解装置１０による最適解の求解処理をＳ３の処理に移行させる。
【０２０２】
一方、少なくとも一部の変数ｉについてθｉ＊≧Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]が成り立たない場合には（Ｓ７；Ｎｏ）、最適解判断部１１ｇは確率計画問題求解装置１０による最適解の求解処理をＳ８の処理に移行させる。
【０２０３】
次に、制御部１１の第一の探索部１１ｈは、入札変数χｉの定義域χｉ∈[ξｉｊ，ξｉｋ＋１]においてθｉ＊＜Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]を満たす変数ｉを選択する（Ｓ８）。
【０２０４】
具体的には、第一の探索部１１ｈは、Ｓ６の処理においてメモリ１５に記憶された最適解θｉ＊の値とＳ７の処理においてメモリ１５に記憶されたＶａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]の値とをメモリ１５から読み込むと共に、入札変数χｉの定義域χｉ∈[ξｉｊ，ξｉｋ＋１]においてθｉ＊＜Ｖａｒ[ψ'ｉ(χｉ＊，ξ'ｉ)]を満たす変数ｉを選択する。
【０２０５】
なお、χｉ∈[ξｉｊ，ξｉｋ＋１]となる区間[ξｉｊ，ξｉｋ＋１]がχの定義域である。この定義域は、最初の問題Ｐ０では、χｉ∈[０，＋∞]という形の全区間（即ち特定の制限する区間はない）をとるが、Ｓ４の処理で問題選択操作された新たな問題には別の定義域に関する制約が加えられて分枝操作が行われる。そして、この分枝操作の結果、分枝が進むに従って区間制約がより細かくなる。
【０２０６】
そして、第一の探索部１１ｈは、選択された変数ｉの値をメモリ１５に記憶させる。
【０２０７】
次に、制御部１１の第二の探索部１１ｉは、Ｓ８の処理において選択された変数ｉの下でχｉ＊∈[ξｉｓ，ξｉｓ＋１]を満たす最大のｓ（ただし、ｊ≦ｓ≦ｋ）を求める（Ｓ９）。
【０２０８】
具体的には、第二の探索部１１ｉは、Ｓ８の処理において選択されてメモリ１５に記憶された変数ｉの値をメモリ１５から読み込む。そして、変数ｓの値をｊからｋまで順に変化させてχｉ＊∈[ξｉｓ，ξｉｓ＋１]を満たす最大の変数ｓの値を求める。なお、ｊとｋとは第二段階制約ｉに含まれる確率変数ξ'のとり得る値の番号即ちシナリオ番号を表す添字番号であり、１からｓｉまでの自然数である。本実施形態では、シナリオ番号ｊの値とｋの値とは確率計画問題設定データ１７の中に格納されている。そして、第二の探索部１１ｉは、確率計画問題設定データ１７からシナリオ番号ｊの値とｋの値とを読み込み、メモリ１５に記憶させて最適解の求解処理に用いるようにしている。
【０２０９】
そして、第二の探索部１１ｉは、求めた変数ｓの値をメモリ１５に記憶させる。
【０２１０】
次に、制御部１１の変数設定部１１ｊは、Ｓ９の処理において求められた変数ｓの値とｋの値とが等しいか否かを判断する（Ｓ１０）。
【０２１１】
具体的には、変数設定部１１ｊは、Ｓ９の処理においてメモリ１５に記憶された変数ｓの値とｋの値とを読み込み、変数ｓの値とｋの値との比較を行う。
【０２１２】
そして、変数ｓの値とｋの値とが等しい場合には（Ｓ１０；Ｙｅｓ）、変数設定部１１ｊはｋの値から１を引いた値を新たな変数ｓの値としてメモリ１５に記憶させる（Ｓ１１）。そして、変数設定部１１ｊは確率計画問題求解装置１０による最適解の求解処理をＳ１２の処理に移行させる。
【０２１３】
一方、変数ｓの値とｋの値とが等しくない場合には（Ｓ１０；Ｎｏ）、変数ｓの値はそのままで変数設定部１１ｊは確率計画問題求解装置１０による最適解の求解処理をＳ１２の処理に移行させる。
【０２１４】
次に、制御部１１の第一の子問題設定部１１ｋと第二の子問題設定部１１ｍとは、問題ＰＭを子問題に分解すると共に新たな問題集合Ｐの設定を行う（Ｓ１２）。
【０２１５】
具体的には、第一の子問題設定部１１ｋは、Ｓ４の処理においてメモリ１５に記憶された問題ＰＭをメモリ１５から読み込み、問題ＰＭに制約θｉ≧Ｌｉｊ，ｓ＋１(χｉ)及びχｉ≦ξｉｓ＋１を追加した問題を子問題ＰＮ＋１とする。さらに、第一の子問題設定部１１ｋは、メモリ１５に記憶されている問題集合Ｐの設定と問題番号Ｎの値とをメモリ１５から読み込み、新たな設定として問題集合Ｐ＝Ｐ∪{ＰＮ＋１}とすると共に問題番号Ｎ＝Ｎ＋１とする（Ｓ１２−１）。問題集合Ｐに新たな問題ＰＮ＋１を加える処理を分枝操作という。
【０２１６】
そして、第一の子問題設定部１１ｋは、新たな問題集合Ｐの設定と問題番号Ｎの値とをメモリ１５に記憶させる。
【０２１７】
また、第二の子問題設定部１１ｍは、Ｓ４の処理においてメモリ１５に記憶された問題ＰＭをメモリ１５から読み込み、問題ＰＭに制約ξｉｓ＋１≦χｉを追加し、ｋ＜|Ξｉ|の場合にはθｉ≧Ｌｉｓ＋１，ｋ＋１(χｉ)を更に追加した問題を子問題ＰＮ＋１とする。さらに、第二の子問題設定部１１ｍは、Ｓ１２−１の処理においてメモリ１５に記憶された問題集合Ｐの設定と問題番号Ｎの値とをメモリ１５から読み込み、新たな設定として問題集合Ｐ＝Ｐ∪{ＰＮ＋１}とすると共に問題番号Ｎ＝Ｎ＋１とする（Ｓ１２−２）。すなわち、第一の子問題設定部１１ｋと第二の子問題設定部１１ｍとによって問題集合Ｐに対して分枝操作が行われる。
【０２１８】
そして、第二の子問題設定部１１ｍは、新たな問題集合Ｐの設定と問題番号Ｎの値とをメモリ１５に記憶させる。
【０２１９】
続いて、図１０及び図１１に、本発明の電源計画問題求解方法、装置及びプログラムの実施形態の一例を示す。この電源計画問題求解方法は、図１０に示すように、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定ステップ（Ｓ２１）と、数式５３で表される電源計画問題を問題Ｐ０として問題集合Ｐ＝{Ｐ０}に設定する問題設定ステップ（Ｓ２２）と、問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断ステップ（Ｓ２３）と、問題集合Ｐから問題ＰＭを選択すると共に問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択ステップ（Ｓ２４）と、問題ＰＭの求解を行うと共に実行可能解がない場合に空集合判断ステップに処理を移行させる最適解求解ステップ（Ｓ２５）と、問題ＰＭの最適解をχｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）とする最適解設定ステップ（Ｓ２６）と、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の場合に空集合判断ステップに処理を移行させる最適解判断ステップ（Ｓ２７）と、入札変数χｊの定義域χｊ∈[ξｊｒ，ξｊｋ＋１]においてθｊ＊＜λＶａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]を満たす変数ｊを選択する第一の探索ステップ（Ｓ２８）と、前記選択された変数ｊの下でχｊ＊∈[ξｊｓ，ξｊｓ＋１]を満たす最大のｓ（ただし、ｒ≦ｓ≦ｋ）を求める第二の探索ステップ（Ｓ２９）と、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定ステップ（Ｓ３０，Ｓ３１）と、問題ＰＭに制約θｊ≧Ｌｊｒ，ｓ＋１(χｊ)及びχｊ≦ξｊｓ＋１を追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第一の子問題設定ステップと（Ｓ３２−１）、問題ＰＭに制約ξｊｓ＋１≦χｊを追加すると共にｋ＜|Ξｊ|の場合にはθｊ≧Ｌｊｓ＋１，ｋ＋１(χｊ)を更に追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第二の子問題設定ステップ（Ｓ３２−２）とを有する。
【０２２０】
【数５３】
0004981559.tif 000053
ただし、ｉ：新設発電所の識別子（ｉ＝１，２，…，ｎ１），
ｊ：負荷領域又は需要領域の識別子（ｊ＝１，２，…，ｍ１），
ｇｉ：新設発電所ｉを建設するための容量当たりの費用（円／ＭＷ），
ｗｉ：第一段階変数であって新設発電所ｉの容量（ＭＷ）
ｃｉ：新設発電所ｉの運転費用（円／ＭＷｈ），
ｔｊ：負荷領域ｊの持続時間（ｈ），
ｘｉｊ：新設発電所ｉの需要領域ｊにおける出力（ＭＷ），
ｑｊ：既存発電所の需要領域ｊにおける運転費用（円／ＭＷｈ），
ｙｊ(ξｊ)：第二段階変数であって既存発電所の需要領域ｊにおける出力
（ＭＷ）
ξ'ｊ：確率変数であって需要領域ｊの需要量（ＭＷ）
（ξ'＝(ξ'１，ξ'２，…，ξ'ｍ１)と表す），
ξ：確率変数である需要量ξ'の実現値であって需要量のシナリオ
（ξ＝(ξ１，ξ２，…，ξｍ１)と表す），
Ξｊ：確率変数である需要量ξ'ｊのとり得る値の集合
（ξ'の台ΞはΞ＝Ξ１×Ξ２×…×Ξｍ１），
λ：リスク尺度パラメータ，ψ：リコース関数
をそれぞれ表す。
また、電源計画問題に分枝操作を加えることによって得られる子問題ＰＭにおいて、
入札変数χｊの定義域に関する制約χｊ∈[ξｊｒ，ξｊｋ＋１]と
分散に対する下界制約θｊ≧Ｌｊｒ，ｋ＋１(χｊ)とが与えられている。
χｊ：ｘｉｊのｊ＝１からｍ１までの合計，
ｒ，ｋ：第二段階制約ｊに含まれる確率変数ξ'のとり得る値の番号，
Ｌ：下界を与える凸関数  をそれぞれ表す。
θｊ：λＶａｒ[ψ(ｗ，ξ')]を表し、θｊ≧０である。
なお、ｍｉｎ：最小値の関数，Ｅ：期待値，Ｖａｒ：分散  をそれぞれ意味する。
【０２２１】
本発明の電源計画問題求解方法、装置及びプログラムの電源計画問題は、リスク尺度として電力購入費用の分散項である数式５４が導入されている。
【０２２２】
【数５４】
0004981559.tif 000054
【０２２３】
リスク尺度パラメータλは運転費用の期待値と電源計画のリスク即ち費用のばらつきとの間のバランスを決定付けるパラメータであり、このリスク尺度パラメータλを導入することにより運転費用の期待値と電源計画のリスクとの間のトレードオフ関係を取り扱うことができるようになる。具体的には、リスク尺度パラメータλの値を大きくすると運転費用の期待値は大きい一方でリスクの小さい計画としての最適解が得られ、また、リスク尺度パラメータλの値を小さくすると運転費用の期待値は小さい一方でリスクの大きい計画としての最適解が得られる。さらに、このリスク尺度パラメータλの値を変化させることにより運転費用の期待値と電源計画のリスクとの間のトレードオフ関係を明らかにすることができる。
【０２２４】
上記電源計画問題求解方法は、本発明の電源計画問題求解装置として実現される。本発明の電源計画問題求解装置は、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定手段と、数式５３で表される電源計画問題を問題Ｐ０として問題集合Ｐ＝{Ｐ０}に設定する問題設定手段と、問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断手段と、問題集合Ｐから問題ＰＭを選択すると共に問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択手段と、問題ＰＭの求解を行うと共に実行可能解がない場合に空集合判断手段に処理を移行させる最適解求解手段と、問題ＰＭの最適解をχｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）とする最適解設定手段と、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の場合に空集合判断手段に処理を移行させる最適解判断手段と、入札変数χｊの定義域χｊ∈[ξｊｒ，ξｊｋ＋１]においてθｊ＊＜Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]を満たす変数ｊを選択する第一の探索手段と、前記選択された変数ｊの下でχｊ＊∈[ξｊｓ，ξｊｓ＋１]を満たす最大のｓ（ただし、ｒ≦ｓ≦ｋ）を求める第二の探索手段と、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定手段と、問題ＰＭに制約θｊ≧Ｌｊｒ，ｓ＋１(χｊ)及びχｊ≦ξｊｓ＋１を追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第一の子問題設定手段と、問題ＰＭに制約ξｊｓ＋１≦χｊを追加すると共にｋ＜|Ξｊ|の場合にはθｊ≧Ｌｊｓ＋１，ｋ＋１(χｊ)を更に追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第二の子問題設定手段とを有する。
【０２２５】
上述の電源計画問題求解方法及び電源計画問題求解装置は、本発明の電源計画問題求解プログラムをコンピュータ上で実行することによっても実現される。本実施形態では電源計画問題求解プログラムをコンピュータ上で実行する場合を例に挙げて説明する。
【０２２６】
電源計画問題求解プログラム２６を実行するための本実施形態の電源計画問題求解装置２０の全体構成を図１１に示す。この電源計画問題求解装置２０は、制御部２１、記憶部２２、入力部２３、表示部２４及びメモリ２５を備え相互にバス等の信号回線により接続されている。
【０２２７】
制御部２１は記憶部２２に記憶されている電源計画問題求解プログラム２６により電源計画問題求解装置２０全体の制御並びに電源計画問題の最適解の求解に係る演算を行うものであり、例えばＣＰＵである。記憶部２２は少なくともデータやプログラムを記憶可能な装置であり、例えばハードディスクである。入力部２３は少なくとも作業者の命令を制御部２１に与えるためのインターフェイスであり、例えばキーボードである。表示部２４は制御部２１の制御により文字や図形等の表示を行うものであり、例えばディスプレイである。メモリ２５は制御部２１が各種制御や演算を実行する際の作業領域であるメモリ空間になる。また、電源計画問題設定データ２７は記憶部２２に記憶されているデータファイルであり、電源計画問題求解装置２０によって最適解の求解が行われる電源計画問題の各種の設定データを格納するものである。
【０２２８】
電源計画問題求解装置２０の制御部２１には、電源計画問題求解プログラム２６を実行することにより、問題集合Ｐ＝空集合φ，目的関数の上界ＵＢ＝＋∞，目的関数の下界ＬＢ＝−∞，問題番号Ｎ＝０に設定する初期設定部２１ａと、数式５３で表される電源計画問題を問題Ｐ０として問題集合Ｐ＝{Ｐ０}に設定する問題設定部２１ｂと、問題集合Ｐ＝空集合φの場合に求解処理を終了させる空集合判断部２１ｃと、問題集合Ｐから問題ＰＭを選択すると共に問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する問題選択部２１ｄと、問題ＰＭの求解を行うと共に実行可能解がない場合に空集合判断部２１ｃに処理を移行させる最適解求解部２１ｅと、問題ＰＭの最適解をχｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）とする最適解設定部２１ｆと、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の場合に空集合判断部２１ｃに処理を移行させる最適解判断部２１ｇと、入札変数χｊの定義域χｊ∈[ξｊｒ，ξｊｋ＋１]においてθｊ＊＜Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]を満たす変数ｊを選択する第一の探索部２１ｈと、前記選択された変数ｊの下でχｊ＊∈[ξｊｓ，ξｊｓ＋１]を満たす最大のｓ（ただし、ｒ≦ｓ≦ｋ）を求める第二の探索部２１ｉと、ｓ＝ｋの場合にｓ＝ｋ−１とする変数設定部２１ｊと、問題ＰＭに制約θｊ≧Ｌｊｒ，ｓ＋１(χｊ)及びχｊ≦ξｊｓ＋１を追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第一の子問題設定部２１ｋと、問題ＰＭに制約ξｊｓ＋１≦χｊを追加すると共にｋ＜|Ξｊ|の場合にはθｊ≧Ｌｊｓ＋１，ｋ＋１(χｊ)を更に追加した問題を問題ＰＮ＋１とすると共に問題集合Ｐ＝Ｐ∪{ＰＮ＋１}，問題番号Ｎ＝Ｎ＋１とする第二の子問題設定部２１ｍとが構成される。
【０２２９】
本実施形態の需要の変動の不確実性を考慮した電源計画問題を以下に示す。
【０２３０】
本実施形態の電源計画問題では、ｎ１箇所の新設発電所及びｍ１箇所の既存発電所によって電力の供給を行い、発電所建設費用と運転費用との総和を最小化することを考える。
【０２３１】
そして、変動する電力需要の値として、図１２に示すように、年間の各時間における負荷を大きさの順に配列して得られる負荷持続曲線或いはその線形近似が用いられる。
【０２３２】
負荷持続曲線をｍ１個の領域に分割して領域ｊ（ただし、ｊ＝１，２，…，ｍ１）の需要量（単位はＭＷ）を確率変数ξ'ｊとし、領域ｊの持続時間をｔｊ(単位はｈ)とする。図１２は、三個の領域に分割した場合を表す。なお、本実施形態の電源計画問題では、既存発電所が各負荷領域への供給を行う。
【０２３３】
負荷持続曲線において、領域ｊの需要を確率変数とし、それらをまとめてξ'＝(ξ'１，ξ'２，…，ξ'ｍ１)と表し、その実現値をξ＝(ξ１，ξ２，…，ξｍ１)とする。なお、本実施形態においては、この実現値がシナリオξとなる。
【０２３４】
ξ'１，ξ'２，…，ξ'ｍ１のとり得る値の集合をΞ１，Ξ２，…，Ξｍ１とすると、ξ'の台ΞはΞ＝Ξ１×Ξ２×…×Ξｍ１と表される。
【０２３５】
次に、電源計画の確率計画モデルを示す。
【０２３６】
第一段階において決定する変数は、新設発電所ｉの容量ｗｉ（ＭＷ）である。新設発電所ｉを建設するための容量当たりの費用をｇｉ（円／ＭＷ）、新設発電所ｉの需要領域ｊにおける出力をｘｉｊ（ＭＷ）とする。
【０２３７】
確率変数である電力需要ξ'に対し、新設発電所と既存の発電所とからの供給を行う。
【０２３８】
確率変数の値に応じて第二段階に決定される変数については、まず、既存発電所の需要領域ｊにおける出力をｙｊ(ξｊ)（ＭＷ）とする。また、これらの出力に応じた運転費用を新設発電所ｉに対してはｃｉ（円／ＭＷｈ）とし、需要領域ｊにおける既存発電所の運転費用をｑｊ（円／ＭＷｈ）とする。
【０２３９】
制約条件として、新設発電所ｉの発電機の出力が容量を超えないという条件である数式５５が与えられる。
【０２４０】
【数５５】
0004981559.tif 000055
【０２４１】
本実施形態の電源計画では、供給不足の対応として、運転費用の高い既存設備の存在を仮定する。具体的には、確率変数である需要ξ'の実現値ξが与えられたとき、新設発電所の能力を上回る場合には、第二段階における追加決定として既存の発電所から供給ｙｊ(ξｊ)（ＭＷ）を行って需要を満たす。この条件は数式５６のように表される。
【０２４２】
【数５６】
0004981559.tif 000056
【０２４３】
電源計画における目的関数は、発電所建設費用と発電所運転費用の期待値との総和である。そして、発電所運転費用は新設発電所の運転費と既存発電所の運転費との和である。
【０２４４】
発電所の建設と新設発電所の運転とに関わる決定はシナリオに応じて変動しない。一方、既存発電所の運転に関わる決定はシナリオに応じて変動する。
【０２４５】
以上より、電源計画問題は数式５３に示すように表される。
【０２４６】
数式５３に示す電源計画問題に含まれる関数ψ(ｗ，ξ)は、シナリオξが起こった場合の新設発電所と既存発電所との運転費用の総和を表す。関数ψ(ｗ，ξ)を定義する第二段階の数理計画問題の目的関数における数式５７に示す項は新設発電所の運転費用を表し、数式５８に示す項は既存発電所の運転費用を表す。
【０２４７】
【数５７】
0004981559.tif 000057
【０２４８】
【数５８】
0004981559.tif 000058
【０２４９】
続いて、本発明の電源計画問題求解プログラムにより実現される電源計画問題求解装置による電源計画問題求解方法による電源計画問題の最適解の求解処理について説明する。電源計画問題求解装置２０による電源計画問題の最適解の求解処理の実行にあたっては、まず、制御部２１の初期設定部２１ａは、以降の処理に用いる変数の初期値の設定を行う（Ｓ２１）。
【０２５０】
具体的には、初期設定部２１ａは、問題集合Ｐを空集合φに設定し、目的関数の上界ＵＢを＋∞に下界ＬＢを−∞に設定し、問題番号Ｎをゼロに設定する。本実施形態では、変数の初期値は電源計画問題求解プログラム２６上に規定されており、初期設定部２１ａは電源計画問題求解プログラム２６から読み込むことにより変数の初期値の設定を行う。
【０２５１】
なお、問題集合Ｐは、各問題が添字を有している個別問題の集合を表す。本実施形態では、添字Ｍを用いて個別問題をＰＭと表す。
【０２５２】
そして、初期設定部２１ａは、問題集合Ｐと上界ＵＢ及び下界ＬＢと問題番号Ｎとの設定をメモリ２５に記憶させる。
【０２５３】
次に、制御部２１の問題設定部２１ｂは、数式５３で表される電源計画問題を問題Ｐ０として問題集合Ｐ＝{Ｐ０}に設定する（Ｓ２２）。
【０２５４】
数式５３で表される電源計画問題は電源計画問題求解プログラム２６上に予め規定しておく。なお、電源計画問題に係るｍ１，ｎ１，ξ'ｊの設定については、電源計画問題求解プログラム２６上に予め規定しておくようにしても良いし、記憶部２２に記憶されているデータファイルである電源計画問題設定データ２７の中に格納しておくようにしても良い。
【０２５５】
そして、問題設定部２１ｂは、数式５３で表される電源計画問題を問題Ｐ０として問題集合Ｐ＝{Ｐ０}に設定し、新たな問題集合Ｐの設定をメモリ２５に記憶させる。
【０２５６】
次に、制御部２１の空集合判断部２１ｃは、問題集合Ｐが空集合φか否かを判断する（Ｓ２３）。
【０２５７】
具体的には、空集合判断部２１ｃは、メモリ２５に記憶されている問題集合Ｐの設定をメモリ２５から読み込み、問題集合Ｐが空集合φであるか否かを判断する。
【０２５８】
そして、問題集合Ｐが空集合φである場合には（Ｓ２３；Ｙｅｓ）、空集合判断部２１ｃは電源計画問題求解装置２０による最適解の求解処理を終了させる（ＥＮＤ）。
【０２５９】
一方、問題集合Ｐが空集合φでない場合には（Ｓ２３；Ｎｏ）、空集合判断部２１ｃは電源計画問題求解装置２０による最適解の求解処理をＳ２４の処理に移行させる。
【０２６０】
次に、制御部２１の問題選択部２１ｄは、問題集合Ｐから問題ＰＭを選択すると共に問題集合ＰをＰ＼{ＰＭ}に設定する（Ｓ２４）。
【０２６１】
具体的には、問題選択部２１ｄは、メモリ２５に記憶されている問題集合Ｐの設定をメモリ２５から読み込み、問題集合Ｐの中から任意の問題ＰＭを選択する。本実施形態では、問題選択部２１ｄは、問題集合Ｐの問題ＰＭの中から添字Ｍの値が最も大きい問題を選択する（奥行優先規則と呼ばれる）。なお、問題集合Ｐの中から任意の問題ＰＭを選択する処理を問題選択操作という。
【０２６２】
さらに、問題選択部２１ｄは、問題集合Ｐ＝Ｐ＼{ＰＭ}に設定する。すなわち、問題集合Ｐから個別の問題ＰＭを削除する。
【０２６３】
そして、問題選択部２１ｄは、新たな問題集合Ｐの設定をメモリ２５に記憶させる。また、問題選択部２１ｄは、問題ＰＭをメモリ２５に記憶させる。
【０２６４】
次に、制御部２１の最適解求解部２１ｅは、問題ＰＭの求解を行うと共に問題ＰＭが解けるか否かを判断する（Ｓ２５）。
【０２６５】
具体的には、最適解求解部２１ｅは、Ｓ２４の処理においてメモリ２５に記憶された問題ＰＭをメモリ２５から読み込み、二次計画問題の解法に従って問題ＰＭを解く。なお、二次計画問題の解法自体は周知の技術であるのでここでは詳細については省略する。
【０２６６】
本実施形態では、最適解求解部２１ｅとして、アイログ株式会社製・ＩＬＯＧ  ＣＰＬＥＸの求解プログラムである二次計画法ソルバが用いられる。なお、最適解求解部２１ｅとして用いられるものはこれに限られるものではなく、二次計画問題を解くことができるものであればどのようなものであっても構わない
【０２６７】
そして、問題ＰＭの実行可能解がある場合には（Ｓ２５；Ｙｅｓ）、最適解求解部２１ｅは電源計画問題求解装置２０による最適解の求解処理をＳ２６の処理に移行させる。
【０２６８】
一方、問題ＰＭの実行可能解がない場合には（Ｓ２５；Ｎｏ）、最適解求解部２１ｅは電源計画問題求解装置２０による最適解の求解処理をＳ２３の処理に移行させる。
【０２６９】
なお、Ｓ２４の処理において問題集合Ｐから問題ＰＭを選択すると共に当該問題ＰＭを問題集合Ｐから削除するようにしているので、Ｓ２５の処理において当該問題ＰＭの実行可能解がない場合（Ｓ２５；Ｎｏ）にＳ２３の処理に戻る処理を繰り返していくと問題集合Ｐが空集合φになる場合（Ｓ２３；Ｙｅｓ）があり、その場合には、空集合判断部２１ｃが電源計画問題求解装置２０による最適解の求解処理を終了させる（ＥＮＤ）ことになる。そして、問題集合Ｐが空集合φになった時にメモリ２５に記憶されている暫定の最適解χｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）が第二段階制約ｊ毎の最終的な確定最適解になる。制御部２１はこれらの確定最適解χｊ＊，θｊ＊を表示部２４に表示する。
【０２７０】
次に、制御部２１の最適解設定部２１ｆは、問題ＰＭの最適解をχｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）とする（Ｓ２６）。
【０２７１】
具体的には、最適解設定部２１ｆは、Ｓ２５の処理において最適解求解部２１ｅによって導出された実行可能解を問題ＰＭの暫定の最適解χｊ＊，θｊ＊（ただし、ｊ＝１，２，…，ｍ１）としてメモリ２５に記憶させる。
【０２７２】
次に、制御部２１の最適解判断部２１ｇは、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]か否かを判断する（Ｓ２７）。
【０２７３】
具体的には、最適解判断部２１ｇは、全ての変数ｊについて、Ｓ２６の処理においてメモリ２５に記憶された最適解χｊ＊の値をメモリ２５から読み込むと共に確率変数ξ'ｊの値を確率計画問題設定データ１７から読み込み、読み込んだ最適解χｊ＊の値と確率変数ξ'ｊの値とを用いてＶａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の値を求める。そして、最適解判断部２１ｇは、求めたＶａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の値をメモリ２５に記憶させる。
【０２７４】
続いて、最適解判断部２１ｇは、Ｓ２６の処理においてメモリ２５に記憶された最適解θｊ＊の値をメモリ２５から読み込むと共に上述の処理によってメモリ２５に記憶されたＶａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の値をメモリ２５から読み込み、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]が成り立つか否かを判断する。
【０２７５】
そして、全ての変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]が成り立つ場合には（Ｓ２７；Ｙｅｓ）、最適解判断部２１ｇは電源計画問題求解装置２０による最適解の求解処理をＳ２３の処理に移行させる。
【０２７６】
一方、少なくとも一部の変数ｊについてθｊ＊≧Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]が成り立たない場合には（Ｓ２７；Ｎｏ）、最適解判断部２１ｇは電源計画問題求解装置２０による最適解の求解処理をＳ２８の処理に移行させる。
【０２７７】
次に、制御部２１の第一の探索部２１ｈは、入札変数χｊの定義域χｊ∈[ξｊｒ，ξｊｋ＋１]においてθｊ＊＜Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]を満たす変数ｊを選択する（Ｓ２８）。
【０２７８】
具体的には、第一の探索部２１ｈは、Ｓ２６の処理においてメモリ２５に記憶された最適解θｊ＊の値とＳ２７の処理においてメモリ２５に記憶されたＶａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]の値とをメモリ２５から読み込むと共に、入札変数χｊの定義域χｊ∈[ξｊｒ，ξｊｋ＋１]においてθｊ＊＜Ｖａｒ[ψ'ｊ(χｊ＊，ξ'ｊ)]を満たす変数ｊを選択する。
【０２７９】
なお、χｊ∈[ξｊｒ，ξｊｋ＋１]となる区間[ξｊｒ，ξｊｋ＋１]がχの定義域である。この定義域は、最初の問題Ｐ０では、χｊ∈[０，＋∞]という形の全区間（即ち特定の制限する区間はない）をとるが、Ｓ２４の処理で問題選択操作された新たな問題には別の定義域に関する制約が加えられて分枝操作がされる。そして、この分枝操作の結果、分枝が進むに従って区間制約がより細かくなる。
【０２８０】
そして、第一の探索部２１ｈは、選択された変数ｊの値をメモリ２５に記憶させる。
【０２８１】
次に、制御部２１の第二の探索部２１ｉは、Ｓ２８の処理において選択された変数ｊの下でχｊ＊∈[ξｊｓ，ξｊｓ＋１]を満たす最大のｓ（ただし、ｒ≦ｓ≦ｋ）を求める（Ｓ２９）。
【０２８２】
具体的には、第二の探索部２１ｉは、Ｓ２８の処理において選択されてメモリ２５に記憶された変数ｊの値をメモリ２５から読み込む。そして、変数ｓの値をｒからｋまで順に変化させてχｊ＊∈[ξｊｓ，ξｊｓ＋１]を満たす最大の変数ｓの値を求める。なお、ｒとｋとは第二段階制約ｊに含まれる確率変数ξ'のとり得る値の番号即ちシナリオ番号を表す添字番号であり、自然数である。本実施形態では、シナリオ番号ｒの値とｋの値とは電源計画問題設定データ２７の中に格納されている。そして、第二の探索部２１ｉは、電源計画問題設定データ２７からシナリオ番号ｒの値とｋの値とを読み込み、メモリ２５に記憶させて最適解の求解処理に用いるようにしている。
【０２８３】
そして、第二の探索部２１ｉは、求めた変数ｓの値をメモリ２５に記憶させる。
【０２８４】
次に、制御部２１の変数設定部２１ｊは、Ｓ２９の処理において求められた変数ｓの値とｋの値とが等しいか否かを判断する（Ｓ３０）。
【０２８５】
具体的には、変数設定部２１ｊは、Ｓ２９の処理においてメモリ２５に記憶された変数ｓの値とｋの値とを読み込み、変数ｓの値とｋの値との比較を行う。
【０２８６】
そして、変数ｓの値とｋの値とが等しい場合には（Ｓ３０；Ｙｅｓ）、変数設定部２１ｊはｋの値から１を引いた値を新たな変数ｓの値としてメモリ２５に記憶させる（Ｓ３１）。そして、変数設定部２１ｊは電源計画問題求解装置２０による最適解の求解処理をＳ３２の処理に移行させる。
【０２８７】
一方、変数ｓの値とｋの値とが等しくない場合には（Ｓ３０；Ｎｏ）、変数ｓの値はそのままで変数設定部２１ｊは電源計画問題求解装置２０による最適解の求解処理をＳ３２の処理に移行させる。
【０２８８】
次に、制御部２１の第一の子問題設定部２１ｋと第二の子問題設定部２１ｍとは、問題ＰＭを子問題に分解すると共に新たな問題集合Ｐの設定を行う（Ｓ３２）。
【０２８９】
具体的には、第一の子問題設定部２１ｋは、Ｓ２４の処理においてメモリ２５に記憶された問題ＰＭをメモリ２５から読み込み、問題ＰＭに制約θｊ≧Ｌｊｒ，ｓ＋１(χｊ)及びχｊ≦ξｊｓ＋１を追加した問題を子問題ＰＮ＋１とする。さらに、第一の子問題設定部２１ｋは、メモリ２５に記憶されている問題集合Ｐの設定と問題番号Ｎの値とをメモリ２５から読み込み、新たな設定として問題集合Ｐ＝Ｐ∪{ＰＮ＋１}とすると共に問題番号Ｎ＝Ｎ＋１とする（Ｓ３２−１）。問題集合Ｐに新たな問題ＰＮ＋１を加える処理を分枝操作という。
【０２９０】
そして、第一の子問題設定部２１ｋは、新たな問題集合Ｐの設定と問題番号Ｎの値とをメモリ２５に記憶させる。
【０２９１】
また、第二の子問題設定部２１ｍは、Ｓ２４の処理においてメモリ２５に記憶された問題ＰＭをメモリ２５から読み込み、問題ＰＭに制約ξｊｓ＋１≦χｊを追加し、ｋ＜|Ξｊ|の場合にはθｊ≧Ｌｊｓ＋１，ｋ＋１(χｊ)を更に追加した問題を子問題ＰＮ＋１とする。さらに、第二の子問題設定部２１ｍは、Ｓ３２−１の処理においてメモリ２５に記憶された問題集合Ｐの設定と問題番号Ｎの値とをメモリ２５から読み込み、新たな設定として問題集合Ｐ＝Ｐ∪{ＰＮ＋１}とすると共に問題番号Ｎ＝Ｎ＋１とする（Ｓ３２−２）。すなわち、第一の子問題設定部２１ｋと第二の子問題設定部２１ｍとによって問題集合Ｐに対して分枝操作が行われる。
【０２９２】
そして、第二の子問題設定部２１ｍは、新たな問題集合Ｐの設定と問題番号Ｎの値とをメモリ２５に記憶させる。
【実施例１】
【０２９３】
本発明の電源計画問題求解プログラムにより実現される電源計画問題求解装置による電源計画問題求解方法を実際の電源計画問題の解析に適用した実施例を図１２から図１４を用いて説明する。
【０２９４】
本実施例では、新設発電所の候補数を三つとし、負荷領域数を二つとした（負荷領域１及び負荷領域２とする）。そして、新設発電所として一つの石炭火力発電所（発電所１とする）と二つのＬＮＧ火力発電所（発電所２及び発電所３とする）とを想定すると共に、既存発電所として石油火力発電所を想定した。
【０２９５】
また、本実施例では、発電コストを表２に示す通りとし（平成１１年公表の経済産業省資源エネルギー庁試算値に基づく）、表２に基づいて設備データを表３に示す通りとした。
【０２９６】
【表２】
0004981559.tif 000059
【表３】
0004981559.tif 000060
なお、新設備投資費用ｇ及び新設備運転費用ｃの添字は発電所１，２，３を表し、既存設備運転費用ｑの添字は負荷領域１，２を表す。
【０２９７】
なお、新設備の投資費用については１年当たりの費用として平準化したものを用いた。
【０２９８】
また、既存設備の発電所は設備投資費用を必要としないが、表２に基づいて、表３に示すように、既存設備である石油火力発電所の運転費用ｑの値は新設設備である石炭火力発電所及びＬＮＧ火力発電所の運転費用ｃより高めである。そして、既存設備である石油火力発電所の運転費用は負荷領域によって異なる値をとり、本実施例では負荷領域は二つであるので、運転費用ｑ１，ｑ２はそれぞれ負荷領域１，２における石油火力発電所の運転費用を表す。
【０２９９】
需要については、図１３に示すように、二つの負荷領域１，２で与えられる負荷持続曲線を想定した。
【０３００】
また、需要データとして表４に示す条件を用いた。
【０３０１】
【表４】
0004981559.tif 000061
【０３０２】
本実施例では、負荷領域１の需要シナリオの数を５個とすると共に、負荷領域２の需要シナリオの数を５個とした。したがって、シナリオの総数はそれらを掛け合わせた２５個となった。
【０３０３】
以上の条件を用い、リスク尺度パラメータλを０から0.05まで0.001間隔で増加させながら、それぞれのλに対して最適化を行った。最適化の結果、例えば、λ＝０の場合について表５に示す結果が得られ、λ＝0.05の場合について表６に示す結果が得られた。なお、表５に示す結果は、リスク尺度パラメータλ＝０の場合であるので、運転費用の分散を考慮することなく期待値のみを考慮する従来のモデルと同じである。
【０３０４】
【表５】
0004981559.tif 000062
【表６】
0004981559.tif 000063
【０３０５】
表５に示すリスク尺度パラメータλ＝０即ち運転費用の期待値のみを考慮する場合と表６に示すλ＝0.05即ち運転費用の分散も考慮する場合とを比較すると、総費用（即ち建設費と運転費との合計）の期待値が494931（＝239400＋255531）百万円と496878（＝243000＋253878）百万円となって分散も考慮する場合の方が約0.4％増加するのに対し、分散の値は17394015と5270141となって分散も考慮する場合の方が約１／３になった。
【０３０６】
新設設備の建設総容量は、運転費用の期待値のみを考慮する（即ちλ＝０）場合は石炭火力発電所１とＬＮＧ火力発電所２との合計で8000ＭＷであり、分散も考慮する（即ちλ＝0.05）場合は石炭火力発電所１のみで8100ＭＷであった。
【０３０７】
また、表３に示すように、石炭火力発電所１の建設費用はＬＮＧ火力発電所２やＬＮＧ火力発電所３よりも高い。したがって、分散も考慮する（即ちλ＝0.05）場合は新設発電所の建設費用が239400百万円から243000百万円へと増大した。
【０３０８】
また、表６に示すように、分散も考慮すると、運転費用の安い石炭火力発電所１の容量が増加して運転費用の期待値が減少した。
【０３０９】
さらに、シナリオ毎の運転費用に関し、λ＝０の場合について表７に示す結果が得られ、λ＝0.05の場合について表８に示す結果が得られた。ただし、負荷領域１におけるシナリオ毎の運転費用は負荷領域２の各シナリオに対する期待値であり、負荷領域２におけるシナリオ毎の運転費用は負荷領域１の各シナリオに対する期待値である。
【０３１０】
【表７】
0004981559.tif 000064
【表８】
0004981559.tif 000065
【０３１１】
表７に示すように、運転費用の分散を考慮することなく期待値のみを考慮する（即ちλ＝０）場合には、負荷領域１における運転費用は５つのシナリオに対して214532〜225044百万円の範囲で変動し、変動幅は10512百万円となった。一方、表８に示すように、分散も考慮する（即ちλ＝0.05）場合には、負荷領域１における運転費用は216645〜219963百万円の範囲で変動して変動幅は3318百万円になり、変動幅が非常に小さくなった。
【０３１２】
具体的には、期待値のみを考慮する場合の方が、分散も考慮する場合と比べ、需要値が小さいシナリオ１においては運転費用が安い一方で、需要値が大きいシナリオ５においては運転費用が高くなった。すなわち、分散も考慮する場合と比べて期待値のみを考慮する場合は需要値の変動に対する費用の変動を抑えることができない結果になった。
【０３１３】
以上のように、本発明の電源計画問題求解方法によれば、期待値に加えて分散も考慮することにより、費用の変動を大きく減らすロバストな解を得ることが可能になることが確認された。
【０３１４】
続いて、リスク尺度パラメータλを変化させ、横軸に分散、縦軸に期待費用をとって二次元平面上に整理することによって最適費用と分散との間の関係を調べた。
【０３１５】
図１４中の実線Ａは本発明の方法による解である。また、図１４中の点線Ｂは、本発明の方法による解との比較対象として、凸計画であって上方半分散である数式５９を分散の代用として用いたモデルを解いて得られた解を用いて真の分散を計算し直して平面上に示したものである。
【０３１６】
【数５９】
0004981559.tif 000066
【０３１７】
図１４に示す結果から、本発明の電源計画問題求解方法によれば、運転費用の分散が等しい解の中で費用の期待値が最も小さい解を求めることができ、同時に、運転費用の期待値が等しい解の中で分散が最も小さい解を求めることができることが確認された。
【０３１８】
なお、本実施例では、運転費用の期待値と電源計画のリスクとの間のトレードオフ関係を明らかにするためにリスク尺度パラメータλの値を０から0.05まで変化させるようにしているが、これに限られるものではなく、リスク尺度パラメータλの値を固定し運転費用のばらつきを考慮する程度即ちばらつきの重みを固定して電源計画問題の最適解を求解するようにしても良い。
【実施例２】
【０３１９】
本発明の電源計画問題求解プログラムにより実現される電源計画問題求解装置による電源計画問題求解方法を実際の電源計画問題の解析に適用した他の実施例を説明する。
【０３２０】
本実施例では、需要シナリオ数の多い電源計画問題に対して本発明の方法と従来の列挙法とを適用して本発明の方法の効率性の評価を行った。
【０３２１】
本実施例では、表９に示す問題を取り扱った。
【表９】
0004981559.tif 000067
【０３２２】
表９に示す問題に対して本発明の方法並びに従来の列挙法を適用して表１０に示す結果が得られた。なお、表１０に示す計算時間並びに子問題数は、リスク尺度パラメータλを０から０．０５まで０．００１間隔で増加させた５０問題の平均値である。
【０３２３】
【表１０】
0004981559.tif 000068
【０３２４】
表１０に示す結果から、本発明の電源計画問題求解方法によれば、従来の列挙法と比べて解くべき子問題の数が２割から６割程度に減少すると共に計算時間が１割から７割程度に減少し、効率的に電源計画問題を解くことが可能であることが確認された。
【０３２５】
以上の実施例１及び２から、本発明の電源計画問題求解方法によれば、期待値分散平面上における厳密な有効フロンティアを導出し、また、従来の上方半分散モデルでは求められなかった効率的フロンティアを求めることが可能であることが確認された。
【産業上の利用可能性】
【０３２６】
本発明の確率計画問題求解装置及びプログラムは、例えば、実施例で取り扱った電源計画問題の他にも生産計画問題等の各種の意思決定問題における最適解の導出を精度良く行うことができるので、生産工学、経営工学、システム工学等の分野で利用価値が特に高い。
【図面の簡単な説明】
【０３２７】
【図１】本発明の確率計画問題求解装置の実施形態の一例の処理ステップを説明するフローチャートである。
【図２】実施形態の確率計画問題求解装置をプログラムを用いて実施する場合の装置の機能ブロック図である。
【図３】リコース関数の期待値と分散との間の関係を説明する図である。
【図４】確率計画問題ＳＰＲＳＴ−ＶとＲＳＰＲＳＴ−Ｖとの目的関数を説明する図である。
【図５】関数Ｖｉｊ(χｉ)，Ｖｉｋ(χｉ)とＬｉｊ，ｋ＋１(χｉ)との間の関係を説明する図である。
【図６】関数Ｖｉｐ(χｉ)，Ｖｉｋ(χｉ)とＬｉｊ，ｋ＋１(χｉ)との間の関係を説明する図である。
【図７】区間[０，８]，[２，８]，[４，８]，[６，８]における下界を説明する図である。
【図８】区間[０，６]，[２，６]，[４，６]における下界を説明する図である。
【図９】区間[０，４]，[２，４]における下界を説明する図である。
【図１０】本発明の電源計画問題求解方法の実施形態の一例を説明するフローチャートである。
【図１１】実施形態の電源計画問題求解方法をプログラムを用いて実施する場合の電源計画問題求解装置の機能ブロック図である。
【図１２】負荷持続曲線を説明する図である。
【図１３】実施例１の負荷持続曲線を説明するである。
【図１４】実施例１の電源計画の期待平均と標準偏差との間の関係を説明する図である。
【符号の説明】
【０３２８】
１０  確率計画問題求解装置
１１  制御部
１２  記憶部
１３  入力部
１４  表示部
１５  メモリ
１６  確率計画問題求解プログラム
１７  確率計画問題設定データ
【図１】
0004981559.tif 000071
【図２】
0004981559.tif 000072
【図３】
0004981559.tif 000073
【図４】
0004981559.tif 000074
【図５】
0004981559.tif 000075
【図６】
0004981559.tif 000076
【図７】
0004981559.tif 000077
【図８】
0004981559.tif 000078
【図９】
0004981559.tif 000079
【図１０】
0004981559.tif 000080
【図１１】
0004981559.tif 000081
【図１２】
0004981559.tif 000082
【図１３】
0004981559.tif 000083
【図１４】
0004981559.tif 000084