《物流业中网络最大流方法的应用资料》由会员分享，可在线阅读，更多相关《物流业中网络最大流方法的应用资料（16页珍藏版）》请在金锄头文库上搜索。
1、目录1引言 22物流学的概念 23网络最大流的概念及其意义 24物流学与最大流的联系 25网络最大流 35.1 运输网络与最大流 35.2 割和流量 45.3 最大流最小割 55.4 求网络最大流的标号算法 65.5 最小费用最大流 86最短路问题 116.1 Dijkstra 算法 117结论 148参考文献 169致谢辞 错误！未定义书签。1引言物流配送的流量问题是物流系统中一个重要的环节，是物流节点送达收货人的过 程。满足货运要求的前提下，如何选择配送线路中流量大小的问题是非常重要的，运用 网络最大流方法的目的在于保证运输安全的前提下，使配送线路和运输时间最优。货物配送的重点就是如何让运
2、输的每一条路线的流量达到最大，如何将车辆进行有效利用，使得在配送时间和距离都相对最优的情况下配送到客户手中，从而达到最大的利润。由于规定了起始点位置，力求多装快跑，节约时间和费用，提高效率，最经济就是两点 间最大流量。采用运筹学中的网络最大流和最短路方法统筹考虑配送路线和配送时间， 寻求最经济运行线路是非常必要的。本文通过运用网络最大流的 Ford-Fulkerson标号算法、最短路算法系统的解决物 流运输中运输线路的选择问题，从而使运输的成本达到最小。2物流学的概念物流(Physical Distribution) 一词源于国外，最早出现于美国，在 1915年阿奇？ 萧在市场流通中的若干问题
3、一书中提到物流一词，并指出“物流是创造需求不同的 一个问题”，然而正式发展物流，则是在二战中，围绕物资供应，是二战期间军队在运 输战略物资、军队给养时使用的名词，物流在二战期间发挥了重大的作用.后来，将这 种体系移植到现代经济生活中，才逐步演变为今天的物流.到目前为止，物流也没有一个权威性的定义，以下是几个比较常见的： 物流是一个控制原材料、制成品、产成品和信息的系统.物流是指物质是实体的供应者向需求者的物理移动，它由一系列创造时间价值和空间价值的经济活动组成，包括运输、保管、配送、包装、装卸、流通加工及物流信息处理 等多项基本活动，是这些活动的统一.但是，物流的定义至今还有争论，不过这也恰恰
4、反应了不同时期物流理论，物流管 理及物流技术的进步.3网络最大流的概念及其意义最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从 A到 B ,如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。如n辆卡车要运送物品，从A地到B地。由于每条路段都有不同的路费要缴纳，每条路能容纳的 车的数量有限制，最小费用最大流问题指如何分配卡车的出发路径可以达到费用最低， 物品又能全部送到。在运输网络中，每条边或弧的权都是代表相应的两点之间运输里程和单位运价，对 运输路线的运输能力没加限制。但是，在实际问题
5、中，运输问题的运输能力总是有限的， 当一个运输网络的每天线路的运输限额给定时，整个运输网络的运输额就改变了，这就 是我们要解决的问题，利用网络最大流问题解决容量网络配送运输问题。4物流学与最大流的联系运筹学是在世界二次大战期间形成并迅速发展起来的学科，是当今社会现代化科学管理必不可少的工具之一。世界经济的快速发展极大地促进了物流业的发展，使其迅速成为具有巨大潜力及发展空间的新兴服务产业。物流业在各个领域的作用日益突出，也 从以仓储、运输管理为主的传统物流阶段发展到了以仓储、运输、配送、装卸搬运、包 装、流通加工、信息处理等功能为一体的现代物流阶段。把运筹学理论与方法应用到现 代物流管理中，便形
6、成了物流运筹学。物流运筹学通过定量的方法对物流运作过程中产 生的问题进行研究，对于有效地利用各种物流资源，提高物流系统的工作效率，具有重 大的意义。在物流中，运输、配送等问题是物流成本构成的主要要素之一.因此，确定运输过 程中的流量问题，是物流中应该考虑的问题。物流与网络流问题是相互渗透，相互发展，而且从方法上来说，最大问题是用来解 决最优资源配置，而物流系统的主要功能（目标）也正是追求一种快速、及时、节约、 库存合理的物流服务。网络最大流在物流中起着极其重要的作用，在本文中我们就学习 一下两门学科的相互应用。5网络最大流5.1 运输网络与最大流如果给定一个有向网络，则有一个问题，即如何指定两
7、点间的最大流量.下面在本 节中我们将介绍网络中的最大流问题.所谓最大流就是在给定容量网络的所有可行流 中，总流量最大的可行流，常称为该容量网络的最大可行流。寻找最大流的问题就称为 最大流问题。一般地，设有向连通图 G V,E , G为每条弧Vi,Vj ,若对应的给与一个非负数G,j,称为弧的容量；G恰有一个入度为零的顶点Vs,称为发点（或源），恰有一个出度为零的顶点vt,称为收点（或汇）；其余顶点都称为中间顶点。这样的有向图 G称为一个容量网络，常记为G V,E,C,其中C G,j是弧集E上的一个非负函数，成为容 量函数。对于容量网络G V,E,C中的每一条弧w,Vj ,若对应的给与一个非负数
8、称为弧Vi,Vj的流量，记为fi,jf vi ,vj ,满足下列条件：（1）容量限制条件，即：对每一条弧 Vi,Vj ,均成立0 fi,j Ci,j,即弧的流量不超过该弧的容量；（2）平衡条件，即，对每一个中间顶点Vi均成立，fk,i即输入Vi的物资总数kj等于输出Vi的物资总数；对于发点Vs和收点Vt ,则成立；fs,ji ,t ,即从发点Vs输ji出的物资总数数量等于输入收点Vt的物资数总量，则称定义在E上的非负数f fi,j是容量网络G上的一个可行流，并称fs，ji，t W为可行流f的总流量，记为jiW f Wo对于任意一个容量网络G V,E,C来说，可行流总是存在的。例如， E中的每条
9、弧Vi,Vj均规定流量为零，则f 。就是一个可行流，其总量 W 0,这个可行流称之为零流。对于任意一个容量网络 G V,E,C ,寻找可行流是十分容易的。5.2 割和流量所谓割是指将容量网络中的发点和分点分割开。并使 s t的流量中断的一组弧的 集合。如图1, KK将网上的点分割成 V和V两个集合，并有s V,t V ,称弧的集合V,VV1,V3 , V2,V4是一个割，割的容量是组成它的集合中的各弧的容量之和，用cV,V表示，由此cV,V ij vcvi,vj，注意在组成上述割的弧集合中不包含V3，V2 ，因为即使这条弧不割断的话，从s t的流仍然中断。图1考虑KK的不同画法，可以找到网络中
10、全部不同的割，看下表:表1VV割割的容量sv1,v2,v3,v4,ts,1s,215s,v1v2,v3,v4,ts,2 1,21,321s,v2v1,v3,v4,ts,12,417s,v1，v2v3, v4,t1,32,418s,v1，v3s,v2,v4v2,v4,t v1,v3,ts,21,23,2 3,ts,14,34,t192414s,v1，v2,v3v4,t2,43,t25s,v1，v2,v4v3,t1,34,34,t15s,v1，v2,v3,v3t3,t 4,t若用f V,V表示通过割V,V中所有V V方向弧的流量的总和，f V,V表示割中所有VV方向的弧的流量的总和，则有f V,V
11、fVi,Vj(i,j) (V,V) f V,VfVj,Vi(j,i) (V,V)从s t的流量实际上等于通过割从V到V的流量减去V V的流量。故有v(f) f(V,V) f(V ,V)若用v (f)代表网络中从s t的最大流，则有， * * * v (f) f (V,V) f (V,V)根据割的概念，v (f)应小于等于网络中最小一个割的容量，即有* * - * *!-v (f) f (V,V) f (V,V) c (V,V)因此，由表1得出网络图1中从s t的最大流量不超过14单位。5.3 最大流最小割如果在网络的发点和收点之间找出一条链，在这条链上所有指向为s t的弧(称前向弧，记作 )，
12、存在f c；所有指向t s的弧(成后向弧，记作)，存在f 0, 这样的链称为增广链，如图2所示当有增广链时，找出minfi ,对所有的再令ffi,对所有的fi,对非增光链上的弧显然f仍是一个可行流，但较之原来的可行流 f ,这是网络中从s t的流量增大 了一个 伯：( 0)。因此只有当网络中找不到增广链时，s t的流才不可能进一步增 大。5.4 求网络最大流的标号算法最大流算法是在1956年由Ford和Fulkerson提出的，故又称Ford-ulkerson 标号 算法，其实质是判断是否有增广链存在，并算出来。第一步：首先给发点s标号(Q (s),括弧中第一个数字是使这个点得到标号的前一个点
13、的代号，因s是发点，故记为。括弧中的第二个数字 s表示从上一标号点到这个标号点的流量的最大允许调整值，s为发点，不限允许调整值量，故 s ;第二步：列出与已标号点相邻的所有未标号点：(1)考虑从标号点i出发的弧i,j ,如果有fij 5 ,不给点j标号；若有fij Cj ,则对点j标号，记为i, (j),括弧中的i表示点j的标号是从点i延伸过来的，j min i , (cj fj);(2)考虑所有指向标好点i的弧h,i ,如果有fhi 0,对h点不标号；若有fhi 0,则对点h标号，记为i, h ,其中(h) min i ,力；如果某未标号点k有两个以上相邻的标号点，为减少迭代次数，可按(1)
14、, (2)中所述规则分别计算出k的值，并取其中最大的一个标记。第三步：重复第二步，可能现两种结局：(1)标号过程中断，t得不到标号，说明该网络中不存在增广链，给定的流量即为对大流。记已标号的网络为V,为标号点集合V, V,V为网络的最小割。t得到标号，这时可用反向追踪法在网络中找出一条从s t的由标号点即相应的弧连接而成的增广链。第四步：修改流量，设图中原有可行流为f,令f t,对增广链上所有的向前弧f f t,对增广链上所有的向后弧f,所有非增光脸上的弧这样有得到网络上的一个新的可行流f第五步：抹掉图上所有标号，重复第一到第四步，直到图中找不到任何增广链，即出现第三步的结局(1)为止，这时网
15、络图中的流量即为最大流。例1、用标号算法求图1中s t的最大流，并找出该网络的最小割。解：(1)先给发点s标号0,(2)从s点出发的弧S,V2,因为有fs2Cs2,故对V2点标号s,V2,其中V min s, Cs2fs22(3)对弧V1,V2 ,因f12 0,对V1标号V2, V1 ,其中VI min V2 , f12min 2,42(4)对弧V1,V3,因f13C13,故对V3标号V1,V3,其中v3min v1 , c13 f13 min 2,52(5)对弧V4,V3,因f430,故对V4标号V3,V4,其中v4 min v3 , f43min 2,11(6)对弧V4,t,因f4tC4t,故对t点得到标号V4, t ,其中t min v4 , c4t f4tmin 1,21(7)因收点t得到标号，可用反向追踪法找出网络图上的一条增广链，如图3中虚线所示。fl2fl2t413f 13f13t 415f43f43t110f4t
