Abstract: To solve the problems in practical applications, a fuzzy decision system model constrained by the minimum cost is proposed. In this model, the optimal decision reduction and the minimum decision cost are defined and analyzed as well. As obtaining the optimal decision reduction and its decision cost is NP-complete, three algorithms including the basic algorithm, the greedy algorithm and the Lagrangian relaxation based subgradient optimization algorithm are presented. It is validated experimentally that these algorithms are quite effective, and capable of satisfying needs in different application backgrounds.

Key words: rough set, fuzzy decision, greedy algorithm, Lagrangian relaxation, subgradient

摘要： 针对模糊决策系统在应用中的实际问题，提出一类最小代价模糊决策系统模型，定义了最优决策约简和最优决策代价，并对其性质进行分析。求解最优决策约简和最优决策代价是NP完全问题，为此给出基本算法、贪婪算法和基于拉格朗日松弛的子梯度优化算法，并进行实验分析。

关键词: 粗糙集, 模糊决策, 贪婪算法, 拉格朗日松弛, 子梯度

CLC Number: 

• TP301.6