The maximum fuzzy weighted matching models and hybrid genetic algorithm

摘要

A matching of a graph is an independent subset of the edges set and a maximum matching is a matching with as many edges in it as possible. The maximum weighted matching problem is to find a maximum matching in a given graph such that the sum of the weights of the edges in it is maximum. In this paper, the concepts of expected maximum fuzzy weighted matching, the α-maximum fuzzy weighted matching and the most maximum fuzzy weighted matching are initialized. According to various decision criteria, the maximum fuzzy weighted matching problem is formulated as expected value model, chance-constrained programming and dependent-chance programming by using the credibility theory, and the crisp equivalents are also given. Furthermore, a hybrid genetic algorithm is designed for solving the proposed fuzzy programming models. Finally, a numerical example is given.