数理解析研究所講究録
第 1864 巻 2013 年 157-163

157

An Interactive Algorithm for Hierarchical Multiobjective
Stochastic Linear Programming Problems
名古屋市立大学大学院・人間文化研究科 矢野 均
Hitoshi Yano
Graduate School of Humanities and Social Sciences, Nagoya City University
名古屋大学大学院・情報科学研究科 松井 孝太

Kota Matsui
Graduate School of Information Science, Nagoya University

1

Introduction

現実世界の意思決定場面では，しばしば階層構造の下でシステム全体の目標を達成することを求められる．
ここで階層構造とは，複数の，システムの各部門に属する意思決定者が，相互作用をしながらそれぞれの目標を個別に達成しようとすることであるとする．例えば，Stackelberg ゲームは階層型多目的数理計画問題とみなすことができる [2]. このゲームの解，Stackelberg 解，を効率的に導出するために，Lai[3] や，Lee ら [4],Shih ら [6] は，階層型線型計画問題に対して，各意思決定者が協カ関係にあるという仮定の下で，最適性のメンバシップ及び決定力という概念を導入したファジイアプローチを提案した．

他方，実際の意思決定状況において，意思決定者は不確実性を含む情報やデータを取り扱うという困難にもしばしば直面する．Sakawa ら等 [5] は，確率計画法 [1] における確率最大化モデルを用いて確率変数係数を含む多目的線型計画問題を定式化した．しかし確率最大化モデルは，意思決定者に対して，あらかじめ目的関数の許容値を設定することを要求する．一般に，確率最大化モデルにおいて，目的関数の許容値と，対応する確率関数の値とは競合しており，上述の要求は困難を伴う．この困難を回避するために，Yano and Matsui[7]は，多目的確率線型計画問題に対してファジイアプローチを提案した．

本論文では，階層型多目的確率線型計画問題に焦点を当て，階層構造を持つ複数の意思決定者の満足する解を導出するための対話型アルゴリズムを提案する．まず，第 2 節で問題を定式化し，新たなパレート最適性の概念を導入する．第 3 節では，意思決定者の満足解を得るための，ファジイ決定に基づくマックスミニ問題を導出する．第 4 節では，第 3 節で導出したマックスミニ問題の最適解と第 2 節で定義したパレート最適解との関係性を示し，第 5 節で対話型アルゴリズムを提案する．第 6 節で本論文をまとめる．
本論文は，文献 [8] のサーベイ論文である．

2Problem Formulation

我々が考察するのは， 人の意思決定者 $(DM_{r}, 1\leq r\leq q)$ が，共通の線型不等式制約条件の下で，各々の持つ確率変数係数を含む複数の線型目的関数を最小化しょうとする問題で，以下のように定式化される:
$q$

158
[HMOSLP]lst level decision maker: $DM_{1}$$\min(\overline{z}_{11}(x), \cdots,\overline{z}_{1k_{1}}(x))$

qth level decision maker: $DM_{q}$$\min(\overline{z}_{q1}(x), \cdots,\overline{z}_{qk_{q}}(x))$

subject to$x=(x_{1_{\rangle}}\cdots, x_{n})^{T}\in X:=\{x\in \mathbb{R}^{n};Ax\leq b, x\geq 0\}$口

ここで， は各成分が実数であるような $m\cross n$ 係数行列，$A$$b\in \mathbb{R}^{m}$$1\leq r\leq q,$ $1\leq l\leq k_{r}$であり，$DM_{r}$の各目的関数$\overline{z}_{rl}(x)$,は，$\overline{c}_{rl}:=c_{rl}^{1}+\overline{t}_{rl}c_{rl}^{2}, \overline{\alpha}_{rl}:=\alpha_{rl}^{1}+\overline{t}_{rl}\alpha_{rl}^{2}$として，$\overline{z}_{rl}(x):=\overline{c}_{rl}x+\overline{\alpha}_{rl}$で定義される形式的線型関数である．ただし，$c_{r}^{i_{l}}\in \mathbb{R}^{n},$増加な累積分布関数$T_{rl}$$\alpha_{r}^{i_{l}}\in \mathbb{R},$$1\leq i\leq 2$であり， は連続かつ狭義単調$\overline{t}_{rl}$を持つ確率変数であるとする．

HMOSLP には通常の数理計画法の議論はそのままでは適用できない．そこで，確率線型計画法の手法により，HMOSLP の目的関数$\overline{z}_{rl}(x)$の最小化を，目的関数が許容値$f_{rl}$以下である確率$p_{rl}(x, f_{rl}):=Pr(\omega;z_{rl}(x, \omega)\leq f_{rl}) , 1\leq r\leq q, 1\leq l\leq k_{r}$の最大化問題に置き換える．ここで，$p_{r}(\cdot)$

ときの目的関数$\overline{z}_{rl}(x)$は確率測度， は事象を表し，$\omega$の実現値を表す．

各意思決定者 $DM_{r},$ $1\leq r\leq q$ が，それぞれ目的関数の許容レベル$f_{r}:= (f。1, \cdots, f_{rk_{r}}) , 1\leq r\leq q$を設定すれば，HMOSLP は次の HMOSLPI(f) に変換される :[HMOSLPI $(f)$ ]lst level decision maker: $DM_{1}$$\max_{x\in X}(p_{11}(x, f_{11}), \cdots,p_{1k_{1}}(x, fik_{1}))$

qth level decision maker: $DM_{q}$$\max_{x\in X}(p_{q1}(x, f_{q1}), \cdots,p_{qk_{q}}(x, f_{qk_{q}})) \square$$z_{rl}(x,\omega)$

はある事象$\omega$

が生起した

159
ここで，HMOSLPI(f) の目的関数
累積分布関数$T_{rl}$$p_{rl}(x, f_{rl})$

は，$c_{r}^{2_{l^{X}}}+\alpha_{r}^{2_{l}}>0,1\leq r\leq q,$$1\leq l\leq k_{r}$であるとき， の$\overline{t}_{rl}$を用いて$p_{rl}( x, f_{r}\iota)=T_{rl}(\frac{f_{rl}-(c_{rl}^{1}x+\alpha_{rl}^{1})}{c_{rl}^{2}x+\alpha_{r}^{2_{\iota}}})$と書ける．以下，本稿ではこれを仮定する．
HMOSLPI (f) を取り扱うために，新たなパレート最適性を次のように定義する :定義 1$x^{*}\in X$ がHMOSLPl(f) の$P$-パレート最適解であるとは，$p_{rl}(x, f_{rl})\geq p_{rl}(x^{*}, f_{rl}) , 1\leq\forall r\leq q, 1\leq\forall l\leq k_{r}$かつ$p_{rl}(x, f_{rl})>p_{rl}(x^{*}, f_{rl}) , 1\leq\exists r\leq q, 1\leq\exists l\leq k_{r}$を満たすような $x\in X$ が存在しないことと定義する．口3 A Satisficing Method Based on the Fuzzy Decision
HMOSLPI (f) において，各 $DM$ 。は，目的関数の許容値ベクトル $f_{r}=(f_{r1}, \cdots, f_{rk_{r}})$ の最小化と，対応する実現確率 $p_{r}(x, f_{r})=(p_{r1}(x, f_{r1}), \cdots ,p_{rk_{r}}(x, f_{rk_{r}}))$ の最大化を同時に望んでいると考えた方が自然である．この意味で HMOSLPI(f) の自然な拡張である次の問題を考察する :[HMOSLP2]
lst level decision maker: $DM_{1}$$\max_{x\in x}(p_{11}(x, f_{11}), \cdots,p_{1k_{1}}(x, fik_{1}), -f_{11}, \cdots, -fi_{k_{1}})$

qth level decision maker: $DM_{q}$$\max_{x\in X}(p_{q1}(x, f_{q1}),$ $\cdots$$p_{qk_{q}}(x, f_{qk_{q}}),$

ここで，HMOSLP2 の各目的関数$p_{rl}(x, f_{rl})$$-f_{q1},$$\cdots$及び$f_{rl}$$-f_{qk_{q}})$口に対して，$DM_{r}$はそれぞれ 「だいたいある値以上にしたい」，「だいたいある値以下にしたい」 というファジイ目標を持っていると考え，これらのファジイ目標を規定するメンバシップ関数をそれぞれ$\mu_{rl}(p_{rl}(x, f_{r}\iota)) , \nu_{rl}(f_{rl})$で表す．
仮定 1(i)$\mu_{rl}(p_{rl}(x, f_{rl}))$$(ii)\nu_{rl}(f_{rl})$

は，$p_{rl}(x, f_{rl})$に関して連続かっ狭義単調増加であるように定める．

は， に関して連続かっ狭義単調減少であるように定める．ロ$f_{rl}$

メンバシツプ関数 $\mu_{rl}(p_{rl}(x, f_{rl}))$ 及び大化する問題に変換できる．

$\nu_{r}\iota(f_{rl})$を用いると，HMOSLP2 は，次のようなファジイ目標を最160[HMOSLP3]
lst level decision maker: $DM_{1}$$\max_{x\in X}(\mu_{11}(p_{11}(x, f_{11})), \cdots, \mu_{1k_{1}}(p_{1k_{1}}(x, fik_{1})), \nu_{11}(f_{11}), \cdots, \nu_{1k_{1}}(fik_{1}))$

qth level decision maker: $DM_{q}$$\max_{x\in X}(\mu_{q1}(p_{q1}(x, f_{q1})), \cdots, \mu_{qk_{q}}(p_{qk_{q}}(x, f_{qk_{q}})), \nu_{q1}(f_{q1}), \cdots, \nu_{qk_{q}}(f_{qk_{q}})) \square$

ここで，HMOSLP3 において，$\mu_{f\iota}(p_{r}\downarrow(x, f_{r}\iota))$の最大化と$\nu_{rl}(f_{rl})$の最大化は完全に競合する，すなわちトレードオフの関係にあることに注意する．

HMOSLP3 は多目的計画問題であるため，通常の数理計画の手法はそのままでは適用できない．そこで，意思決定者がファジィ決定に基づき，統合メンバシップ関数$D_{rl}( x, f_{rl}):=\min\{\mu_{r}\downarrow(p_{r}\downarrow(x, f_{rl})), \nu_{rl}(f_{rl})\}$の最大化を目指すと仮定する．このとき，意思決定者の満足する解は，次の MAX-MIN 問題を解くことで得られる :[MAXMINI]$\max_{x,f_{rt},\lambda}\lambda$

subject to(1)$\mu_{rl}(p_{rl}(x, f_{ri}))\geq\lambda$$D_{rl}(x, f_{rl})\geq\lambda\Leftrightarrow\{$$\nu_{rl}(f_{rl})\geq\lambda$$x\in X,$$\lambda\in[0,1],$$1\leq r\leq q,$$1\leq l\leq k_{r}$口しかし，MAXMINI は 人の意思決定者間の階層構造を反映していない．そこで，上位レベルの意思決定者が，下位レベルの意思決定者に対して優先性を持つという階層構造を反映させるために，MAXMINI の制$q$

約条件 (1) に対して，決定力係数ベクトル$w:=(w_{1}, \cdots, w_{q})$を導入した次の問題を考える:$[MAXMIN2(w)]$$\max_{x_{rl},\lambda}\lambda$

subject to$\mu_{rl}(p_{rl}(x, f_{rl}))\geq\lambda w_{r}$$D_{rl}(x, f_{rl})\geq\lambda w_{r}\Leftrightarrow\{$$\nu_{rl}(f_{rl})\geq\lambda w_{r}$$x\in X,$$\lambda\in[0,1],$$1\leq r\leq q,$$1\leq l\leq$

醇口(2)

161
仮定 2

(i) $DM$ 。が決定カパラメータを定め，は決定カを持たないとする．
(ii)q 人の意思決定者間の階層構造を反映させるため，決定カパラメータは$w_{r+1}$$DM_{q}$$w_{1}=1\geq w_{2}\geq\cdots\cdots\geq w_{q-1}\geq w_{q}>0$を満たすとする．
$\square$

仮定 1 及び$c_{r}^{2_{l}}x+\alpha_{r}^{2_{l}}>0$であることを用いて，MINMAX $2(w)$ の制約条件 (2) は，$D_{r}\iota(x, f_{rl})\geq\lambda w_{r}$(3)$\Leftrightarrow\nu_{rl^{1}}(\lambda w_{r})-(c_{rl}^{1}x+\alpha_{rl}^{1})\geq T_{rl}^{1}(\mu_{rl}^{-1}(\lambda w_{r}))(c_{rl}^{2}x+\alpha_{rl}^{2})$と，決定変数$f_{rl}$を含まない形に変形することができる．従って，MINMAX2(w) は，次の問題と等価である :[MAXMIN3 $(w)$ ]$\max$$\lambda$$x\in X,\lambda\in[0,1]$

subject to(4)$\nu_{rl^{1}}(\lambda w_{r})-(c_{rl}^{1}x+\alpha_{rl}^{1})\geq\tau_{rl}^{-1}(\mu_{rl}^{-1}(\lambda w_{r}))(c_{rl}^{2}x+\alpha_{rl}^{2})$$1\leq r\leq q,$$1\leq l\leq k_{r}$口

ここで，MAXMIN $3(w)$ の制約条件 (4) は，$\lambda\in[0,1]$を固定する毎に線型の不等式制約条件となることに注$MAXMIN3(w)$ の最適解は， に関する二分法と，線型計画法における 2 段階単体法の第 1意する．従って，段階，すなわち実行可能性のテスト段階，の混合アルゴリズムにょって導出することができる．
$\lambda$

4Pareto Optimality of an Optimal Solution of MAXMIN3(w)MAXMIN3(w) の最適解と HMOSLPI(f) の -パレート最適解との間には次のような関係が成り立っ．
$P$

定理 1

$(x^{*}, \lambda^{*})$

が $MAXMIN3(w)$の一意的な最適解ならば，$x”\in X$ は HMOSLPl(f ) の$*$$P$-パレート最適解である．ここで， は，$f^{*}$$f^{*}=(\nu_{11}^{-1}(\lambda^{*}w_{1}), \cdots, \nu_{1k_{1}}^{-1}(\lambda^{*}w_{1}), \cdots, \nu_{q1}^{-1}(\lambda^{*}w_{q}), \cdots, \nu_{qk_{q}}^{-1}(\lambda^{*}w_{q}))$で与えられる HMOSLP の目的関数の目標値ベクトルである．口に対して
定理 1 において，MAXMIN3(w) の最適解適性は保証されない．この場合，MAXMIN3(w) の最適解認する必要がある．このために，次の問題を考える．
$(x^{*}, \lambda^{*})$$x^{*}$$(x^{*}, \lambda^{*})$[P-パレート最適性のテスト問題]$x\in x,0\max_{\epsilon_{rl}\geq}\sum_{r=1}^{q}\sum_{\iota=1}^{k_{r}}\epsilon_{rl}$subject to$(c_{rl}^{1}x+\alpha_{rl}^{1})-T_{rl}^{1}(\mu_{p_{rl}}^{-1}(\lambda^{*}w_{r}))(c_{rl}^{2}x+\alpha_{rl}^{2})+\epsilon_{rl}$$=(c_{rl}^{1}x^{*}+\alpha_{r}^{1_{\iota}})-\tau_{rl}^{1}(\mu_{p_{rl}}^{-1}(\lambda^{*}w_{r}))(c_{rl}^{2}x^{*}+\alpha_{rl}^{2})$$1\leq r\leq q,$$1\leq l\leq k_{r}$口が一意的でなければ，解の$P$-パレート最が $P$ -パレート最適解であるかどうかを確

162$P$-パレート最適性のテスト問題について，次の事実が成り立つ．

定理 2

パレート最適性のテスト問題の最適解$(\tilde{x}, \epsilon_{rl})$

において，$\tilde{\epsilon}_{r}\iota=0, 1\leq\forall r\leq q, 1\leq\forall l\leq r_{k}$ならば，$x^{*}$

は $P$ -パレート最適解．一方，ある

$r$

及び$l$

に対して，

$\tilde{\epsilon}_{rl}>0$ならば， が -パレート最適解．口$\tilde{x}$$P$

5 An Interactive AIgorithm
HMOSLPI (f) の$P$

-パレート最適解集合の中から，階層構造を持つ意思決定者$DM_{f},$$1\leq r\leq q$の満足解を導出するために，対話型アルゴリズムを以下に示す．

Stepl :HMOSLP2 の各目的関数 $p_{rl}(x, f_{rl}),$$\mu_{r}\iota(p_{rl}(x, f_{rl})),$$\nu_{rl}(f_{rl})$$f_{rl}$に対して，仮定 1 を満たすようにメンバシツプ関数を設定する．

Step2: 決定カパラメータの初期値を $w_{r}=1,1\leq r\leq q$ と設定する．
$Step3$ : MAXMIN $3(w)$ に対して， に関する二分法と 2 段階単体法の第 1 段階の混合アルゴリズムを用$\lambda$

いて最適解$(x^{*}, \lambda^{*})$を導出する．

に対して，-バレート最適性のテスト問題を解く．
$1\leq r\leq q$ が現在のメンバシップ関数値に満足していれば終了．
Step5: 各意思決定者がStep4: 最適解$P$$(x^{*}, \lambda^{*})$$DM_{S}$$DM_{r},$が現在のメンバシップ間数値に不満を持っていれば，決定カパラメータ $w_{s}+1$ を以下の仮定 3 に基づいて更新し，Step4 に戻る :仮定 3(決定カパラメータの更新ルール)$w_{t}=w_{s+1}$

6

ある添字 $t>s+1$ で，$w_{s+1}<w_{t}$ となるものが存在するとき，とおく．
$\square$Conclusion

本論文では，階層型多目的確率線型計画問題 (HMOSLP) を定式化し，階層構造を持つ複数の意思決定者の満足解を導出する手法として，対話型アルゴリズムを提案した．まず，形式的な数理計画問題である
HMOSLP を既存の数理計画法で取り扱うために，確率最大化モデルを適用した．従来の確率最大化モデルでは，各意思決定者が目的関数の許容値を設定するのに対して，提案手法では目的関数の許容値及び対応する確率分布関数に対するファジイ目標のメンバシツプ関数を設定する．これによって，目的関数の許容値及び対応する確率分布関数値の間の均衡が期待できる．

今後の課題としては，実データを用いた数値実験を行う必要がある．特に，作物の価格が確率変動するという状況の下で，どの作物をどれだけの面積で栽培するべきかを決定する，農業分野の作付け計画問題への応用が考えられる．また，本論文で取り扱った問題の理論的拡張として，randomness と fuzziness という 2 種類のあいまいさを同時に取り扱う fuzzy random variable や random fuzzy variable を係数に含むような線型計画問題への拡張を試みる．

163

参考文献[1] 石井博昭 ” 確率論的最適化” 数理計画法の応用 : 理論編 (講座・数理計画法 ;10) , pp.1-40, 産業図書，1982.
[2] Anandalingam, G., “mathematical programming model of decentralized multi-Level systems”
Journal of Operational Research Society, 39, pp.1021-1033, 1988.
[3] Lai, Y. . “Hierarchical optimization: a satisfactory solution” Fuzzy sets and systems, 77, pp.321335, 1996.
[4] Lee, E. . and Shih, H. “Fhzzy and Multi-level Decision Making” Springer, 2001.
$A$

$J$

$S$

[5] Sakawa, M., Nishizaki, I. and Katagiri, H. “ Fuzzy Stochastic Multiobjective programming” Springer, 2011.
[6] Shih, H., Lai, Y.- . and Lee, E. ., “Fuzzy approach for multi-level programming problems” Com$J$$S$puters and Opemtions Research, 23, pp. 73-91, 1996.
[7] Yano, H. and Matsui, K. “ Fuzzy Approaches for Multiobjective Fuzzy Random Linear Programming

Problems Through a Probability Maximization Model” Lecture Notes in Engineering and Computer
Science: Proceedings of The International MultiConference of Engineers and Computer Scientists
2011, IMECS 2011, 16-18 March, 2011, Hong Kong, pp. 1349-1354.
[8] Yano, H. and Matsui, K. “Hierarchical Multiobjective Stochastic Linear Programming Problems
Based on the Fuzzy Decision” Iaeng Transactions on Engineering Technologies Volume 7: Special

Edition of the International Multiconference of Engineers and Computer Scientists 201, pp. 1-14,
World Scientific Publishing Company, 2011.