分销网络设计的数学建模(2)

zijkhij pi,(i 1,2,3;j 1,2) k 1 10

zijknkj mk,(i 1,2,3;j 1,2) k 1

xk,ykl {0,1},zijk 0,( i,j,k,l);

5.2模型的求解

本模型网络线路复杂，可行解数量多，若采用传统的分支定界法，程序的时间复杂度较高。对此本文设计了遗传算法。 5.2.1 算法描述 Step1基因编码

分销中心位置及分销中心—分销点路线安排采用11个10进制数编码，前10位为1~10的随机排列，最后一位为1~3之间的一个随机整数。

该编码的前三位的数字所代表的位置作为分销中心位置k1 k2 k3，4、5位的数字所代表的位置由k1负责供货，6、7位的数字所代表的位置由k2负责供货，8、9位的数字所代表的位置由k3负责供货，最后一位数字决定第10位的数字所代表的位置由k1~k3中哪一个负责供货。

例如，编码 8 10 9 1 2 5 3 7 6 4 1的含义为：

8,9,10号位置作为分销中心，8负责1,2,4号位置的供货，9负责6,7号位置的供货，10负责3,5号位置的供货。

每次编码后，计算各分销中心的总需求量并与该分销中心的存储能力进行比较，验证编码的合理性。若所编码路线不合理，则重新编码。

分销中心位置及分销中心-分销点路线安排一经确定，各分销中心的总需求量也就确定，以工厂-分销中心过程总成本最小为目标函数，各工厂供货总量不超过其产能和供货量能达到各分销中心需求量为约束条件，建立线性规划模型，计算工厂-分销中心供货安排。 Step2适应度计算

适应度计算公式如下：

Fit

100000000

Q

其中Fit表示适应度，Q表示总成本。 对整个种群的适应度计算完成后，筛选出最低总成本，并记录下最低总成本所对应的基因。 Step3交叉

对基因1~10号位，可以随机产生两个1~10之间整数i,j，令

p mini{,j}q ,

maix，{j将两条基因p,q之间的部分进行依次对应，按照对应

规则对基因的1~10号位进行变换。

例如，对基因8 10 9 1 2 5 3 7 6 4

和基因 9 3 2 1 7 6 4 8 5 10

假定p=5, q=7，则基因的变换规则为2和7互换，5和6互换，3和4互换。变换后的两条基因（即子代）分别为

8 10 9 1 7 6 4 2 5 3 9 4 7 1 2 5 3 8 6 10

每次进行交叉后，对新基因所编码方案进行合理性检查，若方案不能满足模型的约束条件要求，则重新进行交叉。 Step4变异

所有基因按概率Pm=0.25进行变异，变异时利用随机整数确定变异点位置及变异方式（前移、后移、倒序）。 Step5选择

选择过程的生存率设定为0.99。将所有基因按适应度大小降序排列，从前至后选择原种群规模99%数量的基因组成新的种群。 Step6终止条件

算法每次运行100代后即停止。 5.2.3计算结果

将需求地4,5,9建设为分销中心，4负责6、10的货物供应，5负责3、7的货物供应，9负责1、2、8的货物供应

以上方案下总成本为：38511224元。 5.2.4计算结果分析

观测遗传算法中每一代最高适应度的大小随代数的变化如下图

图2 种群最大适应度随代数的变化

由上图可以看出，种群的最大适应度总体随代数增加而上升，可见该算法的计算过程在逐步接近模型最优解，说明算法设计是较为合理的。但最大适应度随代数有较大波动，说明算法稳定性有待提高。

§6模型评价与推广

6.1模型优点 本文对于多决策变量的复杂二级分销网络的问题提出建立统一的整数规划模型，使该最小费用模型不仅仅局限于该分销网络，具有普适性。并且，对于模型的计算没有采取传统的分支定界法，而是通过自行设计遗传算法，降低了算法的时间复杂性，使模型更加高效，使得对于数据规模更大的分销网络该模型同样适用，且可以保证计算的可操作性。 6.2模型缺点

通过遗传算法降低了模型求解的难度，但得到的该题目的分销网络设计方案 并不能保证为全局最优。而采用遍历搜索的方式，虽由于数据规模较大，需花费时间较长，但可以得到全局最优方案。

§7参考文献

[1]司守奎、孙玺菁，《数学建模算法与应用》，国防工业出版社，2011年版； [2]吴孟达，《数学建模教程》，高等教育出版社，2011年版； [3]先强，刘卫宁，《基于改进遗传算法的二级分销网络优化模型及求解》，重庆大学，2008年；