数理解析研究所講究録
1079 巻 1999 年 196-204

196

ファジィランダムコストをもつ最小スパニングヅリー問題

1

大阪大学

*片桐大阪大学

石井英樹
博昭

KATAGIRI Hideki
ISHII Hiroaki

はじめにネヅトワークにおける応用上重要な問題の つとしてスパニングツリー問題がある。 そのうち、 枝のコストの和を最小にする問題を最小スパニングヅリー問題と呼び、 費用が確定値で与えられている場合の解法については、 [1, 2, 3, 4, 5] によって効率的なアルゴリズムが与えられている。
コストが確率変数で与えられている場合については、 H.Ishii らによって研究されており、 総和コストに関する機会制約条件計画問題として定式化したモデル [6] や目標値とともに確率レベルも同時に最大化しようとするモデル [7] に対し多項式時間で解く効率的なアルゴリズムを提案している。
また、 コストが可能性変数で表される場合における解法は伊藤ら [8] によって導入され、 片桐らによってより効率的なアルゴリズムが提案されている [9]。
従来、不確実性が存在する場合の意思決定法として、 大きく分けて確率計画法によるアプローチとファジィ数理計画法によるアプローチが研究されてきたが、 現実にはコストが確率的に変動する場合でもその実現値を完全に知る事が出来ないこともあり、 ファジィ性とランダム性が同時に現れることも多い。
本研究では、 このような確率とファジィの両性質をもつ要素をファジィランダム変数で表し、 ファジィ性とランダム性が存在する状況下での意思決定法の– つを提案する。
まず、 2 節でファジィランダム変数について簡単に述べた後、 3 節で総和コストに対するファジィ目標を設定し、 そのファジィ目標を満たす可能性測度がある値 以上である確率があるレベル 以上であるという制約の下で、 を最大化する問題として定式化する。 4 節で元の問題を解くための部分問題を導–$h$$\alpha$$h$入し、 さらに 5 節でその部分問題を解くためにパラメータを含むスパニングヅリー問題を導入し、 元の問題の最適解を多項式時間で求めるアルゴリズムを示す。

2

ファジィランダム変数
事象の発生にかかわる不確かさを扱うものとして確率があり、 -方、 人間の主観や言葉、 意味の曖昧さを表現するものとしてファジィ集合は、 これらの曖昧さあるいは不確かさは基本的に異なるものであり、 現実には曖昧な事象がランダムに観測されるといった場合など同時に 2 つを考慮にいれる必要がある場合も多い。 このような状況に適用できる数学的概念として、 1978 年に Kwakernaak によって最初に導入されたファジィランダム変数がある [10]。その後、 Puri とがランダム集合を拡張する形で別の定義を与えると共に理論的な土台を構築した [11]。その他にも何人かの研究者がファジィランダム変数を定義している [12, 13, 14]。ファジィランダム変数はひとことで言えば確率変数の実現値がファジィ集合になる変数のことである。例えば、 ある集団に対し、 明日の天候をたずねた時、「暑い」や「涼しい」 といった言葉で回答する場合、 ある集団における回答は、 ファジィランダム変数の実現値の集ま$\mathrm{R}\mathrm{a}\mathrm{l}\epsilon \mathrm{s}\mathrm{C}\mathrm{u}$り (標本) とみなすことが出来る。

本研究では、 ファジィ数における中心が確率変数であるようなファジィランダム変数を扱っており、 この場合には Kwakernaak の定義と Puri, Ralescu の定義は–致することが知られている [15]。

197
3定式化
を点集合 $N=\{v_{1}, v_{2}, \ldots, v_{n}\}$ と枝集合 $E=\{e_{1}, e_{2}, \ldots, e_{m}\}\subseteq N\mathrm{x}N$ からなる無向グにはコスト果が設定されているものとする。 $G$ におけるスパニングヅリー $T=\tau(N, s)$ は$G^{\mathrm{Y}}=(N, E)$

ラフとし、
$T$

$e_{\dot{*}}$

かつ閉路を含まない連結部分グラフである。

$S\underline{\subseteq}E$は次のように 0–1 変数の$T$:$x_{i}=1$,$e_{i}\in S$$x_{i}=0$,$e_{i}\not\in S$$x_{1},$ $x_{2},$$\ldots,$$x_{m}$で表すことができる。

以下では $X$ を $T(N, S)$ に対応する 0–1 ベクトルの集合とし、 $X$ をスパニングツリ一の集合とみなす。
このとき、 最小スパニングヅリー問題は以下のように定式化される。

:$P_{1}$$7r\iota i7\iota imizecx$

subject to $x\in X$
本稿ではコスト$c_{i}$

が次のようなメンバシヅプ関数をもつ可能性分布$\mu C\dot{.}(\omega)$で制限されるファジィランダ

ム変数である場合について考察する。
$\mu_{C\dot{.}(\omega)}(\mathrm{q})=\max\{L(\frac{c_{i}-d_{i(\omega)}}{\alpha_{i}}),$$0\}$

ここで型関数 $L$ は $\mathrm{R}arrow[0,1]$ である単調減少連続関数で $L(x)=L(-X)\forall x\in \mathrm{R}$ かつ $L(\mathrm{O})=1$ を満たをもつ正規分布に従う互いに独立な確率変数とする。 すすものとする。 また、 &(\mbox{\boldmath $\omega$}) は平均 , 分散
も確率に伴ってなわち、 可能性変数において中心が確率変数になっている場合であり、的に変動する。
は D.Dubois と H.Prade [17] によるファジィ数とすると を表すファジィランダム変数の演算を適用して$\sigma_{i}^{2}$$\mu_{i}$$d_{i}(\omega)$$\mathrm{Y}(\omega)$$y$$y=\mathrm{c}x$$\mu_{C\dot{.}(\omega)}(\alpha)$$\mu_{Y(d)\backslash }‘:y)’\max=\{L(\frac{y-\sum_{i=}^{m_{1}}d_{i}(\omega)X_{i}}{\sum_{--1}^{m}\alpha_{i}X_{i}}.),$$0\}$となる。 次に目的関数値にファジィ目標 $G$ を「Y(\mbox{\boldmath $\omega$}) がだいたい$y_{1}$以下である」 とし、 $G$ を次のようなメンバシヅプ関数に特性づけられるファジィ集合で表す。

1,$\mu_{G}(y)=\{$$g(y)$$0$,$y\leq y_{1}$,$y_{1}<y<y_{2}$$y\geq y_{2}$ここで、 $g$ は単調減少連続関数とする。さらにファジィ目標 $G$ を満たす可能性測度を次のように定義する。
$\Pi_{Y(\omega\}}(G)=\sup_{v}\triangle\min\{\mu_{Y(}\omega)(y), \mu_{G}(y)\}$はに伴って確率変数となる。従来、不確実性が存在する状況下での意思決定法として確率計画法やファジィ数理計画法が考えられており、 種々の意思決定法が研究されている。確率計画法に関しては [18] に、 またファジィ数理計画法に関しては $[19, 20]$ に詳しく述べられている。 また、 ファジィ数理計画法と確率計画法の比較やその類似性についての研究も行われている [21, 22, 23]。近年、 ファジィ性とランダム性を同時に考慮した意思決定法も多く研究されている [24, 25, 26, 27, 28, 29]。ファジィラ
ンダム変数を数理計画に応用した研究には [30, 31, 32] らがあるが、 我々はに対する意思決定法とし$\mathrm{n}_{Y(\omega)}$$\mu_{Y(\omega)}$$P_{1}$

198て、 確率計画法における $P$ モデルとファジィ数理計画法における可能性計画法をあわせた形の次のモデルを提案する。
$P_{2:}$

maximizesubject to$h$$Pr(\mathrm{I}\mathrm{I}_{Y(\omega})(G)\geq h)\geq\alpha$$\in X$$x$である。 ここで $Pr$ は確率測度を表し、 確率レベルは$\alpha$$\alpha>\frac{1}{2}$を満たす確定値とする。

を変形すると$\mathrm{I}\mathrm{I}_{Y(y)}(G)\geq h$$\sup_{y}\min\{\mu Y\mathrm{t}\omega)(y), \mu_{G}(y)\}\geq h$$\exists y$: “$\Leftrightarrow$$\exists y$:$\Leftrightarrow$$\exists y$: “$\Leftrightarrow$$\sum_{i=1}^{m}d_{i}(\omega)Xi-L^{*}(h)\sum_{=i1}\alpha iX:\leq\mu_{G}^{*}(h)m$$\Leftrightarrow$となるので:$P_{3}$$\mu_{\mathrm{Y}(\omega}$) $(y)\geq h,$$\mu_{G}(y)\geq h$”“ $L( \frac{y-\sum_{i1}^{m}=d_{i}(\omega)X_{i}}{\sum_{i=1}^{m}\alpha_{1X_{i}}}.)\geq h,$$\mu_{G}(y)\geq h$$y \geq\sum_{1i=}^{m}\psi(\omega)x:-L*(fl)\sum_{i=}m1\alpha\dot{|}X_{1}.,$”$y\leq\mu_{G()}^{*}h$”は次の角のように変形される。

$P_{2}$

maximize$h$subjed to$Pr[ \sum_{i=1}^{m}\{d_{i}(\omega)-L^{*}(h)\alpha:\}xi\leq\mu_{G}^{*}(h)]\geq\alpha$$x\in X$

ただし、$L^{*}(\cdot),$$\mu_{G}^{*}(\cdot)$は次のような擬逆関数である。
$\sup\{r|L(\Gamma)>h, r\geq 0\}$$L^{*}(h_{I}^{\backslash }$$=$$(h=0)$$\infty$$\mu_{G}^{*}(h)$$=$$(0<h\leq 1)$$\{$$\sup\{r|\mu_{G}(\Gamma)\geq h\}$正規分布の性質から$\frac{\sum_{i=1}^{m}d_{i}(\omega)X_{i}-\sum^{m_{1}}i=\mu_{i^{X_{i}}}}{\sqrt{\sum_{i--1\mathrm{t}}^{m2}\sigma x_{l}}}$は標準正規分布$\mathrm{N}(\mathrm{O},1)$に従うので、$K_{\alpha}$

を$\alpha$分位点とすると次のような等価確定条件に変換される。となる。 ゆえに解くべき問題は次の $P$ となる。
$P$:$-arrow m*\cdot-*\cdot\sim-L$

1994

部分問題の導入
以下ではと定義し、 次の部分問題を考える。
$P_{4}$

minimize $z(x, h)$subject to $x\in X$:

この問題と元の問題 $P$ に対して次の補題が成り立つ。
が $0<h^{*}<1$ であるとき、 高の最適解が $P$ の最適解である必要十分条件は補題 1 $P$ の最適値における最適解げに対して $z(x^{*}, h^{*})=\mu_{G}^{*}(h^{*})$ が成り立つことである。
$h^{*}$$0<h<1$ のとき、

$P_{4}$の定義から、 $\mu_{G}^{*}(h)=g^{-1}(h)$ となる。 $P$ の最適解と最適値をそれそれにおける) の実行でないと仮定する。 このとき、$h^{*}(0<h^{*}<1)$ とし、可能性より $z(x^{*}, h^{*})<g^{-1}(h^{*})$ , すなわち

証明$\mu_{G}$$h^{*}$$z(x^{*}, h*)=_{\mathit{9}^{-}}(1h^{*})$$x^{*},$$x^{*},$が成り立つ。 ところが $L^{*}(h)$ と $g^{-1}(h)$ の単調減少性と連続性から $z(x^{*}, h)$ に対して $h^{*}<h^{r}$ が存在すの最適性に矛盾する。
る。 このことは逆に凸の最適解を $(x^{*}, h^{*})$ とし、 $z(x^{*},’ h^{*})=g^{-1}(h^{*})$ を満たすものとする。 $-$. れが $P$ の最適解でないとすると、 以下の関係式を満たす $(x, h’)$ が存在する。
$h^{*}$(1)$h^{*}<h^{l}$.

(2)

かっ

ところが $(x^{*}, h^{*})$ の最適性と $L^{*}(h),$ $g^{-1}(h)$ の単調減少性により以下の関係式が成り立つ。

$<$$<$

これは (2) 式に矛盾する。

口次に$f1(X$}$= \sum_{i=1}\Delta Lm\{\mu_{i}-*(h)\alpha i\}Xi,$$f_{2}(_{X)}$全.

$\sum_{i=1}^{m}\sigma_{i}^{2}x_{1}$200$\ovalbox{\tt\small REJECT}$を解くために補助問題として$P_{4}’$:$h$

一定の下で 2 目的問題

minimize $f1(x)$miminize $f_{2}(x)$subject to $x\in X$
を考える。

補題 2

$P_{4}$の最適解であるための必要条件はの最適解げがで、 $i\neq j$ に対して証明$P_{4}$$P_{4}’$$P_{4}’$の雲譲解であることである。の非読解でないとする。 このとき、 げは 2 目的問題

$P_{4}’$の非劣解ではないの$f_{i}(_{X^{*}})>f_{i}$(3)$f_{j}(x^{*})\geq f_{j}$(4)を満たすある $x’$ が存在する。の最適性より $z(x^{*}, h^{*})=g^{-1}(h^{*})$ であるが、 (3), (4) より $x’$ に対し$z(x’,h^{*})<g^{-1}(h^{*})$てはが成り立つ。 このとき、 $z(x’, h’)<g-1(h’)$ を満たす $h^{*}<h’$ が存在することになりの最適性に矛盾する。 口$x^{*}$$h^{*}$5

解法とアルゴリズム

補題 2 より、 $P$ の最適解を求めるには、 効率よく非劣解を列挙し、 可能性測度を最大化するスパニングツリーを求めればよいことがわかる。
また、に対しては、 スカラー化して– 目的にすることにより、 異なる全ての非劣解を求めることができる。 したがって、 次の問題を考える。
$P_{4}’$$P_{4}^{l}(\lambda)$$h$:一定のとき、minimize$\sum_{\mathrm{i}=1}^{m}(\mu_{i}-L^{*}(h)\alpha i+\lambda K_{\alpha}\sigma_{i}^{2})x_{i}$subjed to$x\in X$

$P_{4}’(\lambda)$

は–つのパラメータ$\lambda$をもつパラメトリヅク最小スパニングツリー問題となり、[33] による効率的な解法が提案されている。
したがって、 目的関数の係数部分を$c_{i}’=\mu i-L*(h)\alpha i+K_{a}\sigma_{i}^{2}\lambda$とおくと、 , は枝に付随するコストであり、 と の 2 つのパラメータによって変化する。の非劣解のうち、 異なるものを全て求めるには、 最小スパニングツリーを求めるアルゴリズムを考慮に入れると,の順序が入れ替わるところを全て調べれば十分であることがわかる。 (5) 式は 2 つのパラメータ$h,$をもつことから $L$ “ $(h)=q$ とおくとこれは 3 次元空間 ( $h,$ , 果) における平面を表している。
を満たす をとすると$c_{i}$$h$$e_{i}$$\lambda$$P_{4}’$$c_{\acute{i}}$$\lambda$$\lambda$$c_{\dot{l}}’=c_{\acute{j}}$$\lambda$$\lambda_{i\mathrm{j}}$(5)$\lambda_{ij}=\frac{\mu_{i}-\mu_{j}+q(\alpha j-\alpha i)}{K_{\alpha}(\sigma_{j}^{2}-\sigma^{2})i}$

であり、, K。は定数であるから、平面における直線になる。ゆえに
順序は–意に決まる。 ここで次の補題が成り立つ。
$\mu_{i},$$\sigma_{i}$補題 3 異なる 2 平面の交わりの$\lambda$$(q, \lambda)$

座標の順序が–定ならば、$c_{i}’$$q$が固定されれば$\lambda_{\dot{\iota}j}\text{の}$座標の順列の集合は –意に決まる。

201の前後のみで変わる。とすると 2 平面の 座標の順序は
証明 2 平面 $k,$ の交わりの直線をま、 平面 $\lambda=0$ との交わりである直線の 切片の順序が $i(i=1, \ldots, m)$ であるとする。 2 平面の交点において $m$ 本の平面のとするとの中で より大きい値の中でうち–番小さい値をにおいて直線 $s,$ が交わり、 その 2 直線の . 座標の順序のみが座標の順序は–定であり、 平面$\mathrm{A}\mathrm{a}$$l$$\lambda_{kl}$$c_{i}’$$\lambda_{kl}$$c_{i}’$$\lambda_{kl}$$\mathrm{c}_{1}’$$0<\lambda<\lambda\epsilon t$$\lambda_{st}$$0$$c_{1}’$$t$$\lambda=\lambda_{st}$入れ替わる。 以下、 順に 座標の小さいものから順に考えていけば交点間では 座標の順序は–意に決まり、 その前後では交わった 2 平面の順序が入れ替わるだけである。 よって、 2 直線の交点の順序が定ならば現れる順序の集合は –意に決まる。 口$c_{\acute{i}}$$\lambda$

補題 4 から次の定理が導かれる。
定理 12 目的スパニングヅリー問題の非劣解の数はせいぜい $O(m^{4})$ である。
証明 2 平面 $k,$

$l$の交線は$c_{\acute{k}}=c_{l}’$より$\lambda=\frac{\mu\iota-\mu_{k}+q(\alpha k-\alpha\iota)}{K_{o}(\sigma^{2}-k\sigma_{l}^{2})}$が決定されれば交点の値は定まり、 交点の順序は–意に決まる。 逆に 2 平面同士の交線の順序が–致する (その前後で入れ替わる) はもし存在するならばただ–つに決まる。 また 2 平面の交わる直線 \mbox{\boldmath $\lambda$}毎と 2 平面 $j,$ の交わる直線 \mbox{\boldmath $\lambda$}鈎の交点、 すなわち 3 平面の交点も、 もし存在するならとなるため、$q$$i,$ $j$$q$$k$ば、 ただ $-$ つに決まる。 4 平面以上が交点を持つ場合は少なくとも 3 平面が交点をもつ必要があるため、考慮する必要はない。残りは平面 $\lambda=0$ , すなわち 切片における順序が入れ替わる場合があり、$c_{i}’$$h= \frac{\mu_{k}^{l-\mu l}}{\alpha_{k}-\alpha_{l}}$によって求まる。 2 平面の交線の数は $o(m^{2})$ あり、 交線の 座標が–致する の数は高々 $O(m^{4})$ であ
切片の順序については $O(m^{2})$ であるため、 全体としては $O(m^{4})$る。 3 平面については $o(m^{3})$ , またで抑えられる。 口$\lambda$$q$$c_{\acute{i}}$これまでのことを考慮して以下のようなアルゴリズムを示す。 アルゴリズム内において最適値限、 下限をそれぞれ、$\overline{h},$$\underline{h}$$h^{*}$の上で表す。

アルゴリズム

手順 1: 次の 3 つについて $h=L(q)$ の計算し、 ソートする。

1.

2.

$\mu_{i}-\beta\alpha_{i}$$y_{i},$$y_{j},$の計算をおこなう。
$(i, j, k=1, ... , m)$ の交点を求め、 かつ $\lambda>0$ を満たす組を保持の順序が入れ替わる$y_{k}$$q$する。

3.

$y_{i}$と防の交線.

$\lambda_{1j}$と、 脈と坊の交線$\lambda_{kl}$を求め、 それらの順序が変わるところを求める。

ソートした結果を $h_{1}<f\iota_{2}<\cdots<h_{q}$ とし、 手順 2 へ進む。
手順 2:$\overline{h}=$んならば手順 5 へ進む。 そうでなければ中央値$\hat{h}$で $h=\hat{h}$ を固定し非劣解を求める。 さらにそれらの非劣解のうちで $z(x, h)\leq g^{-1}(h)$ を満たすものが存在するかどうか調べる。 $z(x, h)>g^{-1}(h)$ ならば手順 3 へ進む。 $z(x, h)=g^{-1}(h)$ ならば終了し、そのときの解が最適解となる。 $z(x, h)<g^{-1}(h)$ ならば手順 4 へ進む。
手順 3:

$h=\underline{h}$とし、 手順 2 へ戻る。

手順 4:

$h=\overline{h}$とし、 手順 2 へ戻る。

202を求めて、での最適なスパニングツリーの候補をすべて求め$z(x, h)\leq g^{-1}(h)$ を満たす最大のを与えるスパニングヅリーが最適解である。

手順 5: 求めた$\min_{:\in K}c_{i}^{;}$

$h$

$h$

定理 2

$P_{4}$の最適解はせいぜい $O(m^{4}\log m)$ の計算量で求まる。

証明 手順 1 においては、 -\beta 砺の数が $m$ 個存在するために $O(m^{2})$ の計算を、 また、 $m$ 個のうち 3 つをの数は多くとも $O(m^{2})$ で抑えられるため、 $O(m^{4})$ の計算を選んで交点を求めるため $O(\pi l^{3})$ , さらに必要とする。 そして求めた が全体で $O(m^{4})$ 個存在し、 それらをソートするため、 全体で $O(m^{4}\log m)$の計算時間を必要とする。手順 2 においては、 ソートしたものに対しその中央値を選択しその の下$\mu_{\dot{\iota}}$$\lambda_{ij}$$h$$h$で非劣解を求めるが、 繰り返し毎に多くとも $O(mn^{1/3})$ 個の非劣解が存在し、 一回あたりスパニングヅリーを求める計算時間を $O(SP\tau)$ とすると、 全体で $O(mn^{1/3})\mathrm{x}O(SPT)=O(mn1/3o(sPT))$ の計算時間がかかる。 手順 5 においては最適な が存在する範囲を見つけた後、 その範囲での最適なスパニングヅリーの候補を全て求めるのに、 ( $O(n^{2.5}\mathrm{x}O(SPT))$ の計算時間を要し、 さらにを求めるのに
口$(O(n^{2.5}\log n))$ の計算時間を要する。 よって全体で計算時間は多くとも $O(m^{4}\log m)$ になる。
$h$6結言

本稿では可能性測度最大化モデルについて述べたが、 必然性測度最大化モデルについても同様の方法で解くことができる。

本研究で考案したアルゴリズムでは、 (3) 式においてコストの順序が変わる可能性のあるところを全て求めている、、 しかし、パラメータが–つである場合のパラメトリックスパニングヅリー問題の最適解のう
ち異なるものを全て効率よく列挙する方法が [33] で提案されており、 この方面からのアプローチによってさらにアルゴリズムの効率化がはかられると思われる。 また、本研究は組合せ幾何学における -set 問
題、 特に 3 次元空間における -set 問題とも関わりが深い。 なお、 この研究は文部省科学研究費基盤研
究 $(\mathrm{c})(2)10680428$ によるものであることを付記しておく。
$k$

$k$

参考文献
[1] C. Berge and A. Ghouila-Hour, Programming, Games andYork (1965).

$\mathrm{R}an\varphi O\Gamma ta\mathrm{f}ion$

Networks, Wiley, New[2] D. Cheriton and R. E. Tarjan, “Finding minimum spanning trees”, SIAM Joumal of Computing
5 (1976) 724-742.
[3] A. C. Yao, “An $O(|E|\log\log|V|)$ algorithm for finding minimum spanning trees”,
Information
Processing Letters 4 (1975) 21-23.
[4] J. B. Kruskal, “On the Spanning Subtree of a Graph and the Traveling Salesman Problem”,
Proceedings of AMS, 7 (1956) 48-50.

[5] R. C. Prim, “Shortest Connection Networks and Some Generalizations”, Bell System TechnicalJournal, 36 (1957) 1389-1401.
[6] H. Ishii and S. Shiode, “Chance constrained spanning tree problem”, Joumal of theResearch Society of Japan 24 (1981) 147-157.

$\ovalbox{\tt\small REJECT} erations$[7] H. Ishii, S. Shiode and T. Nishida, “Stochastic spanning tree problem”, Discrete Applied Mathematics 3 (1981) 263-273.

203[8] 伊藤健, 石井博昭, “必然性測度に基づくファジィ. スパニングツリー問題の –解法”, Jaurnal of theOperations Research Society of Japan 39 (1996) 247-257.

[9] H. Katagiri and H. Ishii, “A Revised Algorithm for Mimimum Spanning Tree with Fhzzy Costs, In Proceedings of 4th European Workshop on Fuzzy Decision Analysis and Neural Networks
for Management, Planning and Optimization (1998) in press.
$n$[10] H. Kwakernaak, “Fuzzy random variable-l. Definitions and theorems”, Informahon Sciences 15(1978) 1-29.
[11] M. L. Puri and D. A. Ralescu, “Fuzzy random variables”, Journal of Mathmatical Analysis &Application. 114 (1986) 409-422.

[12] N. Watanabe, “Fuzzy Random Variables and Statistical Inference”, 日本フアジイ学会誌 8(1996)

126-135.
[13] G. Wang and Y. Zhang, “The theory of fuzzy stochastic processes”, Fuzzy Sets and Systems 51(1992) 161-178.
[14] K. Piasecki, “On fuzzily measurable random variables”, Fuzzy Sets and Systerns (1989) 65-87.
variables”, Fuzzy Sets and Systems 92 (1997) 83-93.
[15] C. Zhong and G. Zhou, “The Equivalence of Two Definition of Fuzzy Random Variab16”, $in$of 2nd IFSA Congress (1987) 59-62.
$Pre_{\mathrm{P}^{\dot{\mathcal{H}}’}}nts$[16] T. Dey, Improved bounds for planar -set and related problems, Discrete Computational Geometry, 19 (1998), 37&382. Also in Proc. 38th IEEE Symp. om Fhndations of Computer Science,
1997, 156161.
$k$[17] D. Dubois and H. Prade, “Operations on FUzzy Numbers”, Int. Journal Systems Science 9 (6)613-626.
[18] 石井博昭, “ 「講座 数理計画法 10, 数理計画法の応用 〈理論編〉」伊理正夫, 今野浩編, 第一章確率論的最適化” 産業図書 (1982).
[19] 乾口, ファジィ数理計画問題の可能性理論に基づく体系的定式化法, 大阪府立大学博士論文 (1991).

[20] M. Inuiguchi, “Fuzzy Linear Programming : What, Why, andPubl. 13 (1997), 123-167.

’$\mathrm{H}\mathrm{o}\mathrm{w}?^{7}$

Tatra Moutains Math.

[21] M. Robens and J. Teghem, “Comparison between multiobjective fuzzy linear programming andmultiobjective stochastic programming”, $in$ : Lecture Notes in Econom. and Math. Systems 310(1988) 240-265.
[22] M. Inuiguchi and M. Sakawa, “A possibilistic linear program is equivalent to a stochastic linear
program in a special case”, Fuzzy Sets and Systems 76 (1995) $30*317$ .

[23] A. V.

$\tau r_{\mathrm{a}}\mathrm{Z}\mathrm{e}\mathrm{n}\mathrm{i}\mathrm{n}$, “Fuzzy and Stochastic Programmimg”, Fuzzy Sets and Systems 22 (1987) 171-180.

[24] 太田, 山口, 高野, “係数間の関係を考慮したファジィ多目標計画法 7’, 日本ファジィ学会誌 6166-176.
[25] 横山, 太田, 山口, “ フアジイ多目的確率制約条件計画問題”, 日本フアジイ学会誌 61193-1201.

204[26] M. K. Luhandjula, “Linear programming under randomness and fuzzineaes”, Fuzzy Sets and Systems (1983).

[27] R. H. Moham\’e, “A chance-constrained fuzzy goal program”, Fuzzy Sets and Systems 47 (1992)

183-186.
[28] M. Roubens and J. Teghem Jr., “Comparison of methodologies for fuzzy and stochastic multiobjective programming”, Fuzzy Sets and Systems (1991) 119-132.

[29] S. Hulsuker, M. P. Biswal and S. B. Sinha, “Fuzzy programming approach to multi-objective
stochastic linear programmimg problems”, Fuzzy Sets and Systems 88 (1997) 173-181.
[30] Q. Zhong and W. Guang-yuan “On solutions and distribution problems of the linear programmingwith fuzzy random variable coefficients”, Fuzzy Sets and Systems 58 (1993) 155170.
[31] W. Guang-yuan and Q. Zhong, “Linear programming with fuzzy random variable coefficients”,
Fuzzy Sets and Systems 57 (1993) 295311.
[32]-Ming Hwang and Jing-Shing Yao, “Independent fuzzy random variables and their applicatiom”, Fuzzy Sets and Systems 82 (1996) 335-350.
$\mathrm{C}\mathrm{h}\mathrm{u}\}-$[33] D. Fernadez-Baca, G. Slutzki and D. Eppstein “Using Sparsification for Parametric Minimum
Spanning Tree Problems”, Nordic Journal of Computing 3 (1996) 352-366.