包装物流系统优化方法.ppt

专业 包装工程E mail fygpack 包装物流技术 第5章包装物流系统优化方法 5 1概述5 2多段图问题5 3节约里程法5 4背包问题 货物配载问题 5 50 1背包问题5 6矩阵连乘积问题5 7凸多边形最优三角剖分 物流系统规划所关注的问题是如何合理 有效地利用或配置各种资源 劳动力 材料 设备 资金 使实现预定目标所需的费用最小 或资源最少 或者所获得的收益最大 物流系统的规划一般都可以用优化模型来表达 其基本思想是在满足一定的约束条件下 使预定的目标值达到最优 物流系统规划的数学基础主要是运筹学理论 常用的方法包括线性规划 整数规划 动态规划等 5 1概述 多阶段决策问题 求解的问题可以划分为一系列相互联系的阶段 在每个阶段都需要做出决策 且一个阶段决策的选择会影响下一个阶段的决策 从而影响整个过程的活动路线 求解的目标是选择各个阶段的决策是整个过程达到最优 如图所示 对于中间的任意一段 例如第k 1段作出相应的 决策 或控制 uk后 才能确定该段输入状态与输出状态间的关系 即从xk变化到xk 1的状态转移规律 在选择好每一段的 决策 或控制 uk以后 那么整个过程的状态转移规律从x0经xk一直到xN也就被完全确定 全部 决策 的总体 称为 策略 DynamicProgramming 动态规划 动态最优的核心是最优性原理 它首先将一个多阶段决策问题转化为一系列单阶段决策问题 然后从最后一段状态开始逆向递推到初始段状态为止的一套求解最优策略的完整方法 最优性原理 一个过程的最优策略具有这样的性质 即无论其初始状态及其初始决策如何 其以后诸决策对以第一个决策所形成的状态作为初始状态而言 必须构成最优策略 动态规划算法的依据是最优化原理 最优子结构性质 一个最优化策略具有这样的性质 不论过去的状态和决策如何 余下的决策必须相对于前一决策所产生的状态构成最优决策序列 简言之 一个最优化策略的子策略总是最优的 问题的最优解可以通过其子问题的最优解构成 无后效性 在多段决策过程中 每一段 如第k 1段 的输出状态 xk 1 都仅仅与该段的决策 uk 及该段的初始状态 xk 有关 而与其前面各段的决策及状态的转移规律无关 1 划分阶段 按照问题的时间或空间特征 把问题分为若干个阶段 2 选择状态 将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来 3 确定决策并写出状态转移方程 状态转移就是根据上一阶段的状态和决策来导出本阶段的状态 4 写出规划方程 包括边界条件 动态规划的基本方程是规划方程的通用形式化表达式 动态规划算法的基本步骤 常见的动态规划问题 1 多段图问题 配送路径优化问题 2 节约里程问题 配送路径优化问题 3 背包问题 货物配装 装箱问题 4 矩阵连乘积问题 5 数字三角形问题 6 最长不下降子序列 7 最长公共子序列 8 最大子段和 9 多边形游戏 10 资源分配问题 5 2多段图问题 多段图G V E 是 个有向图 它具有如下特性 图中的结点被划分成k 2个不相交的集合Vi 1 i k 其中V1和Vk分别只有一个结点s 源点 和t 汇点 图中所有的边均具有如下性质 若u Vi 则v Vi 1 1 i k 且每条边均附有成本c u v 从s到t的一条路径成本是这条路径上边的成本和 多段图问题 multistagegraphproblem 是求由s到t的最小成本路径 证明最优化原理对多段图成立 假设s v2 v3 vk 1 t是一条由s到t的最短路径再假设从源点s开始 已作出了到结点v2的决策 因此v2就是初始决策所产生的状态如果把v2看成是原问题的一个子问题的初始状态 解决这个子问题就是找出一条由v2到t的最短路径这条最短路径显然是v2 v3 vk 1 t如果不是 设v2 q3 qk 1 t由v2到t的一条更短路径 则s v2 q3 qk 1 t是一条比路径s v2 v3 vk 1 t更短的由s到t的路径 这与假设矛盾 因此最优性原理成立 一 多段图问题的最优化原理证明 二 求解多段图问题的动态规划算法 1 递推公式法 多段图向前处理的算法 设P i j 是一条从Vi中的节点j到汇点t的最小成本路径 COST i j 表示这条路径的成本 根据向前处理方法有 边的成本 例子中5段图的实现计算步骤 COST 4 9 4COST 4 10 2COST 4 11 5 COST 3 6 min 6 COST 4 9 5 COST 4 10 7COST 3 7 min 4 COST 4 9 3 COST 4 10 5COST 3 8 min 5 COST 4 10 6 COST 4 11 7 COST 2 2 min 4 COST 3 6 2 COST 3 7 1 COST 3 8 7COST 2 3 min 2 COST 3 6 7 COST 3 7 9COST 2 4 min 11 COST 3 8 18COST 2 5 min 11 COST 3 7 8 COST 3 8 15 COST 1 1 min 9 COST 2 2 7 COST 2 3 3 COST 2 4 2 COST 2 5 16 例子中5段图的计算步骤 在计算每一个COST i j 的同时 记下每个状态 结点j 所做出的决策 即 使c j l cost i 1 l 取最小值的l值 设它为D i j 则可容易地求出这条最小成本路径 D 3 6 10D 3 7 10D 3 8 10D 2 2 7D 2 3 6D 2 4 8D 2 5 8D 1 1 2 设这条最小成本路径是s l v2 v3 vk 1 t 12 则可得知 v2 D 1 1 2 v3 D 2 D 1 1 D 2 2 7和v4 D 3 D 2 D 1 1 D 3 D 2 2 D 3 7 10所以最短路径的结点序列为 s 2 7 10 t 2 图上作业法 1 逆向法 12 1 2 正向法 1 12 假如由一家配送中心 DistributeCenter 向两个用户A B送货 配送中心到两客户的最短距离分别是L1和L2 A和B间的最短距离为L12 A B的货物需求量分别是Q1和Q2 且 Q1 Q2 小于运输装载量Q 图1节约法基本原理示意图 如果改用一辆车对两客户进行巡回送货 则只需一个车次 总路程为 如果配送中心分别送货 那么需要两个车次 总路程为 5 3节约里程法 一 问题的提出 利用里程节约法确定配送路线的主要出发点有 1 配送方的运输能力 2 配送方与客户之间的距离和各客户之间的相对距离 3 制定使配送车辆总的周转量达到或接近最小的配送方案 6 用户 30 需求量 10 两点之间距离的距离 利用节约里程法求出最优配送路线 假设配送中心的车辆运力足够 每辆车的载重极限为70t 3 具体问题 第一步计算配送中心到客户间的最短距离 画出距离表 第二步 根据最短距离表 利用节约法计算出用户间的节约里程 并由大到小排列 编制节约里程顺序表 第二步 根据最短距离表 利用节约法计算出用户间的节约里程 并由大到小排列 编制节约里程顺序表 节约里程顺序表 第三步根据节约里程顺序表和配送中心的约束条件 绘制配送路线 1 选择最节约里程的路径 3 4 约束条件 50 20 70 二者不能在与其他客户共线 在上表中去掉与3 4相关的路径 2 选择下一条节约里程的路径 5 6 40 60 70 二者不能共线 3 选择下一条节约里程的路径 1 2 30 40 70 二者不能在与其他客户共线 在上表中去掉与1 2相关的路径 4 无可选的节约里程路径 客户5 6只能单独送货 总路径 DC 3 4 DCDC 1 2 DCDC 5 DCDC 6 DC 总路程 7 3 8 185 6 6 176 6 125 5 10 节约里程 12500 节约法的缺点 1 利用节约法选择配送路线过于强调节约路程 而没考虑行程中的时间因素 在许多情况下 时间更能决定物流配送的成本与服务质量 2 利用节约法选择配送路线不能对客户的需求进行灵活多变的处理 客户的需求倾向于个性化 小批量 多品种 多批次 而节约法更适合需求稳定或是需求的时间不紧迫 这显然不能满足现代多变得市场环境 3 节约法计算的配送路线并不一定是总路程最短 有一个徒步旅行者 其可携带物品重量的限度为a公斤 设有n种物品可供他选择装入包中 已知每种物品的重量及使用价值 作用 问此人应如何选择携带的物品 各几件 使所起作用 使用价值 最大 这就是背包问题 类似的还有工厂里的下料问题 运输中的货物装载问题 包装箱内货物码放等 5 4背包问题 货物配载问题 设xj为第j种物品的装件数 非负整数 则问题的数学模型如下 用动态规划方法求解 令fk y 总重量不超过y公斤 包中只装有前k种物品时的最大使用价值 其中y 0 k 1 2 n 所以问题就是求fn a 其递推关系式为 当k 1时 有 例题 求下面背包问题的最优解 解 a 5 问题是求f3 5 所以 最优解为X 1 1 0 最优值为Z 13 5 50 1背包问题 给定n种物品和一个背包 物品i的重量是wi 其价值为vi 背包的容量为C 背包问题是如何选择装入背包的物品 使得装入背包中物品的总价值最大 如果在选择装入背包的物品时 对每种物品i只有两种选择 装入背包或不装入背包 即不能将物品i装入背包多次 也不能只装入物品i的一部分 则称为0 1背包问题 在0 1背包问题中 物品i或者被装入背包 或者不被装入背包 设xi表示物品i装入背包的情况 则当xi 0时 表示物品i没有被装入背包 xi 1时 表示物品i被装入背包 根据问题的要求 有如下约束条件和目标函数 问题归结为寻找一个满足约束条件 并使目标函数达到最大的解向量X x1 x2 xn 0 1背包问题可以看作是决策一个序列 x1 x2 xn 对任一变量xi的决策是决定xi 1还是xi 0 在对xi 1决策后 已确定了 x1 xi 1 在决策xi时 问题处于下列两种状态之一 a 背包容量不足以装入物品i 则xi 0 背包不增加价值 b 背包容量可以装入物品i 则xi 1 背包的价值增加了vi 这两种情况下背包价值的最大者应该是对xi决策后的背包价值 令V i j 表示在前i 1 i n 个物品中能够装入容量为j 0 j C 的背包中的物品的最大值 则可以得到如下动态规划函数 V i 0 V 0 j 0 1 表明 把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包 得到的价值均为0 第一个式子表明 如果第i个物品的重量大于背包的容量 则装入前i个物品得到的最大价值和装入前i 1个物品得到的最大价值是相同的 即物品i不能装入背包 第二个式子表明 如果第i个物品的重量小于背包的容量 则会有以下两种情况 1 如果把第i个物品装入背包 则背包中物品的价值等于把前i 1个物品装入容量为j wi的背包中的价值加上第i个物品的价值vi 2 如果第i个物品没有装入背包 则背包中物品的价值就等于把前i 1个物品装入容量为j的背包中所取得的价值 显然 取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解 第一阶段 只装入前1个物品 确定在各种情况下的背包能够得到的最大价值 第二阶段 只装入前2个物品 确定在各种情况下的背包能够得到的最大价值 依此类推 直到第n个阶段 最后 V n C 便是在容量为C的背包中装入n个物品时取得的最大价值 为了确定装入背包的具体物品 从V n C 的值向前推 如果V n C V n 1 C 表明第n个物品被装入背包 前n 1个物品被装入容量为C wn的背包中 否则 第n个物品没有被装入背包 前n 1个物品被装入容