（概率论与数理统计专业论文）网络最大流及回收中心选址问题研究.pdf

网络最大流及回收中心选址问题研究 摘要 本文研究网络最大流闻题及回收中心选址定价闯题 网络最大流问题是个经典的组合优化问题同时也是一个特殊的线性规划问 题最大漉问题在通信、电力、交通等工程领域和物理、化学、生物以及应用数学 等许多科学领域有着广泛的应用最大流问题已经有四十多年的研究历史，在这四 十多年中，包括图灵奖获得者k a r l ) 和t a x j a n 在内的许多学者为最大流问题创建 了比较宪善的理论和丰富的算法但是，对于最大流模型的研究却不是很多近年 来，随着各类网络的飞速发展，规模越来越大，最大漉网络翡研究更具有意义，已 引起越来越多学者的广泛关注 本文在传统孵络最大流模型的基础上，提出了一种多源点多汇点的最大流模 型。且源点和汇点在不同的子网络中即具有分解功能的网络最大流模型，我们还 提出了一种分解算法求得该6 j l 题的最优解 一个完整的供应链系统不仅包括正向物流，还包括逆向物流但是长期以来， 管理者忽略了顾客退阐物品以及产品使用后废弃物品的处理随着环保意识的增 强，环保立法的出台和可观的经济利益的显现，企业开始关注逆向物流，人们对废 弃物品的回收利用日益重视逆向物流已成为物流系统研究的一个热门课题，人们 对诧进行了大量的研究工作并且成为国外许多著名企业管理战略的重要组成部 分作为逆向物流网络中的重要环节，回收中心的选址对整个物流系统的顺利实施 起着重要的作用 本文的另一个内容就是研究在第三方物流公司承包回收任务下，回收中心的 选垃问题以及网收价格的制定问题 关键词：最大流，可行流，逆向物流，回收中心，递减比值选择算法 i i 硕士学仪论文 a b s t r a c t t h i st h e s i ss t u d i e st h en e t w o r km a x i m a l - f l o wp r o b l e ma n dt h el o c a t i o no ft h e r e c y c l i n gc e n t e r t kn e t w o r km a x i m a l - f l o wp r o b l e mi sn o to n l yac l a s s i c a lc o m b i n a t o r i a lo p - t i m i z a t i o np r o b l e m ，b u ta l s oas p e c i a ll i n e a rp r o g r a m m i n gp r o b l e m i th a saw i d e v 糠e t yo fa p p l i c a t i o n si ne n g i n e e r i n gf i e l d ss u c ha sc o m m u n i c a t i o n ，e l e c t r i cp o w e r ， t r a n s p o r t a t i o n ，e t c ，a n ds c i e n t i f i cf i e l d ss u c ha sp a y s i c s ，c h e m i s t r y , b i o l o g y , a p - p l i e dm a t h e m a t i c ，e t c 。t h ep r o b l e mh a sb e e ns t u d i e df o rm o r et h a nf o r t yy e a r s m a n yr e s e a r c h e r s ，i n c l u d i n gt u r i n gp r i z ew i n n e r sk a r pa n dt a r j a n ，h a v ee s t a b - l i s h e di n t e g r a t et h e o r i e sa n de x p l o r e dm a n ya l g o r i t h m sf o rt h ep r o b l e m o nt h e o t h e rh a n d ，h o w e v e r ，t h er e s e a r c hi nt h em a x i m a l - f l o wm o d e lv a r i e si sr e l a t i v e l y f e w e r w i t ht h er a p i dd e v e l o p m e n to fn e t w o r k sm a x i m a l - f l o wb e c o m e sm o r ea n d m o r ei m p o r t a n ta n dh a sa t t r a c t e dm u c hp e o p l e sa t t e n t i o n o nt h eb a s eo ft r a d i t i o n a ln e t w o r km a x i m u mf l o wm o d e l ，t h i st h e s i ss t u d i e s n e t w o r km a x i m u mf l o wm o d e lw i t hm o r et h a no n es o u r c ea n ds i n ki nd i f f e r e n t s u b - n e t w o r k w ea l s op r o p o s ead e c o m p o s i t i o nm e t h o dt os o l v et h em o d e l a c o m p l e t es u p p l yc h a i ns y s t e mi n c l u d e sn o to 出t h ef o r w a r dl o g i s t i c s ，b u t a l s or e v e r s el o g i s t i c s i th a sp a s t e dav e r yl o n gt i m es i n c et h ee n t e r p r i s e sp a y a t t e n t i o nt ot h er e t u r np r o d u c t sa n do v e r d o n ep r o d u c t s 。w i 毛he n v i r o n m e n t a l c o n s c i o u s n e s de n h a n c e m e n t ，e n v i r o n m e n t a lp r o t e c t i o nl e g i s l a t i o n sr e l e a s i n ga n d t h ec o n s i d e r a b l ee c o n o m i ci n t e r e s t sa p p e a r a n c e ，t h ee n t e r p r i s e ss t a r tt op a ya t - t e n t i o nt ot h er e v e r s el o g i s t i c s r e v e r s el o g i s t i c sh a sb e c o m et h ew a r mt o p i c t h e r e s e a r c hi nt h i st o p i ch a st a k e ng o o dp r o g r e s s a st h ei m p o r t a n tl i n ko fr e v e r s e l o g i s t i c sn e t w o r k ，t h el o c a t i o no fr e c y c l i n gc e n t e rp l a y sa ni m p o r t a n tr o l ei nt h e e n t i r el o g i s t i c ss y s t e m i nt h i st h e s i s ，w ew i l la l s os t u d yt h el o c a t i o no fr e c y c l i n gc e n t e ra n dt h er e t l t r n p r i c e k e yw o r d s ：m a x i m u mf l o w ；f e a s i b l ef l o w ；r e v e r s el o g i s t i c s ；r e c y c l i n g c e n t e r ；d e c r e a s i n gr a n k i n gs e l e c t i o na l g o r i t h m 湖南大学 学位论文原创性声明 本人郑重声明；所呈交的论文是本人在导师的指导下独立进行研究 所取得眨成果。除了文中特别加以标注引用鲶内容外，本论文不包含任 何其弛个人或集体已经发表或撰写的成果作品。对本文的研究做出重要 贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律詹果由本人承担。 作者签名：朝毒荔 霉期：阳g 年r 月；f 霉 学位论文版权使用授权书 本学位论文作者完全了解学校有关傈嫠、使用学位论文的规定，同 意学校保留并向囡家有关部门或机构送交论文的复印件和电子舨，允许 论文被查阕和借阅。本人授权湖南大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年勰密后试用本授权书。 2 、不保密留。 ( 请在以上相应方框内打“) 作者签 导师签 日期：髻年r 胃fy 曷 日期：w ，绰厂月ffb 硕士学位论文 第1 章绪论 1 1网络最大流问题研究背景 电力网络给我们带来动力和光明；交通网络便利我们出行；电话网络把我们的 声音传给远方的亲人和朋友可以说在我们的日常生活中，网络无处不在而近年 来计算机网络的快速发展更使我们的生活发生了很大的变化 考虑这些网络的共同特性，可以把网络看成是由一些边和结点构成的图，我 们希望通过图的边在它的结点之间传递某种物质我们把这些物质称作流，例如 表1 1 给出的一些现实网络的组成 表1 1 一些实际网络的组成 网络结点边流 交通网机场、车站铁路、公路飞机、车辆、旅客 通信网计算机、卫星电缆、光纤音频、视频信号 计算机集成电路 门、寄存器、处理器线电流 我们想知道，在一个给定的网络中，利用何种方法可以更加有效地传输网络中 的流这是一个十分重要的课题网络流问题就是描述这类问题的数学模型网络 流问题是指在结点和边有一定约束的网络中，使流的某些目标最优化其中最常见 的网络流问题包括最小费用流问题、最短路径问题、最大流问题、最小费用最大 流问题等等 网络流问题是一类经典的优化问题，它不仅用来解决实际网络中的问题，科学 和工程领域的许多问题也可以抽象为网络流问题网络流问题是计算机科学和运 筹学的重要研究内容，具有悠久的历史近年来，计算机和通信等网络飞速发展，规 模越来越大，对网络流问题的研究提出了更高的要求，促使网络流问题的研究进入 一个新的高潮 在现实生活的网络中，网络的结点和边一般都是有容量限制的很多时候我们 想知道在一个容量有限制的网络中两个指定结点( 分别称为源点和汇点) 之间最多 能传输多少流量，并找到使网络达到最大流量的传输策略网络最大流问题( 简称 最大流问题) 就是描述这个问题的数学模型 最大流问题是网络流理论的重要组成部分，它是一个经典的组合优化问题，同 时也可以看作是特殊的线性规划问题最大流问题除了解决实际网络中的问题以 外。在许多工程领域和生物、物理、化学以及应用数学等科学领域有着广泛的应 用因此，最大流问题是运筹学和计算机科学的重要研究内容 最大流问题已有四十多年的研究历史【1 】在这四十多年中，人们不仅建立了最 大流问题较为完善的理论，同时也开发了大量的算法近年来，随着各种网络和计 算机科学的飞速发展，最大流问题得到了更加深入的研究但是对于最大流模型的 一l 一 网络最大流及回收中心选址问题研究 研究还不是很多 最大流问题的对偶问题最小截问题也是经典的组合优化问题，也是特殊的线 性规划问题它和最大流问题一样在实际生活中有很重要的作用它们的应用涉及 交通、通信、计算机等许多工程领域和物理、化学、生物等许多科学领域，在应用 数学、管理科学和社会科学等众多领域中最大流和最小截问题也起到了非常重要 的作用最大流和最小截问题的应用表现在： 在许多现实的网络中需要确定在两点间最大可输送的流量例如在计算机网 络中从一个端口传输到另一个端口的最大数据量 最大流或最小截问题常常作为一些其它问题，主要是图论、组合优化和线性规 划等问题的一个子问题出现 许多问题表面上看起来和最大流或最小截问题无关。但它们可以通过图论和 线性规划等方法把问题转化为最大流问题或最小截问题 e 1 目前最大流和最小截问题的应用已经深入到众多的领域，有许多文献做了大 量这方面的工作如在计算机科学和通信系统领域r ka h u j a 1 】研究了双处理 器计算机的分布计算；a f e d e r g r u e n 和h g r o e n e v l e l t 【2 】研究了双处理器计算机 的分布计算问题；m g g o u d a 和m s c h n e i d e r 3 1 研究了最大流路由问题在应 用数学领域c b e r g e 和a g h o u i l ah o u r i 4 1 研究了最大可行流问题：l r f o r d 和 d r f u l k s o nf 5 】研究了最大动态流问题关于最大流问题在社会，军事和工程领域 的应用研究也有很多文章，在这里我们就不一一列举了 尽管多年来许多学者的努力极大地推进了最大流问题的研究进展，但关于最 大流问题的研究还远远没有结束首先，在理论算法研究方面，人们还没有发现最 大流问题算法时间复杂度的精确下界，更没有任何一个通用算法达到或接近问题 的下界；其次，在算法的实际性能方面，目前算法的实际性能也不能满足许多应用 问题的要求；同时，最大流问题作为特殊的线性规划问题，它远比一般线性规划问 题容易解决，发现应用领域中的问题和最大流问题的联系可以使应用问题更好地 得到解决 传统的最大流模型是流从一个源点经过一个网络，到达一个汇点的形式本 文在传统模型的基础上，对网络进行分解即把网络分解成几个相互独立的子网 络，从而得到从多源点到多汇点的模型 1 2逆向物流的定义及其主要环节 供应链本身是一项循环物流系- 统( c y c l el o g i s t i c ss y s t e m ) ，即由正向物流与逆 向物流构成。商品的正常需求与交易活动为供应_ 制造一配送一零售途径，满足 顾客的需要，这是物流的主流向渠道，称为正向物流；在另一种情况下，商品从顾客 一2 一 硕士学位论文 又流向了供应商，故称此为逆向物流 根据物流管理协会( c l m ) 的定义，逆向物流就是对由最终消费端到最初的 供应源之间的在制品、库存、制成品以及相应的信息流、资金流所进行的一系列 计划、执行和控制等活动及过程，目标是对产品进行适当的处理或者恢复一部分 价值 中国国家标准物流术语则将逆向物流分解为两大类：( 1 ) 回收物流( r e t 啪e d l o g i s t i c s ) ：不合格物品的返修、退货以及周转使用的包装容器从需方返回到供方 所形成的物品实体流动；( 2 ) 废弃物物流( w a s t em a t e r i a ll o g i s t i c s ) ：将经济活动中 失去原有使用价值的物品，根据实际需要进行收集、分类、加工、包装、搬运、储 存，并分送到专门处理场所时所形成的物品实体流动 许多学者对逆向物流的定义和内涵都提出了自己的看法综合这些学者的表 述，逆向物流意指物资从产品消费点到产品的来源点的物理性流动尽管逆向物流 主要是指物资的逆向流动，但同时又伴随着信息流、资金流、价值流、商务流，它 与常规物流无缝对接而成为整个物流系统的有机组成部分 产品由企业到消费者的物流过程与使用过产品的处理从来都是一对孪生姐妹 逆向物流更多的是针对“返回”供应链渠道中的产品或者材料，所以逆向物流主要 是指处理由损坏、不符合顾客要求的退回商品、季节性库存、残值处理、产品召回 等，另外还包括废物回收、危险材料的处理、过期设备的处理和资产的回收主要 包括以下几个环节： 1 回收回收是将顾客所持有的产品通过有偿或无偿的方式返回销售方这里的 销售方可能是供应链上任何一个节点，如来自顾客的产品可能返回到上游的 供应商、制造商，也可能是下游的配送商、零售商 2 检验与处理决策该环节是对回收品的功能进行测试分析，并根据产品结构特 点以及产品和各零部件的性能确定可行的处理方案，包括直接再销售、再加工 后销售、分拆后零部件再利用和产品或零部件报废处理等然后，对各方案进 行成本效益分析，确定最优处理方案 3 分拆按产品结构的特点将产品分拆成零部件 4 再加工对回收产品或分拆后的零部件进行加工，恢复其价值 5 报废处理对那些没有经济价值或严重危害环境的回收品或零部件，通过机械 处理、地下掩埋或焚烧等方式进行销毁西方因家对环保要求越来越高，而后 两种方式会对环境带来一些不利影响，如占用土地、污染空气等因此目前西 方国家主要采取机械处理方式【7 】 一3 一 网络最大流及回收中心选址问题研究 1 3逆向物流的成因分析 近年来，随着全球经济的快速发展，企业之间竞争越来越激烈如何在经济全 球化浪潮中站稳脚步，如何提高自身企业的竞争力，成为许多企业必须面对的问 题而逆向物流在市场竞争中的重要作用使越来越多的企业意识到逆向物流已成 为市场竞争的一个有力武器很多著名企业纷纷制定逆向物流战略，作为强化其竞 争优势、增加顾客价值、提高供应链整体绩效的重要手段逆向物流在产业界的广 泛实践不是偶然的，它的产生源自于市场竞争、供应商的产品召回行为和环境保 护 ( 1 ) 逆向物流的“市场竞争刀成因 逆向物流首先起因于竞争，因为客户满意是维持竞争优势最重要的策略逆向 物流随着市场竞争程度的不同而不同市场竞争程度越高，顾客在交易中的地位越 有利，逆向物流也就越发达下面以完全垄断市场和完全竞争市场这两个极端为例 来说明市场竞争程度对逆向物流带来的影响在完全垄断市场中，完全不存在市场 竞争，只有一家厂商垄断产品的生产或销售，顾客在交易中处于绝对劣势交易发 生后，即使是厂商的原因，顾客要求退货的愿望根本得不到满足，因为顾客根本没 有其它选择因此逆向物流在这个市场中基本不存在反之，完全竞争市场的竞争 程度最高，顾客完全处于优势，厂商任何引起顾客不满意的行为都会失去顾客因 此厂商对顾客退货的条件相当宽泛，由此而来的是顾客退货的增加当退回产品规 模变大时，会对供应链中的正向物流产生较大的影响为了降低成本，厂商不仅要 设立专门机构处理退回产品，而且需要借助信息技术建立专门的逆向物流系统，对 逆向物流活动和正向物流活动进行全面协调，从而提高效率，节约成本因此在高 度竞争的市场中，逆向物流的发达程度关系着企业的经营成败，采用一个高效的逆 向物流系统己成为企业的战略选择- ( 2 ) 逆向物流的“环境保护起因 在产品生命周期的不同阶段，都可能会对生态环境产生不良影响，这种影响主 要是源于物质不恰当的流动例如，生产过程中的有毒中间物、产品使用过程及产 品报废后废弃物的流出等，均会对生态环境造成严重破环西方国家的经验研究表 明，企业的物流能力与环境策略的成功实施之间具有密切的关系：企业对环境问题 的反应将影响企业整个价值链上的许多物流决策；同时，物流管理者的决策对企业 环境项目的成功实施又具有深远的影响【7 】 1 4供应链逆向物流的战略价值 供应链的优化与管理成为企业聚集的焦点，这个以实物和业务为主线的流程 自上游供应商向下游顾客完成商务的基本使命。因而贯穿了物流、资金流、信息 一4 一 硕士学位论文 流在内的诸多因素通过这些职能，企业提升了利润空间，降低了成本同样，逆向 物流涵盖了正向物流所提到的一切功能，只是实物流和信息流与正向物流的方向 截然相反，即出于重新获取和恢复价值或以适当处理为目的而将原材料、半成品、 制成品及相关信息由供应链下游的最终消费端( 或客户端) 返回上游生产端( 或供应 端) 的过程 作为竞争中制胜的战略因素，无论是政府还是企业都为逆向物流的实际运作 提供了足够的资源和支持，很多企业投入大量精力人力财力构建和完善自己的供 应链和逆向供应链逆向物流虽然是传统供应链的一个组成部分，但是通过实旌一 系列控制手段、建立逆向物流信息系统，就可以降低在逆向物流管理领域出现的 由退货造成的资源损失 ( 1 ) 供应链逆向物流可以改善和提高顾客价值，增强供应链的整体战略竞争优 势逆向物流能够确保不符合要求的产品及时退货，有利于消除顾客的后顾之忧， 提高顾客的满意度和忠诚度，扩大市场份额，从而增强企业的战略竞争优势另一 方面，对于供应链上的企业来说，上游企业采取宽松的退货策略，能减少下游企业 的经营风险，改善供需关系，促进企业间的战略合作，强化整个供应链的竞争优势 ( 2 ) 改善环境行为，塑造企业形象随着人们生活水平和文化素质的提高，环保 意识日益增强，人们的消费观念发生了巨大变化，顾客对环境的期望越来越高另 外，由于不可再生资源的稀缺以及环境污染的日益加重，各国都制订了许多环境保 护法规，为企业的环境行为规定了一个约束性标准企业的环境业绩已成为评价企 业运营绩效的重要指标为了改善企业的环境行为，提高企业在公众中的形象，许 多企业纷纷采取逆向物流战略，以减少产品对环境的污染及对资源的消耗 ( 3 ) 提升信息整合能力和产品质量监管体系信息流如同资金流，贯穿于整个 供应链的各个环节之中同样，逆向物流的成功实施，实质上就是企业内和企业间 的信息沟通与整合能力的强化，通过对退货和召回信息的归类与处理，可以直接追 踪所发生的逆向物流总成本，为正向物流的运作提供正确、及时的信息反馈 ( 4 ) 重新捕获价值和回收资产的成本优势减少物料耗费，提高物料利用率是 企业成本管理的重点，也是企业增效的重要手段废旧产品价格低、来源充足，对 这些产品回购加工可以大幅度的降低企业的物料成本此外逆向物流的战略性功 能还表现在洁净渠道、合法处置等方面，对于企业长期利益目标而言，它的战略贡 献是多维的 1 5论文的工作和研究框架 本文致力于研究带分解功能的网络最大流问题并研究回收中心选址及回收价 格的制定问题最大流的应用一直是十分有意义的研究工作本文在m oj i a n 舀c , a o 一5 一 网络最大流及回收中心选址问题研究 和l i q u n | 8 1 的带分解功能的网络最小费用流模型的基础上，对已有网络最大流模 型进行改进，提出带分解功能的多源点多汇点网络最大流模型该模型在现实生活 中有很广泛的应用 本文的另一个研究内容是利润最大化的回收中心选址问题田肇云 9 】研究了 逆向物流网络中的选址路径问题，本文在左军 1 0 】的基础上，研究了一种新的回收 中心选址模型该模型不仅能确定回收中心的建立地点和建立数目，并能在利润最 大化的前提下制定各回收中心不同的回收价格，不仅为企业节省资源，更为企业带 来很好的利润 以下各章节安排如下：在第二章中，我们主要研究带分解功能的网络最大流问 题第三章主要介绍逆向物流及选址问题的基础知识第四章主要研究利润最大化 的回收中心选址及定价问题 一6 一 硕士学位论文 第2 章带分解功能的网络最大流问题 2 1引言和基本概念 网络最大流问题是网络的一个基本问题许多系统包含了流量问题例如交 通系统有车流量，金融系统有现金流，控制系统有信息流等随着计算机网络的飞 速发展，对网络最大流的研究更加的迫切网络流研究的一个主要问题是确定这类 系统网络所能承受的最大流量以及如何达到这个最大流量 网络最大流问题的研究常借助于线性规划或组合最优化工具迄今为止已经有 许多关于网络最大流模型的描述，例如文献 1 1 】一【1 3 】及其参考文献在文献【1 4 】中， y i 研究了最大流模型的应用本章将着重研究一类带分解功能的网络最大流问 题为此，我们先引入一些有关概念 定义2 1 1 ：一个有向图( d i r e c t e dg r a p h ) g 是由一个非空有限集合y ( g ) 和v ( c ) 中某些元素的有序对集合a ( g ) 构成的二元组，记为g = ( y ( g ) ，a ( g ) ) 其中y ( g ) = p l ，耽，称为图g 的节点集( n o d e8 e t ) ，y ( g ) 中的每个元素哦o = 1 ，2 ，神 称为该图的一个节点( n o d e ) ；a ( a ) = 忙1 ，a q ， 称为图g 的弧集( s l i = _ c8 e t ) ， a ( g ) 中的每一个元素口七( 即y ( g ) 中某两个元素饥，的) 记为口七= 做，) ( 七= 1 ，2 ， ，m ) ，被称为该图的一条从佻到的弧( 缸c ) 在不引起混淆的情况下，记有向 图g = ( ka ) ，= ( i ，歹) 定义2 1 2 ：对于鲰= 似，) ，我们称优，为a k 的端点，其中讧为尾，为头； 弧a 七称为与顶点铫，关联，并称弧讯为的出弧，为吻的入弧；称和同一个节点相 关联的弧为邻弧：如果两条弧共用两个端点，称它们为重弧只与一个节点相关联 的弧称为圈无重弧无圈的图称为单图 定义2 1 3 ：如果一个图g ，= ( v ，a ) 和另一个图g = ( va ) ，满足v 7 v ， 彳a ，则称g ，为g 的子图图g 中的一条道路是g 的一个子图，它由一系列结点 和边u l a l 耽d 2 仇一1 鲰一l 讥组成，且满足与吩一1 ，嘭相关联结点不重复的道路称 为路径起点和终点重合的路径称为环 如未特别指出，本文讨论的图都是单图 定义2 1 4 ：所谓网络是指一个有向加权图g = ( ka ) ，其中y 代表g 中节点的 集合，a 为弧的集合记l y i = n ，i a i = m 其中每条弧( ，歹) 上的权勺称作该弧的容 量图g 称作网络的底图如非特别指出，一个网络的底图是一个连通单图在不引 起混淆的情况下，我们直接用底图g 代表一个网络 定义2 1 5 ：如果一个矩阵a 的任何子方阵的行列式的值都等于0 ，1 或- 1 ，则 称a 是全幺模的( w o t n yu n i m o d u k ) ，或称a 是全幺模矩阵 一7 一 网络最大流及回收中心选址问题研究 2 2 模型描述 我们考虑如下问题现有p 个供应商，有q 个客户，每个客户有一个运输子 网络，且这些子网络是相互独立的，现在从这p 个供应商往这q 个客户发送货物， 发货量由路况来决定从而可以预算库存量，也确保能满足顾客的需求在本文中 我们假设顾客的需求只受到它的路的容量上界的影响 ，1 定义2 2 1 ：在以y 为节点函数，a 为弧集的有向图g ( va ) 中，定义如下的权函 数： 岛：弧( i ，歹) a ，弧( i ，歹) 的容量下界 ：弧( i ，j i ) a ，弧( i ，j ) 的容量上界 d ：节点i v ，节点i 的供需量 勺：弧( i ，歹) a ，弧( i ，歹) 的标号 l ：容量下界集 。 u ：容量上界集 忍：网络g 中顶点i 的入点集，即d v ：u ，i ) a 厶：网络g 中顶点珀勺出点集，即d v ：( i ，歹) a ) d ：节点上的权函数，节点i v 对应的权d ( 0 记为磊，称为顶点i 的供需量此时 所构成的网络称为流网络，可以记为n = ( va ，厶以d ) 在本文中不妨假设幻= 0 定义2 2 2 ：对于流网络n = ( va ，l ，阢d ) ，其上的一个流z 是指从的弧 集a 至j j r 的一个函数，即对每条弧( i ，歹) a 赋予一个实数z 材如果流z 满足 z 巧一= 盔，v ( 2 1 ) j e l ( i )j e e ( o 岛z 嵇“巧，v ( i ，歹) a ( 2 2 ) 则称z 为可行流至少存在一个可行流的流网络称为可行网络约束( 2 1 ) 称为流量 平衡条件约束( 2 2 ) 称为容量约束 下面，我们给出一种带分解功能的网络模型的结构设g i ( k ，a ) 是相互独立的 网络，即没有公共顶点也没有相邻的顶点，i = 0 ，1 ，口其中岛是第歹个目的地所 在的子网络其顶点表示需求点或转运点，歹= 1 ，2 ，口，g o 是供应子网络，其顶 点表示供应商或转运点其中在k 中取点i ，巧中取巧，分别添加弧( i ，i j ) ，所得到的 网络记为c w , a ) ，这就是带分解功能的网络模型其中 v = u ：= o k ，a = ( u ：o a ) ua +，a + = u i e v o o ，i 七) ：k = 1 ，g ) 在模型中，假设每条弧满足容量约束为： 0 x q u o ，v ( i ，歹) a 一8 一 硕士学位论文 其中0 ，且为整数并且假设网络中的所有顶点均满足流平衡约束，即 一= d i ，v 对y 中的节点编号，1 ，2 ，p ，七l ，岛，n ，这里l ，p 为p 个供 应商的编号，b 为第歹个客户的编号j = 1 ，q 由此可知 ， i 玩， i = 1 ，p ； d i = 一c i ，i = 后l ，k q ； lo ，其他 这里，6 i o ，c o ，且以= - vc i = d ，那么最大流的问题可以表示为 m a x 玩 5 t z 谚一= 盔 ( 2 3 ) 0sz i j ，v ( i ，j ) a 其中画如前面所定义 定理2 2 1 ( 整流定理) ：最大流问题所对应的约束矩阵是全幺模矩阵，若所有 弧容量均为正整数，则问题的最优解为整数解 证明：v 中的节点编号如前面所示，弧表按节点字典序排列，记网络的关联矩 阵为b ，并记 x = x l l , x 1 2 ，) t z = ( 一b l ，0 ，0 ，一玩，0 ，o ，c l ，0 ，o ，q ，0 ) t i = 1 ，p ，歹= 七1 ，k u = ( u l l , u 1 2 ，) t 则问题( 2 渤中的第一个约束条件可以记为b x + z = 。，即cb ，( 喜) = 。 引入松弛变量y ，则问题( 2 3 ) 中的第二个约束条件可以记为x + y = u ，因此最大 流问题可以用矩阵形式表示为 眦玩 ， 5 t 地0 ，q 0 x ，y 0 9 一 ( 至 p ，= 、l _ 、 0 u b ， = 、，h 、l、 ， 0 ， 一 ，o l= b ， i 网络最大流及回收中心选址问题研究 其中j r 和0 分别表示相应维数的单位矩阵和零矩阵因为关联矩阵b 为全幺模矩阵， 因此，当所有弧容量均为正整数时，问题的最优解为整数解口 2 3 增广路算法 定义2 3 1 ：设限邪是网络n = ( s ，t ，k a ，u ) 中给定的一个割，且5 s ，t t ， 则称割限卅为3 一培 i 5 一培慨t 】中的弧( i ，j ) 0 s , j t ) 称为割的向前弧， 弧( i ，j i ) g 只i t ) 称为弧的反向弧s 一培0 限刁的容量定义为向前弧的容量之 和，记为 u ( 只t ) = ( 2 4 ) “j ) a ，i e h j t 一个网络中容量最小的5 一培u 称为最小割 定理2 3 1 ：任意一个5 一亡可行流的流值不超过任意一个5 一亡割的容量 证明：设z 为一个3 一t 可行流，【s ，列为一个s 一培4 ，则由式( 2 4 ) 有 口( z ) =( z 嵇一) i c sj yj y ( z 嵇i ) + 0 巧一) i s j si e s j i 2 eg i j 一i ) ( 0 ) ( ) = u ( 最t ) 因此定理成立口 从上面的定理证明过程同时可以看出，任意一个5 一t 可行流的流值等于任意 一个5 一t 割的所有向前弧的流量之和减去所有向后弧的流量之和进一步，如果 存在一个可行流的流值等于一个5 一t 割的容量，则该可行流为最大流，该s t 为最 小割 定义2 3 2 ：设z 是流网络n = ( 5 ，t ，ka ，u ) 中给定的可行流，p 是一条从节 点s 到节点亡的路，则p 中满足下列两个条件之一的弧( i ，歹) 称为增广弧 1 弧( i ，歹) 是p 的向前弧( 即( i ，歹) p + ) 且为不饱和弧( 即z 材 o ) 如果p 中的弧都是增广弧，则称p 为关于流z 的增广路，简称增广路 定理2 3 2 ：如果对于一个可行流存在增广路，则可行流不是最大流 一1 0 一 一v 一” z u 徊触3i；!j； t ，( z ) 故z 不是最大流口 定理2 3 3 ：一个可行流为最大流的充要条件的是不存在增广路 证明：必要性可以由前面的定理直接得到下面证明充分性 假设流网络n = ( 5 ，t ，va ，u ) 中不存在关于可行流z 的增广路，记网络中从5 出 发沿增广弧可以到达的节点集合为s ，令t = v s ，j l l j s 墨t t ，即旧刀为s 一 培并且，对于a 中的任意弧0 j ) ，如果它是该5 一t 割的前向弧，则z 巧= ；如果 它是该5 一培 i 的反向弧，则z 西= 0 于是利用前面定理2 3 1 证明中的中间结果有 t ，( z )= ( 一) i a a j t = i e $ j t = u ( s t ) 因此，慨卅为最小割，z 为最大流，定理证毕口 在上面的基础上，不难证明下面定理 定理2 3 4 ： ( 最大流最小割定理) 最大流的流值等于最小割的容量 我们假设网络中没有反向弧，即都是从供应点流向客户的弧且对网络中的每 个弧，根据实际的路况，如交通情况，最大承受力等对每条弧都做了标号，假设标 号越小，则路况越好，即会在同等条件下走这条路，由此求解本文所提出的最大流 的问题我们用改进的f o r d - m i k e r s o n 标号算法来求解 利用f o r d - f u l k e r s o n 标号算法的基本思想对所有的节点j 标号，其标号包括两 部分信息( 佗e z t 0 ) ，竹i 凹，g ) ) ：该节点在可能的增广路中的下一个节点n e = t ( j ) ，以 及沿该节点可能的增广路到该节点为止可以增广的最大流m 凹，0 ) 算法： s t e p 0 比较从节点i ，i = 1 ，p 出发的所有可增广弧的标号，选标号最小的 弧的终点，即为( 他晚( i ) ，m a x f ( i ) ) s t e p l 从节点n e z t ( i ) 出发，寻找节点几e 科( ) 的下一个节点的编号 s t e p 2 若重复s t e p l 能找到从某个供应点到客户的可增广路，则进行增广， s t e p 3 重复进行前面的三步，直到网络中不再存在可增广的路，则停止 一1 1 网络最大流及回收中心选址问题研究 2 4数值例子 如图l 所示，令p = 3 ，q = 2 弧旁边的数( 勺，u i ，) 分别表示弧( i ，歹) 的标号和 弧的容量上界以及弧上的流量 图1 利用本文中改进的增广路算法对本例题进行增广，所选的第一条增广路为1 4 5 8 _ 9 。1 0 ，增广量m i n r n a x f ( j ) = 2 ，其中歹= 1 ，4 ，5 ，8 ，9 ，1 0 增广后的 图如图2 所示一直利用上面所提到的算法进行增广，一直到网络中不存在增广路， 3 则停止最后的增广t m a x b i = 1 9 如图3 所示 i = l 2 5结论 本章，我们对已有的模型进行了改进，使得最大流的模型得以更广泛的应用 特别是在城市的交通运输，物流公司物资的配送公司仓库的选址以及预测安全库 存量方面有较好的效果 一1 2 一 硕士学位论文 图2 图3 1 3 网络最大流及回收中心选址问题研究 第3 章逆向物流中的选址问题研究进展 3 1再制造情况下的回收模式 随着各国人们环保意识的增强以及出台的谁生产谁负责回收处理的法规，以 现代环境管理原则实现产品系统环境性能的改善的一种主要制度是传统的污染者 付费原则的深化和延伸，它要求生产者不仅要对生产过程中产生的环境污染负责， 而且要对产品在整个生命周期内的环境影响负责，即企业必须对其生产的产品的 整个生命周期( 包括生产过程和生命结束阶段) 负责，尤其是必须对其因销售而产 生的终极产品进行回收，再循环，再利用和废弃处理，从而实现资源的循环利用和 环境保护的目的因此，在这样的背景下。大量的终极产品不再流入小商小贩和维 修站，而是由企业选择采取合理的方式进行回收处理，由此逆向物流回收，可以分 为企业直接参与和间接参与两种方式所谓直接参与即由企业自己直接负责终极 产品的回收处理工作；而间接参与是指企业可通过一定的契约或转让价将终极产 品的回收处理工作转让给联合团体或其他第二方物流公司负责因此，根据参与逆 向物流回收主体的不同可分为：企业自营回收方式，企业联合体回收方式和第二方 回收方式 参与逆向供应链的基本实体主要有用户、回收商、回收中心、原制造商、原供 应商、原销售商和服务商产品在用户手中的使用情况不同，导致了逆向供应链中 逆向物流的三种走向：第一种是用户在购买商品后使用不满意，要求退货：第二种 是用户在使用商品的过程中出现故障，要求维修；第三种是用户在产品的生命周期 内使用了产品主要的客户价值，产品中还有一定的价值残留产品回收是先将这三 种初始的逆向物流汇聚在一起，然后将其中包含的实物价值和信息价值提炼出来， 经过细分后传递给逆向供应链上的不同成员产品回收是逆向供应链的物流载体， 有了回收的产品后逆向供应链的运作才真正启动起来，产品回收和将回收产品中 的实物价值和信息价值传递到逆向供应链的目标成员构成逆向供应链的主体 产品回收不但回收了产品外显的再循环价值，也回收了产品内潜在的市场信 息和客户信息客户端作为供应链和逆向供应链衔接点，起到了承上启下的作用， 通过客户端的衔接，才使正向供应链和逆向供应链啮合为循环流程的可持续发展 供应链因此，产品回收管理是从用户手中收回用户不能使用或不愿继续使用的产 品，并对回收产品分类检测，分析处理后对其实施基于现代信息技术的回收产品数 据信息管理和基于现代管理理念的回收产品客户关系管理 逆向物流的联合体经营方式是指生产相同产品或者相似产品的同行业企业进 行合作，以合资等形式建立共同的逆向物流系统( 包括回收网络和处理系统) ，为各 合作企业甚至包括非合作企业提供逆向物流服务 一1 4 一 硕士学位论文 逆向物流的自营方式就是指生产企业建立独立的逆向物流体系，自己管理退 货和废旧物品的回收处理业务在逆向物流自营方式下，企业不但重视产品的生产 销售和售后服务( 包括退货的管理) ，还重视产品在消费之后的废旧物品以及包装 材料的回收和处理企业建立了遍及所有本企业产品销售区域的逆向物流网络，以 便回收各种回流物品，并将其送到企业的回流物品处理中心进行集中处理在政府 管制的条件下，生产企业建立自己的逆向物流系统，这是外部社会成本的内部化， 是生产者责任延伸制度的主要形式 逆向物流的外包方式是生产企业通过协议形式将其回流产品的回收处理中的 部分或者全部业务，以支付费用等方式，交由专门从事逆向物流服务的企业负责实 施 随着政府对企业回收责任限制的加大，企业逆向物流中的各功能模块可能由 一个或多个企业来承担，可以采取的形式也是多种多样的，根据美国逆向物流委员 会对3 0 0 多家物流企业的逆向物流活动模式选择的调查结果显示，不同企业会根据 逆向物流活动的不同而选择不同的模式逆向物流和传统的正向物流相比，在运作 和机理上具有其特殊性，不同的模式对企业逆向物流系统的不同方面存在不同的 影响 ( 1 ) 在联营回收模式下，以由生产商联合体来负责完成相应的回收处理同时， 生产商联合体回收的是同类产品，产品具有相似性，只需建立少量的回收处理中 心，减少产品回收的中间环节，节约回收成本但是，亦不可避免地具有缺陷尽管 负责回收的是同类产品，但是同类产品依然在一定程度上具有各自产品的专业机 密信息，而联营回收模式很难获得这些信息，增加回收拆卸难度，同时产品被回收 之后，不可能进入闭环再循环，而只能进行其它产品的再利用和再制造工作 ( 2 ) 自营回收模式下，由于是由企业本身回收自己生产销售的产品，企业能根 据市场销售渠道掌握产品的流向，具有快速信息反馈的能力，使其回收工作运作高 效同时，企业熟知回收产品的设计流程，能进行准确的拆卸，节省了拆卸时间，提 高了经济效益再者，企业对回收的产品具有独占性，拆卸下来的零部件和材料在 经过适当的处理之后即可进行生产再利用，实现了资源的闭环再循环当然，任何 事物都具有其两面性在企业自营回收模式下，生产商只对自己销售产生的产品进 行回收，其专业化程度较高，回收产品有限，从而对于整个地区来说，不同的