内容发布更新时间 : 2024/12/23 13:12:54星期一 下面是文章的全部内容请认真阅读。
山东科技大学本科毕业设计（论文）
致谢辞
本科毕业论文即将完成，回顾我大学四年的学习生涯，我得到了众多老师的教诲，同学的支持和帮助，再次对他们表示中心的感谢。
首先感谢我的导师王朝阳老师，他生活中待人十分热情诚恳，给予我无微不至的关怀和照顾；工作中他治学严谨，思维活跃，在研究课题阅读文献、论文写作上给予我许多指导和帮助，使我对数学的认识有了很大的提高，我将铭记恩师的教诲、关心和帮助。
还要感谢大学四年来所有的老师，为我们打下坚实的数学专业知识基础，在论文的写作过程中，还要感谢班内同学的帮助，他们在我完成论文的过程中，给我提了许多宝贵的建议，正是因为有了你们的支持和鼓励。此次毕业设计才能够顺利的完成。
感谢所有给予我帮助和锻炼的人。
最后，衷心感谢所有老师对我的栽培、支持和鼓励，感谢所有朋友的关心和帮助。向在百忙中抽出时间对此论文进行评审并提出宝贵意见的各位专家表示衷心地感谢！
衷心祝愿母校山东科技大学明天更加美好！
32
山东科技大学本科毕业设计（论文）
附录1英文原文
Maximum flow problem in the introduction, we listed one of the largest flow of goods delivery. If this issue also includes the known conditions of delivery of each unit while the cost of goods, then how to transport, to get the most traffic, and transportation costs to a minimum? This is the so-called maximum flow problem minimum cost. The maximum flow based on the definition, if each side of a first-priority claim to the number of c(e)(that the edge capacity) but also have another weights w(e) (that the unit cost flow), and has been seeking a maximum flow of the network value of F, then the minimum cost maximum flow problem, it is clear the following linear programming model can be used to describe:
min?w(e)f(e) e?E
Satisfy 0?f(e)?c(e) for all e?E
f?(v)?f?(v)
for all v?V f?(x)?F(maximum flow constraints)(Orf?(y)?F) Algorithm ideas Solve the minimum cost maximum flow problem, there are two general ways. Way is to use a maximum flow algorithm to calculate the maximum flow, and then based on the cost side, check whether it is possible to balance the flow by adjusting the flow side, so that to reduce the total cost? As long as there is a possibility, on such adjustments. After adjusting for a new maximum flow. Then, on the basis of the new flow to continue to check and adjust. This iteration continues until no adjustment may be, they will have the minimum cost maximum flow. The characteristics of this line of thought is to
33
山东科技大学本科毕业设计（论文）
maintain the feasibility of the problem (always maintain maximum flow), to promote optimal. Solution to another and in front of the maximum flow algorithm, introduced a similar line of thought, first of all, given the general flow as the initial flow of zero. The cost of the flow to zero, of course, is the smallest cost. And then find a source to the Meeting Point by flow chain, but by the requirements of this chain must be a stream flow of all chain costs by a minimum. If we can find out by flow chain, the chain in the flow by increasing flow, a new flow. The flow will be treated as the initial flow, continue to search for links by increasing stream flow. This iteration continues, until found by flow chain, then the flow is the minimum cost maximum flow. Idea of the characteristics of this algorithm is to maintain the optimal solution of (each of the new fees are the smallest stream flow), but gradually close to the feasible solution (up to maximum flow is a feasible solution when). As a result of the second algorithm and has introduced close to the maximum flow algorithm and the algorithm by finding the minimum cost flow chain, can be turned into a source to find the shortest path to the Meeting Point, so this algorithm here. In this algorithm, in order to seek to increase the minimum cost flow chain, the current flow of each, accompanied by the need to establish a network flow by the flow network. For example, Figure 1 is a network G of minimum cost flow, next to parameters c(e),f(e), w(e), and Figure 2 is the network flow by the flow network G '. By the peak-flow network and the same as the original network. By the following principles in accordance with the establishment of the network edge flow:
If G in the edge (u,v) is not enough traffic, that is, f(u,v)?e(u,v), then
34
山东科技大学本科毕业设计（论文）
G 'in the building edge (u,v), Empoweringw'(u,v)?w(u,v); edge of G if
(u,v) has been the flow, that is, f(u,v)?0, then G' in the building edge (u,v), to empower the w'(u,v)??w(u,v).
The establishment of the network by streaming, you can seek in this network to the Meeting Point source shortest path, as decided by flow path, and then in the original network by flow in this path. Here, the use of maximum flow algorithm is still the principle of increasing flow, but the cost must be selected by the smallest chain by stream flow. Calculation, there is a need to address the problem. This is the stream network by G 'the right to have a negative side, thus labeling law can not be directly applied to find x to y of the shortest path, using the right of other negative side computing network approach to the shortest path x to yto find the shortest path, will greatly reduce the computational efficiency. In order to still use the labeling method to calculate the shortest path, each flow set up by the network to achieve the shortest path, the network G can be the right of w(e) an amendment to do so by the stream to build the network will not be a negative right side, and guarantee the shortest path does not change. This modified method described below. When the flow value is zero, the first built by the shortest path for flow network, the result of non-negative right side, of course, can be used to calculate labeling law. In order to increase flow network after the establishment of a negative time is not right side of the approach taken is to have stream G edge (f (e)> 0) the right to w (e) amendment to 0. To this end, each time a flow network obtained by the shortest path, the following computing G in the right side of the new
35