【作者】 刘英；

【导师】 刘红卫；

【作者基本信息】 西安电子科技大学 ， 应用数学， 2010， 硕士

【摘要】 网络流问题是网络最优化的重要组成部分,其中最小费用流是一类最为基本的网络流模型,对于该模型已有丰富的研究成果。但是随着人类活动和生产过程日益复杂,新的约束条件不断出现,这对原有的网络流问题构成了挑战。基于此,生产网络模型应运而生,它引入六种顶点,以便表示不同类型的额外线性约束。将生产网络模型与最小费用流问题相结合则构成了一类新的网络流问题,其中顶点具有流量需求的最小费用流问题和最小费用分配流问题就是两个典型的代表,并且在现实生活中具有广泛的应用。本文的主要工作概括如下:首先,针对顶点具有流量需求的最小费用流问题,提出了一种新的最小费用流算法。新算法中引入了顶点分层的思想,克服了已有网络不适用于大型网络的缺点,使得网络在庞大的情况下能够有次序的将网络规模减小,有利于计算机化。通过数值试验表明新算法的性能良好。其次,针对最小费用分配流问题,在经典最小费用路算法的基础上设计了一种新的最小费用分配流算法。该算法通过对顶点进行三次标号,首先找到最小费用路,然后分析特殊点对需要增广流值的影响,给出了使其能够在已找到的最小费用路上增广流值的算法。文中给出有效性证明及算法实例。更多还原

【Abstract】 Network flow problem is an important part of Network optimization. The minimum cost flow model is the most fundamental of all network flow problems. It has been extensively studied and fruitful results have been developed. As human activities and the production process are becoming increasingly complex, new restraints are emerging, which posed a challenge to the original network flow problems. Based on the above things, manufacturing network model is proposed, which consists of six kinds of vertices that express different types of additional constraints.The model and the minimum cost flow problem constitute a new class of network flow problems.Two typical representatives of these related problems are the minimum node with flow demands cost flow problem and the minimum distribution cost flow problem. They have wide applications in the real world.The main work is summarized as follows:Firstly, a new minimum cost flow algorithm is proposed for the minimum node with flow demands cost flow problem. The new algorithm makes all vertices stratified.The idea overcomes to shortcomings of the existing method which does not apply to the large network and reduces the size of network by order which is more conducive computerization. Numerical results show that the new algorithm has good performance.Secondly, a new algorithm is designed for the minimum distribution cost flow problem based on the classical minimum cost path algorithm. The algorithm labels vertexs three times.It firstly finds the minimum cost path, and then analyze the impact of special points to broaden flow value. Then we design the algorithm on the path.The paper gives an example to certificate the new algorithem.更多还原