鲍姆尔沃尔夫算法ppt课件.ppt

鲍姆尔 沃尔夫算法 目录 例题解析 概述 1 2 概述 Part1 鲍姆尔 沃尔夫法此方法以运输问题为基础 同时也考虑非线性的费用 存储费用 函数 在一定的物流服务水平下 根据不同的算法和模型求出物流成本最低的最优解或满意解 以获得选址方案 运输费用与运输距离 运输量和运输单价一定时 的关系是线性的 但是流通中心的管理费在工作效率提高时 需采用边际费用递减的非线性费用函数来描述 鲍姆尔 沃尔夫网点布局方法是针对图1所示的网络结构提出的一种启发式方法 这种方法在求解过程中只需要运用一般运输规划的计算方法即可 大大降低了计算成本 不仅如此 鲍姆尔法还较好地解决了网点存储费用非线性的问题 图1 鲍姆尔法用非线性函数来描述网点的存储费用 如图2所示 从图2中的曲线可以看出 随着网点规模的增大 存储费用曲线变得平坦 即费率下降 这是符合实际情况的 但是非线性函数的引入 使计算求解变得复杂 为了使问题简化 鲍姆尔法在迭代求解过程中对非线性函数采取分段线性化的做法 即在每一次迭代过程中用边际成本表示存储费率 边际成本表示在一定网点规模下的单位货物存储费用 因此可与单位运输费用直接相加 经过这样处理后 就可直接利用运输规划的方法计算求解 下面的讨论中 假定网点的存储成本与规模的关系为 3 式中 为网点K的存储成本 为网点规模 以为常系数 设网点K某一规模时的边际成本为 有 4 所以 如果知道网点K的规模 那么此规模下的存储费率也就容易按公式 4 求得 2沃尔夫法运用步骤2 1求初始方案开始时 令各备选地址上设置网点的规模均为O 即 0 因此 k 1 2 q 上角标表示迭代次数 以下同 对所有资源点和需求点 求资源点和需求点之间的最小费用率 以表示 则i 1 2 mj 1 2 n 5 上角标 O 表示初始值 显然 由公式 5 可知由资源点i向需求点j调运物资时经过的物流网点为K 各资源点的资源量和需求点的需求量均为已知 以为运价系数构成运输模型i 1 2 mj 1 2 n表示由资源点i经网点K向需求点j调运物资的数量 由公式 5 中与的关系 不难求得各网点的中转量 k 1 2 q 即一组网点设置方案 2 2计算网点的边际成本以表示网点规模的大小 按公式 4 计算此规模下的边际成本 存储费率 k 1 2 q 6 2 3求改进方案用代替 与求初始方案的过程完全一样 求出一组新方案 2 4比较新旧方案 确定最终解将新方案与旧方案进行比较 如果两个方案完全相同 则新方案为最终解 否则返回步骤二 反复进行步骤二至四 直到与相同时为止 即获得满意解 鲍姆尔法每次迭代使系统总成本有单调下降的趋势 因为迭代过程中采用了线性规划这种系统优化的方法 每次迭代的结果是在使系统总费用最小的前提下寻求新的更好的布局方案 换言之 该方案是沿着仓储成本下降的方向寻找最佳方案 直至存储成本不能再下降 或者存储成本下降会引起运输成本的上升而使总成本增大时 获得最终解 因此 应该相信这一最终解是我们所要求得到的 例题解析 Part2 有两个资源厂A1 A2 可供资源量分别为a1 40单位 a2 50单位 有8个需求点Bj j 1 2 8 各点需求量如表4 1所示 已选定5个备选网点DK K 1 2 5 网点 存储费用和网点规模的关系为一次方根函数 其中为吞吐量 各备选网点存储费用函数以及它与源 汇点之间的运费率分别列与表 如表4 2 表4 3和4 4所示 各需求点需求量 4 1 存储费用函数 4 2 资源厂至备选点运费率 4 3 备选点至需求点运费率 4 4 解 设CK为仓库边际成本 因网点的吞吐量为2dK 则 4 6 为便于观察分析 由4 2 表4 3和表4 4汇成费率表 如表4 5所示 费率表 4 5 表4 5左上方表示资源厂与备选点之间的运费率 右下方一块表示备选网点与需求点之间的运费率 左下方一块的对角线上为备选网点存储库费率的边际成本 由此可以看出 欲求资源厂i经过备选网点K到资源点j的总费率时 只需将上述三块中相应的三项费率求和即得 下面我们按鲍姆 沃尔夫法计算步骤迭代求解 步骤一 求初始方案开始时 我们不需要考虑存储成本 可以假设备选网点的边际成本均为0 从表4 5中可找出资源厂到需求点之间的最小费用及其相应的中转网点 如表4 6所示 4 6 表中斜线下方数字为中转网点序号 上方数字为经该网点中转时资源厂与需求点之间的最小费率 由表4 6所示的费率与资源厂的资源量和需求点的需求量构成供需平衡的运输规划模型 如图4 7所示 4 7 求解出此运输问题 即可求得表4 8所示的结果 表中斜线下方数字为中转网点序号 上方数字为中转掉运量 4 8 由表4 8查得各网点的中转量后 代入公式 4 6 即可求得相应的存储费用和边际成本 如表4 9所示 4 9 4 9为初始方案 其中的中转量为网点的设置规模 该方案总成本为2499元 步骤二 第一次迭代由表4 9中的边际成本和运费率汇成新的费率表 如表4 10所示 4 10 由表4 10求得新的费用系数后 就可以建立新的运输规划模型 如表4 11所示 4 11 求解出此运输规划模型后 即可求得4 12所示的结果 4 12 由表4 12查得网点中转量后 并代入公式 4 6 即可求得相应的存储费用和边际成本 如表4 13所示 这里备选网点D3的中转量为0 所以可以从备选点中去掉 即把该点的边际成本看作 4 13 第一次迭代方案表4 13为第一次改进后的网点布局方案 方案的总成本为2362元 注 用纯运费加上存储费用 该方案与初始方案不一样 且总成本下降了137元 所以还需继续改进 步骤三 第二次迭代由表4 12中的边际成本和运输费率汇成新的费率表 如表4 14所示 4 14费率表根据表4 14求得新的费用系数 重新再建立新的运输规划模型 如表4 15所示 求解出此运输问题后 即可求得表4 16所示的结果 4 16 至此 我们可以看到4 16与表4 12所示的结果完全一样 说明方案已不能再继续得到改进 即获得最佳网点布局方案 如表4 17所示 4 17 最佳方案因此 最佳方案为建立D1 D2 D4 D5四个网点 运输方案为 A1经D1运10单位货物至B1 A1经D1运10单位货物至B1 A1经D1运10单位货物至B3 A1经D5运5单位货