模块六 运输与配送网络优化课件讲解

港口物流优化模块六目录

CONTENTS模块三模块四模块五物流决策优化认知物流管理决策分析物流资源配置优化物流任务指派优化模块二模块七模块一物资调运方案优化运输与配送网络优化物流项目计划优化模块六运输与配送网络优化任务1网络图认知任务2最小费用流问题任务3最大流问题任务4最小费用最大流问题任务5最短路问题任务6最小支撑树问题任务7节约里程法模块知识点了解网络图的相关基本概念及含义了解节约里程法的基本原理和求解步骤掌握节约里程法的求解方法掌握最小费用流、最大流、最小费用最大流、最短路、最小支撑树、货郎担、中国邮路等问题的基本描述、数学模型特点及应用情境模块能力点掌握最小费用流、最大流、最小费用最大流、最短路、最小支撑树、货郎担、中国邮路等问题的表格模型建模及求解节约里程法求解配送问题任务1网络图认知许多研究问题可以用网络图来表示，研究的目的归结为网络图的最优化问题。网络图点权弧或边网络图具有下列特征：(1)点（圆圈）——研究对象，连线（无方向的不带箭头的边或有方向的带箭头的弧）——对象之间的某种关系。(2)强调点之间的关联关系，不讲究图的比例大小与形状（曲直）。(3)每条边（或弧）都赋有一个权，其图称为网络图或赋权图。实际中，权可以表示两点之间的距离、费用、利润、时间、容量等不同的含义；(4)建立一个网络模型，求最大值或最小值。任务1网络图认知研究对象之间的关系可能具有对称性和非对称性，因此将图划分为无向图和有向图。点边无向图点弧有向图3947326141287110823546668v1v4v2v3v5v6链：无向网络中，前后相继点和边的交替序列称为一条链。圈：闭合的链称为一个圈。路：有向网络图中，前后相继并且方向一致的点弧序列称为一条路径。回路：闭合的路径称为一个回路。任务2最小费用流问题①节点：包括供应点、需求点和转运点。②弧：可行的运输线路（节点i->节点j）。③有最大运输能力（容量）的限制。最小费用流问题的构成（网络表示）最小费用流问题的数学模型为：（1）决策变量：设fi

j为弧（节点i->节点j）的流量。（2）目标：通过网络的流量总成本最小。（3）约束条件（净流量=总流出-总流入） ①供应点：净流量为正（已知，总流入=0）； ②转运点：净流量为零（总流出=总流入）； ③需求点：净流量为负（已知，总流出=0）； ④弧流量fi

j受到弧的容量限制； ⑤弧流量fi

j非负。任务2最小费用流问题①至少有一个供应点和一个需求点，可有转运点。②通过弧的最大流量取决于该弧的容量。③网络中有足够的弧提供足够容量，使得所有在供应点中产生的流，都能够到达需求点（有可行解）。

⑤目标是在满足给定需求的条件下，使得通过配送网络的总成本最小（或总利润最大）。⑥具有可行解：在以上假设下，当且仅当供应点所提供的供应量总和等于需求点所需要的需求量总和时（即平衡条件）。⑦整数解特征：只要所有的供应量、需求量和弧的容量都是整数最小费用流问题的特点任务2最小费用流问题例1某公司有两个工厂（F1,F2）生产产品，这些产品需要运送到两个仓库（W1,W2）中。其配送网络图如图所示（DC为配送中心，（c,b）表示（弧容量，单位运费））。目标是确定一个运输方案（即每条线路上运送多少单位的产品），使得通过配送网络的总运输成本最小。（50，400）（50，200）（50，400）（50，300）F1F2DCW2W180706090（无限制，700）（无限制，900）任务2最小费用流问题解：

该问题的要考察从工厂W1、W2经配送中心运输货物到仓库W1、W2的运费最优化问题，在线路上有容量限制的情况下，求线路上流量（货运量）。因此，属于最小费用流问题。最小费用流问题的数学模型为：（1）决策变量：设fi

j为弧（节点i->节点j）的流量。（2）目标函数本问题的目标是使通过配送网络的总运输成本最小任务2最小费用流问题（3）约束条件(节点净流量、弧的容量限制、非负）①供应点F1:

供应点F2: ②转运点DC: ③需求点W1:

需求点W2: ④弧容量限制：⑤非负：任务2最小费用流问题结果解释：从F1运往W1和DC分别为30和50单位，从F2运往W2和DC分别为40和30单位，DC分别运往W1和W2为30和50单位，这样安排配送，成本最小为110000元。1、下图表示了企业所处的供应市场（v1和v2）、配送中心（v3和v4）、以及销售市场（v5、v6和v7）组成的网络。弧旁的数字为(bijcij),分别表示弧的费用和容量。试求这个供应-销售网络流的最小费用流（v1和v2供应能力分别为30和35，v5、v6和V7的需求均为1）.练一练V1V2V3V4V5V6V7(10,5)(15,4)(4,6)(4,10)(5,10)(6,8)(6,3)任务3最大流问题问题描述：在有一个起点和一个终点的网络中，最大流问题是企图找出，在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量（不管它是物资、卡车、飞机、液体或电流）。最大流问题，就是在一定条件下，要求流过网络的流量为最大的问题。如：交通网络中要研究车辆的最大通行能力；生产流水线上产品的最大加工能力；供水网络中通过的水流量；信息网络中的信息传送能力等。708060403050407050VSV1V2V3V5V4VT任务3最大流问题①节点：包括供应点、需求点和转运点。②弧：可行的运输线路（节点i->节点j）。③有最大运输能力（容量）的限制。最大流问题的构成（网络表示）最大流问题的数学模型为：（1）决策变量：设fi

j为弧（节点i->节点j）的流量。（2）目标：通过网络流量最大（区别于最小费用流问题）。（3）约束条件 ①供应点：净流量为正（但未知，区别于最小费用流）； ②转运点：净流量为零； ③需求点：净流量为负（但未知，区别于最小费用流）； ④弧流量fi

j受到弧的容量限制； ⑤弧流量fi

j非负。任务3最大流问题例2某公司要从起始点VS（供应点）运送货物到目的地VT（需求点），其网络图如图所示。图中每条弧（节点i->节点j）旁的权ci

j表示这段运输线路的最大运输能力（容量）。要求制订一个运输方案，使得从VS到VT的货运量达到最大，这个问题就是寻求网络系统的最大流问题。708060403050407050VSV1V2V3V5V4VT任务3最大流问题例2最大流问题的线性规划数学模型：（1）决策变量设fi

j为弧（节点i->节点j）的流量。（2）目标函数从供应点VS流出的总流量最大。（3）约束条件转运点的净流量为0

弧的容量限制

决策变量非负任务3最大流问题例2最大流问题的电子表格模型任务3最大流问题最大流问题的变形主要在于：有多个供应点和（或）多个需求点。例3

在例2的基础上，增加了一个供应点PS、一个需求点PT、两个转运点P1和P2以及与之相连的7条弧，如图所示。目标是从2个供应点VS和PS运出的货物量最大。本问题是一个有2个供应点和2个需求点的最大流问题。70804010203050406030404070502060V1V2V3V5V4VTP1PSPTP2VS任务3最大流问题例3的线性规划模型任务3最大流问题例3的电子表格模型2、某第三方物流企业从配送中心VS向客户仓库VT送货，运输网路如图所示，线路上的数字表示该线路的最大运量通过能力（单位：t），各线路均为单行线。试计算通过该运输网络VS向VT的最大送货量。练一练VSVTV1V2V31085107243、如图所示是5个城市之间公路所能承受的最大流量(辆/小时)，求1-5之间的最大流量及安排。练一练2356000400020002000700042000300030001任务4最小费用最大流问题在实际的网络应用中，当有时考虑的不只是流量，还要考虑费用问题。尤其是需兼顾流量和费用问题，于是就出现了最小费用最大流问题。所谓的“最小费用最大流问题”，就是保证网络在最大流的情况下，如果有多个最大流量运输方案，则寻求其中费用最小的方案。最小费用最大流问题，是最小费用流问题的特殊情况。如果问题明确提出求最小费用最大流问题，则问题可以分成两步求解：第一步：求出问题不考虑成本时的最大流量；第二步：将确定的最大流量作为新的约束条件，添加到求最小费用的模型中去。任务4最小费用最大流问题例4

某公司有一个管道网络（如图所示），使用这个网络可以把石油从采地V1运送到销地V7。由于输油管道长短不一，每段管道除了有不同的容量cij限制外，还有不同的单位流量的费用bij。每段管道旁括号内的数字为（cij，bij）。如果使用这个管道网络，从采地V1向销地V7输送石油，怎样才能输送最多的石油并使得总的输送费用最小？(3,2)(6,3)(2,8)(1,3)(4,4)(2,3)(5,7)(2,4)（2,5）(3,4)(6,6)V1V7V6V5V4V3V2(容量cij,费用bij)任务4最小费用最大流问题解：用线性规划来求解此问题，分为两步：第一步：先求出此管道网络的最大流量F（最大流问题）。设通过弧（Vi,Vj）的流量为fij，最大流问题的线性规划模型为：任务4最小费用最大流问题第一步：先求出此管道网络的最大流量F（最大流问题）。石油网络最大流问题的电子表格模型：求得的最大流量F＝10任务4最小费用最大流问题第二步：在最大流量F的所有解中，找出一个最小费用的解（最小费用流问题）。设通过弧（Vi,Vj）的流量为fij，则例4最小费用最大流问题的线性规划模型为：任务4最小费用最大流问题第二步：在最大流量F=10的所有解中，找出一个最小费用的解（最小费用流问题）石油网络最小费用最大流问题的电子表格模型：求得的最小费用为1454、求下图中网络从Vs到Vt的最小费用最大流，图中弧上的数字为（弧容量，单位费用）。练一练任务5最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新、管道铺设、路线安排、厂区布局等。最短路问题最普遍的应用是在两个点之间寻找最短路线，是最小费用流问题的一种特殊类型：出发地（供应点）的供应量为1、目的地（需求点）的需求量为1、转运点的净流量为0、没有弧的容量限制，目标是使通过网络到目的地的总距离最短。在已知的物流网络（通过各段线路所需的时间、距离或费用为已知）中，有一货物发点（供应点）对一货物收点（客户）专门送货，在这种直送情况下找出货物运送所需的最少时间、最短距离或最少费用的路径问题。任务5最短路问题例5

某人每天从V1开车到V7送货，图中各弧旁的数字表示道路的长度（单位：公里），试问他从V1出发到V7，应选择哪条路线，才能使路上行驶的总距离最短。V1V2V3V4V5V6V729683.51452.53任务5最短路问题解：这是一个最短路问题。其数学模型为：（1）决策变量：设xij为弧(节点Vi->节点Vj)是否走（1表示走，0表示不走）。（2）目标函数：目标是总距离最短（3）约束条件(节点净流量、非负）任务5最短路问题例5最短路问题的电子表格模型求解结果：某人从V1出发到V7，他开车应行驶的路线为：V1－>V2－>V3－>V5－>V7，此时路上行驶的总距离最短，为13.5公里。任务5最短路问题例6应用于设备更新问题。某工厂的某台机器可连续工作4年，决策者每年年初都要决定机器是否需要更新。若购置新机器，就要支付购置费用；若继续使用旧机器，则需要支付一定的维修与运行费用。试制订今后4年的机器更新计划，使得总的支付费用最少。估计该种设备计划期（4年）内各年年初的购置费用和使用不同年限的设备所需要的维修与运行费用。年份第1年第2年第3年第4年购置费用2.52.62.83.1维修费用11.524任务5最短路问题解：可以把设备更新问题看作最短路问题。

用节点i代表“第i年年初购买一台新设备”这种状态（增加一个节点5，可以理解为第4年年末），节点1和节点5表示计划期的始点和终点。从节点i到i＋1，⋯，5各画一条弧，弧（i，j）表示在第i年年初购进的机器使用到j年年初（第j-1年年底）。任务5最短路问题每条弧的权（弧旁的数字）可以根据表中的数据计算得到。

弧长＝购置费用＋使用多年的维修与运行总费用如，考虑从节点1到节点3的弧（1,3），这条弧对应的是在第1年年初购进一台新机器（支付购置费2.5），一直使用到第3年年初（第2年年末，即使用了2年，支付维修与运行总费用1＋1.5＝2.5），所以

从①到③的弧长＝2.5＋1+1.5=5这样一来，制订一个最优的设备更新计划问题就等价于寻求从节点1到节点5的最短路问题。年份第1年第2年第3年第4年购置费用2.52.62.83.1维修费用11.524任务5最短路问题例6的电子表格模型求解结果为：①

③

⑤，即计划期内机器更新最优计划为：第1年年初、第3年年初各购置一台新机器，4年总的支付费用为10.3。任务5最短路问题如果已知不同役龄机器的处理价格，那么在计划期（4年）内机器的最优更新计划又会怎样？这还是一个最短路问题，网络模型仍然如图5-22所示，只是弧长有所不同。

弧长＝购置费用＋使用多年的维修与运行总费用

－使用多年后的处理价格使用年数1年2年3年4年处理价格21.61.31.1任务5最短路问题有处理价格的设备更新问题的电子表格模型求解结果为：①－>②－>③－>⑤，即计划期内机器更新最优计划为：第1年年初、第2年年初、第3年年初各购置一台新机器，同时在第2年年初（第1年年末）、第3年年初（第2年年末）、第5年年初（第4年年末）将旧的机器处理掉，4年总的支付费用为6.8。5、某车队要从甲市运送一批物资到乙市，中间可穿行的市镇与行车网络道路如图所示，图中表明的数字为里程数，试着找出甲市到乙市的最短路线。练一练甲市12345乙市3340275212437023202033任务6最小支撑树问题点边无向图链：无向网络中，前后相继点和边的交替序列称为一条链。圈：闭合的链称为一个圈。无向图中任意两点之间，至少有一条链，则为连通图，否则为不连通图。树（针对无向图）：无圈的连通图支撑树：与图G顶点相同，边是图的一部分的树。支撑树的权：在赋权图中，构成其支撑树各边权的总和。最小支撑树：具有最小权的支撑树，简称最小树。v2v1v3(a)925v2v1v3(b)95v2v1v3(c)25图

连通图a与部分树b、c注：树的边数=图的顶点数-1任务6最小支撑树问题v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)v1v2v3v4v5v6v7e1e6e7e9e10e11(c)任务6最小支撑树问题许多网络问题可以归结为最小支撑树问题。例如，设计长度最短的公路网，把若干城市（乡村）联系起来；设计用料最省的电话线网（光纤），把有关单位联系起来；等等。这种问题的目标是设计网络。虽然节点已经给出，但必须决定在网络中要加入哪些边。特别要指出的是，向网络中插入的每一条可能的边都有成本。为了使每两个节点之间有连接，需要提供足够的边。目标就是以某种方法完成网络设计，使得边的总成本最小。这种问题称为最小支撑树问题。任务6最小支撑树问题例7某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。v1v2v3v4v5v6651572344任务6最小支撑树问题5v1v2v3v4v5v612344避圈法：每步从图中未选的边中选取边e,使它与已选边中的最小权边不构成圈,直到选够n-1（n为顶点数）条边为止.破圈法：在图G中任意取一个圈，从圈上任意舍弃一条边（通常选权最大者）,将此圈破掉。重复此步骤直到图G中没有圈为止。v1v2v3v4v5v6651572344v1v2v3v4v5v6651572344电话线铺设线路最短为最小支撑树的权，即5+1+2+3+4=15.，铺设方法如图所示。任务6最小支撑树问题v1v2v3v4v5v6651572344电子表格模型如下:可知，铺设方法为(v1,v2),(v2,v3),(v2,v4),(v4,v5),(v5,v6),费用最省为15.任务6最小支撑树问题解：使用Excel软件求解最小生成树的基本步骤如下：（1）输入网络图到Excel工作表中。表中左上角是一个6×6的对称权矩阵。例如单元格C2位置的“5”代表从v1点到v2点的距离；同样，单元格B3位置的“5”代表的是从v2点到点v1的距离。矩阵中“1000”代表距离是无穷大，意味着相应两点间没有路。（2）输入6×6的变量矩阵。矩阵中的元素只能取“0”和“1”，“0”代表没有选中，“1”代表被选中。（3）输入约束条件：1）变量矩阵的每行的行和大于等于1。这意味着一个节点至少与其它一个节点相连。

2）变量矩阵的每列的列和=相应的行和（对称矩阵）。3）总边数等于顶点数减1，这是树的定义。总边数就是B10：G15的所有元素和除以“2”（因为每条边有两个节点重复计算了一次，所有要除以“2”）。（4）输入目标函数：总铺设费用最小。总铺设费用等于选中路径的权重之和，即SUMPRODUCT(B2:G7，B10:G15)/2。（5）求解：目标函数：Min（总建设费用最小）;约束条件：变量矩阵=bin;总边数=顶点个数-1=5;行和大于等于1;行和等于列和6、如图所示，A、B、C、D、E、F、G代表某集团公司及下属的工厂，它们之间的连线代表彼此之间的道路交通情况，连线旁的数字代表相应道路的长度。现在要