第4篇 数学方法在物流运输中的应用 第12章 货物运输的优化求解.doc

第 4 篇 数学方法在物流运输中的应用 第12章 货物运输的优化求解 本章学习目的：了解常见货物运输问题，如产销运输问题、分配运输问题、最短路径问题、最小费用最大流问题、送货（集货）问题等，并掌握对这些问题进行系统分析、数学模型建立和优化求解的一些方法，以提高货物运输的科学管理水平。 降低物流成本、提高物流效率，要求对货物运输进行优化组织，即要运用掌握的资源（人力、物力、财力）合理安排运输任务，消灭对流、迂回、重复等不合理现象，尽量以最少的资源来完成最多的任务。这就需要对货物运输问题进行系统分析，建立模型，并应用各种数学方法进行求解，以实现货物运输的科学管理。常见的货物运输问题有产销运输问题、分配运输问题、最短路径问题、最小费用最大流问题、送货（集货）问题等，下面就这些问题的优化求解进行介绍。 12.1 产销运输问题 销售商在组织某一产品销售时，需要从多个厂家或产地采购，运输到其不同的销售门店，而每个厂家或产地可提供的产品数量和运价各不相同，如何组织运输才能使总运费最低？或生产厂家从多个地方采购原料时，各地原料可供数量和运价不同，如何确定各地原料调拨量，才能使运输费用最省？这就是产销运输问题，根据供求双方的物资数量关系，可分为产销平衡的运输问题和产销不平衡的运输问题。 12.1.1 产销平衡的运输问题 12.1.1.1 模型分析 产销平衡的运输问题一般可表述为：某种物资有m个产地A1，A2,.,Am，其供应量分为a1,a2,.,am;有n 个销地B1,B2,.,Bn,其销量分为b1,b2,.,bn;产地物资供应量总合等于销地物资销量（需求量）总合；从产地Ai到销地Bj的物资量和单位物资运价为分为xij,cij,求此时调运物资最佳方案。 对此问题可有下述线性规划模型： mnminz=cxijiji=1j=1s.t.nx=a(i=1,.,m)ijij=1 （12.1） mx=b(j=1,.,n)ijji=1nmb=ajij=1i=1x0(i=1,.,m;j=1,.,n)ij12.1.1.2 表上作业法求解 12-1 上述模型是一种线性规划模型，自然可以用单纯形法求解，但是根据其特殊结构而建立的表上作业法比起用单纯形法要简单得多。其思路为：由初始运输方案开始，通过检验、改进，最后获得最优运输方案。 下面结合例12-1具体说明表上作业法的步骤和方法： 例12-1 设有两个煤矿供应三个城市用煤，煤矿A1和A2的日产量分别为a1=200吨;a2=250吨。三城市（B1,B2,B3）的日销量分别为b1=100吨，b2=150吨，b3=200吨。假定每吨货物的社会运输费与出行公里线性有关，取cij代表煤矿I至城市j的最短距离。已知c11=90公里，c12=70公里，c13=100公里，c21=80公里，c22=65 公里，c23=80公里。问如何安排运输使运输费用最省？ 解：设xij为煤矿I运往j的煤量，根据每个煤矿产煤总量和城市的用煤总量，xij(I=1,2;j=1,2,3)必须满足下列条件： x11+x12+x13=200 x21+x22+x23=250 x11+x21=100 x12+x22=150 x13+x23=200 目标函数为：minz=90x11+70x12+100x13+80x21+65x22+80x231.列运输平衡表 列表时要求表内供销平衡，并将运费标入表内空格，如下表12-1所示： 表 12-1 运输平衡表 需 B1B2B3供应量 供 90 70 100A1X11X12 X13200 80 65 80 A2X21X22 X23250 需求量 100 150 200 450 2.建立初始调运方案 鉴于最好运输方案是使总运费最小，采用最小元素法，即在平衡表中挑取运价最小或较小的供需点格子尽量优先分配的调运方法。一行（或一列）满足了，就划去一行（或一列），如果运费相等时可任选一个，直到全部分配完为止。分配时注意一个问题，即分配数字的格数要为“行数+列数-1”，若分配完时出现规定数时，应在适当的空格补零，这个补零的格子在数量上是零，但要当成非零数字格对待。如表12-2所示： 表 12-2 初始调运方案表 需 B1B2B3供应量 供 90 70 100A10 200 200 80 65 80 12-2 A2100 150 250 需求量 100 150 200 450 表12-2先从A2,B2（c22最小）开始，确定c22=150,划去余下的B2 列，然后确定x21=100(c21为剩下方格中最小运价)，划去余下的B1列，A2的供应量也同时得到满足，故此时余下的A2也被划去，最后确定x12为200，形成初始调运方案。 3.方案的检验和调整 （1）闭回路 从调运方案的任意空格出发，沿水平方向或垂直方向前进，而遇到填有数字的方格，折转90度前进，当然可以直接穿过数字格和空格，但只能遇有数字的格才能折转，只能水平、垂直方向前进，不能对角线移动，这样经过多次折转直到回到原来出发的空格，形成一条闭回路。 （2）位势法检验 由方案表列出检验表。表中行列数与方案表一样，运价在每个格的右上角，原方案表中的空格填写检验数，原方案表中的数字格为检验表中的空格，原方案表中的供应量、需求量格填写行与列的位势，称为行或列位势格。 求位势。记第i行位势为ui ，第j列位势为vj，可任选一个位势格填任意数，通常取0作为该格的位势。其它位势格的位势由下列法则求出：每个空格右上角的运价cij等于该行位势与该列位势之和，即cij=ui+vj. 例如在表12-2中，任取左下端的位势格为0，由上述法则求出其它4个位势格的位势,如表12-3。 表12-3 位势表 需 B1B2B3Vj供 90 70 100A10 200 90 80 65 80 A2100 150 80 Ui0 -15 10 求检验数。若空格位于第i行第j列，则其检验数ij按下式求出： =c?u?v ijijij例如由表12-3可求出1行2列空格的检验数12=70+15-90=-5，其它如检验数表12-4所示。 表12-4 检验数表 B1B2B3vj需 供 90 70 100A1 -5 90 80 65 80 12-3 A2 -10 80 ui0 -15 10 由表12-4知，有负的检验数存在，这表明12-2所给的运输方案不是最优的，需要进行调整。 （3）调整运输方案。当运输表对应的检验表中有负的检验数时，需在运输方案表上对运输方案进行调整。 确定闭回路。在需调整的运输方案表上选取对应的检验数为负的格作为调整格， 若有两个以上格的检验数为负，选其中检验数绝对值最大的格为检验格，从检验格出发在运输方案表上作闭回路。 例如在表12-4中，A2B3格的检验数是-10，为绝对值最大的负检验格，故选取此格为调整格，并用虚线在运输方案表上作闭回路，如表 12-5所示。 表12-5 闭回路表 需 B1B2B3供应量 供 200 90 70 100 A10 200 250 80 65 80 A2100 150 需求量 100 150 200 450 在闭回路上作运输量最大的调整,得出新的运输方案。从空格开始，沿闭回路在各偶数格中挑选运量最小的作为调整量，调整闭回路各点的运输量。 例如在表12-5中，闭回路上偶数格最小运输量为min(200,100)=100,调整闭回路各点运输量，得表12-6. 表12-6 新运输方案1表 需 B1B2B3供应量 供 200 90 70 100A1100 100 250 80 65 80 A2 150 100 需求量 100 150 200 450 （4）返回（2），对新运输方案进行位势法检验。若无负检验数，则此方案为最优方案，否则继续进行调整。 例如对于表12-6，得检验表12-7。 12-4 表12-7 新运输方案1检验表 B1B2B3vj需 供 90 70 100A1 -15 90 10 80 65 80 A2 70 ui0 -5 10 表12-7中有负得检验数，继续进行调整，得新运输方案表12-8. 表12-8 新运输方案2表 需 B1B2B3供应量 供 90 70 100A1100 100 200 80 65 80 A2 50 200 250 需求量 100 150 200 450 对表12-8进行检验，得检验表12-9 表12-9 新运输方案2检验表 B1B2B3Vj需 供 90 70 100A1 15 90 80 65 80 A2-5 85 ui0 -20 -5 表中有负检验数，继续进行调整，得新运输方案表12-10 表12-10 新运输方案3表 B1B2B3需 供应量 供 90 70 100A150 150 200 80 65 80 12-5 A250 200 250 需求量 100 150 200 450 对此运输方案进行检验，得检验表12-11 表12-11 新运输方案3检验表 需 B1B2B3Vj供 90 70 100A1 10 90 80 65 80 A2 5 80 Ui0 -20 0 从表12-11中可以看到，检验数全是正数，因此表12-10中的运输方案为最优方案，即应确定A1向B1、B2调运煤数量分别为50、150;A2向B1、B3调运数量分别为50、200。 二.产销不平衡时的运输问题 （一）产大于销的运输问题 nm对于产量大于销量即b<a的运输问题，必然有些产地的产品不能安排运输，jij=1i=1此时引入虚拟需求点，令其需量等于总供量与总需量之差，并设其相应运价为0。这样，就可以用上面介绍的表上作业法求解产大于销的运输问题。 （一） 销大于产的运输问题 nm对于销量大于产量即b>a的运输问题，必然有一些销地不能得到满足，发生jij=1i=1缺货，此时引入虚拟供应点，并设其相应运价为0。这样，就可以用产销平衡的表上作业法求解销大于产的运输问题。 12.2 分配运输问题 在运输过程中经常遇到这样的问题，需完成几条运输线路的任务，恰好有几个运输单位可承担这些任务。由于每个单位的情况各不相同，其完成各项任务的效率（或效益）也不同，如何安排这些运输单位去完成任务，使效率（或效益）也最高，这一类问题统称为分配问题。 12.1.1 模型分析 例12-2 某材料厂有B1、B2、B3三台叉车可分配给A1、A2、A3三个仓库进行搬运作业，其中任一叉车都可以在任一仓库中进行搬运工作，只是搬运作业费不同，各台叉车相应作业费Cij如表12-12所示，要求一台叉车只分配给一个仓库使用，试求搬运作业费用最小的分配方案。 12-6 表12-12 效率矩阵表 仓库 c Bij1 B2 B3叉车 A1 25 15 22 A2 31 20 19 A3 35 24 17 对应于每个分配问题， 都有类似于表 12-12 的数字表，称之为效率矩阵，其元素 cij0(i,j=1,2,.,n)表示分配第i个单位去完成第j项任务时的效率(或时间、成本等)。根据问题引入变量xij，并按以下规定取值： ?1第i个单位被分配去完成第j项任务 x= ?ij0第i个单位不去完成第j项任务?其中i=1,2,.,n; j=1,2,.,n 当问题要求极小时,有数学模型: nn minz=cx ijiji=1j=1 st. n?x=1,j=1,2,.,nij?i=1 (12.2) ?nx=1,i=1,2,.,n?ijj=1? 上述模型中,约束条件1表明第j项任务只能由1个单位去完成；约束条件2则说明第i个单位只能完成1项任务。对于求极大问题时，可转化cij为cij,即令cij=cij-maxcij,将原maxz=cijxij转化为minz= cijxij求解。 12.2.2 匈牙利算法 可以看到，分配问题是0-1规划问题，对于几个单位分配几项任务的分配问题，总共有n！种可能的分配方案，若用隐枚举法求解，当n较大时，计算量是很大的。由匈牙利数学家考尼格给出的匈牙利算法，是一种求解分配问题最简单、最有效的方法。 匈牙利法的主要依据是，在效率矩阵的任何行或列中，加上或减去同一常数，并不改变最优分配。利用此性质，可使原效率矩阵变换为含有很多0元素的新效率矩阵，找出在其中的位于不同行、不同列的n个独立的0元素，将其取值为1，其它元素取值为0，即得原分配问题的最优解。 以下通过求解例12-2的分配问题，介绍匈牙利算法 已知其效率矩阵为： 251522? 312019 ?352417? 第一步 变换效率矩阵，使其每一行和每一列都至少有一个0元素，具体通过减去每行、每列的最小元素，如下： 1007007?251522-15 ?1210210 312019 -19 ?352417-17 1870870? ?10 12-7 第二步 试求最优分配方案。 （1）从1行开始，依次检查各行，找出只有一个未标记的0元素的行，并将该元素用“0”表示，与该元素同行同列的其它0元素用“”表示，其含义为，0元素对应的任务仅由所对应的单位去完成，此单位不再去完善渌挝瘢庀钊挝褚膊辉儆善渌煌瓿伞?和称为已标记的0元素。重复此过程，直到每一行没有一个尚未标记的0元素，或至少有两个未标记的0元素。 （2）依次检查各列，找出只有一个未标记的0元素的列，将该元素标以0，并与该元素同行同列的其它未标记0元素标以，直到每列没有一个尚未标记的0元素，或至少有两个未标记的0元素。 （3）重复上述步骤，直到效率矩阵中没有未标记的0元素为止，若n行n列效率矩阵中恰有n个0元素，就得到最优分配方案，否则，仍需进行效率矩阵调整，本例中为： ?0 7 ? 2 1 0 ?8 7 ?第三步 继续调整效率矩阵 （1）对每个0元素划一条水平线或垂直线，使这些线覆盖所有0元素。直线个数与0元素个数相同。本例中为： 0 7 ? 2 1 0 ?8 7 ?(2)在直线不穿过的所有元素中找出最小元素。 (3)在没有水平线的各行减去此最小元素,有垂直线的各列加上此最小元素,得新的效率矩阵。 本例中，所求最小元素为1，计算过程为： 008?0 7 ?2 1 0 100 -1?8 7 0 ?-1 ?760?+1 第四步 回第二步,直到求出最优分配方案。 本例中，对修改后的效率矩阵重复第二步得： ?0 8 ? 1 0 ?7 6 0 ?已经得3个0元素，故得最优分配方案为： A1B1，A2B2，A3B3根据原效率矩阵，3叉车总搬运作业费为： 25+20+17=62元 12.2.3 巡回运输问题（旅行商问题） 在单网点配送中，物流网点向所属用户送货，各用户的需求量bi（i=1,2,n），货车载重量为Q，若满足bQ，则该网点只需一辆货车巡回送货即可。显然，在这种情i况下使费用最省的方案就是合理安排货车访问各用户的顺序，使货车的巡回线路的总距离最短，这也就是旅行商问题。 12-8 例12-3 已知5用户间距离如表12-13，其中d(i,j)=表示从第i个用户到第j个用户是没有意义的, 用户1为物流网点所在位置，如果只考虑将每个用户都当作一个出发用户,每个用户都当作一个到达用户,则对每个出发用户都要选择一个到达用户,而每个到达用户只能有一个出发用户到达该地,将问题变成了一个分配问题,可用匈牙利法求解。 表12-13 用户间距表 到达 出发 1 2 3 4 5 1 1 7 4 3 2 2 6 3 4 3 1 6 2 1 4 1 5 4 6 5 7 5 4 5 以例12-13说明求解步骤 第一步 令d(i,i)=,不存在通路的也记为,得距离阵,通常d(i,j)与d(j,i)不一定相同,即矩阵不一定对称。 第二步 对距离矩阵用匈牙利法求解,若得到无环路的路线,则就是最优路线;若路线有环路,就不是最优路线,但所走总距离给出了旅行商问题总距离的下界。 在本例中，匈牙利法求解过程为：-1 ?0 ?-2 26340412420 ?-1 ?1621 ?05105 0 ?-1 154604354350 ?-4 ?0 7545310131? ?1 得不考虑环路下的最优方案： 12，24，41，35，53 所走总距离为： 1+3+1+1+4=10 可以看出上述路线存在环路，不是原问题的最优路线，但给出了原问题的下界10。 第三步 出现环路时，打开节点个数最少的环路。即在此环路上考虑某段路线不通的各种情况，分别用匈牙利法求解，其中距离最短又无环路的路线即为最优路线。 本例中，出现两个环路，1241和353，打开节点数少的环路，分别令d(3,5)=和d(5,3)=求解。 （1）当d(3,5)=时,用匈牙利法求解 0 1743-1 063262?-2 0 263404124?-1 ?162? ?051?50 ?-1 ?0-4 ?75453101310 ? ?1 ?2 可得无环路的最优方案: 534125 12-9 所走总距离为: 1+4+2+1+4=12 （2）当d(5,3)=时,用匈牙利法求解 0-1 ?263404120 112-2 ?16?21- 1 ?05?1040 ?1 ?-1 1546043540 5?-5 ?755200200 ? ?3 得路线: 12,21,35,43,54 总距离: 1+2+1+4+5=13 可以看到: 上述方案出现环路121和3543,如果打开环路求解,其总距离一定不小于13,而已经得到总距离为12的路线,故不必再作计算； 因此得上述旅行商的最优路线为:534125,总距离为12。 12.2.4 旅行商问题的神经网络求解 虽然可以应用匈牙利算法求解旅行商问题，但是该方法需要进行多次试探，只适用于小规模的问题，而随着距离矩阵维数的增加，求解的时间将大量增长，求解的复杂度也急剧增加，该方法变得不再适用，此时可采用人工智能的方法神经网络方法进行求解。 1.连续Hopfield神经网络模型 连续Hopfield神经网络模型如图12-1所示。第i个神经元的输入为ui ，输出状态为vi；运算放大器模拟神经元的转移函数g(其中g为sigmoid函数)，跨导Tij模拟神经元之间互连的突触特性，电容ci 及电阻Ri用来模拟生物神经元的输出时间常数。设有n个神经元互连，则可用下述非线性微分方程描述： （a）Hopfield神经元 12-10 （b）Hopfield神经网络 图12-1 连续时间神经网络模型 n?du(t)u(t)iic=Tv(t)?+I?iijji (12.3) ?dtRi=1i?v(t)=g(u)?ii对式(12.3)可以定义系统的能量函数为： nnnnv11i?1E=?Tvv?vI+g(v)dv (12.4) ijijii02Ri=j1i=1i=1idE可以证明，对于该能量函数，恒有0，即当t，网络达到稳态。显然应用网dt络的这一特性，可以进行优化问题的求解。求解时，只需将优化问题的目标函数转化成(12.4)式的形式，然后应用式(12.3)运算到网络收敛即可。通常在用Hopfield神经网络求解实际问题时，一般忽略能量式中的积分项，将能量函数简化为下式(12.5)，以便目标函数的映射。 nnn1E=?Tvv?vI (12.5) ijijii2i=1j=1i=12.神经网络求解旅行商问题 对于n个用户的TSP问题，任何一个用户在最终访问路径上的访问次序可用一个n维向量表示，因此每一个用户可用n个神经元表示。下面仍以例12-3为例说明，如果用户1第3个被访问，则表示为00100，即第三个神经元输出为1，其余为0。为了表示n个用户，可简单地用nn换位矩阵表示，如表12-14所示。 表 12-14 换位矩阵 次序 1 2 3 4 5 用户 1 0 0 1 0 0 2 0 1 0 0 0 3 1 0 0 0 0 4 0 0 0 1 0 5 0 0 0 0 1 上述换位矩阵表示巡回线路为：32145 巡回距离为：distance=d(3,2)+d(2,1)+d(1,4)+d(4,5) 12-11 显然，一条换位距阵可表示一条有效路径，如果要构成一条有效的最短巡回路线，必然要求满足下列条件： （1）换位矩阵中每行只能有一个为“1”； （2）换位矩阵中每列只能有一个为“1”； （3）换位矩阵中元素“1”之和应为n； （4）所构造的函数的极小值对应。 用nn=25个神经元的输出v(1xn,1in)表示换位矩阵中的某一元素（取值xi为“0”或“1”），其中x表示用户，i表示访问次序，则可以写出与本问题对应的计算能量函数为： nnnnnnnnABC2E=vv+vv+(v?n)xixjxiyixi222x=1i=1jii=1x=1yxx=1i=1 (12.6) nnnD+d(x,y)v(v+v)xiy,i+1y,i?12x=1yxi=1式(12.5)中第1、2、3项对应于换位矩阵的条件（1）、（2）、（3），第4项对应于条件（4），即使路径最短的目标要求。A、B、C、D为4个正常系数，将式（12.6）写成如（12.5）所表示的Hopfield能量函数标准形式，得T的表达式和I的值如下： xi,yixiT=?A(1?)?B(1?)?C?Dd(x,y)(+)(1?)?xi,yixyijijxyj,i+1j,i?1xy (12.7) ?I=CN?xi1ifx=y?其中= ?xy0?由(12.6) 得Hopfiled网络运行方程式如式（12.8）: nnnnnduu?xixi=?C(v?n)?Av?Bv?Dd(x,y)(v+v)?xjxjyiy,i+1y,i?1 (12.8) ?dtx=1j=1jiyxyx?v=g(u)x=1,2,L,n;i=,2,L,n;?xixi1作用函数g选用sigmoid函数g(u)=(1+th(u/u),网络初始值可置为xixi02u=1/n,在选择适当的系数A,B,C,D, ,进行迭代运算，得网络收敛稳定输出v，即可xixi获得巡回配送的最短路径。 12.3 网络流问题 12.3.1 图的基本概念 考虑6个城市间的交通路线图,如图12-12所示,图中的点V1、V2、V3、V4、V5、V6代表6个城市，又称为顶点，连接各顶点的弧记作（V1、V2）、（V2、V3）、.等。这种表明各点之间连接关系的图形，通常称为图。 从一个顶点沿着弧、顶点、弧、顶点的顺序，回到出发点的路线称为回路，如图12-2中，V1V2V4V3V1、V4V5V6V4都是回路，不含回路、各顶点又相互连通的图称为树，如图12-3就是一个树。 V1 V2 V2 V3 V4 V3 V4 VB5 12-12 VB6 VB5 VB6 图12-2 回路 图12-3 树 在实际问题中，对于一个图，总要考虑它们代表的各城市间道路的交通流量、流动方向，因此需在各顶点弧上标明流动方向和流量限制，这种表示流动方向和流量限制的图称为网络或网络流，如图12-4。 V1 V2 V3 V4 V5 V6 图12-4 在网络流中有些点只有发出，称不发点或源点，如图12-4中的V1；有些点只有收入，无发出，称为收点或汇点，如图12-4中的V6，还有些顶点既有收入又有发出，称为中间点。 12.3.2 网络最大流问题 1.问题的提出 已知连接产地V1与销地Vn的交通网，每一弧（Vi,Vj）代表从Vi到Vj的运输线，产品经由Vi输送到Vj，弧旁括号外的数字Cij为弧的容量，括号内的数字Xij为Vi到Vj的货运量，要求合理安排Xij，使V1到Vn的货运量最大。这种问题称为最大流问题，如图12-5所示。 V4V2 6(3) 11(6) 10(5) 5(1) 2(3) 10(5) V1 3(2) V6 17(2) 8(3) V3 V5 6(3) 图12-5 2.寻求最大流的标号法 对于包含n个顶点V1，V2.,Vn的网络流，V1为发点，Vn为收点，各段弧(Vi,Vj)上容量为Cij，设Xij是一个可行流，如果存在一条从V1到Vn的路线，这条路线具有以下特点： （1）所有正向弧（弧的方向与流向一致）上 Xij<Cij； （2）所有反向弧（弧的方向与流向相反）上 Xij>0。 则称此条路线为可行流Xij的一个增广链，记 1=mincij-xij| 当（vi,vj）为正向弧 （12.8） 2=minxij| 当 (vi,vj)为反向弧 (12.10) =min1, 2 (12.11) 由增广链的特点可知>0,按如下公式调整可行流xij为xij: 当(vi,vj)是增广链的正向弧 当(vi,vj)是增广链的反向弧 (12.12) 12-13 当(vi,vj)不在增广链上 ?x+ij? x=x? ?ijij?xij?显然,此时xij仍为可行流,且它的值比xij增加了。 由此不难看出,对于可行流xij,判断它是否最大流及对它进行调整,关键在于求出其增广链,标号法就是基于此来寻求最大流的,其具体步骤如下: 第1步 给发点以标号(0,+) 第2步 设vi已经有了标号,与vi相邻的点vj尚未标号。若在弧(vi,vj)上, xij<cij,则给vj以标号(i,+);若在(vj,vi)上，xij>0,则给vj以标号(i,-)。继续这个步骤，直到给收点vn以标号为止。 第3步 利用“反向追踪”，找出v1到vn的增广链，例如设vn的标号为(k,+)，则在增广链上vn前面的一点为vk,且弧(vk,vn)是正向弧，接下来检查vk，若其标号为(i,+)，则找出正向弧(vi,vk)；若标号为(i,-),则找出反向弧(vk,vi)，依此下去，一直追踪至具有标号(0,+)的发点v1，得到由v1到vn的一个增广链。 第4步 调整过程，由式（12.9）至(12.11)得出增广链的调整量,根据式(12.12)得出新的可行流xij,令可行流xij=xij,去掉所有标号,重新上述标号、寻找增广链及调整过程，如果标号过程进行不下去，而vn尚未标号，则说明再也找不出增广链，当前可行流即为最大流。 例12-4 求出图12-5的最大流 解： 第1步 首先给v1标上（0,+） 第2步 检查v2，在弧(v1,v2)上，x12=5<c12=10,则v2标上(1,+) 检查v4，在弧 (v2,v4)上,x24=2<c24=5,故v4标上(2,+) 检查v6，在弧(v4,v6)上，x46=6<c46=11，故v6标上(4,+)，因为v6是收点，所以标号过程结束，如图12-6所示。 第3步 利用“反向追踪”，得到增广链为v1v2v4v6 第4步 因为增广链上的弧(v1,v2)、(v2,v4)、(v4,v6)都是正向弧，由式（12.9）、（12.11）得： =1=min(10-5,5-2,11-6)=3 根据式(12.12)调整增广链上每段弧的流量,经调整后可行流如图12-7所示。 V2V4 V2 (1,+) V4 (2,+) 6(3) 11(6)10(5) 5(1) 2(3) V1 4(1) 3(2) V1 V6V6 17(2) (0,+) (4,+) 8(3) V 3 V5 V3 V5 6(3) 图12-6 图12-7 重新执行1-4步，v1标上(0,+)，依次给v2标上(1,+)，给v3标上(2,+)，给v5标上(3,+),给v6标上(5,+)，得增广链v1v2v3v5v6，因为此增广链上的弧都是正向弧，由式(12.9)、(12.11)得： =1=min10-8,4-1,6-3,17-2=2 12-14 根据式(12.9)调整流量,得新的可行流如图12-8 V2 V4 5(5) 11(9) 10(10) 5(1) 3(3) V1 4(3) 3(2) V6 17(4) 8(3) V3 V5 6(5) 图12-8 对图12-8,重新标号、调整，v1标上(0,+),V3标上(1,+),v5标上(3,+),v6标上(5,+)，得增广链v1v3v5v6，此增广链上的弧皆为正向弧，由式(12.9)、(12.11)得 =1=min8-3,6-5,17-4=1 根据（12.9）调整流量,得新可行流如图12-9 V2 V4 5(5) 11(9)10(10) 5(1) 3(3)V14(3) 3(2) V6 17(5)8(4) V3 V5 6(6) 图12-9 对图12-9,重新标号、调整，v1标上(0,+),V3标上(1,+),v4标上(3,+),v6标上(4,+)，得增广链v1v3v4v6，此增广链上的弧皆为正向弧，由式(12.9)、(12.11)得 =1=min8-4,5-1,11-9=2 根据（12.9）调整流量,得新可行流如图12-10 V2 V4 5(5) 11(11) 10(10) 5(3) 3(3) V1 4(3) 3(2) V6 17(5)8(6) VV5 6(6) 图12-10 对图12-10,重新标号、调整，v1标上(0,+),V3标上(1,+),v4标上(3,+),v5标上（4,-），v6标上(5,+)，得增广链v1v3v4v5v6，其中(v1,v3)(v3,v4)(v5,v6)为为正向弧，由式(12.9)得 1=min8-6,5-3,17-5=2 (v4,v5)为反向弧，由式（12.10）得2=3 由式(12.11)得=min1,2=2,因此在此增广链的正向弧上流量增加2,反向弧上流量减少2,得可行流如图12-11. V2 V4 5(5) 11(11) 10(10) 5(5) 3(1)VB14(3) 3(2) VB6 12-15 17(7)8(8) VB3 VB5 6(6) 图12-11 对图12-11显然用标号法再也不能得到一个增广链,故其所给的可行流即为最大流,最大流量=x12+x13=x46+x56=18 12.3.3 最小费用最大流问题 在实际运输工作中，人们除了考虑运量外，还需考虑成本问题，从而产生了最小费用最大流问题，即对于某个网络D=(V,A,C)，每个弧(vi,vj)上巳萘縞ij外，还给出了单位流量的费用bij，要求找出一个最大流x，使流的总输送费用b(x)=bijxij 最小。 解最小费用最大流问题的基本思想是，通过已知的由v1到收点vn的最小费用流x，寻找其对应的最小费用增广链，沿此增广链去调整x，实现最大流。 对于网络D=(V,A,C)，构造赋权有向图W（X），其顶点为原网络D的顶点，而把D中的每一条弧(vi,vj)变成两个相反方向的弧(vi,vj)和(vj,vi)，定义W（X）中弧的权wij为（其中长度为+的弧可从W（X）中略去）： 若xij<cijb?ij(12.13) w= ?ij xij=cij+?b?若xij>0 (12.14) ij w= ?ij+ xij=0 ? 在w(x)中寻找到的v1 到vn 的最短路即为关于可行流x的最小费用增广链。 最小费用最大流算法如下： 第一步：取x(o)=0为初始可行流，即流量为0的最小费用流，k=0 (k)第二步：对于可行流x(k)，根据式(12.12)、(12.13)构造赋权有向图w(x)，并在此有向图中找出v1到vn的最短路。 (k)(k)第三步：若存在最短路，则此最短路为x的最小费用增广链，在增广链上对x进行调整，即 (k)?x+当(vi,vj)是增广链上的正向弧 ij?(k+1)(k)当(vi,vj)为增广链上的反向弧 x=x? ?ijij(k)?当(vi,vj)不在增广链上 xij?=min,12(k)其中 =minc?x| 当(vi,vj)为正向弧 1ijij(k)=minx|2ij当(vi,vj)为反向弧 (k+1) 得到新的可行流x,此可行流为同一流量中费用最小的可行流，若不存在最短路， 转第五步。 第四步 令k=k+1，重复第二步至第三步。 第五步 退出计算，所得x(k)即为最小费用最大流。 例12-5 求图12-12所示网络的从v1到v8的最小费用最大流，图中(vi,vj)上所标的三个数字依次表示 bij、cij、xij。 (0)(0)解：首先对x=0的初始可行流，根据式（12.13）、（12.14）构造赋权有向图w(x)如图12-13，并找出v1到v8的最短路径为：v1v2v5v6v8 12-16 V2 (2,4,0) V5 V2 2 V5 (2,4,0) (6,3,0) (3,2,0) (8,3,0) 2 6 3 8 V3 (7,3,0) V6 V3 7 V6 V1 V1 (2,4,0) (3,3,0) V8 2 3 V8 (3,2,0) 3 (3,2,0) 3 (3,2,0) 3 (4,4,0) (6,4,0) 4 6 V4 V7 V4 (2,2,0) 2 V4 V7 V7 图12-12 图12-13 (0)(1)沿此增广链对x进行调整，显然可增加的流量为2，得可行流x，如图12-14所示，对(1)(1)x根据式（12.13）、（12.14）构造赋权有向图w(x)如图12-15，找出v1到v8的最短路径为：v1v3v7v8 V2 (2,4,2) V5 V2 2 V5 -2 (2,4,2) (6,3,0) (3,2,2) (8,3,0) 2 6 8-2 -3 V3 (7,3,0) V6 V3 7 V6 3V1 V1 (2,4,0) (3,3,2) V8 2 V8 (3,2,0) 3 -3(3,2,0) 3 (3,2,0) 3 (4,4,0) (6,4,0) 4 6 V4 (2,2,0) V7 V4 2 V7 图12-14 图12-15 (1)(2)(2) 沿此增广链对x进行调整，可增加的流量为2，得可行流x，如图12-15所示，对x(2)构造赋权有向图w(x)如图12-17，找出v1到v8的最短路径为：v1v2v6v8 V2 (2,4,2) V5 V2 2 V5 -2 (2,4,2) (6,3,0) (3,2,2) (8,3,0) 2 -2 6 8-3 V3 (7,3,0) V6 V1 2 V3 7 V6 3 V1 (2,4,2) (3,3,2) V8 V8 (3,2,2) -2-3 -3 (3,2,0) 3 (3,2,0) 43 6 (4,4,0) (6,4,2) -6 V4 (2,2,0) V7 2V4 V7 图12-16 图12-17 (2)(3)(3) 沿此增广链对x进行调整，可增加的流量为1，得可行流x，如图12-18所示，对x(3)构造赋权有向图w(x)如图12-19，找出v1到v8的最短路径为：v1v4v7v8 V2 (2,4,2) V5 V2 2 V5 -2 (2,4,3) (6,3,1) (3,2,2) (8,3,0) 2 -2 68 -6 -3 V3 (7,3,0) V6 2 V3 7 V6 V1 (2,4,2) (3,3,3) V8 -3 V8 (3,2,2) V1 -2-3 (3,2,0) 3 (3,2,0) 43 6 (4,4,0) (6,4,2) -6 V4 (2,2,0) V7 V4 2V7 图12-18 图12-19 12-17 (3)(4)(4)沿此增广链对x进行调整，可增加流量2，得可行流x，如图12-20所示，对x构造(4)赋权有向图w(x)如图12-21，找出v1到v8的最短路径为：v1v2v5v8 VV2 2 V5 2 (2,4,2) V5 -2 2 -2 68(2,4,3) (6,3,1) (3,2,2) (8,3,0) -6 -3 V1 V 2 V3 7 V6 3 (7,3,0) V6 V1 -3 V(2,4,2) (3,3,3) V8 8 -2-3 (3,2,2) 3 (3,2,0) 43 -6 (3,2,0) (4,4,2) (6,4,4) -4 VV4 -2 V7 4 (2,2,2) V7 图12-20 图12-21 (4)(5)(5)沿此增广链对x进行调整，可增加流量1，得可行流x，如图12-22所示，对x构造(5)赋权有向图w(x)如图12-23，找出v1到v8的最短路径为：v1v3v6v2v5v8 V2 (2,4,3) V5 V2 2 V5 -2 (2,4,4) (6,3,1) (3,2,2) (8,3,1) -2 6 8-8 -6 -3 V1 V3 (7,3,0) V6 2 V3 7 V6 V1 (2,4,2) (3,3,3) V8 -3 (3,2,2) -2-3 (3,2,0) 3 (3,2,0) 43 -6 (4,4,2) (6,4,4) -4 V4 (2,2,2) V7 V4 -2 V7 图12-22 图12-23 (5)(6)(6)沿此增广链对x进行调整，可增加流量1，得可行流x，如图12-24所示，对x构造(6)赋权有向图w(x)如图12-25，找出v1到v8的最短路径为：v1v3v6v5v8 V5 V2 (2,4,4) V5 V2 -2 (2,4,4) (6,3,0) (3,2,2) (8,3,2) -2 68-8 -3 V1