鲍姆尔-沃尔夫算法.ppt

鲍姆尔-沃尔夫算法,目录,例题解析,概述,1,2,概述,Part1,鲍姆尔沃尔夫法此方法以运输问题为基础，同时也考虑非线性的费用（存储费用）函数；在一定的物流服务水平下，根据不同的算法和模型求出物流成本最低的最优解或满意解，以获得选址方案。运输费用与运输距离（运输量和运输单价一定时）的关系是线性的，但是流通中心的管理费在工作效率提高时，需采用边际费用递减的非线性费用函数来描述。鲍姆尔沃尔夫网点布局方法是针对图1所示的网络结构提出的一种启发式方法。这种方法在求解过程中只需要运用一般运输规划的计算方法即可，大大降低了计算成本。不仅如此，鲍姆尔法还较好地解决了网点存储费用非线性的问题。图1,例题解析,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单位货物至B4；A1经D1运5单位货物至