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

港口物流优化模块六目录

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