离散型配送中心选址鲍姆尔沃尔夫算法

1、离散型配送中心选址鲍姆尔沃尔夫算法1、原理所谓离散型配送中心选址，就是配送中心的地址是不能任意选择的，只能限制在预先给定的几个备选地点。在很多情况下，配送中心地址选址是有限制的，如在原有的大仓库、大货场等，还有的地点可能在自然条件不允许选用的地方等等。所以在实际应用中，大部分采用离散型模型，离散型配送中心的选址算法，更具有应用价值。鲍姆尔沃尔夫模型是一种简明的配送中心选址模型。如图1所示的是从几个工厂经过几个仓库向用户输送物资的选址模型，对此问题一般只考虑运费最小的运输规划，而鲍姆尔沃尔夫选址算法所要考虑的问题是，各个工厂向哪些仓库运输多少物资？各个仓库向哪些用户发送多少物资？然后根据物流量的

2、大小，来决定仓库的容量。 工厂(k) 仓库(i) 用户(j) k=1 2 3 . . . . . . . m 图1 鲍姆尔沃尔夫选址模型2、操作步骤1求初始解。要求最初的工厂到用户（k,j）间的运输费用相对最小，也就是说，要求工厂到仓库间的运输费率和仓库到用户间的发货费率hij之和为最小，即cki0=min(ckj0+hij)设所有的(k,j)取最小费率ckj0，仓库序号是ikj0。这个结果决定了所有工厂到用户间的费用。如果工厂的生产能力和用户的需要量已知。按希契科克运输问题求解，使费用函数cki0 xkj为最小时， xki0就为初始解。2二次解。根据初始解，仓库i的通过量可按下式计算： wi

3、0= 所有的k,j如ikj0i xkj0用通过量反过来计算仓库的可变费用：在这个阶段中，对于所有的（k,j）取下式： chj2的仓库序号设为hhj2。再次按希契科克运输问题求解，使费用函数chj2 xni为最小时，就为二次解。3n次解。设n1次的解为，则仓库的通过量如下：是n1次解得到的所使用仓库的序号。n1次解可使仓库通过量反映到可变费用上，因此求得n次解，就可得到仓库的新的通过量。4最终解。把n1次解的仓库通过量和n次解的仓库通过量进行比较，如果完全相等就停止计算；如果不等，再继续反复计算。也就是说，当=时，为最终解。3.部分程序说明3、1 输入已知条件i=5;%表示仓库的个数;j=8;%

4、表示用户的个数;k=2;%表示工厂的个数;%ckh表示最小运输费率所通过的仓库号;gcck=7 7 8 12 11; 14 12 9 6 8;%工厂仓库之间的单位运输费率;ckkbfyxs=75,80,75,80,70;%仓库可变费用系数;ckyh=5 11 3 8 5 10 11 11 14 16 8 9 4 7 4 4 10 11 3 5 2 5 9 5 15 13 9 6 7 2 10 2 9 7 3 2 6 5 12 8;ckh=ones(k,j);%工厂用户之间的中转的仓库号码;gcyh=zeros(k,j);%工厂用户之间的运输费率;3、2最小元素法求初调方案ylb=zeros(2

5、,10); %设一个2行、10列的零运量表wqgcyhwq=gcyhwq;for i=1:k+j-1 %i表示仓库个数，k表示工厂个数，j表示客户个数 min=999; for m=1:2 %m表示从第一个工厂到第二个工厂的循环 for n=1:10 %n表示十个客户的循环 if mingcyh(m,n) min=gcyh(m,n); hzb=m; zzb=n; %判断工厂到用户的运输费用是不是最小，如果是最小就把工厂m赋予hzb,用户n赋予zzb end end endmin;hzb;zzb;if gcyhwq(hzb,11)gcyhwq(3,zzb) ylb(hzb,zzb)=gcyhwq

6、(3,zzb); gcyh(:,zzb)=gcyh(:,zzb)*10000; gcyhwq(hzb,11)-ylb(hzb,zzb); gcyhwq(hzb,11)=gcyhwq(hzb,11)-ylb(hzb,zzb);%如果行中的生产能力大于需求能力，就将最小的客户所需要的需求量全部满足。elseif gcyhwq(hzb,11)=0 disp(此调运方案就是运输问题的最优解) 四、运行结果gcyh = 12 18 10 13 10 13 11 11 17 15 11 10 11 8 16 8ckh = 1 5 1 5 3 3 2 2 5 5 5 5 3 4 2 4运输平衡问题的费用表g

7、cyhwq = 12 18 10 13 10 13 11 11 40 17 15 11 10 11 8 16 8 50 10 10 10 15 5 15 10 15 90此问题是运输平衡问题ylb = 10 5 10 0 5 0 10 0 0 5 0 15 0 15 0 15u(1)+v(1)=12u(1)+v(2)=18u(1)+v(3)=10u(1)+v(5)=10u(1)+v(7)=11u(2)+v(2)=15u(2)+v(4)=10u(2)+v(6)=8u(2)+v(8)=8aa = 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0

8、 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1u = 0 -3v = 12 18 10 13 10 11 11 11jys = 0 0 0 0 0 2 0 0 8 0 4 0 4 0 8 0此调运方案就是运输问题的最优解ysf = 935ckh = 1 5 1 5 3 3 2 2 5 5 5 5 3 4 2 4ylb = 10 5 10 0 5 0 10 0 0 5 0 15 0 15 0 15ww = yesww = 2

9、0 10 5 30 25ckf = 1.5443e+003zfy = 2.4793e+003第一次运算结束=ckkbfy2 = 8 13 17 7 7gcckzf = 0 0 0 0 0 0 0 0 0 0gcckzf = 15 20 25 19 18 22 25 26 13 15gcyh = 20 25 18 20 20 21 24 21 24 22 18 17 20 15 23 15ckh = 1 5 1 5 1 4 2 4 5 5 5 5 4 4 4 4运输平衡问题的费用表gcyhwq = 20 25 18 20 20 21 24 21 40 24 22 18 17 20 15 23 1

10、5 50 10 10 10 15 5 15 10 15 90此问题是运输平衡问题ylb = 10 5 10 0 5 0 10 0 0 5 0 15 0 15 0 15u(1)+v(1)=20u(1)+v(2)=25u(1)+v(3)=18u(1)+v(5)=20u(1)+v(7)=24u(2)+v(2)=22u(2)+v(4)=17u(2)+v(6)=15u(2)+v(8)=15aa = 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0

11、0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1u = 0 -3v = 20 25 18 20 20 18 24 18jys = 0 0 0 0 0 3 0 3 7 0 3 0 3 0 2 0此调运方案就是运输问题的最优解ysf = 935ckh = 1 5 1 5 1 4 2 4 5 5 5 5 4 4 4 4ylb = 10 5 10 0 5 0 10 0 0 5 0 15 0 15 0 15ww =yesww = 25 10 0 30 25ckf = 1.4162e+003zfy = 2.3512e+003第二次运算结束=

12、ckkbfy3 = 8 13 0 7 7gcckzf3 = 0 0 0 0 0 0 0 0 0 0gcckzf3 = 23 33 25 26 25 30 38 26 20 22gcyh = 20 25 18 20 20 21 24 21 24 22 18 17 20 15 23 15ckh = 1 5 1 5 1 4 2 4 5 5 5 5 4 4 4 4运输平衡问题的费用表gcyhwq = 20 25 18 20 20 21 24 21 40 24 22 18 17 20 15 23 15 50 10 10 10 15 5 15 10 15 90此问题是运输平衡问题ylb1 = 10 5 1

13、0 0 5 0 10 0 0 5 0 15 0 15 0 15u(1)+v(1)=20u(1)+v(2)=25u(1)+v(3)=18u(1)+v(5)=20u(1)+v(7)=24u(2)+v(2)=22u(2)+v(4)=17u(2)+v(6)=15u(2)+v(8)=15aa = 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0

14、0 0 1u = 0 -3v = 20 25 18 20 20 18 24 18jys = 0 0 0 0 0 3 0 3 7 0 3 0 3 0 2 0此调运方案就是运输问题的最优解ysf = 935ckh = 1 5 1 5 1 4 2 4 5 5 5 5 4 4 4 4ylb = 10 5 10 0 5 0 10 0 0 5 0 15 0 15 0 15ww =yesww = 25 10 0 30 25ckf =03zfy = 2.3512e+003第三次运算结束五、结果分析本次课程设计主要是运用matlab软件，运用配送中心鲍姆尔沃尔夫计算方法来计算出运输费用和仓库费用，再算出总费用。多次迭代进行对比找出最优解。第一次求解：由已知条件，将工厂到仓库间单位运输费率行与仓库到用户间的单位发送费用的列一一对应相加，取其最小即为最小运费，同时注明通过的仓库号。采用位势法计算初始方案每个空格的闭合回路的检验数，经计算得知该方案的检验数均是正数，因此，该出事方案可行。第二次求解：根据初始解求第二次解。将可变费用加上已知条件的工厂到仓库见的单位运输费，同初始解的计算一样，计算出最小运输费率，根据最小运输费加上发送费结合最小元素法分配工厂向用户提供