Research On Efficient & Robust Algorithms For Some Problems In Network Optimization And Its Application In Management

Network optimization is to study how to plan, manage and control the network system effectively and efficiently so that it yields maximal social and economical returns, i.e., to study the optimization problems relative to graph or weighted graph. Network optimization is a subject with theoretical and practical implication, which has been studied by many scholars at home and abroad, and very good research achievement has been acquired. In order to apply the research achievement to practice better, an alternative measure is to build the related decision support system. For convenience to build the related decision support system, some problems in network optimization have been studied with a view to solving problems by computer conveniently, and efficient & robust algorithms to solve these problems have been acquired on the basis of building their mathematical models, and all the algorithms acquired in this dissertation have been implemented on computer. The main problems studied in this dissertation include management scheduling problem, transportation problem with supply amount specified and demand interval constraint, minimum duration project schedule problem, fixed-charge transportation problem, problem of maximum flow & minimum cut set in network with lower & upper arc capacities, problem of minimum cost flow & minimum cost maximum flow in network with lower & upper arc capacities, capacitated transportation problem with bounds on rim conditions, more-for-less paradox for transportation problem, more-for-less paradox for fixed-charge transportation problem, multi-stage supply chain optimization problem.The research of this dissertation involves three aspects, i.e., classical network flow theory & its application, flow theory & its application of network with lower & upper arc capacities, and multi-stage supply chain optimization. This dissertation is organized as follows.First, in this dissertation, the two basic problems in classical network flow theory, i.e., maximum flow problem & minimum cost maximum flow problem, are formulated in such a way that the two problems can be conveniently solved by computer, and numerical algorithms for solving the two probems as well as their dependent theory are presented, and the applications of the numerical algorithms are illustrated with examples, in order to provide a sound basis for further research on application and theory. Next, the applications of classical network flow theory to solving management scheduling problem, transportation problem with supply amount specified and demand interval constraint, minimum duration project schedule problem, and fixed-charge transportation problem, are studied in this dissertation; based on building the mathematical models of these problems, efficient & robust numerical algorithms are consequently obtained to solve these problems.Then, flow theory & its application of network with lower & upper arc capacities are studied in this dissertation, and the related results of classical network flow theory are consequently generalized; i.e., problem of maximum flow & minimum cut set in network with lower & upper arc capacities, and problem of minimum cost flow & minimum cost maximum flow in network with lower & upper arc capacities, are studied; and efficient & robust numerical algorithms, which are based on building the mathematical models of the two problems, are consequently obtained to solve the two problems; and the obtained algorithms are applied to solving minimum duration project schedule problem, capacitated transportation problem with bounds on rim conditions, more-for-less paradox for transportation problem, and more-for-less paradox for fixed-charge transportation problem; and efficient & robust numerical algorithms are consequently obtained to solve these problems, which are based on building the mathematical models of these problems.Finally, multi-stage supply chain optimization problem is studied in this dissertation, and a rst-GA (revised spanning tree-based genetic algorithm) is obtained to solve the problem, which is based on building the mathematical model of the problem. The rst-GA can be used to find the best production/distribution design in multi-stage logistics system, which has more powerful ability to search the global optimum than original st-GA (spanning tree-based genetic algorithm), and has kept the merits of original st-GA. The C language resource code of rst-GA is presented in this dissertation to solve multi-stage supply chain optimization problem. The resource code is carefully designed and strictly debugged using Visual C++ 6.0 language, and verified to be so correct that it can be called at ease. The resource code is designed by adopting the structural and block-built techniques, and easy to read.The solution methods of the above-mentioned problems in network optimization proposed by this dissertation have good performance in the sense of being implemented on computer, computational time and required memory for computation, therefore these methods have practical application value. The research results in this dissertation can provide help for building related decision support system,which have been applied to management very well. A practical application research,which is live pig product supply chain management for Paishang Pig Breeding Association in Pingxiang City of Jiangxi Province, has been presented in this dissertation. This application research is to find the optimal shipping scheme for "association plus fanner " live pig fodder supply sub-network, and the optimal distribution scheme for "association plus fanner " live pig sale, which has been carried out efficiently; and very good application result has been acquired.