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

《网络最大流及回收中心选址问题研究.doc》由会员分享，可在线阅读，更多相关《网络最大流及回收中心选址问题研究.doc（50页珍藏版）》请在三一办公上搜索。

1、湖南大学硕士学位论文网络最大流及回收中心选址问题研究姓名：郭玉芬申请学位级别：硕士专业：概率论与数理统计导教师：李董辉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

2、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- plii mathematic, etc. The problem has been studied for more than forty yeara. Many researchers, including T

3、uring 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 an

4、d li肪 attracted much peoples 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

5、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 legislations releasing and the considerable economic int

6、erests 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 ent

7、ire 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湖南大学 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的成果。除了文中特别加以标注引用的内容外，本论文不包含任

8、 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要 贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律后果由本人承担。作者签名：約+窄日期-功年r月ir日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。本学位论文属于1、保密,_年解密后试用本授权书2、不保密0，(请在以上相应方框内打“/”） 作者签名：I+日期年、

9、月（r日曰期：r月ir日导师签名第1章绪论1.1 网络最大流问题研究背景电力网络给我们带来动力和光明；交通网络便利我们出行；电话网络把我们的声音传给远方的亲人和朋友.可以说在我们的日常生活中，网络无处不在.而近年来计算机网络的快速发展更使我们的生活发生了很大的变化.考虑这些网络的共同特性，可以把网络看成是由一些边和结点构成的图，我们希望通过图的边在它的结点之间传递某种物质.我们把这些物质称作流，例如表1.1给出的一些现实网络的组成表1.1 一些实际网络的组成网络结点边流交通网机场、车站铁路、公路飞机、车辆、旅客通信网计算机、卫星电缆、光纤音频、视频信号计算机集成电路门、寄存器、处理器线电流我们

10、想知道，在一个给定的网络中，利用何种方法可以更加有效地传输网络中 的流.这是一个十分重要的课题.网络流问题就是描述这类问题的数学模型.网络 流问题是指在结点和边有一定约束的网络中，使流的某些目标最优化.其中最常见 的网络流问题包括最小费用流问题、最短路径问题、最大流问题、最小费用最大 流问题等等.网络流问题是一类经典的优化问题，它不仅用来解决实际网络中的问题，科学 和工程领域的许多问题也可以抽象为网络流问题.网络流问题是计算机科学和运 筹学的重要研究内容，具有悠久的历史.近年来，计算机和通信等网络飞速发展，规 模越来越大，对网络流问题的研究提出了更高的要求,促使网络流问题的研究进入 一个新的高

11、潮.在现实生活的网络中，网络的结点和边一般都是有容量限制的.很多时候我们 想知道在一个容量有限制的网络中两个指定结点(分别称为源点和汇点)之间最多 能传输多少流量，并找到使网络达到最大流量的传输策略.网络最大流问题(简称 最大流问题)就是描述这个问题的数学模型.最大流问题是网络流理论的重要组成部分，它是一个经典的组合优化问题，同 时也可以看作是特殊的线性规划问题.最大流问题除了解决实际网络中的问题以 外，在许多工程领域和生物、物理、化学以及应用数学等科学领域有着广泛的应 用.因此，最大流问题是运筹学和计算机科学的重要研究内容.最大流问题已有四十多年的研究历史1.在这四十多年中，人们不仅建立了最

12、 大流问题较为完善的理论，同时也开发了大量的算法.近年来，随着各种网络和计 算机科学的飞速发展，最大流问题得到了更加深入的研究.但是对于最大流模型的研究还不是很多.最大流问题的对偶问题最小截问题也是经典的组合优化问题，也是特殊的线 性规划问题.它和最大流问题一样在实际生活中有很重要的作用.它们的应用涉及 交通、通信、计算机等许多工程领域和物理、化学、生物等许多科学领域,在应用 数学、管理科学和社会科学等众多领域中最大流和最小截问题也起到了非常重要 的作用.最大流和最小截问题的应用表现在： 在许多现实的网络中需要确定在两点间最大可输送的流量.例如在计算机网络中从一个端口传输到另一个端口的最大数据

13、量. 最大流或最小截问题常常作为一些其它问题，主要是图论、组合优化和线性规划等问题的一个子问题出现. 许多问题表面上看起来和最大流或最小截问题无关，但它们可以通过图论和 线性规划等方法把问题转化为最大流问题或最小截问题 目前最大流和最小截问题的应用已经深入到众多的领域，有许多文献做了大 量这方面的工作.如在计算机科学和通信系统领域R.K Ahuja研究了双处理 器计算机的分布计算;A.Federgmen和H.Groenevlelt 2研究了双处理器计算机 的分布计算问题；M.G.Gouda和M.Schneider 3研究了最大流路由问题.在应 用数学领域C.Berge和A.Ghouila Ho

14、uri研究了最大可行流问题;L.R.Ford和 D.R.Filkson丨5j研究了最大动态流问题.关于最大流问题在社会，军事和工程领域 的应用研究也有很多文章，在这里我们就不一一列举了.尽管多年来许多学者的努力极大地推进了最大流问题的研究进展，但关于最 大流问题的研究还远远没有结束.首先,在理论算法研究方面，人们还没有发现最 大流问题算法时间复杂度的精确下界，更没有任何一个通用算法达到或接近问题 的下界;其次,在算法的实际性能方面，目前算法的实际性能也不能满足许多应用 问题的要求；同时，最大流问题作为特殊的线性规划问题，它远比一般线性规划问 题容易解决，发现应用领域中的问题和最大流问题的联系可

15、以使应用问题更好地 得到解决.传统的最大流模型是流从一个源点经过一个网络,到达一个汇点的形式.本 文在传统模型的基础上，对网络进行分解.即把网络分解成几个相互独立的子网 络，从而得到从多源点到多汇点的模型.1.2逆向物流的定义及其主要环节供应链本身是一项循环物流系统(Cycle Logistics System),即由正向物流与逆 向物流构成.商品的正常需求与交易活动为供应制造配送零售途径，满足 顾客的需要，这是物流的主流向渠道，称为正向物流;在另一种情况下，商品从顾客又流向了供应商，故称此为逆向物流.根据物流管理协会（CLM)的定义，逆向物流就是对由最终消费端到最初的 供应源之间的在制品、库

16、存、制成品以及相应的信息流、资金流所进行的一系列 计划、执行和控制等活动及过程，目标是对产品进行适当的处理或者恢复一部分 价值.中国国家标准物流术语则将逆向物流分解为两大类：（1)回收物流(Returned Logistics):不合格物品的返修、退货以及周转使用的包装容器从需方返回到供方 所形成的物品实体流动；（2)废弃物物流(Waste Material Logistics):将经济活动中 失去原有使用价值的物品，根据实际需要进行收集、分类、加工、包装、搬运、储 存，并分送到专门处理场所时所形成的物品实体流动.许多学者对逆向物流的定义和内涵都提出了自己的看法.综合这些学者的表 述，逆向物流

17、意指物资从产品消费点到产品的来源点的物理性流动.尽管逆向物流 主要是指物资的逆向流动，但同时又伴随着信息流、资金流、价值流、商务流，它 与常规物流无缝对接而成为整个物流系统的有机组成部分.产品由企业到消费者的物流过程与使用过产品的处理从来都是一对孪生姐妹. 逆向物流更多的是针对“返回”供应链渠道中的产品或者材料，所以逆向物流主要 是指处理由损坏、不符合顾客要求的退回商品、季节性库存、残值处理、产品召回 等，另外还包括废物回收、危险材料的处理、过期设备的处理和资产的回收.主要 包括以下几个环节：1. 回收.回收是将顾客所持有的产品通过有偿或无偿的方式返回销售方.这里的 销售方可能是供应链上任何一

18、个节点，如来自顾客的产品可能返回到上游的 供应商、制造商，也可能是下游的配送商、零售商.2. 检验与处理决策.该环节是对回收品的功能进行测试分析，并根据产品结构特 点以及产品和各零部件的性能确定可行的处理方案，包括直接再销售、再加工 后销售、分拆后零部件再利用和产品或零部件报废处理等.然后，对各方案进 行成本效益分析，确定最优处理方案.3. 分拆.按产品结构的特点将产品分拆成零部件.4. 再加工.对回收产品或分拆后的零部件进行加工,恢复其价值.5. 报废处理.对那些没有经济价值或严重危害环境的回收品或零部件，通过机械 处理、地下掩埋或焚烧等方式进行销毁.西方因家对环保要求越来越高，而后 两种方

19、式会对环境带来一些不利影响，如占用土地、污染空气等.因此目前西 方国家主要采取机械处理方式PI.1.3逆向物流的成因分析近年来，随着全球经济的快速发展，企业之间竞争越来越激烈.如何在经济全 球化浪潮中站稳脚步，如何提高自身企业的竞争力，成为许多企业必须面对的问 题.而逆向物流在市场竞争中的重要作用使越来越多的企业意识到逆向物流已成 为市场竞争的一个有力武器.很多著名企业纷纷制定逆向物流战略，作为强化其竞 争优势、增加顾客价值、提高供应链整体绩效的重要手段.逆向物流在产业界的广 泛实践不是偶然的，它的产生源自于市场竞争、供应商的产品召回行为和环境保 护.(1) 逆向物流的“市场竞争”成因逆向物流

20、首先起因于竞争，因为客户满意是维持竞争优势最重要的策略.逆向 物流随着市场竞争程度的不同而不同.市场竟争程度越髙,顾客在交易中的地位越 有利，逆向物流也就越发达.下面以完全垄断市场和完全竞争市场这两个极端为例 来说明市场竞争程度对逆向物流带来的影响.在完全垄断市场中，完全不存在市场 竞争，只有一家厂商垄断产品的生产或销售，顾客在交易中处于绝对劣势.交易发 生后，即使是厂商的原因，顾客要求退货的愿望根本得不到满足，因为顾客根本没 有其它选择.因此逆向物流在这个市场中基本不存在.反之，完全竞争市场的竞争 程度最高,顾客完全处于优势，厂商任何引起顾客不满意的行为都会失去顾客.因 此厂商对顾客退货的条

21、件相当宽泛，由此而来的是顾客退货的增加.当退回产品规 模变大时，会对供应链中的正向物流产生较大的影响.为了降低成本，厂商不仅要 设立专门机构处理退回产品，而且需要借助信息技术建立专门的逆向物流系统，对 逆向物流活动和正向物流活动进行全面协调，从而提高效率，节约成本.因此在高 度竞争的市场中，逆向物流的发达程度关系着企业的经营成败，采用一个高效的逆 向物流系统己成为企业的战略选择.(2) 逆向物流的“环境保护”起因在产品生命周期的不同阶段都可能会对生态环境产生不良影这种影响主 要是源于物质不恰当的流动.例如，生产过程中的有毒中间物、产品使用过程及产 品报废后废弃物的流出等,均会对生态环境造成严重

22、破环.西方国家的经验研究表 明，企业的物流能力与环境策略的成功实施之间具有密切的关系：企业对环境问题 的反应将影响企业整个价值链上的许多物流决策;同时，物流管理者的决策对企业 环境项目的成功实施又具有深远的影响1.4供应链逆向物流的战略价值供应链的优化与管理成为企业聚集的焦点，这个以实物和业务为主线的流程 自上游供应商向下游顾客完成商务的基本使命，因而贯穿了物流、资金流、信息 流在内的诸多因素.通过这些职能，企业提升了利润空间，降低了成本.同样，逆向 物流涵盖了正向物流所提到的一切功能，只是实物流和信息流与正向物流的方向 截然相反，即出于重新获取和恢复价值或以适当处理为目的而将原材料、半成品、

23、 制成品及相关信息由供应链下游的最终消费端(或客户端)返回上游生产端(或供应 端)的过程.作为竞争中制胜的战略因素，无论是政府还是企业都为逆向物流的实际运作 提供了足够的资源和支持，很多企业投入大量精力人力财力构建和完善自己的供 应链和逆向供应链.逆向物流虽然是传统供应链的一个组成部分，但是通过实施一 系列控制手段、建立逆向物流信息系统，就可以降低在逆向物流管理领域出现的 由退货造成的资源损失.(1) 供应链逆向物流可以改善和提高顾客价值，增强供应链的整体战略竞争优 势.逆向物流能够确保不符合要求的产品及时退货，有利于消除顾客的后顾之忧， 提高顾客的满意度和忠诚度，扩大市场份额，从而增强企业的

24、战略竞争优势.另一 方面，对于供应链上的企业来说，上游企业采取宽松的退货策略，能减少下游企业 的经营风险，改善供需关系,促进企业间的战略合作，强化整个供应链的竞争优势.(2) 改善环境行为，塑造企业形象随着人们生活水平和文化素质的提高,环保 意识日益增强，人们的消费观念发生了巨大变化，顾客对环境的期望越来越髙.另 外，由于不可再生资源的稀缺以及环境污染的日益加重，各国都制订了许多环境保 护法规，为企业的环境行为规定了一个约束性标准.企业的环境业绩已成为评价企 业运营绩效的重要指标.为了改善企业的环境行为，提髙企业在公众中的形象,许 多企业纷纷采取逆向物流战略，以减少产品对环境的污染及对资源的消

25、耗.(3) 提升信息整合能力和产品质量监管体系.信息流如同资金流，贯穿于整个 供应链的各个环节之中.同样，逆向物流的成功实施,实质上就是企业内和企业间 的信息沟通与整合能力的强化，通过对退货和召回信息的归类与处理，可以直接追 踪所发生的逆向物流总成本，为正向物流的运作提供正确、及时的信息反馈.(4) 重新捕获价值和回收资产的成本优势.减少物料耗费，提高物料利用率是 企业成本管理的重点，也是企业增效的重要手段.废旧产品价格低、来源充足,对 这些产品回购加工可以大幅度的降低企业的物料成本.此外逆向物流的战略性功 能还表现在洁净渠道、合法处置等方面，对于企业长期利益目标而言，它的战略贡 献是多维的.

26、1.5 论文的工作和研究框架本文致力于研究带分解功能的网络最大流问题并研究回收中心选址及回收价 格的制定问题.最大流的应用一直是十分有意义的研究工作.本文在Mo JiMigtao 和Liqun丨8j的带分解功能的网络最小费用流模型的基础上，对已有网络最大流模 型进行改进，提出带分解功能的多源点多汇点网络最大流模型.该模型在现实生活 中有很广泛的应用.本文的另一个研究内容是利润最大化的回收中心选址问题.田輋云9j研究了 逆向物流网络中的选址-路径问题，本文在左军lOj的基础上，研究了一种新的回收 中心选址模型.该模型不仅能确定回收中心的建立地点和建立数目，并能在利润最 大化的前提下制定各回收中心

27、不同的回收价格，不仅为企业节省资源，更为企业带 来很好的利润.以下各章节安排如下：在第二章中，我们主要研究带分解功能的网络最大流问 题.第三章主要介绍逆向物流及选址问题的基础知识.第四章主要研究利润最大化 的回收中心选址及定价问题.第2章带分解功能的网络最大流问题2.引言和基本概念网络最大流问题是网络的一个基本问题.许多系统包含了流量问题.例如交 通系统有车流量，金融系统有现金流,控制系统有信息流等.随着计算机网络的飞 速发展，对网络最大流的研究更加的迫切.网络流研究的一个主要问题是确定这类 系统网络所能承受的最大流量以及如何达到这个最大流量.网络最大流问题的研究常借助于线性规划或组合最优化工

28、具.迄今为止已经有 许多关于网络最大流模型的描述，例如文献丨11 - I3及其参考文献.在文献I4中， Yi研究了最大流模型的应用.本章将着重研究一类带分解功能的网络最大流问 题.为此，我们先引入一些有关概念.定义2.1.1:个有向图(directed graph)G是由一个非空有限集合V(G)和 中某些元素的有序对集合4(G)构成的二元组,记为G = (V(G),A(G).其中V(G)= vi,V2,-, Vn称为图G的节点集(node set), VG)中的每个元素= 1，2，n) 称为该图的一个节点(node); AG) = ai.oz，称为图G的弧集(axe set),中的每一个元素a

29、fc(即中某两个元素z;i，v,的）记为dfc = vi,vj)ik = 1,2, .，m),被称为该图的一条从Vi到的弧(aic).在不引起混清的情况下，记有向 图G = (V，a, = ii,j).定义2.1.2:对于afc = vi, Vj),我们称Vi，为a*的端点，其中Vi为尾，为头； 弧a,称为与顶点；关联，并称弧at为的出弧，为Vj的入弧；称和同一个节点相 关联的弧为邻弧；如果两条弧共用两个端点，称它们为重弧.只与一个节点相关联 的弧称为圏.无重弧无圈的图称为单图.定义2.1.3:如果一个图= (V, 0和另个图= (V,),满足G V, A A,则称G为G的子图.图G中的一条道

30、路VT是G的一个子图，它由一系列结点 和边组成，且满足v彡与aj_i，a,相关联.结点不重复的道路称 为路径.起点和终点重合的路径称为环.如未特别指出，本文讨论的图都是单图.定义2.1.4:所谓网络是指一个有向加权图G = 0，1)，其中7代表0中节点的 集合，/I为弧的集合.记丨=n，丨4 =m.其中每条弧(i，j)上的权cj,称作该弧的容 量.图G称作网络的底图.如非特别指出，一个网络的底图是一个连通单图.在不引 起混淆的情况下，我们直接用底图G代表一个网络.定义2.1.5:如果一个矩阵A的任何子方阵的行列式的值都等于0, 1或-1，则 称A是全么模的(Totally Unimodulai

31、),或称A是全么模矩阵.2.2模型描述我们考虑如下问题.现有P个供应商，有q个客户，每个客户有一个运输子 网络，且这些子网络是相互独立的，现在从这P个供应商往这q个客户发送货物， 发货量由路况来决定.从而可以预算库存量，也确保能满足顾客的需求.在本文中， 我们假设顾客的需求只受到它的路的容量上界的影响.定义2.2.1:在以为节点函数，j为弧集的有向图G(V，1)中，定义如下的权函数：Ui ：弧(i，j) A,弧(i，:0的容量下界 Uij ：弧(i，j) e A,弧(i，j)的容量上界. di ：节点i e 节点i的供需量. 0:弧(丨，：01，弧(i，j)的标f. L:容量下界集.U:容量上

32、界集.Ei ：网络G中顶点i的入点集，即j G V ： (j,i) G A. Li ：网络G中顶点i的出点集，即j e V ： i,i) G A. D ：节点上的权函数，节点i V对应的权P记为di，称为顶点i的供需量.此时 所构成的网络称为流网络，可以记为iv = (V； A, L, U, D).在本文中不妨假设iij = 0.定义2.2.2:对于流网络JV = V,A,L,U,Dl其上的一个流a:是指从iV的弧 集A到的一个函数,即对每条弧(i,：/) 4斌予一个实数:ri,、如果流满足E 而i- E 印=4 Viey(2.1)iei(i) iGB(i)liiXiiUij，(2.2)则称:

33、T为可行流.至少存在一个可行流的流网络称为可行网络.约束(2.1)称为流量 平衡条件.约束(2.2)称为容量约束.下面，我们给出一种带分解功能的网络模型的结构.设Gi(K，Ai)是相互独立的 网络，即没有公共顶点也没有相邻的顶点，i 二0，1，.g.其中是第j个目的地所 在的子网络.其顶点表示需求点或转运点，j = l,2, .9, Go是供应子网络，其顶 点表示供应商或转运点.其中在H中取点i, Vj中取i,，分别添加弧(i,i,)，所得到的 网络记为，这就是带分解功能的网络模型.其中在模型中，假设每条弧满足容量约束为：0Xij0,Ci 0，且f： b = Z a = d那么最大流的问题可以

34、表示为=fcli=lYl ij ji = Vie v ,n,这里 1，P为P个供,P；iGL(i)j&E(i) 0 Xij 则问题(2.3)中的第二个约束条件可以记为A:+y = c/，因此最大 流问题可以用矩阵形式表示为X ZY , f 二 ki0uVbi0,cjx,ro其中J和0分别表示相应维数的单位矩阵和零矩阵.因为关联矩阵5为全么模矩阵， 因此，当所有弧容量均为正整数时，问题的最优解为整数解.2.3增广路算法定义2.3.1:设5，T是网络iV = (S, t, V, A, CO中给定的个割，M.sS,tT, 则称割S，r为s t割.S剩5，ri中的弧(i，j)(i S,j r)称为割的

35、向前弧， 弧(i，j)(j e S,i G r)称为弧的反向弧.s-f割s，T的容量定义为向前弧的容量之 和，记为mT)= Y.叫(2-4)(ij)eA,iesjeT一个网络中容量最小的s f割称为最小割. 0)ieSjeTE E 叫j iij iGSjerUS,T)因此定理成立.口从上面的定理证明过程同时可以看出，任意一个S - f可行流的流值等于任意 一个s-t割的所有向前弧的流量之和减去所有向后弧的流量之和.进一步，如果 存在一个可行流的流值等于一个S傳j的容量，则该可行流为最大流,该S -1为最 小割.定义2.3.2:设Z是流网络iV = 0，t，V；或CO中给定的可行流，P是一条从节

36、 Ms到节点f的路，则P中满足下列两个条件之一的弧(i，j)称为增广弧1. 弧(i，j)是的向前弧（即(i，j)e P+)且为不饱和弧(即: 0). 如果P中的弧都是增广弧，则称P为关于流I的増广路，简称增广路.定理2.3.2:如果对于一个可行流存在增广路，则可行流不是最大流.证明：设为关于可行流a;的一条增广路,令A= niin min - Xij, mm lij.j)6p-则么 0.于是，可以构造一个新的可行流如下：Xij+ A, (i,i) Gp+； ij = Xij- A, (i,j) ep-.Xij, 0,jHP.则:也是可行流，JLv(x) = v(x)-h A v(x).故z不是

37、最大流.定理2.3.3: 个可行流为最大流的充要条件的是不存在增广路. 证明：必要性可以由前面的定理直接得到.下面证明充分性. 假设流网络TV = (s, t, V, A, 17)中不存在关于可行流a;的增广路，记网络中从S出 发沿增广弧可以到达的节点集合为民令r = VS,则s GS,tT,即S，T为s 劇.并且，对于中的任意弧(ij),如果它是该 -_的前向弧，则:= Uij；如果 它是该3 割的反向弧，则=0.于是利用前面定理2.3.1证明中的中间结果有ieSjGT ieSieT=US,T)因此，Filkerson标号算法的基本思想对所有的节点J标号，其标号包括两 部分信息(ne:rt(

38、j)，max/(j):该节点在可能的增广路中的下一个节点ne:Et(j)，以 及沿该节点可能的增广路到该节点为止可以增广的最大流mox/(j). 算法：STEPO比较从节点i，i = 1， ，P出发的所有可增广弧的标号cy，选标号最小的 弧的终点，即为(ne:ct(i)，max/(i).STEP1从节点出发，寻找节点ne:rt(i)的下一个节点的编号. STEP2若重复STEP1能找到从某个供应点到客户的可增广路,则进行增广， STEP3重复进行前面的三步，直到网络中不再存在可增广的路，则停止.-11- 2.4数值例子如图1所示，令P = 3,q = 2.弧旁边的数(Ci,，Uij，:ri,)

39、分别表示弧(i,j)的标号和 弧的容量上界以及弧上的流量.图1利用本文中改进的增广路算法对本例题进行增广，所选的第一条增广路为1 4 5 8 9 10，增广量minmai/(j) = 2，其中= 1，4,5，8,9，10.增广后的图如图2所示.一直利用上面所提到的算法进行增广，一直到网络中不存在增广路，则停止.最后的增广量max i；? = 19.如图3所示.i=i2.5结论本章，我们对已有的模型进行了改进，使得最大流的模型得以更广泛的应用. 特别是在城市的交通运输，物流公司物资的配送.公司仓库的选址以及预测安全库 存量方面有较好的效果.图2图3第3章逆向物流中的选址问题硏究进展3.1 再制造

40、情况下的回收模式随着各国人们环保意识的增强以及出台的谁生产谁负责回收处理的法规，以 现代环境管理原则实现产品系统环境性能的改善的一种主要制度是传统的污染者 付费原则的深化和延伸，它要求生产者不仅要对生产过程中产生的环境污染负责， 而且要对产品在整个生命周期内的环境影响负责，即企业必须对其生产的产品的 整个生命周期(包括生产过程和生命结束阶段)负责，尤其是必须对其因销售而产 生的终极产品进行回收，再循环，再利用和废弃处理，从而实现资源的循环利用和 环境保护的目的.因此，在这样的背景下,大量的终极产品不再流入小商小贩和维 修站，而是由企业选择采取合理的方式进行回收处理，由此逆向物流回收，可以分 为

41、企业直接参与和间接参与两种方式.所谓直接参与即由企业自己直接负责终极 产品的回收处理工作；而间接参与是指企业可通过一定的契约或转让价将终极产 品的回收处理工作转让给联合团体或其他第二方物流公司负责.因此，根据参与逆 向物流回收主体的不同可分为:企业自营回收方式，企业联合体回收方式和第二方 回收方式.参与逆向供应链的基本实体主要有用户、回收商、回收中心、原制造商、原供 应商、原销售商和服务商.产品在用户手中的使用情况不同，导致了逆向供应链中 逆向物流的三种走向：第一种是用户在购买商品后使用不满意，要求退货：第二种 是用户在使用商品的过程中出现故障,要求维修;第三种是用户在产品的生命周期 内使用了

42、产品主要的客户价值，产品中还有一定的价值残留.产品回收是先将这三 种初始的逆向物流汇聚在一起，然后将其中包含的实物价值和信息价值提炼出来， 经过细分后传递给逆向供应链上的不同成员.产品回收是逆向供应链的物流载体， 有了回收的产品后逆向供应链的运作才真正启动起来，产品回收和将回收产品中 的实物价值和信息价值传递到逆向供应链的目标成员构成逆向供应链的主体.产品回收不但回收了产品外显的再循环价值，也回收了产品内潜在的市场信 息和客户信息.客户端作为供应链和逆向供应链衔接点，起到了承上启下的作用， 通过客户端的衔接，才使正向供应链和逆向供应链啮合为循环流程的可持续发展 供应链.因此，产品回收管理是从用

43、户手中收回用户不能使用或不愿继续使用的产 品，并对回收产品分类检测,分析处理后对其实施基于现代信息技术的回收产品数 据信息管理和基于现代管理理念的回收产品客户关系管理.逆向物流的联合体经营方式是指生产相同产品或者相似产品的同行业企业进 行合作，以合资等形式建立共同的逆向物流系统(包括回收网络和处理系统)，为各 合作企业甚至包括非合作企业提供逆向物流服务.逆向物流的自营方式就是指生产企业建立独立的逆向物流体系，自己管理退 货和废旧物品的回收处理业务.在逆向物流自营方式下，企业不但重视产品的生产 销售和售后服务(包括退货的管理)，还重视产品在消费之后的废旧物品以及包装 材料的回收和处理.企业建立了

44、遍及所有本企业产品销售区域的逆向物流网络，以 便回收各种回流物品，并将其送到企业的回流物品处理中心进行集中处理.在政府 管制的条件下，生产企业建立自己的逆向物流系统，这是外部社会成本的内部化, 是生产者责任延伸制度的主要形式.逆向物流的外包方式是生产企业通过协议形式将其回流产品的回收处理中的 部分或者全部业务，以支付费用等方式,交由专门从事逆向物流服务的企业负责实 施.随着政府对企业回收责任限制的加大，企业逆向物流中的各功能模块可能由 一个或多个企业来承担，可以采取的形式也是多种多样的，根据美国逆向物流委员 会对300多家物流企业的逆向物流活动模式选择的调查结果显示，不同企业会根据 逆向物流活

45、动的不同而选择不同的模式.逆向物流和传统的正向物流相比，在运作 和机理上具有其特殊性，不同的模式对企业逆向物流系统的不同方面存在不同的 影响.(1) 在联营回收模式下，以由生产商联合体来负责完成相应的回收处理.同时， 生产商联合体回收的是同类产品，产品具有相似性，只需建立少量的回收处理中 心，减少产品回收的中间环节，节约回收成本.但是，亦不可避免地具有缺陷.尽管 负责回收的是同类产品，但是同类产品依然在一定程度上具有各自产品的专业机 密信息，而联营回收模式很难获得这些信息，增加回收拆卸难度，同时产品被回收 之后，不可能进入闭环再循环,而只能进行其它产品的再利用和再制造工作-(2) 自营回收模式下，由于是由企业本身回收自己生产销售的产品，企业能根 据市场销售渠道掌握产品的流向，具有快速信息反馈的能力，使其回收工作运作高 效.同