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

Solving Possibilistic Minimum Spanning Tree Problems by Using Expected Value Models

10.6285/MIC.201908/SP_02_8.0004

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

模糊聯結權數 ； 最小生成樹 ； 最佳化條件 ； 模糊均值 ； 參數分析 ； Fuzzy arc weights ； Minimum spanning tree ； Optimal conditions ； Mean values ； Parametric analysis

管理資訊計算

8卷特刊2（2019 / 08 / 01）

37 - 50

繁體中文

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

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.

1. 林高正,曾文宏,邱清爐,許惠馨(2017)。以機遇限制規劃模式求解可能性最小生成樹問題。管理資訊計算，6(特刊 2)，82-95。
   連結：
2. Adamo, J.M.(1980).Fuzzy decision trees.Fuzzy Sets and Systems,4(3),207-219.
3. Ahuja, R.K.,Magnanti, T.L.,Orlin, J.B.(1993).Network Flows: Theory, Algorithms, and Applications.Englewood Cliffs, New Jersey:Prentice-Hall.
4. Ball, M.O(ed.),Magnanti, T.L(ed.),Monma, C.L(ed.),Nemhauser, G.L.(ed.)(1995).Handbooks in Operations Research and Management Science, Volume 8: Network Routing.Amsterdam:Elsevier Science.
5. Ball, M.O(ed.),Magnanti, T.L(ed.),Monma, C.L(ed.),Nemhauser, G.L.(ed.)(1995).Handbooks in Operations Research and Management Science, Volume 7: Network Models.Amsterdam:Elsevier Science.
6. Bazaraa, M.S.,Jarvis, J.J.,Sherali, H.D.(1990).Linear Programming and Network Flows.New York:John Wiley & Sons.
7. Bazlamacci, C.F.,Hindi, K.S.(2001).Minimum-weight spanning tree algorithms: A survey and empirical study.Computers and Operations Research,28(8),767-785.
8. Bertsimas, D.(1990).The probabilistic minimum spanning tree problem.Networks,20(3),245-275.
9. Bezdek, J.C.(ed.)(1987).Analysis of Fuzzy Information-Vol. 1: Mathematics and Logic.Boca Raton, Florida:CRC Press.
10. Carlsson, C.,Fullér, R.(2001).On possibilistic mean value and variance of fuzzy numbers.Fuzzy Sets and System,122(2),315-326.
11. Chang, P.-T.,Lee, E.-S.(1999).Fuzzy decision networks and deconvolution.Computers and mathematics with Applications,37(11/12),53-63.
12. Cook, W.J.,Cunningham, W.H.,Pulleyblank, W.R.,Schrijver, A.(1998).Combinatorial Optimization.New York:John-Wiley & Sons.
13. Dubois, D.(ed.),Prade, H.(ed.)(2000).Fundamentals of Fuzzy Sets.Dordrecht:Kluwer Academic Publishers.
14. Dubois, D.,Prade, H.(1989).Fuzzy sets, probability and measurement.European Journal of operational Research,40(2),135-154.
15. Dubois, D.,Prade, H.(1992).When upper probabilities are possibility measures.Fuzzy Sets and Systems,49(1),65-74.
16. Dubois, D.,Prade, H.(1987).The mean value of a fuzzy number.Fuzzy Sets and Systems,24(3),279-300.
17. Dubois, D.,Prade, H.(1978).Operations on fuzzy numbers.International Journal of System Science,9(6),613-626.
18. Dubois, D.,Prade, H.(1997).The three semantics of fuzzy sets.Fuzzy Sets and Systems,90(2),141-150.
19. Fredman, M.L.,Tarjan, R.E.(1987).Fibonacci heaps and their uses in improved network optimization algorithms.Journal of the Association for Computing Machinery,34(3),596-615.
20. Frieze, A.M.(1985).On the value of a random minimum spanning tree problem.Discrete Applied Mathematics,10(1),47-56.
21. Haymond, R.E.,Jarvis, J.P.,Shier, D.R.(1984).Computational methods for minimum spanning tree algorithms.SIAM Journal on Scientific and Statistical Computing,5(1),157-174.
22. Hsu, L.-H.,Jan, R.-H.,Lee, Y.-C., Hung, C.-N.,Chern, M.-S.(1991).Finding the most vital edge with respect to minimum spanning tree in weighted graphs.Information Processing Letters,39(5),277-281.
23. Iwano, K.,Katoh, N.(1993).Efficient algorithms for finding the most vital edge of a minimum spanning tree.Information Processing Letters,48(5),211-213.
24. Klement, E.P.,Mesiar, R.,Pap, E.(2000).Triangular Norms.Boston:Kluwer Academic Publishers.
25. Klir, G.J.,Yuan, B.(1995).Fuzzy Sets and Fuzzy Logics: Theory and Applications.Upper Saddle River, New Jersey:Prentice-Hall.
26. Kruskal, J.B., Jr.(1956).On the shortest spanning subtree of a graph and traveling salesman problem.Proceedings of AMS,7,45-50.
27. Kulkarni, V.G.(1988).Minimum spanning trees in undirected networks with exponentially distributed arc weights.Networks,18(2),111-124.
28. Liang, W.(2001).Finding the k most vital edges with respect to minimum spanning trees for fixed k.Discrete Applied Mathematics,113(2/3),319-327.
29. Lin, K.-C.,Chern, M.-S.(1993).The most vital edges in the minimum spanning tree problem.Information Processing Letters,45(1),25-31.
30. Lin, K.-C.,Chern, M.-S.(1993).The fuzzy shortest path problem and its most vital arcs.Fuzzy Sets and Systems,58(3),343-353.
31. Liu, B.(1998).Minimax chance constrained programming models for fuzzy decision systems.Information Sciences,112(1),25-38.
32. Liu, B.,Iwamura, K.(1998).Chance constrained programming with fuzzy parameters.Fuzzy Sets and Systems,94(2),227-237.
33. Pettie, S.,Ramachandran, V.(2002).An optimal minimum spanning tree algorithm.Journal of the Association for Computing Machinery,49(1),16-34.
34. Prim, R.C.(1957).Shortest connection networks and some generalizations.Bell System Technical Journal,36,1389-1401.
35. Steele, J.M.(1987).Growth rates on Frieze’s ζ (3) limit for lengths of minimal spanning trees.Discrete Applied Mathematics,18(1),99-103.
36. Wang, X.,Kerre, E.E.(2001).Reasonable properties for the ordering of fuzzy quantities (I).Fuzzy Sets and Systems,118(3),375-385.
37. Zadeh, L.A.(1999).Fuzzy sets as a basis for a theory of possibility.Fuzzy Sets and Systems,100(1),9-34.
38. Zadeh, L.A.(1965).Fuzzy sets.Information and Control,8(3),338-353.
39. 林高正,鄧凱年(2006)。具模糊權數之最小生成樹的可能性分配。中華民國第十四屆模糊理論及其應用會議論文集，高雄縣:
40. 鄧凱年(2007)。台南縣，南臺科技大學工業管理研究所。

1. 蔡元立,曾文宏,林高正(2023)。高品質工作台鑄件與製程技術建立專案之規劃。管理資訊計算，12(特刊2)，47-63。
2. 鄧凱年,曾文宏,林高正(2020)。具模糊權數網路之最小生成樹可能性分配。管理資訊計算，9(特刊1)，40-52。