网络最大流及回收中心选址问题研究.doc

湖南大学硕士学位论文网络最大流及回收中心选址问题研究姓名：郭玉芬申请学位级别：硕士专业：概率论与数理统计导教师：李董辉20080320AbstractThis thesis studies the network maximal-flow problem and the location of the recycling center.The network maximal-flow problem is not only a classical combinatorial optimization problem, but also a special linear programming problem. It has a wide variety of applications in engineering fields such as communication, electric power, transportation, etc., and scientific fields such as physics, chemistry, biology, ap- pli«i mathematic, etc.. The problem has been studied for more than forty yeara. Many researchers, including Turing Prize winners Karp and Taxjan, have established integrate theories and explored many algorithms for the problem. On the other hand, however, the researdi in the maximal-flow model varies is relatively fewer. With the rapid development of networks maximal-flow becomes more and more important and li肪 attracted much people's attention.On the base of traditional network maximum flow model, this thesis studies network maximum flow model with more than one source and sink in different sub-network. We also propose a decomposition method to solve the model.A complete supply diain system includes not only the forward logistics, but also reverse logistics. It has pasted a very long time since the enterprises pay attention to the return products and overdone products. With environmental consciousness' enhancement, environmental protection legislation's releasing and the considerable economic interest's appearance, the enterprises start to pay attention to the reverse logistics. Reverse logistics has become the warm topic. The research in this topic has taken good progress. As the important link of revetse logistics network, the location of recycling center plays an important role in the entire logistics system.In this thesis, we will also study the location of recycling center and the return price.Key Words: Maximum Flow; Feasible Flow; Reverse Logistics; Recycling Center; Decreasing Ranking Selection algorithm湖南大学 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的成果。

除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品对本文的研究做出重要 贡献的个人和集体，均已在文中以明确方式标明本人完全意识到本声 明的法律后果由本人承担作者签名：約+窄 日期-功年r月ir日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅本人授权湖南大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文本学位论文属于1、保密□,«__年解密后试用本授权书》2、不保密0<，(请在以上相应方框内打“/”） 作者签名：I+々 日期年、<月（r日曰期：r月ir日导师签名第1章绪论1.1 网络最大流问题研究背景电力网络给我们带来动力和光明；交通网络便利我们出行；网络把我们的声音传给远方的亲人和朋友.可以说在我们的日常生活中，网络无处不在.而近年来计算机网络的快速发展更使我们的生活发生了很大的变化.考虑这些网络的共同特性，可以把网络看成是由一些边和结点构成的图，我们希望通过图的边在它的结点之间传递某种物质.我们把这些物质称作流，例如表1.1给出的一些现实网络的组成表1.1 一些实际网络的组成网络结点边流交通网机场、车站铁路、公路飞机、车辆、旅客通信网计算机、卫星电缆、光纤音频、视频信号计算机集成电路门、寄存器、处理器线电流我们想知道，在一个给定的网络中，利用何种方法可以更加有效地传输网络中 的流.这是一个十分重要的课题.网络流问题就是描述这类问题的数学模型.网络 流问题是指在结点和边有一定约束的网络中，使流的某些目标最优化.其中最常见 的网络流问题包括最小费用流问题、最短路径问题、最大流问题、最小费用最大 流问题等等.网络流问题是一类经典的优化问题，它不仅用来解决实际网络中的问题，科学 和工程领域的许多问题也可以抽象为网络流问题.网络流问题是计算机科学和运 筹学的重要研究内容，具有悠久的历史.近年来，计算机和通信等网络飞速发展，规 模越来越大，对网络流问题的研究提出了更高的要求,促使网络流问题的研究进入 一个新的高潮.在现实生活的网络中，网络的结点和边一般都是有容量限制的.很多时候我们 想知道在一个容量有限制的网络中两个指定结点(分别称为源点和汇点)之间最多 能传输多少流量，并找到使网络达到最大流量的传输策略.网络最大流问题(简称 最大流问题)就是描述这个问题的数学模型.最大流问题是网络流理论的重要组成部分，它是一个经典的组合优化问题，同 时也可以看作是特殊的线性规划问题.最大流问题除了解决实际网络中的问题以 外，在许多工程领域和生物、物理、化学以及应用数学等科学领域有着广泛的应 用.因此，最大流问题是运筹学和计算机科学的重要研究内容.最大流问题已有四十多年的研究历史[1].在这四十多年中，人们不仅建立了最 大流问题较为完善的理论，同时也开发了大量的算法.近年来，随着各种网络和计 算机科学的飞速发展，最大流问题得到了更加深入的研究.但是对于最大流模型的网络最大流及回收中心选址问鹿研究研究还不是很多.最大流问题的对偶问题最小截问题也是经典的组合优化问题，也是特殊的线 性规划问题.它和最大流问题一样在实际生活中有很重要的作用.它们的应用涉及 交通、通信、计算机等许多工程领域和物理、化学、生物等许多科学领域,在应用 数学、管理科学和社会科学等众多领域中最大流和最小截问题也起到了非常重要 的作用.最大流和最小截问题的应用表现在： •在许多现实的网络中需要确定在两点间最大可输送的流量.例如在计算机网络中从一个端口传输到另一个端口的最大数据量. •最大流或最小截问题常常作为一些其它问题，主要是图论、组合优化和线性规划等问题的一个子问题出现. •许多问题表面上看起来和最大流或最小截问题无关，但它们可以通过图论和 线性规划等方法把问题转化为最大流问题或最小截问题 目前最大流和最小截问题的应用已经深入到众多的领域，有许多文献做了大 量这方面的工作.如在计算机科学和通信系统领域R.K Ahuja⑴研究了双处理 器计算机的分布计算;A.Federgmen和H.Groenevlelt [2]研究了双处理器计算机 的分布计算问题；M.G.Gouda和M.Schneider [3]研究了最大流路由问题.在应 用数学领域C.Berge和A.Ghouila Houri⑷研究了最大可行流问题;L.R.Ford和 D.R.F\ilkson丨5j研究了最大动态流问题.关于最大流问题在社会，军事和工程领域 的应用研究也有很多文章，在这里我们就不一一列举了.尽管多年来许多学者的努力极大地推进了最大流问题的研究进展，但关于最 大流问题的研究还远远没有结束.首先,在理论算法研究方面，人们还没有发现最 大流问题算法时间复杂度的精确下界，更没有任何一个通用算法达到或接近问题 的下界;其次,在算法的实际性能方面，目前算法的实际性能也不能满足许多应用 问题的要求；同时，最大流问题作为特殊的线性规划问题，它远比一般线性规划问 题容易解决，发现应用领域中的问题和最大流问题的联系可以使应用问题更好地 得到解决.传统的最大流模型是流从一个源点经过一个网络,到达一个汇点的形式.本 文在传统模型的基础上，对网络进行分解.即把网络分解成几个相互独立的子网 络，从而得到从多源点到多汇点的模型.1.2逆向物流的定义及其主要环节供应链本身是一项循环物流系统(Cycle Logistics System),即由正向物流与逆 向物流构成.商品的正常需求与交易活动为供应—制造—配送—零售途径，满足 顾客的需要，这是物流的主流向渠道，称为正向物流;在另一种情况下，商品从顾客-2- 硕士学位论文 又流向了供应商，故称此为逆向物流.根据物流管理协会（CLM)的定义，逆向物流就是对由最终消费端到最初的 供应源之间的在制品、库存、制成品以及相应的信息流、资金流所进行的一系列 计划、执行和控制等活动及过程，目标是对产品进行适当的处理或者恢复一部分 价值.《中国国家标准物流术语》则将逆向物流分解为两大类：（1)回收物流(Returned Logistics):不合格物品的返修、退货以及周转使用的包装容器从需方返回到供方 所形成的物品实体流动；（2)废弃物物流(Waste Material Logistics):将经济活动中 失去原有使用价值的物品，根据实际需要进行收集、分类、加工、包装、搬运、储 存，并分送到专门处理场所时所形成的物品实体流动.许多学者对逆向物流的定义和内涵都提出了自己的看法.综合这些。