原材料订购多目标优化模型及求解算法_左霞.pdf

1引言随着我国市场经济的持续发展，原材料的订购成本控制越来越被生产企业关注，合理的订购不仅能够降低企业经营风险，还能提高企业竞争能力。实际采购中，订购方案除了追求最经济的目标外，还需要考虑对多种原材料的选择、供货商的数量等等，因此优化一个多目标的原材料订购方案尤为必要。多目标优化在工程应用、推荐系统、物流配送、路径规划等各个领域中都普遍存在，但是多个性能目标之间常存在不可比较性和相互矛盾的现象，不一定在所有目标上都有最优解，即所有目标函数必须达到最优。文献1用遗传算法得到Pareto最优解后用TOPSIS方法生成最优方案；文献2求出Pareto最优解集供决策者和设计者选择；文献3对多目标优化模型进行求解，得到了Pareto前沿解集，提出了基于加权相对距离的决策方法，得到了最优生产方案；文献4给出了对已有的Pareto最优解用R方法评价，求得最佳折中方案。解决多目标优化的方法有MOEA算法、NSGA-II算法、粒子群算法，以及其他智能算法如遗传算法、蚁群算法、人工蜂群算法等。其中普通的粒子群算法的粒子初始位置、更新速度都是连续函数，与之对应，位置和速度更新均为离散值的算法是离散PSO算法。BPSO是在离散粒子群算法基础上，约定位置向量、速度向量均由0、1值构成；BPSO有很强全局搜索能力，但不能收敛于全局最优值，且随着算法迭代搜索随机性越来越强，缺乏后期的局部搜索能力。NSGA-II算法的特点是Pareto最优解分布更均匀，因此，本文采用这两种算法对实例进行仿真实验，并对结果进行对比。2问题描述及其数学模型的构建2021年高教社杯数学建模竞赛C题，是以某生产企业订购与运输原材料为背景的竞赛题。其中制定的订购方案，有要求供应商最少、有要求最经济，以及对于多种原材料有选择性地订购等。在实际订购中，决策者往往希望这三个要求都能满足，故本文把这三问稍加改变和聚合，得到如下问题，其表述为：某生产企业所用原材料总体可分为A，B，C三种类型，该企业每年按48周安排生产，需要提前制定24周的原材料订购，即根据产能要求确定需要订购的原材料供应商（称为“供应商”）和相应每周的原材料订购数量（称为“订货量”）。该企业每周的产能为2.82万立方米，每立方米产品需消耗A类原材料0.6立方米，或B类原材料0.66立方米，或C类原材料0.72立方米。由于原材料的特殊性，供应商不能保证严格按订货量供货，实际供货量可能多于或少于订货量。为了保证正常生产的需要，该企业要尽可能保持不少于满足两周生产需求的原材料库存量，为此该企业对供应商实际提供的原材料总是全部收购。原材料的采购费用对企业的生产收益有直接的影响，实际中A类和B类原材料的采购单价分别比C类原材料高20%和10%。三类原材料运输和储存的单位费用相同。现在有50家最重要的供应商，决策者希望选择最少的供应商，根据前5年的供货量制定未来24周每周最经济的原材料订购方案，同时该企业为了控制生产成本，计划尽量少地采购A类和尽量多地采购C类原材料。原材料订购多目标优化模型及求解算法左 霞封汉颍（南通理工学院 基础教学学院，江苏南通226000）摘要：原材料的订购是企业按时完成生产的一个关键因素，决策者制定方案时，不仅要考虑满足生产量，还要考虑购买费用，对多种原材料的选择，以及对供货商数量的要求。针对这类问题，建立了多目标的0-1规划模型，并利用V-B PSO 算法和NSG A-II算法进行了求解。实验证明，NSG A-II算法求得到Pa r e t o 最优解分布更均匀，而V-B PSO 算法速度更快。最后用R 方法进行评价，计算出各个备选订购方案的综合得分，综合分最高的方案被认为是最佳折中的订购方案。关键词：原材料订购；多目标0-1规划；V-B PSO 算法；NSG A-II算法；R 方法中图分类号：TH128文献标识码：A文章编号：1008-6609(2022)10-0077-05作者简介：左霞（19 76），女，江苏镇江人，讲师，研究方向为运筹学与控制论。电脑与电信算法研究-77DOI:10.15966/ki.dnydx.2022.10.0162.1建立目标函数的模型根据决策者订购的要求，按照不同的优化目标建立相应的模型，具体分为以下三步：第一步，把选择最少的供应商作为目标函数。设dij表示第i个供货商在第j周的供货量，由dij构成了一个供货量的矩阵D。设决策变量为xij，当xij=1，代表第i个供货商在第j周被选上，当xij=0，代表第i个供货商在第j周没有被选上，由xij构成决策变量矩阵X，现在建立如下数学表达式：z1=min(iTsgn(j=1Nxij)(1)其中T为所有供货商对应的指标集，N表示计划订购的总周次，sgn(x)为符号函数。第二步，把原材料订购费用作为目标函数，求最经济的订购方案。设mij表示第i个供货商在第j周的订货量，因为该企业对供应商实际提供的原材料总是全部收购，如果第i个供货商在第j周被选上，则mij=dij，如果第i个供货商在第j周没有被选上，则mij=0。根据前面的决策变量xij的定义，有mij=xijdij。因为三类原材料运输和储存的单位费用相同，不妨设运输单位费用为a,储存的单位费用为b，假设a+b与原材料C的单价比是1:1，若原材料C的单价为1，原材料A和原材料B的单价分别为1.2和1.1，则M家供货商在N周内原材料订购的费用为：z2=min(1.2+1)iTAj=1Nmij+(1.1+1)iTBj=1Nmij+(1+1)iTCj=1Nmij=min(2.2iTAj=1Nxijdij+2.1iTBj=1Nxijdij+2iTCj=1Nxijdij)其中TA，TB，TC是原材料A，B，C三类供货商集合分别对应的指标集。第三步，以尽量少地采购A类和尽量多地采购C类为目标函数。通过增加权重转化成如下的单目标函数：z3=min(100.6iTAj=1Nxijdij+10.06iTBj=1Nxijdij+0.10.72iTCj=1Nxijdij)2.2写出约束条件因为总的供货量会在转运的过程中有损耗，根据近5年8家转运商的相关数据，平均的损耗率是1%，所以这里假设生产企业的接收量是供货量的99%。根据题目的说明，为了保障企业正常生产的需要，该企业要尽可能保持不少于两周生产需求的原材料库存量，企业每周产量是28200立方米，两周是56400立方米。按%的损耗率得到约束条件为：99%j=1kiTAdij0.6xij+iTBdij0.66xij+iTCdij0.72xij56400+28200(k-1)=28200(k+1)xij=0,1i=1,2,M;j=1,2,N;k=1,2,N(2)2.3整体模型为了简华模型，设aij=dij0.6iTAdij0.66iTB,则dij0.72iTCz2=min1.32iTAj=1Nxijaij+1.386iTBj=1Nxijaij+1.44iTCj=1Nxijaij(3)z3=min10iTAj=1Nxijaij+iTBj=1Nxijaij+0.1iTCj=1Nxijaij(4)记A=(aij)MN，设B=28484.82,28484.83,28484.825T，B中第j个分量为Bj。再记A=(A1,A2,AN),X=(X1,X2,XN)，则约束条件表达式(2)整理为：j=1k(AjXj)Bjk=1,2,Nxij=0,1i=1,2,M;j=1,2,N(5)综 上，该 模 型 为 非 线 性 多 目 标 0-1 规 划 模 型：minf=min(z1,z2,z3)，其中：z1=min(iTsgn(j=1Nxij)z2=min1.32iTAj=1Nxijaij+1.386iTBj=1Nxijaij+1.44iTCj=1Nxijaijz3=min10iTAj=1Nxijaij+iTBj=1Nxijaij+0.1iTCj=1Nxijaijs.t.j=1k(AjXj)Bjk=1,2,Nxij=0,1i=1,2,M;j=1,2,N3V-BPSO算法和NSGA-II算法3.1V型二进制粒子群算法（V-BPSO）3.1.1二进制粒子群算法（BPSO）二进制粒子群算法（BPSO）最初是在1997年由J.Kenne-dy和R.C.Eberhart设计，是在离散粒子群算法基础上，约定位置向量、速度向量均由0、1值构成。算法流程如下：初始化粒子位置：按一定策略，生成二进制编码；第i个 粒 子 的 位 置xi=(xi1,xi2,xiN)T，速 度 为vi=(vi1,vi2,viN)T。速度更新公式：电脑与电信算法研究-78vid=vid+c1rand1()(Pbestid-xid)+c2rand2()(Gbestd-xid）(6)位置的更新公式：概率映射方式，采用sigmoid函数将速度映射到0,1 区间作为概率，这个概率就是粒子下一步取值为1的概率；s(Vid)=11+exp(-Vid)(7)位置变化的绝对概率：当前位置为0变化为1，当前为1变化为0，这二者被称为绝对变化；概率表示为：xid=1if rand()s(Vid)0otherwise(8)公式(6)中，i=1,2,M，M为该群体中的粒子总数，其中为非负的惯性因子，学习因子c1和c2是0,2之间的常数；rand1()和rand2()是介于0,1之间的随机数；Pbestid是粒子i在第d维的个体极值点的位置；Gbestd是整个种群在第d维的全局极值点的位置。3.1.2V型二进制粒子群算法（VBPSO）BPSO有很强全局搜索能力，但不能收敛于全局最优值，且随着算法迭代搜索随机性越来越强，缺乏后期的局部搜索能力，因此有学者对BPSO算法进一步改进，Seyedali Mirjali-li，Andrew Lewis提出二元粒子的S型和V型传递函数5，通过引入一个新的传递函数族来改进BPSO算法，在本文中，采用的位置更新函数公式为：T(x)=|(x)/1+x2(9)xki(t+1)=(xki(t)-1randf3f1，利用公式（12）转化成相应的权重。通过目标权重与备选方案的相应权重相乘后再求和，得方案12345678f20.062190.050450.073130.152360.083100.058760.049100.05386f30.052020.066730.049100.045920.047910.053860.073130.05876综合分0.043790.042920.047860.082710.052010.042790.044230.04205方案9101112131415权重f20.045920.052020.046860.101570.047910.066730.056060.45205f30.152360.062190.101570.046860.083100.050450.056060.30137综合分0.066670.042260.051790.060040.046700.045370.04224表1各方案综合得分电脑与电信算法研究-80到备选方案的综合得分。其中方案4的综合得分最高，认为它是最佳折中的订购方案，综合得分见表1。6结语本文基于生产企业订购原材料的三个需求目标和该企业对供应商实际提供的原材料总是全部收购的特点，建立原材料订购方案的模型，最后转化成非线性的0-1规划问题。该模型采用V型的二进制粒子群算法（V-BPSO），引入一个新的函数更新粒子的位置，改进粒子群算法容易陷入局部最小的缺点，同时也提高收敛速度。用该算法对原材料订购模型求解，找到Pareto前沿，用R方法对备用方案评价，得到最佳折中解。因此该模型具有一定的理论价值和实践价值。参考文献：1张鼎森基于改进遗传算法的多目标优化配矿方法研究D 沈阳：东北大学，2 0 172 涂兵，刘来辉，邓年春，等基于遗传算法的大跨钢管混凝土桁式拱肋多目标优化J 公路交通科技，2 0 2 1，3 8(12)：56-6 3+7 2 3 刘海亮，贾翠玲，王东辉数控加工工艺参数的多目标优化与决策算法研究J 制造技术与机床，2 0 2 1(9)：13 8 142 4R a oR V，La k s h m i R JR a n k i n go f Pa r e t o-o p t i m a ls o l u t i o n s a n ds e l e c t i n gt h eb e s t s o l u t i o ni nm u l t i-a n dm a n y-o b j e c t i v eo p t i m i z a t i o n p r o b l e m su s i n gR-m e t h o d J So f tC o m p u t i n g Le t t e r s，2 0 2 1，3：10 0 0 155M i r j a l i l i S，Le w i s A S-s h a p e dv e r s u s V-s h a p e dt r a n s-f e r f u n c t i o n s f o r b i n a r y Pa r t i c l e Sw a r mO p t i m i z a t i o n J Sw a r ma n d Ev o l u t i o n a r y C o m p u t a t i o n，2 0 13，9：1146 D e bK，A g r a w a l S，Pr a t a pA，等A Fa s t El i t i s t No n-d o m i n a t e dSo r t i n g G e n e t i c A l g o r i t h mf o r M u l t i-o b j e c t i v e O p-t i m i z a t i o n：NSG A-IIA 见：M Sc h o e n a u e r，K D e b，G R u d o l p h，等Pa r a l l e l Pr o b l e mSo l v i n gf r o mNa t u r e PPSN VIM B e r l i n，H e i d e l b e r g：Sp r i n g e rB e r l i nH e i d e l b e r g，2 0 0 0，19 17：8 49 8 58 7 近5年40 2 家供应商的相关数据，2 0 2 1高教社杯全国大学生数学建模竞赛官网EB/O L.(2 0 2 1-9-9).h t t p：/w w w.m c m.e d u.c n/h t m l _c n/n o d e/4d 7 3 a 3 6 c c 8 8 b 3 5b d 48 8 3 c 2 7 6 a f e 3 9d 8 9 H t m l Raw Material Ordering Scheme Based on Multi-objective Optimization ModelZUO XiaFENG Han-ying(Nantong Institute of Technology,Nantong 226000,Jiangsu)Abstract:Abstract:The ordering of raw materials is a key factor for enterprises to complete production on time.When making plans,decisionmakers must not only consider meeting the production volume,but also consider the purchase cost,the selection of various raw ma-terials,and the requirements for the number of suppliers.Aiming at this kind of problem,this paper establishes a multi-objective 0-1programming model,and uses V-BPSO algorithm and NSGA-II algorithm to solve.Experiments show that the Pareto optimal solu-tion obtained by the NSGA-II algorithm has a more uniform distribution,while the V-BPSO algorithm is faster.Finally,the R meth-od is used for evaluation,and the comprehensive score of each alternative ordering scheme is calculated,and the scheme with thehighest comprehensive score is regarded as the best compromise ordering scheme.Keywords:Keywords:raw material ordering;multi-objective 0-1 programming;V-BPSO optimization;NSGA-II genetic algorithm;R-method电脑与电信算法研究-81