Research On Models And Algorithms Of Some Network Optimization Problems Under Fuzzy Environment

Network optimization is an important branch of operations research, and its research problem involves many fields, such as transportation, urban planning, economic control, material management, communication and network technology, computer science and information technology. In a sense, we live in a complex network society consists of a wide variety of networks, such as computer information network, transport network, material distribution network, telephone communication network, and then it is necessary to analyze it mathematically. Network optimization aims at how to plan and control this network system effectively and bring it to produce the best possible social and economic benefits. Based on the previous research, this dissertation studies some network optimization problems under fuzzy environment, including transportation problem, assignment problem and flow sharing problem. These problems have wide applications in actual, such as logistics system, job scheduling, system optimization, material distribution, network design, pattern recognition etc. The main work of this dissertation can be summarized as follows:1. Three kinds of bottleneck transportation problem with both random and fuzzy factors are proposed, i.e., stochastic bottleneck transportation problem with fuzzy supply and demand quantity, chance constrained bottleneck transportation problem with preference of routes, and three-criteria bottleneck transportation problem. Here, the transportation time choosing each route may change according to many factors, we assume them to be random variables, aims at minimize the transportation time target to a chance constraint; the flexibility of the supply and demand quantity reflects on the actual situation that total quantity from suppliers is less than that to demand customers, and aims at maximize the minimal satisfaction degree among all supply and demand points; preference of each route reflects on the satisfaction degree using this route, and aims at maximize the minimal preference among the used routes. For these three problems, we propose the corresponding algorithms to seek non-dominated solutions respectively, show their validity and time complexity of the algorithms. Finally, numerical examples are presented to demonstrate how our algorithms work.2. Two kinds of assignment problem are proposed, that is, fuzzy bottleneck assignment problem with ranked preference of jobs, assignment problem with a fractional objective function (also called balanced fractional assignment problem). For these two problems, we propose the corresponding effective algorithms and show the time complexity. Finally, numerical examples are presented to demonstrate how our algorithms work. In the first problem, not only consider the ranked preference of jobs for each worker but also consider the suitability that each job is done by each worker. It has important sense in how to assign player's position in the sports, the team manager makes the decision not only based on the hope of each player but also based on the suitability for the position, aims at unleash the maximum advantage and gain the best results. The second problem is an extension of balanced assignment problem introduced by Martello et al.3. We make some extensions on flow sharing problem and propose two kinds of integer flow sharing problem with fuzzy capacity and fuzzy weight such that the flux received at each sink node and the flow value through each arc are some block-unit, that is, a generalized fuzzy bi-criteria integer flow sharing problem and a bi-criteria fuzzy integer flow sharing problem with possibility measure. Here, fuzzy capacity describes the flexibility of the upper limit of flow value through each arc, fuzzy weight represents the satisfaction degree of the flux to a sink node. For the first problem, we propose a pseudo-polynomial algorithm. For the second problem, we present an effective algorithm based on modal optimization. Besides, numerical examples are presented to show how our algorithms work.