配送管理课件：第三章 配送方案的优化

1、第三章 配送方案的优化,第一节 配送优化,1、 配送优化定义： 按照货物的特点合理流向以及运输条件，走最少的里程，经最少的环节，用最少的运力，花最少的费用，以最短的时间，把货物运到目的地。,2、优化配送的意义 （1）有利于物资产品迅速地从生产地向消费地转移， 加速资金的周转，提高企业资金的使用效率。 （2）缩短运输时间，加快物流速度。 （3）节约运输费用，降低物流成本。 （4）节约运力，缓解运力紧张的状况，节约能源。,3、不合理配送的概念 在组织货物运输过程中，违反货物流通规律，不按照经济区域和货物自然流向组织货物调运，在各运输方式间或在同一运输方式线路上，发生相同或可替代产品的对流，或相向运

2、输、重复运输以及过远运输、迂回运输等违反各种运输合理分工原则，而造成不必要的货物周转或装卸工作量，浪费运力，增加运输费用的运输。,4、不合理运输的表现,（1）返程或起程空驶。因调运不当、货源计划不周而形成的空驶是不合理运输最严重的表现形式。 造成空驶的原因有： 能利用社会化的运输体系不利用，却依靠自备车 送货，则往往出现单程实车、单程空驶现象。 由于工作失误或计划不周，造成货源不实，车辆 空去空回。 由于车辆过于专用，无法搭运回程货物，只能单 程实车，单程空驶。,（2）对流运输。 对流运输指的是同种货物以不同的发送点同时或先后作面对面的运输，并且彼此重复对方旅程的全部或一部分。,10,30,1

3、0,10,B1,A1,A2,B2,30,40,30,(10),(10),调整前有对流的配送,调整后无对流的配送,（3）迂回运输。 在货物发点与收点之间有两条以上的同类交通线可以采用时，未能利用最短路径的运输。,5,5,6km,4km,5吨,迂回运输,无迂回运输,重要原则：环状线路上，收点与发点的货物行走公路数，不应超过整个环状路线长度的一半。,（4）过远运输。 调运物资舍近求远的现象。 （5）运力选择不当。 即运输工具没有正确的利用所造成的不合理现象。,弃水走陆。 铁路、大型船舶的过近运输。 运输工具承载能力选择不当。出现大马拉小车，小驴拉大车。,（6）托运方式不当。 本应采用直运而采用了转运

4、。,5、合理配送的途径,（1）、减少运输次数，缩短运输距离。 如在煤炭基地建发电厂，在林业基地建木材加工厂。 （如福建泰宁） 企业往往其厂址选择有以下几种类型： 靠近原料供应 靠近市场 动力指向型 廉价劳动力指向型 技术指向型,（2）提高运输工具的实载率。 充分利用专业运输队伍。 充分获取和利用相关信息，如货源信息、道路交通状 况、天气预报、同行业运输状况信息等。 采取盒装整车运输方式。即零担拼整车中转运输，主要用于杂货运输。,5、优化配送的途径,（3）周密进行运输系统设计 运输与原料采购的配合、运输与产品销售的配合、运输与仓库的合理设计、运输网络的合理布局。,（4）科学选择运输方式，避免动力

5、闲置浪费。 铁路、水路的经济运输里程在200-300km以上，适合“重、厚、长、大”的货物。 公路的经济运输里程在300km以下，适合“轻、薄、短、小”货物,（5）、采用四就直拨运输 这种方式是指物流经理在组织货物调运的过程中，以当地盛产或外地到达的货物不运进批发站仓库，运用直拨的方法，把货物直接分拨给基层批发、零售中间环节。 该种方式可以减少一道中间环节，在时间和各方面起到双重的经济效益。,第二节 物流配送网络布局优化,1、配送网络布局的定义： 根据物资的供需情况，运输条件，自然状况等因素，来合理布置物流节点的位置、规模和供货范围。,2、配送网络布局的步骤,（1）找出物流配送网络规划的约束条

6、件。 （2）依据约束条件构造模型； （3）将模型转变成数学模型求出可行解； （4）依据一定判断标准对可行解进行排序，求出较于满意解。,例如:某企业打算在南昌或沈阳设立分公司（也许在两个城市都设立分公司）增加市场份额，同时计划在新设立分公司城市最多建一个配送中心，也可以不建配送中心，总的预算费用不得超过20万。求如何规划使的企业总净现值最大。,a,b,c,d,e,f,g,h,1,2,3,4,5,7,8,9,6,10,11,12,14,13,3、备选地址的选择原则,（1）用户满意原则 （2）有利于运输合理化 （3）费用最小原则 （4）动态性原则 （5）战略性原则,4、网点布局的常用方法,（1）解析

7、方法 （2）模拟方法 （3）启发式方法（迭代法）,5、一元网点布局问题,1 因素评分法。 步骤如下： 给出备选地点。 列出影响选址的各个因素。 给出各因素的分值范围。 由专家对各备选点就各因素评分。 将每一个地点因素的得分相加，求出总分后加以比较，得分最多的地点中选。,影响选址的每个因素及其分值范围,2 重心法 将配送系统的资源点和需求点看成是分布在某一平面范围的物体系统，各资源点与需求点的物流量可分别看成是物体的重量，物体系统的重心将作为配送中心的最佳位置。 如果（Xi,Yi)表示个点的坐标，Wi表示各点的运量，Ci表示各点的运输费率，则重心的坐标为： X0=（X1W1C1+ +XiWiCi

8、）/（W1C1+ +WiCi） Y0=（Y1W1C1+ +YiWiCi）/（W1C1+ +WiCi）,A,N,B,Q,例题1,假设某家电集团在P1地生产冰箱，在P2地生产洗衣机，在P3地生产空调，在P4地生产小家电，假设各生产地的运输费率相同，各工厂所在地与某城市中心的距离和每年产量如下。求配送中心的位置,例题2,假设配送中心有三家主要客户A、B、C，位置如下图，其中配送中心到A 的运输量为100单位，运费为10元/单位，到B 的运输量为200单位，运费为8元/单位，到C 的运输量为150单位，运费为10元/单位，求最佳的配送中心点。,A （5，20）,C（20，5）,P（X，Y）,B （25

9、，25）,(3)微分法 弥补重心法的不足，采取逐次迭代而形成满意结果。,6、多元网点布局问题,有m个资源点Ai（i=1,2，m），各点的资源量为ai；有n个需求点Bj（j=1,2，n），各点的需求量为bj；有q个可能设置网点的备选地址Dk（k=1,2，q）。需求点可以从设置的网点进货，也可以从资源点直接进货。,第三节 货物配装优化,最大化的利用运输工具的运输力。,1、货物配装时应该注意的问题,外观、形状易混淆的货物应该分开摆放 重不压轻； 后送先装； 有气味挥发和吸收的货物应分开装； 将易散发粉尘和清洁货物分开装； 渗水货物与易受潮货物分开装； 包装不同货物应分开装； 有锐角的货物应该加上外框

10、，以免碰撞受损； 圆状易滚动货物应放直； 货物之间，货物与车辆之间应加上衬垫； 注意货车开门处的货物稳固； 注意货车的重心平稳，及注意货车的装货高度；,危险品在运输中出现问题的处置方式,爆炸品：迅速转移至安全场所修理或更换包装，对漏洒的物品及时用水湿润，洒些锯屑或棉絮等松软物，轻轻收集。 压缩气体或易挥发液体：打开车门、库门，并移到通风场所。液氨漏气可浸入水中，其他剧毒气体应浸入石灰水中。 自燃品或遇水燃烧品：黄磷洒落后要迅速浸入水中，金属钠、钾等必须浸入盛有煤油或无水液体石蜡的铁桶中。 易燃品：将渗漏部位朝上。对漏洒物用干燥的黄沙、干土覆盖后清理。 毒害品：迅速用沙土掩盖，疏散人员，请卫生防

11、疫部门协助处理。 腐蚀品：用沙土覆盖，清扫后用清水冲洗干净。 放射品：迅速远离放射源，保护好现场，请卫生防疫部门指导处理。,2、配装方法与数学模型,（1）原始手工经验配载 即按照配装工人的日常经验实施配装。往往简要考虑车辆的容量与载重要求。,（一）、基本概念 1、阶段： 把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。 描述阶段的变量称为阶段变量。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。,（2）动态规划方法,阶段(stage)n:也就是作出决策的若干轮次。n = 1、2、3、4、5。,1阶段,2阶段,3阶段,4阶段,5阶段,

12、2、状态：表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述过程状态的变量称为状态变量， 记为Sn S1=A，S2=B1,B2,B3，S3=C1,C2,C3，S4=D1,D2,D3，S5=E1,E2。阶段的起点。,3、决策(decision)dn：从一个阶段某状态演变到下一个阶段某状 态的选择。 一阶段所有的决策构成决策集，记为Dn(Sn)。 阶段的终点。 D1(S1)=d1(A)=B1,B2,B3= S2， D2(S2)=d2(B1),d2(B2),d2(B3)=C1,C2;C1,C2,C3 ;C2,C3 =C1,C2,C3=S3， D3(S3)=d3(C1),d3(C

13、2),d3(C3)=D1,D2;D1,D2,D3; D1,D2,D3=D1,D2,D3=S4， D4(S4)=d4(D1),d4(D2),d4(D3)=E1,E2;E1,E2;E1,E2=E1,E2=S5， D5(S5)=d5(E1),d5(E2)=F;F=F。,4、策略(policy)：全过程中各个阶段的决策dn组成的有序总体 dn. 如 A B2 C1 D1 E2 F 上例从 A F 共有38种走法，即有38条路线，38个策略。,5、子策略(sub-policy) ：剩下的n个阶段构成n子过程，相应的决策系列叫n子策略。 如 C1 D1 E2 F,6、状态转移方程 当第K阶段处于状态sk时

14、，若选用决策dk,则下一阶段即第K+1阶段所处状态sk+1便唯一确定，此事记之为： sk+1 = dk （sk）/ uk （sk）,7、指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为指标函数。指标函数的最优值，称为最优值函数。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。 动态规划模型的指标函数，应具有可分离性，并满足递推关系。,最优值函数 Z=optv1(s1,u1)* * vn(sn,un)。 其中：opt为max或min，*为运算符号。,指标函数,1、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要

15、做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。,（二）、动态规划的基本思想,例题： 设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。,解：依据题意，是要求 f4(60) 。,按顺序解法计算。 第一阶段：求 f1(x)。显然有 f1(x) g1(x)，得到下表,第二阶段：求

16、f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。,最优策略为（40，20），此时最大利润为120万元。,同理可求得其它 f2(x) 的值。,最优策略为（30，20），此时最大利润为105万元。,最优策略为（20，20），此时最大利润为90万元。,最优策略为（20，10），此时最大利润为70万元。,最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为20万元。,f2(0) 0。最优策略为（0，0），最大利润为0万元。 得到下表,最优策略为（20，0），此时最大利润为50万元。,第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得

17、最大的总利润。,最优策略为（20，10，30），最大利润为155万元。,F3(60),第四阶段：求 f4(60)。即问题的最优策略。,最优策略为（20，0，30，10），最大利润为160万元。,练习：某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。,x1=2，x2=1，x3=1，f3(4)=47,有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大

18、？,（三）（背包问题）（用于解决车辆运输过程中容量有限的问题）,设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下：,用动态规划方法求解，按可装入物品的n种类型划分n个阶段，令 fk(y) = 总重量不超过 y 公斤，包中只装有前k 种物品 时的最大使用价值。 其中y 0， k 1,2, , n 。所以问题就是求 fn(a),1,其递推关系式为：,当 k=1 时，有：,例题：求下面背包问题的最优解,解：a5 ，问题是求 f3(5),所以，最优解为 X（1 , 1, 0），最优值为 Z = 13。,练习1：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售

19、，运输能力总重量不超过 6 吨，问如何安排运输，使总利润最大？,最优方案：X1 =（0.2.0）X2 =（1.0.1）Z=260,练习2：求下列问题的最优解,X=(2. 1. 0) 最优值为 Z = 13,四、集装箱问题,d0 :集装箱宽 h0：集装箱长 li:货箱长度 hi:货箱高度,例：某运输问题的资料如下：,第四节 物资调度优化,数学模型的一般形式 已知资料如下：,当产销平衡时，其模型如下：,当产大于销时，其模型是：,当产小于销时，其模型是：,.重复. ，直到找到最优解为止。,步骤：,.找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法、伏格尔法；,.求出

20、各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；,.改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；,表上作业法,例一、某运输资料如下表所示：,1、求初始方案：,.西北角法（或左上角法）： 此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作。 如图：,总的运输费用 （33）（411）（29）（22）（310）（65）135元,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,.最小元素法： 基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,总的运输费用 （31）（64）（

21、43）（12）（310）（35） 86元,3,11,3,10,1,9,2,7,4,10,5,8,（3）伏格尔法： 一产地的产品假如不能按最小运费就近供应，就应考虑次小运费;这就有一个差额,差额越大，说明不能按最小运费调运时，运费增加越多。因此 ，差额越大，越要按最小运费调运。,行差额,列差额,1 2 3 4 5,1 2 3 4 5,0 0 0 7,1 1 1 6,1 2,2,5,1,3,6,2 1 3,3,2 1 2,3,1 2,5,2,1,总的运输费用（31）（64） （53）（18）（210） （35） 85元,最优解判断法则ij0 （因为目标函数要求最小化） 表格中有调运量的地方为基变量

22、，空格处为非基变量。基变量的检验数ij0，非基变量的检验数 ij0。,ij 0 表示运费增加。,2、最优解的判别（检验数的求法）： .闭合回路法：,3,1,3,4,6,3,（1）,（1）,（1）,（1）,计算如下：空格处（ A1 B1 ） (13) (1)3 (12) (1)1 1 此数即为该空格处的检验数。,1,3,1,3,6,3,1,2,4,11,3,10,4,5,计算如下：空格处（ A1 B2） (111) (1)10 (15) (1)4 2 此数即为该空格处的检验数。,（+1）,（-1）,（-1）,（+1）,3,1,3,6,3,1,2,-1,4,3,10,2,8,计算如下：空格处（ A

23、2B4） (18) (1)10(13) (1)2 -1 此数即为该空格处的检验数。,3,1,3,6,3,1,2,1,-1,4,4,5,10,3,2,计算如下：空格处（ A2 B2） (19) (1)4(15) (1)10 (13) (1)2 1 此数即为该空格处的检验数。,9,3,1,3,6,3,1,2,1,-1,12,4,3,10,5,计算如下：空格处（ A3B3） (110) (1)5(110) (1)3 12 此数即为该空格处的检验数。,10,3,1,3,6,3,1,2,1,-1,12,10,4,7,1,2,3,10,5,计算如下：空格处（ A3B1） (17) (1)1(12) (1)

24、3 (110) (1)5 10 此数即为该空格处的检验数。,0,0,0,0,0,1,2,1,-1,12,10,0,检验数中有负数，说明原方案不是最优解。,运输问题的约束条件共有m+n个，其中：m是产地产量的限制；n是销地销量的限制。 由单纯形法可知，基变量的ij 0 cij(ui+vj) 0 因此ui ,vj可以求出。,.位势法,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,原运输图,接上例：,成本表,u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令： u10,u10 v12 u2 1 v2 9 u

25、3 5 v3 3 v4 10,(ui+vj),按ij=cij(ui+vj) 计算检验数，并以ij0 检验，或用(ui+vj) cij 0 检验。,cij,(ui+vj),表中还有负数，说明还未得到最优解，应继续调整。,ij,闭合回路调整法,接上例：,3,1,3,4,6,3,3、解改进的方法,-1,改进后的运输方案,经检验,所有ij0,得到最优解，最小运费 =(35)( 210)(13)( 81) (46) (53) =85,0,ui,vj,Cij,所有ij0,得到最优解，最小运费 =(23)( 53)(11)( 38) (64) (35) =85,(+2),(-2),(-2),(+2),另一运

26、输方案,.无穷多最优解：产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。如上例：（1.1）中的检验数是 0，经过调整，可得到另一个最优解。,.退化：表格中一般要有(m+n-1)个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格。一般可在划去的行和列的任意空格处加一个 0 即可。,4、表上作业法计算中的问题,例1：,2 1 3 5 5 2 6 8 2 1 7 6,例2：,0,0,0,1、产大于销：模型,方法是先将原问题变成平衡问题，需假设一个销地(Bn+1 )(实际上考虑产地的存量)，,三、产销不平衡的运输问题及

27、其求解方法,模型为：,2、销大于产：同样假设一个产地即可，变化同上。,单位运价表中的单位运价为,40,30,30,20,30,20,20,用最小元素法求初始方案,例题：,（产大于销的情况）,已知某运输问题的资料如下表所示,1、表中的发量、收量单位为：吨，运价单位为：元/吨 试求出最优运输方案.,练习：,2、如将A2的发量改为17，其它资料不变，试求最优调 运方案。,解：1、用最小元素法求初始方案,最小运费 =(125)( 33)(101) (21) (132) =107,2、用位势法判断：,成本表,u1+v3=5 u2+v4 =1 u1+v4 =3 u3+v2=2 u2+v1=1 u3+v4

28、=4 令： u10,u10 v13 u22 v2 1 u3 1 v3 5 v4 3,(ui+vj),cij,表中还有负数，说明没有得到最优解，调整运输方案。,ij,(ui+vj),2,2,2,2,新的运送方案,新的成本表,(ui+vj)1,总的运费 105元/吨,表中还有负数，说明没有得到最优解，继续调整运输方案。,cij,(ui+vj)1,(ij)1,cij,(ui+vj)2,(ij)2,表中没有负数，说明已经得到最优解。但有无穷多最优解。,0,总的运输费用（102）（53）（122）（132） 85元,（第2小题）,成本表,u1+v3=5 u2+v3 =2 u1+v5 =0 u2+v4 =

29、1 u2+v1=1 u3+v2=2 u3+v4=4 令： u10,u10 v14 u2-3 v2 2 u3 0 v3 5 v4 4 v50,(ui+vj),cij,ij,成本表,u1+v1=2 u2+v4 =1 u1+v3 =5 u3+v2 =2 u1+v5=0 u3+v4=4 u2+v3=2 令： u10,u10 v12 u2-3 v2 2 u3 0 v3 5 v4 4 v50,(ui+vj),cij,ij,C =75,已知资料如下表所示，问如何供电能使总的输电费用为最小？,电力供需表,单位输电费用,作业：,初始方案,100,100,50,250,400,100,单位输电费用,电力供需表,i

30、j,成本表,- (ui+vj),=,cij,(ui+vj),cij,成本表,(ui+vj),调运方案,ij,- (ui+vj),=,cij,成本表,调运方案,(ui+vj),ij,- (ui+vj),=,cij,C=5200,试用表上作业法求最优解,最小总费用为945。,第五节 线路优化,1、一对一的运输 2、一对多的运输 3、多对多的运输,1、一对一的运输,一个供货点对另一个点运输送货 常常描述为物品由一个点经过若干个阶段且每个阶段都有若干个点后到达另一终点的运输。,（1）有序经过若干个阶段（各阶段点不相连情况） （2）不好划分阶段情况。,例如、从A 地到D 地要铺设一条煤气管道,其中需经过

31、两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,（1）有序经过若干阶段的情况,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,从最终状态开始,自右至左,逆着决策次序进行计算(故名逆推法),每次在已知某阶段初所处状态的条件下,推算应选取什么决策，阶段末应处于什么状态,使从所处状态出发到最终状态的各决策构成该所处状态的最优（后部）子策略。算完后再从初始状态到最终状态顺序找最优策略。,逆推法：,解：整个计算过程分三个阶段，从最后一个阶段开始。,

32、第三阶段（C D）： C 有三条路线到终点D 。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,显然有 f0(D ) =0 ; f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4,第一阶段,第二阶段,第三阶段,d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5,第二阶段（B C）： B 到C 有六条路线。,A,B1,B2,C1,

33、C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,(最短路线为B1C1 D),d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,(最短路线为B2C1 D),第一阶段（ A B ）： A 到B 有二条路线。,f3(A)1 = d(A, B1 ) f2 ( B1

34、 ) 246 f3 (A)2 = d(A, B2 ) f2 ( B2 ) 437, f3 (A) = min = min6,7=6,d(A, B1 ) f2 ( B1 ) d(A, B2 ) f2 ( B2 ),(最短路线为AB1C1 D),A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,A,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,A,最短路线为 AB1C1 D 路长为 6,练习：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,

35、E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,最优路线为：A B1 C2 D1 E2 F2 G 路长18,用逆推法求从A到G的最短路径,3,第一阶段,第二阶段,第三阶段,第四阶段,第五阶段,第六阶段,k=5，出发点E1、E2、E3,4,k=2, f2(B1)=13 d2(B1)=C2 B1 C2 D1 E2 F2 G f2(B2)=16 d2(B2)=C3 B2 C3 D1 E2 F2 G,7 5 9,d5(E2)=F2,d6(F2)=G,最优策略,A,B1,B2,C1,C2,C3,C4,D1,D2,D

36、3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,一般提法为：设 为连通图，图中各边 有权 （ 表示 之间没有边）， 为图中任意两点，求一条路 ，使它为从 到 的所有路中总权最短。即： 最小。,(一)、 狄克斯屈拉(Dijkstra)算法 适用于wij0，给出了从vs到任意一个点vj的最短路。,（2） 、无序经过若干各点的情况,算法步骤： 1.给始点vs以P标号 ，这表示从vs到 vs的最短距离为0，其余节点均给T标号， 。 2.设节点 vi 为刚得到P标号的点，考虑点vj，其中 ，且v

37、j为T标号。对vj的T标号进行如下修改： 3.比较所有具有T标号的节点，把最小者改为P标号，即： 当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。,例如、 用Dijkstra算法求下图从v1到v6的最短路。,解 （1）首先给v1以P标号，给其余所有点T标号。,（2）,（3）,（5）,（4）,（6）,（7）,5，,5,（8）,（9）,（10）,反向追踪得v1到v6的最短路为：,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从1到8的最短路径,2,3,7,1,8,4,5,6,6,1,3,4

38、,10,5,2,7,5,9,3,4,6,8,2,X=1, w1=0,min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1 X=1,4, p4=1,p4=1,p1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 X=1,2,4, p2=2,p1=0,p4=1,p2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min c16

39、,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 X=1,2,4,6, p6=3,p2=2,p4=1,p1=0,p6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 X=1,2,4,6,7, p7=3,p2=2,p4=1,p1=0,p6=3,p7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min

40、c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 X=1,2,4,5,6,7, p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 X=1,2,3,4,5,6,7, p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,2,3,7,1,8,4,5,6,6,1,3,4,10

41、,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min c38,c58,c78=min 8+6,6+4,3+8=min 14,10,11=10 X=1,2,3,4,5,6,7,8, p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到8的最短路径为1，4，7，5，8，长度为10。,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,求从V1 到 V8 的最短路线。,v1 v

42、2 v5 v6 v8,练习：计算出V1到V8的最短路,（二）、 逐次逼近法(Floyd算法） 算法的基本思路与步骤： 首先设任一点vi到任一点vj都有一条弧。 显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设d1j表示从v1到vj的最短路长，d1i表示从v1到vi的最短路长，则有下列方程： 开始时，令 即用v1到vj的直接距离做初始解。 从第二步起，使用递推公式： 求 ，当进行到第t步，若出现 则停止计算， 即为v1到各点的最短路长。,v1,v4,v3,v2,v8,v7,v6,v5,v1,v4

43、,v3,v2,v8,v7,v6,v5,0 ,1,3 ,1,-2 ,1,-1 ,1,6,0,2,-5,0,-3,1,0,2,0,7,1,0,-1,0,0,-5,-1,1,-3,t=1,t=2,t=3,t=4,0,3,-2,-1,0 ,1,-5 ,3,-2 ,1,-7 ,3,1 ,2,-1 ,3,5 ,4,0 ,1,-5 ,3,-2 ,1,-7 ,3,-3 ,2,-1 ,3,-5 ,4,6 ,6,0 ,1,-5 ,3,-2 ,1,-7 ,3,-3 ,2,-1 ,3,-5 ,4,6 ,6,表中红线以左第 i 行第 j 列数据表示点Vi 到点Vj 的弧的权（“长度”）。红线以右第t=j 列第 i 行数

44、据表示V1 到 Vi 至多经过t=j条弧的最短路的长度。,紧前点的编号,用 p(t-1)(v1, vj)表示 v1 到 vj至多经过 t-1 条弧的最短路 的长度，则v1 到 vj至多经过 t 条弧的最短路的长度为： p ( t) (v1, vj )=M i n p ( t -1) (v1, v i)+p i j, ,i,w i j,v8,0 ,1,3 ,1,-2 ,1,-1 ,1,6,0,2,-5,0,-3,1,0,2,0,7,1,0,-1,0,0,-5,-1,1,-3,t=1,t=2,t=3,t=4,0,3,-2,-1,0 ,1,-5 ,3,-2 ,1,-7 ,3,1 ,2,-1 ,3,5

45、 ,4,0 ,1,-5 ,3,-2 ,1,-7 ,3,-3 ,2,-1 ,3,-5 ,4,6 ,6,0 ,1,-5 ,3,-2 ,1,-7 ,3,-3 ,2,-1 ,3,-5 ,4,6 ,6,紧前点的编号,t=1 那一列红色数据表示V1至多经过1条弧到达各点（同行最左边所给的点）的最短路的长度，实为左边第一行的数据。 t=2 那一列红色数据表示V1至多经过2条弧到达各点（同行最左边所给的点）的最短路的长度。该列第 i 个（第 i 行的那一个）数据等于： 紧左边那一列（第 t=1列）的各数与左边第 i 列 (V i 那一列）对应各数和的最小者。 t=3， t=4，.,各列数据之计算同此。当算得两

46、列数据全同时，计算停止。设图的顶点数为P，若图中无负回路，则至多计算P列数据就可以终止。,p( t) (v1, vj )=M i n p ( t -1) (v1, v i)+w i j ,w i j,v1,v4,v3,v2,v8,v7,v6,v5,v1,v4,v3,v2,v8,v7,v6,v5,紧前点的编号,w i j,v1,v2,v3,v4,v5,v6,v7,6,-1,-1,-1,-3,-3,-5,-5,3,8,2,1,1,1,7,-2,2,v8,本点 紧前点 路长,1 1 0,2 3 -5,3 1 -2,4 3 -7,5 2 -3,6 3 -1,7 4 -5,8 6 6,（3）、 各个点之

47、间有运输流量控制情况 （即求最大流问题） 1述为：设一个赋权有向图D=（V, E）,在V中指定一个发点vs和一个收点vt ,其它的点叫做中间点。对于D中的每一个弧（vi , vj）E ,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做 D=（V，E，C）。 其中f(vi ,vj) =fij 叫做弧(vi，vj)上的流量。,2、称满足下列条件的流为可行流： （1）容量条件：对于每一个弧（vi ,vj）E 有 0 fij cij 。 （2）平衡条件： 对于发点vs，有 对于收点vt ，有 对于中间点，有,可行流中 fijcij 的弧叫做饱和弧，fijcij的弧叫

48、做非饱和弧。fij0 的弧为非零流弧，fij0 的弧叫做零流弧。,图中 为零流弧，其余为非饱和弧。,3、容量网络G，若 为网络中从vs到vt的一条链，给 定向为从vs到vt， 上的弧凡与 方向相同的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用 和 表示。 f 是一个可行流，如果满足： 则称 为从vs到vt 的关于f 的一条增广链。,推论 可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条可增广链。,即 中的每一条弧都是非饱和弧,即 中的每一条弧都是非零流弧,是一个增广链,显然图中增广链不止一条,4、容量网络G =（V，E，C），vs为始点，vt为终点。如果把V分成两

49、个非空集合 使 ，则所有始点属于S，而终点属于 的弧的集合，称为由S决定的截集,记作 。截集 中所有弧的容量之和，称为这个截集的容量，记为 。,容量为24,设 ，,则截集为,容量为20,5 求最大流的标号法 标号过程： 1 给发点vs 标号（0，+）。 2 取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理： （1）如果边 ，且 ，那么给vj 标号 ，其中： （2）如果边 ，且 ，那么给vj 标号 ，其中： 3重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流

50、。,（也就是所有后向 弧中最小的流量）,（所有前向弧中可增量的最小值）,调整过程 设 A令 B去掉所有标号，回到第一步，对可行流重新标号。,求下图所示网络中的最大流，弧旁数为,最小截集,13 (11),9 (9),4 (0),5 (5),6(6),5 (5),5 (4),5 (4),4 (4),4 (3),9 (9),10 (7),截集1,截集2,最小截量为：9+6+5=20,引例,4、最小费用最大流问题 常描述为从一个点出发经过若干各点，各点之间的可以容纳的最大流量不同，而且各点之间单位产品的运输费用不同。求花费最少的运输 费用运出最大量的物品。,例如：求下图的最小费用最大流,弧旁的数字为（

51、bij,cij),初始最小费用可行流图,v1,v2,v3,v4,0,赋权图,可行流图,-,v1,v2,v1,v2,v3,v4,-1,-3,3,1,3,-3,题目,最小费用+,赋权图,-,再例如，试求下例的最小费用最大流,（运价，容量）,(2,4),4,4,1,2,3,1,6,2,vs,vt,v1,v2,v3,按最短路根据弧的容量调整运量得流量图下图.,W(f (0),0,0,0,0,vs,vt,v1,v2,v3,(a ),( b ),f (1),v(f (1 )=5,1,-2,3,1,6,2,vs,vt,v1,v2,v3,-1,-1,W(f (1),(c ),作相应赋权有向图并求出最短路,bi

52、 j ,若 f i j c i j ，,+,若 f i j =c i j .,- b j i ,若 f i j 0,+, 若 f i j = 0,w i j =,w j i =,以0流 f(0)=0为初始流构造赋权有向图并算得最短路如右,0,0,0,5,5,5,(2,4),（运价，容量）,1,4,0,5,5,0,5,0,0,vs,vt,v1,v2,v3,( b ),f (1),v(f (1 )=5,1,3,1,6,2,vs,vt,v1,v2,v3,-1,W(f (1),(c ),作相应赋权有向图并求出最短路,0,5,5,0,5,0,0,vt,v1,vs,v2,v3,( d ),4,3,-1,6

53、,2,vs,vt,v1,v2,v3,-1,W(f (2),(e ),-4,沿最短路调整,得左下图,作相应赋权有向图并求出最短路,vs,vt,v1,v2,v3,题目,-1,2,7,(4,10),(1,8),(2,5),(3,10),(1,7),(6,2),(2,4),(bij,cij),-2,-2,1,2,5,5,0,7,0,0,vs,vt,v1,vs,v2,v3,( d ),4,3,-1,6,2,vs,vt,v1,v2,v3,-1,W(f (2),(e ),-4,作相应赋权有向图并求出最短路,4,-2,3,-1,6,2,vs,vt,v2,v3,-1,W(f (3),(g ),-4,-2,-3,

54、2,5,5,0,7,0,0,vs,vt,v1,v2,v3,( f ),f ( 3),v(f ( 3 ) )=10,作相应赋权有向图并求出最短路,沿最短路调整流量,bi j ,若 f i j c i j ，,+,若 f i j =c i j .,- b j i ,若 f i j 0,+, 若 f i j = 0,w i j =,w j i =,vs,vt,v1,v2,v3,题目,8,3,3,(4,10),(1,8),(2,5),(3,10),(1,7),(6,2),(2,4),(bij,cij),-2,8,5,7,0,3,vt,v1,vs,v2,v3,( h ),f ( 4),v(f ( 4 )

55、 )=11,4,-2,3,-1,6,2,vs,vt,v2,v3,-1,W(f (3),(g ),-4,-2,-3,2,8,5,3,7,0,3,vs,vt,v1,v2,v3,( f ),f ( 3),v(f ( 3 ) )=10,4,-2,3,-1,6,vs,vt,v2,v3,-1,W(f (4),(i ),-4,-2,-3,2,从发点到收点的路长为无限大, 故左边的网络流是最小费用最大流.,vs,vt,v1,v2,v3,bi j ,若 f i j c i j ，,+,若 f i j =c i j .,- b j i ,若 f i j 0,+, 若 f i j = 0,w i j =,w j i =,沿最短路调整流量,作相应赋权有向图并求出最短路,作相应赋权有向图并求出最短