具模糊權數網路之最小生成樹可能性分配

The Possibility Distribution of Minimum Spanning Tree in a Network with Fuzzy Arc Weights

林高正(Kao-Cheng Lin) ； 曾文宏(Wen-Hung Tseng) ； 鄧凱年(Kai-Nian Deng)

《管理資訊計算》 9卷特刊1 (2020/08) Pp. 40-52

https://doi.org/10.6285/MIC.202008/SP_01_9.0005

摘要

本文在探討當聯結權數為模糊數時，如何求解網路最小生成樹的可能性分配。首先，指出可利用Zadeh的擴充原則將問題轉成最小生成樹參數分析問題。接著，分別以最小生成樹問題之路徑最佳化條件與割集最佳化條件為基礎，提出兩個求解最小生成樹參數分析的方法。

關鍵字

模糊網路 ； 最小生成樹 ； 可能性分配 ； 擴充原則 ； 參數分析

並列摘要

In this paper, we consider the problem of finding the possibility distribution of minimum spanning tree in a network with fuzzy arc weights. At first, it is shown that this problem can be transformed into a parametric minimum spanning tree problem, using Zadeh's extension principle. Then, two algorithms, based on the path optimality and cut optimality respectively, are proposed to solve the parametric analysis problem.

並列關鍵字

Fuzzy networks ； Minimum spanning tree ； Possibility distribution ； Extension principle ； Parametric analysis

參考文獻

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

林高正、曾文宏、鄧凱年、許惠馨 (2019)，以期望值模式求解可能性最小生成樹問題，管理資訊計算，第8卷，特刊2，37-50。 doi: 10.6285/MIC.201908/SP_02_8.0004

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

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

Dubois, D. and Prade, H. (1979), Fuzzy real algebra: some results, Fuzzy Sets and Systems 2 (4), 327−348. doi: 10.1016/0165-0114(79)90005-8