资源描述：
《鲍姆尔-沃尔夫算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、鲍姆尔-沃尔夫算法目录例题解析概述12概述Part1鲍姆尔—沃尔夫法此方法以运输问题为基础，同时也考虑非线性的费用（存储费用）函数；在一定的物流服务水平下，根据不同的算法和模型求出物流成本最低的最优解或满意解，以获得选址方案。运输费用与运输距离（运输量和运输单价一定时）的关系是线性的，但是流通中心的管理费在工作效率提高时，需采用边际费用递减的非线性费用函数来描述。鲍姆尔—沃尔夫网点布局方法是针对图1所示的网络结构提出的一种启发式方法。这种方法在求解过程中只需要运用一般运输规划的计算方法即可，大大降低了计算成本。不仅如此，鲍姆尔法还较好地解决了网点存储费用非线性的问题。图1鲍姆尔法用非线性
2、函数来描述网点的存储费用，如图2所示。从图2中的曲线可以看出，随着网点规模的增大，存储费用曲线变得平坦，即费率下降,这是符合实际情况的。但是非线性函数的引入，使计算求解变得复杂。为了使问题简化，鲍姆尔法在迭代求解过程中对非线性函数采取分段线性化的做法，即在每一次迭代过程中用边际成本表示存储费率，边际成本表示在一定网点规模下的单位货物存储费用，因此可与单位运输费用直接相加。经过这样处理后，就可直接利用运输规划的方法计算求解。下面的讨论中，假定网点的存储成本与规模的关系为：(3)式中：为网点K的存储成本，为网点规模，以为常系数。设网点K某一规模时的边际成本为，有(4)所以，如果知道网点K的规
3、模，那么此规模下的存储费率也就容易按公式(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)中与的关系，不难求得各网点的中转
4、量(k=1,2,…,q)，即一组网点设置方案。2.2计算网点的边际成本以表示网点规模的大小，按公式(4)计算此规模下的边际成本(存储费率)。(k=1,2,…,q)(6)2.3求改进方案用代替,与求初始方案的过程完全一样，求出一组新方案。2.4比较新旧方案，确定最终解将新方案与旧方案进行比较，如果两个方案完全相同，则新方案为最终解；否则返回步骤二，反复进行步骤二至四，直到与相同时为止，即获得满意解。鲍姆尔法每次迭代使系统总成本有单调下降的趋势，因为迭代过程中采用了线性规划这种系统优化的方法，每次迭代的结果是在使系统总费用最小的前提下寻求新的更好的布局方案。换言之，该方案是沿着仓储成本下降的
5、方向寻找最佳方案，直至存储成本不能再下降。或者存储成本下降会引起运输成本的上升而使总成本增大时，获得最终解。因此，应该相信这一最终解是我们所要求得到的。例题解析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）备选网点D
6、1D2D3D4D5存储费用边际成本备选点至需求点运费率（4-4）`解：设CK为仓库边际成本，因网点的吞吐量为2dK，则（4-6）为便于观察分析，由4-2、表4-3和表4-4汇成费率表，如表4-5所示。费率表（4-5）表4-5左上方表示资源厂与备选点之间的运费率，右下方一块表示备选网点与需求点之间的运费率，左下方一块的对角线上为备选网点存储库费率的边际成本。由此可以看出，欲求资源厂i经过备选网点K到资源点j的总费率时，只需将上述三块中相应的三项费率求和即得。下面我们按鲍姆——沃尔夫法计算步骤迭代求解。【步骤一】求初始方案开始时，我们不需要考虑存储成本，可以假设备选网点的边际成本均为0。从表
7、4-5中可找出资源厂到需求点之间的最小费用及其相应的中转网点，如表4-6所示。（4-6）表中斜线下方数字为中转网点序号，上方数字为经该网点中转时资源厂与需求点之间的最小费率。由表4-6所示的费率与资源厂的资源量和需求点的需求量构成供需平衡的运输规划模型，如图4-7所示。（4-7）求解出此运输问题，即可求得表4-8所示的结果。表中斜线下方数字为中转网点序号，上方数字为中转掉运量。（4-8）由表4-8查得各网点的中转量后，代入公式（4-
