以機遇限制規劃模式求解可能性最小生成樹問題

Solving Possibilistic Minimum Spanning Tree Problems by Using Chance-Constrained Models

10.6285/MIC.6(S2).07

林高正(Kao-Cheng Lin)；曾文宏(Wen-Hung Tseng)；邱清爐(Chin-Lu Chyu)；許惠馨(Hey-Sin Hsu)

可能性規劃 ； 最小生成樹 ； 機遇限制模式 ； Minimin 模式 ； Maximin 模式 ； Possibilistic Optimization ； Minimum Spanning Tree ； Chance-constrained Models ； Minimin Model ； Maximin Model

管理資訊計算

6卷特刊2（2017 / 08 / 01）

82 - 95

繁體中文

本文在探討，當聯結權數為模糊數時，如何以機遇限制規劃模式求解最小生成樹問題。在模式中，聯結權數為受限於機遇限制的決策變數，要求實際的聯結權數不大於規劃的聯結權數之可能性不低於預定的信賴水準。依決策者的特性，所提出模式分為 Minimin 模式與 Maximin 模式兩種。本文指出當聯結權數為具無互動性的模糊數時，可將問題轉成傳統的最小生成樹問題。

In this paper, two possibilistic chance-constrained models for solving the minimum spanning tree problem with fuzzy arc weights are proposed. In these models, the arc weights used in planning are treated as decision variables and subject to a set of chance constraints. These constraints require the possibilities that the arc weights used in planning are sufficient are not less than the specified levels. According to the characteristic of the decision maker, there are two kinds of chance-constrained model, the minimin model and the maximin model. It is shown that when the arc weights are non-interactive, these two models can be transformed into the classical minimum spanning tree problems easily.

1. Ahuja, R.K.,Magnanti, T.L.,Orlin, J.B.(1993).Network Flows: Theory, Algorithms, and Applications.Englewood Cliffs, New Jersey:Prentice-Hall.
2. 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.
3. Bertsekas, D.P.,Gallager, R.(1992).Data Networks.Upper Saddle River, New Jersey:Prentice-Hall.
4. Bertsimas, D.(1990).The probabilistic minimum spanning tree problem.Networks,20(3),245-275.
5. Carlsson, C.,Fullér, R.(2001).On possibilistic mean value and variance of fuzzy numbers.Fuzzy Sets and System,122(2),315-326.
6. Chang, P.-T.,Lee, E.-S.(1999).Fuzzy decision networks and deconvolution.Computers and Mathematics with Applications,37(11/12),53-63.
7. Charnes, A.,Cooper, W.W.(1959).Chance-constrained programming.Management Science,6(1),73-79.
8. Dubois, D.(Ed.),Prade, H.(Ed.)(2000).Fundamentals of Fuzzy Sets.Dordrecht:Kluwer Academic Publishers.
9. Dubois, D.,Prade, H.(1988).Possibility Theory: An Approach to Computerized Processing of Uncertainty.New York:Plenum Press.
10. Dubois, D.,Prade, H.(1978).Operations on fuzzy numbers.International Journal of System Science,9(6),613-626.
11. Dubois, D.,Prade, H.(1987).The mean value of a fuzzy number.Fuzzy Sets and Systems,24(3),279-300.
12. Dubois, D.,Prade, H.(1992).When upper probabilities are possibility measures.Fuzzy Sets and Systems,49(1),65-74.
13. 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.
14. Frieze, A.M.(1985).On the value of a random minimum spanning tree problem.Discrete Applied Mathematics,10(1),47-56.
15. 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.
16. Klement, E.P.,Mesiar, R.,Pap, E.(2000).Triangular Norms.Boston:Kluwer Academic Publishers.
17. Klir, G.J.,Yuan, B.(1995).Fuzzy Sets and Fuzzy Logics: Theory and Applications.Upper Saddle River, New Jersey:Prentice-Hall.
18. Kruskal, J.B., Jr.(1956).On the shortest spanning subtree of a graph and traveling salesman problem.Proceedings of AMS,7,45-50.
19. Kulkarni, V.G.(1988).Minimum spanning trees in undirected networks with exponentially distributed arc weights.Networks,18(2),111-124.
20. 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.
21. Lin, K.-C.,Chern, M.-S.(1993).The most vital edges in the minimum spanning tree problem.Information Processing Letters,45(1),25-31.
22. 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.
23. Liu, B.(2015).Uncertainty Theory.Heidelberg:Springer.
24. Liu, B.(1998).Minimax chance constrained programming models for fuzzy decision systems.Information Sciences,112(1-4),25-38.
25. Liu, B.,Iwamura, K.(1998).Chance constrained programming with fuzzy parameters.Fuzzy Sets and Systems,94(2),227-237.
26. Liu, B.,Liu, Y.-K.(2002).Expected value of fuzzy variable and fuzzy expected value models.IEEE Transactions on Fuzzy Systems,10(4),445-450.
27. Pettie, S.,Ramachandran, V.(2002).An optimal minimum spanning tree algorithm.Journal of the Association for Computing Machinery,49(1),16-34.
28. Prim, R.C.(1957).Shortest connection networks and some generalizations.Bell System Technical Journal,36,1389-1401.
29. Steele, J.M.(1987).Growth rates on Frieze's z (3) limit for lengths of minimal spanning trees.Discrete Applied Mathematics,18(1),99-103.
30. Wang, X.,Kerre, E.E.(2001).Reasonable properties for the ordering of fuzzy quantities (I).Fuzzy Sets and Systems,118(3),375-385.
31. Zadeh, L.A.(1999).Fuzzy sets as a basis for a theory of possibility.Fuzzy Sets and Systems,100(1),9-34.
32. 林高正、鄧凱年(2006)。具模糊權數之最小生成樹的可能性分配。中華民國第十四屆模糊理論及其應用會議論文集，高雄縣:
33. 林高正、鄧凱年、許惠馨(2008)。具模糊權數之最小生成樹問題的期望值模式。中華民國第十六屆模糊理論及其應用會議論文集，桃園縣中壢市:
34. 鄧凱年(2007)。碩士論文(碩士論文)。台南縣永康市，南台科技大學工業管理研究所。

1. 鄧凱年,曾文宏,許惠馨,林高正(2019)。以期望值模式求解可能性最小生成樹問題。管理資訊計算，8(特刊2)，37-50。
2. 鄧凱年,曾文宏,林高正(2020)。具模糊權數網路之最小生成樹可能性分配。管理資訊計算，9(特刊1)，40-52。