The Models And Algorithms Of Some Optimal Problems In Fuzzy Environment

The assignment problem, matching problem, spanning-tree problem and trans-portation problem have been widely applied in many systems such as the system op-timization, pattern recognition and logistic. According to the different applied back-grounds, these problems have also been extended to the quadratic assignment problem,quadratic matching problem, quadratic spanning-tree problem, fixed charge transporta-tion problem and the equilibrium optimal problems such as the multi-job equilibriumassignment problem and the equilibrium spanning tree. However, most of the extendedproblems are NP-hard. Furthermore, there exist many uncertain factors when theseproblems are applied to solve the practical problems. The main purposes of this disser-tation are focused on both the methods of formulating the mathematical models of theseproblems and the algorithms to solve the mathematical models (there ere 8 algorithmsin all).In this dissertation, the concept of the equilibrium optimal problem is firstly initial-ized and the models such as the expected value model, the chance-constrained program-ming and the dependent-chance programming with respect to the quadratic assignmentproblem, quadratic matching problem, quadratic spanning-tree problem, fixed chargetransportation problem and the multi-job equilibrium assignment problem and the equi-librium spanning tree are formulated by using the credibility theory. In order to solvethese mathematical models, the known genetic algorithms of these problems are care-fully analyzed and then some genetic algorithms with respect to these mathematicalmodels are designed. For the quadratic assignment problem and quadratic matchingproblem, a heuristic genetic algorithm is designed, respectively. By using the ideasof the genetic algorithm of the quadratic assignment problem, a priority based geneticalgorithm is designed for the multi-job equilibrium assignment problem and then therelated evolution operator is extended to the algorithm for solving the weighted edgecover set problem of the complete bipartite graph. Furthermore, a cycle based geneticalgorithm of the quadratic spanning-tree problem is designed by using the structureproperties of the solution and the designed newly encode method of the solution andthen extend this algorithm to a genetic algorithm of the k-tree problem. This algorithmcompletely overcomes the defects of the known genetic algorithms of the quadraticspanning-tree problem. Finally, a spanning-tree and cycle based genetic algorithm,which also greatly overcomes the defects of the known genetic algorithms, is designedfor the fixed charge transportation problem by using the properties of the solution ofthe related problem.The main contributions of this dissertation include the following five parts: (1)The concepts of equilibrium optimal problem and quadratic matching are proposed;(2) A knowledge based heuristic genetic algorithm is designed for the quadratic as-signment problems and the quadratic matching problem; (3) A priority based heuristicgenetic algorithm is designed for the multi-job equilibrium assignment problem; (4) Aknowledge and cycle based genetic algorithm is designed for the quadratic spanning-tree problem and then extended this algorithm to that of the k-tree problem; (5) Aspanning-tree and cycle based genetic algorithm is designed for the fixed charge trans-portation problem.