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

Solving Possibilistic Minimum Spanning Tree Problems by Using Expected Value Models

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