【作者】 谢凡荣；

【导师】 贾仁安；

【作者基本信息】 南昌大学 ， 管理科学与工程， 2009， 博士

【摘要】 网络优化就是研究如何有效地计划、管理和控制网络系统,使之发挥最大的社会和经济效益;就是研究与(赋权)图有关的最优化问题。网络优化课题是有理论意义和实际意义的课题,国内外不少学者从事网络优化的研究,并且取得了很好的研究成果。为了更好地把这些研究成果应用于实际,一种可供选择的措施是建立相关的决策支持系统。为了给建立相关决策支持系统提供方便,本文从便于计算机求解的角度对网络优化中若干问题进行了深入探究,在建立数学模型的基础上得到了求解这些问题的高效能算法,并且在计算机上编程实现了所有这些算法。本文研究的主要问题包括:管理安排问题、供给总量限定需求区间约束型运输问题、最短工期项目计划问题、固定费用运输问题、有上下界网络最大流与最小截问题、有上下界网络最小费用流与最小费用最大流问题、具有容量限制和边界条件约束的运输问题、运输问题的多反而少悖论、固定费用运输问题的多反而少悖论、多级供应链优化问题。本文从经典网络流理论及其应用、有上下界网络流理论及其应用、多级供应链优化这三个方面展开探究,组织如下。首先,本文给出了经典网络流理论中网络最大流问题与网络最小费用最大流问题这两个基础性问题的便于计算机求解的问题描述、相关理论与数值算法,并举例说明了它们的应用,为进一步的应用与理论研究奠定基础。接着,本文探究了经典网络流理论在求解管理安排问题、供给总量限定需求区间约束型运输问题、最短工期项目计划问题、固定费用运输问题中的应用,在建立数学模型的基础上得到了求解这些问题的高效能数值算法。然后,本文探究了有上下界网络流理论及其应用,拓广了经典网络流理论的有关结果;即探究了有上下界网络最大流与最小截问题、有上下界网络最小费用流与最小费用最大流问题,在建立数学模型的基础上得到了求解这两个问题的高效能数值算法,并把它们用于求解最短工期项目计划问题、具有容量限制和边界条件约束的运输问题、运输问题的多反而少悖论、固定费用运输问题的多反而少悖论,从而在建立数学模型的基础上得到求解这些问题的高效能数值算法。最后,本文探究了多级供应链优化问题,在建立数学模型的基础上得到了求解该问题的基于生成树改进遗传算法。该基于生成树改进遗传算法可用于在多级物流系统中寻求最好的生产配送方案,比原有的基于生成树遗传算法有更强的搜索全局最优解的能力,并且保留了原有的基于生成树遗传算法的优点。本文还提供了求解多级供应链优化问题的基于生成树改进遗传算法的C语言源代码。该源代码是我们用Visual C++6.0调试通过的,经过严格测试无误,可供调用或参考。该源代码是采用结构化模块化技术设计的,易于阅读。本文对网络优化中以上问题提出的求解方法,具有易于在计算机上编程实现、计算效率高等优点,因此具有实用价值,研究成果可以为建立相关的决策支持系统提供帮助,在管理中获得了很好的应用,并给出了江西省萍乡市排上养猪协会生猪农产品供应链管理实际应用案例,应用研究成果进行了“协会+农户”生猪饲料供应子网络最优运送方案计算设计有效研究,进行了“协会+农户”生猪销售最优配送方案计算设计有效研究,获得了很好的应用效果。更多还原

【Abstract】 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.更多还原