以期望值模式求解可能性最小生成樹問題

Solving Possibilistic Minimum Spanning Tree Problems by Using Expected Value Models

林高正(Kao-Cheng Lin) ； 曾文宏(Wen-Hung Tseng) ； 鄧凱年(Kai-Nian Deng) ； 許惠馨(Hui-Hsin Hsu)

《管理資訊計算》 8卷特刊2 (2019/08) Pp. 37-50

https://doi.org/10.6285/MIC.201908/SP_02_8.0004

摘要

當聯結權數為模糊數時，網路生成樹的總權數亦為模糊數。由於網路生成樹的數量眾多，如何選取生成樹成為有趣的問題。本文，以可能性理論為基礎，首先提出在選取比序函數時應考慮的基本與重要準則。接著，指出當所採用的比序函數具有可加性時，可用比序函數對聯結權數解模糊，將問題轉成傳統的最小生成樹問題。具體而言，建議採用機率性均值或可能性均值之上下限的加權平均做為比序函數，其中的加權權數可用以代表決策者之特性。最後，則討論如何同時求解各種加權權數所對應之最小生成樹的問題。

關鍵字

模糊聯結權數 ； 最小生成樹 ； 最佳化條件 ； 模糊均值 ； 參數分析

並列摘要

When the arc weights are fuzzy numbers, the total weight of a spanning tree is also a fuzzy number. Since the number of spanning trees in a network is usually very large, how to select a spanning tree is an interesting problem. In this paper, based on the possibility theory, some rules and criteria for choosing a ranking function for this problem are proposed at first. Then, it is pointed out that if the ranking function is additive, then the problem can be transformed into the classical problem by defuzzifying the arc weights using the ranking function. In particular, weighted averages of the upper bound and the lower bound of the probabilistic mean value or the possibilistic mean value are suggested, in which the weight can be used to represent the characteristic of the decision maker. Finally, we consider the problem of finding the optimal spanning trees for all kinds of decision makers at the same time.

並列關鍵字

Fuzzy arc weights ； Minimum spanning tree ； Optimal conditions ； Mean values ； Parametric analysis

參考文獻

林高正、曾文宏、邱清爐、許惠馨 (2017)，以機遇限制規劃模式求解可能性最小生成樹問題，管理資訊計算，第 6 卷，特刊 2，82-95。 doi: 10.6285/MIC.6(S2).07

Bazlamacci, C.F. and Hindi, K.S. (2001), Minimum-weight spanning tree algorithms: A survey and empirical study, Computers and Operations Research 28 (8), 767-785. doi: 10.1016/S0305-0548(00)00007-1

Bertsimas, D. (1990), The probabilistic minimum spanning tree problem, Networks 20 (3), 245-275. doi: 10.1002/net.3230200302

Carlsson, C. and Fullér, R. (2001), On possibilistic mean value and variance of fuzzy numbers, Fuzzy Sets and System 122 (2), 315-326. doi: 10.1016/S0165-0114(00)00043-9

Chang, P.-T. and Lee, E.-S. (1999), Fuzzy decision networks and deconvolution, Computers and mathematics with Applications 37 (11/12), 53-63. doi: 10.1016/S0898-1221(99)00143-1