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

港口物流优化模块六目录

CONTENTS模块三模块四模块五物流决策优化认知物流管理决策分析物流资源配置优化物流任务指派优化模块二模块七模块一物资调运方案优化运输与配送网络优化物流项目计划优化模块六运输与配送网络优化任务1网络图认知任务2最小费用流问题任务3最大流问题任务4最小费用最大流问题任务5最短路问题任务6最小支撑树问题任务7节约里程法模块知识点了解网络图的相关基本概念及含义了解节约里程法的基本原理和求解步骤掌握节约里程法的求解方法掌握最小费用流、最大流、最小费用最大流、最短路、最小支撑树、货郎担、中国邮路等问题的基本描述、数学模型特点及应用情境模块能力点掌握最小费用流、最大流、最小费用最大流、最短路、最小支撑树、货郎担、中国邮路等问题的表格模型建模及求解节约里程法求解配送问题任务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送货，运输网路如图所示，线路上的数字表示该线路的最大运量通过