第六章 物流系统模型及分析.ppt

第六章物流系统模型及分析 主要内容 1 线性规划法 LinearProgrammingMethod 2 运输调配法 TransportationProgrammingMethod 3 指派问题 AssignmentProblem 4 威门法 WimmertMethod 5 动态规划法 DynamicProgrammingMethod 引言 本章将介绍设备位置规划和物料移动规划的量化分析方法 由于这些方法都涉及到应用数学 特别是运筹学 OperationResearch 目前已经有专著进行介绍 这里仅就量化方法的构架予以介绍 并通过设备配置或物料移动有关的例子加以说明 最后对这种技术在实际运用上进行评估与比较 为日后从事这方面分析 研究时选择采用的依据 一般而言 计量方法通常是衡量效果的一个基准 例如运输距离 TrafficDistance 运输作功或运输成本等 然而这些方法并不保证一定能求得最优解 但可提供较优解 量化方法的型式 量化方法的型式 确定型 Deterministic 概率型 Probabilistic 线性确定型 Linear deterministic 非线性确定型 Nonlinear deterministic 线性概率型 Linear probabilistic 非线性概率型 Nonlinear probabilistic 6 2线性规划法 LinearProgramming 线性规划是作业研究中最常用的量化分析技术 用在资源或能量有限时 用数学方法进行最佳的调配 以达到最小成本或最大效益的要求目标 线性规划可应用在寻求非自动化或输送带式物料搬运系统的最优化 一 模型的假设条件 1 确定性 deterministic 在模型中有关的技术状况 资源及策略均为已知而不是呈现某种概率分配 例如特定场所或区域有良好的储存和仓储位置 搬运距离 成本或时间为确定 可做为衡量的基准等 2 线性 linearity 模型中的目标函数与约束结构型式均为线性函数 即各种成本 距离等参数关系为一次关系 3 可分割性 divisibility 模型中的决策变量假定为连续性变量 因此具有分割性 即模型中变量的解不一定是整数 而可以是小数 4 非负性 Nonnegativity 模型中的变量不能有负值 变量的值最小为零 5 比例性 Proportionality 模型中变量的边界贡献或单位成本是固定常数 并不因使用量的变动而变动 二 线性规划模型 1 目标函数或 2 结构约束条件或 3 非负约束条件以上各符号意义如下 Z 目标函数值 cj 目标函数系数 计有n个 指第j个决策变量的权重贡献或单位成本 xj 决策变量 计有n个 aij 技术系数 指第j个决策变量所需投入的第i种资源的数量 bi 常数 指第i种资源的数量 共有m种 三 线性规划法例 某公司现有类似功能的设备在甲 乙两地 下游的两个部门A与B 各设备的产量 部门的需求量以及设备至部门间的单位成本资料如下 试求在运输成本最低的目标下 各设备与各部门间的运输量应为多少 三 线性规划法例 解 根据以上资料建立线性规划模式如下 S t 根据线性规划的方法 可将此模型变成下列形式 S t 三 线性规划法例 S t 初解表 三 线性规划法例 x11进 x5出 x22进 x4出 三 线性规划法例 基变量的解值均大于或等于零 目标函数的系数均小于或等于零 因此 此表为最优解表 最优解为 x11 10 x12 10 x22 30 四 线性规划法的实用评估 线性规划能广泛地应用在物料分 Distribution 设施位置选择 Location 设备配置 Allocation 产品组合 ProductMix 设备更新 Replacement 和模型规划上 然而在工厂布置上 线性规划缺乏真实的衡量单位 在大多数的问题上 时间与成本是我们要求最优化的值 但在实际运用上 这些值往往已被任意选取 以致造成以时间与成本来当作衡量标准是否最合适的问题 6 3运输调配法 TransportationProgramming 运输调配是针对单一商品自不同供应点分配到不同需求点 而其总运输成本为最低 成本可以用距离 时间或金额来表示 1 2 3 1 2 3 4 本问题的型式仅允许自供运点连至目的地 假定有m个供应点 每一供应点i可以供应的数量为ai个 i l 2 m 需求点有n个 每一需求点需要bj个 j l 2 n 则运输成本有m n个 每一个分别代表自每一供应点运一个至每一需求点的成本 运输问题的目标在用完供应点的物料而满足需求点的物料需求 且其总运输成本为最小 一 运输调配模型 1 供应点的总供应量必等于需求点的需求量 2 由任一供应点运至各需求点的总量必等于此一供应点总量 i l 2 m 3 每一需求点的需求量必由各供应点运来加以完全满足 j 1 2 n 4 对所有的i和jxij 0 5 目标成本函数cij表示供应点i运至需求点j每一个的成本 xij表示由i运至j的个数 由上面模型可知 总共有m n个决策变量 有m n个约束条件 但这m n个约束条件因为有的关系 因而真正只有m n 1个约束条件是独立的 换言之 在m n个约束条件中只要有m n l个成立的话 剩下来的那个约束条件式也必然成立 因此 只要取m n个约束条件中任意m n 1个来求解即可 也就是说将会得到m n l个非负的基变量解值 二 运输调配法例 假设厂内物料搬运系统使用相同的叉车和容器 由甲 乙 丙三个储存区运至A B C D四个工作区 假设容器由叉车一次搬运一个 且搬运后不再可用 下表所示各区的容器储存量 需求量和搬运单位成本 试在最低的目标下决定由各储存区至各工作区的运送量 运输问题成本矩阵 运输问题可用西北角法 最低成本法 简捷法 Simplexmethod 或差额法来求得最优解 本例以差额法求解 此法的进行是分别计算各行各列中成本最小与次小间的差额 再从各差额中找出最大者 从差额最大的那行或那列填起 只要某行或某列满足了 即将该行或该列划掉 再重新计算各行各列中未划线地方的最小与次小成本差额 直到各行各列均满足为止 二 运输调配法例 总运输成本为10 5 8 25 12 5 10 25 7 15 8 25 865 6 4指派问题 AssignmentProblem 指派问题为线性规划的特殊情况 用以指派n个工作到n部设备 每一个工作对每一部设备的效益为已知 其目标在使每一部设备仅能指派一个工作 而其目标的效益为最佳 一 指派问题模型 约束条件为 由指派问题的模型可知 指派问题是运输问题的一个特例 因为ai bj 1 且m n 则 ai bj n 所以在矩阵表中各行各列均只有一个xij l 且同一行或同一列中均只有一个xij l 其他的xij均等于零 故知在n n的指派问题中 共有n n个约束条件 但只有n个是相互独立的 也只有n个基变量解值为l 换言之 另外有n个基变量退化了 二 指派问题解题的原理 对于指派问题的解法 早有学者 K W Kuhn 提出一套方法 称之为匈牙利法 HungarianMethod 匈牙利法是以最小平衡问题为基础 至于不是最小平衡的问题 仍应先化成最小平衡之后再用匈牙利法来解 其基本道理与矩阵减化法是相似的 三 指派问题解题的流程 四 指派问题例 布置设计师拟增三部新设备A B C到现有布置上 叉车负荷大小是每次仅能一个单位 车子移动受限于通道而为直角方向 图中的X Y Z为新机器的可能候选位置 而l 2 3 4 5为现有机器位置 现有机器位置 方块 与新机器候选位置 圆圈 四 指派问题例 距离数据 矩阵 交通数据 矩阵 效益矩阵 效益矩阵 交通矩阵 距离矩阵 Hungarian法求解 减去该行的最小值241减去该行的最小值96减去该行的最小值236 各行均已出现了 0 再观察列 就是第一列还未出现 0 第一列减去该列的最小值102 最佳布置可以出来 A到Y B可以到X或Z C可以分派到Z 因此 其最佳的布置可行解为A机器指派到Y位置B机器指派到X位置C机器指派到Z位置 五 指派问题的实用评估 指派法对于设备布置与物料搬运问题是具有相当的实证价值 而且数学运算也很容易 也可处理设备与候选位置数目不相等以及限制指派位置的问题 然而 指派问题的处理也有其极限 它无法处理设备非为独立的状况 因为若两设备间有直接的物料搬运相连接 在模型建立时无法结合其需求而设定在模型中 指派问题的另一个缺点是缺乏考虑空间有效利用或限制空间大小的能力 它可能使得小设备被指派到大空间而导致地面空间的浪费 对此缺点有一部分可由成本矩阵的数字来控制 但不完全 6 5威门法 WIMMERTMethod 威门法是指派问题的另一种处理方法 此法是由R J WIMMERT于1957年所提出 也是针对n个部门 或设备 放置于n个区域的布置组合问题 其主要着眼点是要使部门间的距离与运送量的乘积为最小 一 威门法的假设条件 WIMMERT模型的假设条件 1 各个部门的位置是可互换的 2 二个部门间的距离与方向无关 亦即由A部门到B部门的距离与由B部门到A部门的距离是一样的 3 搬运成本与距离成正比例 二 WIMMERT方法简介 WIMMERT的处理方式先将各区域间的搬运距离B1 B2 Bt以单调非减 MonotonicNondecreasing 的次序排列 而各部门间的搬运重量A1 A2 At以单调非增 MonotonicNonincreasing 的次序排列 然后依据搬运距离与搬运重量做成一阶的特殊矩阵 其中t c n 2 以此一特殊矩阵作为讨论的基础 如后表所示 其中Xij Ai Bj 搬运距离与搬运重量合成的特殊矩阵 其方法是先将原来n 个可行的布置组合 透过此特殊矩阵放大为t 个解 包含了非可行解 在t 解中 先删去不可能成为最优解中一元的元素 同时亦删去n 个可行解中不可能成为最优解的布置组合 并以划记的方法求得某部门不可能放在那些位置 进而求得最佳或接近最佳的布置组合出来 三 威门法的实例 某公司新建一厂房 经过规划之后 将整个厂房划分成四个区域 位置 而且也将整个工厂的组织分成四个部门 各个位置 Location 间的距离如距离表所示的距离矩阵 D矩阵 而各个部门间的搬运量如搬运量表所示的搬运量矩阵 P矩阵 距离矩阵 D矩阵 D 搬运量矩阵 P矩阵 P 三 威门法的实例 总搬运量矩阵 由于部门间的搬运与方向无关 因而可将搬运量表的搬运量矩阵中相关的部门间的搬运作一合并 得总搬运量表 该表无方向性 L矩阵 L 合成的特殊矩阵 东北角 主对角线 3次对角线 2次对角线 1次对角线 A C在1 3B C在l 4B D在2 4A D在2 3根据上列的分配可知 部门与位置的最佳组合为 部门位置A在3B在4C在lD在2 四 威门法的实用评估 威门法对布置问题有极高的实用性 无需繁杂的计算 仅以简单划记的方法 配合特殊的矩阵即可求得最佳或接近最佳的布置方案 且其以运输作功为衡量的标准 具有代表意义 是符合实际的基准选择 尤其适合大型布置极易以计算机来求解 其缺点则由于划记的次序是依特殊矩阵的位置而非数值而定 因此其形成的布置组合为近似最佳解 并不一定是最佳解 其次 它的三个假设条件在实际运用上有时不完全符合实际情况 这也是这一方法的缺点 6 6动态规划法 DynamicProgramming 动态规划在决策上是一新的技术 它不仅牵涉的变量多 又有多个约束条件 更须考虑到这一阶段的决策对下一阶段状况的连带影响的决策技术 它与其它方法最大的不同点是以往是一个问题有n个变量的处理方法 而动态规划是处理n个问题有n个变量 一 动态规划的问题特性 动态规划方法是RichardBellman在1962年提出的 动态规划问题可以划分成数个阶段 Stage 所谓阶段可以是指不同的时期 也可以是指连续决策的不同步骤 必须根据问题的性质而作不同地划分 而且在每一个阶段均需做出决策 一旦决策制订之后便限制了后面阶段的可行方案 因此 在做决策之前应作整体的考虑 每个阶段都存在数个不同的状态 State 在任何一个状态的最佳决策与其以前所做的决策无关 是所谓的无记忆性 Memoryless 基于这一原理以及整体的考虑 动态规划问题的求解往往是采用倒推的方式来进行 也即由最后阶段开始 逐步往前面的阶段推算 二 动态规划问题的模型与求解 状态函数决策的间断程序是由有限个阶段 Stage n所构成 且每一个阶段各有不同的状态 State 第一个决策qn是发生在程序的第n个阶段 而其状态为pn 而状态pi是程序在状态pi 1 下决策qi 1的结果 其函数关系式表示如下 pi T pi 1 qi 1 报酬函数决策的程序需要有评估的基础 这种评估的基础称为报酬函数 如投资报酬率 利润 时间的节省 距离 资金及其它任何价值的衡量等 报酬函数是因变于一连串的状态和决策 表示如下 R p1 p2 pn q1 q2 qn 我们的目标是要使报酬函数为最大或最小 总报酬来自于一连串的个别决策的报酬 分别为 g1 p1 q1 g2 p2 q2 gn pn qn 基于个别决策是报酬函数的共同参数 且整体决策的总数报酬是个别报酬的总和设 则R p1 p2 pn q1 q2 qn g1 p1 q1 g2 p2 q2 gn pn qn 二 动态规划问题的模型与求解 二 动态规划问题的模型与求解 函数的方程式上式为函数方程式的一般式 则决策qn的报酬为gn pn qn 此结果使得程序由pn改变至pn l 且仅剩 n 1 阶段 而剩余 n 1 个决策的报酬必同时为状态pn l的最大值 二 动态规划问题的模型与求解 动态规划的求解动态规划的最佳性原则是不论最初的状态和决策如何 所谓最优解必是以第一个决策和状态的条件下 其余决策以