（电工理论与新技术专业论文）基于双向搜索免疫遗传算法的变价格物资的库存优化.pdf

圭些垄茎堡主堂堡垒圭 ! ! ! ! 竺! o p t i m a li n v e n t o r yc o n t r o lo fv a r i a b l ep r i c em a t e r i a lb a s e d o nd o u b l e d i r e c t i o n - s e a r c h i n gi m m u n eg e n e t i ca l g o r i t h m a b s t r a c t w i t ht h es t u d i e do b j e c to fs o m em a t e r i a lw h o s ep r i c ec h a n g er e g u l a r l yw i t ht i m e ， w i t ht h eb a c k g r o u n do ft h eo p t i m a li n v e n t o r yc o n t r o lo fat y p eo fm i l i t a r ym a t e r i a l ，a v a r i a b l ep r i c i n gi n v e n t o r yc o n t r o lm o d e li se s t a b l i s h e di nt h i sa r t i c l e t h eo b j e c to ft h e m o d e li sm i n i m i z i n gt h ec o s t t h ed e c i s i v ev a r i a b l e sa r eo r d e r i n gt i m e sa n do r d e r i n g i n t e r v a l s ，t h em o d e li san o n l i n e a rp r o b l e mw i t hr e s t r i c t i o n c o n d i t i o n s a n dt os o l v et h e p r o b l e m ，n o to n l yt h ev a l u e so fd e c i s i v ev a r i a b l e s ，b u ta l s ot h en u m b e ro fd e d i s i v e v a r i a b l e sa n dt h em a p p i n gr e l a t i o nb e t w e e no b j e c ta n dd e c i s i v ev a r i a b l e sh a v et ob e w o r k e do u t t og e tt h eo p t i m a lc o n s e q u e n c eo ft h em o d e l ，ad o u b l e d i r e c t i o n - s e a r c h i n gi m m u n e g e n e t i ca l g o r i t h mi sa d v a n c e d t h el e n g t ho ft h ec o d eo ft h ea l g o r i t h mi sv a r i a b l e ，a n d j u s ta c c o r d i n gt ot h ed i f f e r e n tl e n g t h s ，i n d i v i d u a l ss p a c ea n dp o p u l a t i o ns p a c ea r ed i v i d e d i n t os e v e r a ls u b i n d i v i d u a l s s p a c e s a n d p o p u l a t i o ns p a c e s a n dt h e d o u b l e d i r e c t i o n s e a r c h i n g i ss e a r c h i n gf r o mt h et w od i r e c t i o n so fg e n ea n dl e n g t h f o l l o w i n gt h i s ，t h ec o n c e p t i o n so fe q u a ll e n g t h c r o s s o v e ra n du n e q u a ll e n g t h - c r o s s o v e r o p e r a t o r sa r ea d v a n c e d t h eu n e q u a ll e n g t h c r o s s o v e ro p e r a t o rc a ne x e c u t et h ef u n c t i o n o fo p t i m a ll e n g t hs e a r c h i n g ，w h i l et h ee q u a l - c r o s s o v e ro p e r a t o rf i n i s ht h eo p t i m a lg e n e s s e a r c h i n g a n dt h ef o r m e ri so p e n ，i tr u nb e t w e e n t w od i f f e r e n ts u b s p a c e s ，b u tt h el a t t e r r u ni nac l o s e ds u b s p a c e e x a c t l yw i t ht h et w oo p e r a t o r s ，t h ed o u b l e d i r e c t i o n s e a r c h i n g i sr e a l i z e d a b o u tt h ec o n s t r i c t i o nc o n d i t i o n s ，c o n c e p t i o no fi m m u n i t yi su s e d w i t h i m m u n ei d e n t i f i c a t i o na n di n j e c t i n gb a c t e r i n ，m a p p i n gr e l a t i o nf r o mf i n i t ea r e at o o p t i m a ls o l u t i o ni se s t a b l i s h e d t h u s ，t h ew a y so fs e a r c h i n go p t i m a ls o l u t i o ni se n l a r g e d ， a n di ti sp o s s i b l et h a te v e nt h es o l u t i o n sf a rf r o mt h eo p t i m a ls o l u t i o nc o u l db em a p p e dt o o p t i m a ls o l u t i o n t h em a r k o vc h a i nm o d e lo ft h ed d s i g ai se s t a b l i s h e d ，a n dt h e c o n v e r g e n c eo ft h ed d s i g a i sp r o v e di nt h ea r t i c l e i na r t i c l e ，d d s i g ai su s e dt os o l v et h ea c t u a li n v e n t o r yp r o b l e ma b o u tat y p eo f m i l i t a r y , a n dt h ec o n s e q u e n c es h o wt h a td d s i g a c a nd i m i n i s ht h ei n v e n t o r yc o s tf u r t h e r , c o n s e q u e n t l y , e c o n o m i cb e n e f i tw i l lb ea c h i e v e d i i i 东北大学硕士学位论文a b s t r a c t k e y w o r d s ：v a r i a b l epr i c e ；o p t i m a li n v e n t o r y ；g e n e t i ca l g o r i t h m ：u n e q u a lc r o s s o v e r ； i v 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰 写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示谢意。 学位做作者獬：瓮 日期：。w 衫z 留 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文 的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文 第一章引言 第一章引言 1 1 库存问题的研究概况 1 - 1 1 库存问题发展史 1 9 1 5 年，f h a r r i s 对商业中的库存问题进行了研究，建立了一个简单的确定性数 学模型，并求得最优解。但他的工作并未引起重视，1 9 3 4 年，r h w i l s o n 重新得出 j h a r r i s 的公式，现在称为e o q 或w i l s o n 公式，这是库存模型中的一个普遍使用的 公式。 二次大战后，研究人员对随机性、多阶段以及非平稳的库存模型进行了广泛的 研究。模型中考虑到了需求的随机性、非平稳性、供货滞后的随机性以及多阶段多 品种多级的库存管理系统等，使用的工具有随机过程、动态规划、马氏决策过程以 及其他一些运筹学方法。同时由于计算机的发展，使得库存进入计算机管理的时代， 使库存理论在实践中应用更为方便和广泛。 从研究发展上讲，a r r o w 2 1 等人的文章及d v o r e t z k y 3 1 等人的文章为现代库存 理论奠定了基础。而a r r o w 在1 9 5 8 年主编的库存与生产领域的数学理论研究一书， 提炼了生产库存问题中的数学问题，从此以后，库存论成了运筹学中的一个独立分 支。 1 1 2 现代库存管理 关于现代库存管理，j i t 、m r p 和e r p 是学术界讨论和关注的焦点。 j i t ( j u s ti nt i m e ) 系统是2 0 世纪7 0 年代日本创造的一种库存管理和控制的现代 方法，其基本思想是适时地将生产需要的物资正确地运达生产场地。j i t 系统要求企 业的供、产、销各环节紧密配合，大大降低了库存，从而降低了成本，提高生产的 效率和效益。 早期的m r p ( m a n u f a e t u r i n gr e s o u r c e sp l a n n i n g ) 是基于物料库存计划管理的生 产管理系统。m r p 系统的目标是：围绕所要生产的产品，应当在正确的时间、地点、 按照规定的数量得到真正需要的物料。 7 0 年代，m r p 经过发展形成了闭环m r p ( c l o s e dl o o pm r p y _ 生2 产计划与控制系 】 东北大学硕士学位论文 第一章引言 统，其基本原理是将企业产品中的各种物料分为独立物料和相关物料，并按时间段 确定不同时期的物料需求，基于产品结构的物料需求组织生产，根据产品完工日期 和产品结构规定生产计划，从而解决库存物料订货与组织生产问题。m r p 以物料为 中心的组织生产模式体现了为顾客服务、按需定产的宗旨，计划统一且可行，实现 了对生产的闭环控制，比较经济和集约化。 8 0 年代，在闭环m r p 的基础上产生了m r p i i 。m r p i i 进一步从市场预测、生产 计划、物料需求和库存控制延伸到产品销售的整个生产经营过程以及与之有关的所 有财务活动中，形成一个面向整个企业一体化的系统。这些系统在统一数据环境下 工作，从而使企业能够进行迅速、准确、高效的管理。 9 0 年代以来，m r p i i 经过进一步发展完善，形成了目前的企业资源计划 e r p ( e n t e r p r i s er e s o u r s ep l a n n i n g ) 系统。与m r p i i 相比，e r p 除了包括和加强了m r p i i 各种功能之外，更加面向全球市场，功能更为强大，所管理的企业资源更多，支持 混合生产方式，管理覆盖面更宽，并涉及了企业供应链管理，从企业全局角度进行 经营与生产计划，是企业的综合集成经营系统。 1 1 3 变价格库存问题的研究现状 取得经济效益是库存管理的目的，孺库存物品价格的变化直接影响到经济效益， 因此，围绕价格有变化的物品的库存管理而开展的研究成为一个热点问题。k y l e y l i n t 4 1 针对对于不同时间到达的顾客，销售商可以制定不同的商品价格以期获得最 大的利润的情况，建立了一个相继动态价格模型，并使用渐近优化启发式策略对模 型求解，该方法不依赖于顾客到达分布的假设，从而拓宽了模型的应用范围。s u d h i r a s h a h 5 j 等研究了库存价格和销售价格都发生随机波动的情况。s t e f f e nj o r g e n s o n 6 1 等研究了需求依赖于商品价格和库存的情况，将库存分为中心仓库和零售仓库两级， 并在e 0 q 公式基础上求取了最优解。y a s u oa d a c h i t 7 】等和y u nz e n gw a n g t 8 】等都研究 了仓库积压物品价值发生贬值的情形，前者建立了有损耗物品的库存模型，并说明 了它是马尔可夫过程。后者则建立了有限有效期的物品，随着库存时间的延长，价 格发生打折的库存模型，并给出最优解。p e n g s h e n gy o u l 9 1 研究了通过调节服务性产 品的价格来增加销量，以取得最大利润的模型。p l a b a d i l o 】研究了二级销售商在有 促销打折时的库存模型。y o u h u ac h e n j 等研究了( s ，s ) 模型中，需求随机且对价格敏 感，固定费用提高则s 下降情况下，如何动态地制定价格和库存策略。李乃雄【l2 】研究 了具有线性变价格物资的库存优化模型。这些围绕价格变化丌展的库存优化研究更 2 东北大学硕士学位论文 第一章引言 统，其基本原理是将企业产品中的各种物料分为独立物料和相关物料，并按时间段 确定不同时期的物料需求，基于产品结构的物料需求组织生产，根据产品完工日期 和产品结构规定生产计划，从而解决库存物料订货与组织生产问题。m r p 以物料为 中心的组织生产模式体现了为顾客服务、按需定产的宗旨，计划统一且可行，实现 了对生产的闭环控制，比较经济和集约化。 8 0 年代，在闭环m r p 的基础上产生了m r p i i 。m r p i i 进一步从市场预测、生产 计划、物料需求和库存控制延伸到产品销售的整个生产经营过程以及与之有关的所 有财务活动中，形成一个面向整个企业一体化的系统。这些系统在统r 数据环境下 工作，从而使企业能够进行迅速、准确、高效的管理。 9 0 年代咀来，m r p l l 经过进一步发展完善，形成了目前的企业资源计戈i e r p ( e n t e r p r i s er e s o u r s e p l a n n i n g ) 系统。与m r p i i 相比，e r p 除了包括和加强t m r p i i 各种功能之外，更加面向全球市场，功能更为强大，所管理的企业资源更多。支持 混合生产方式，管理覆盖面更宽，并涉及了企业供应链管理，从企业全局角度进行 经营与生产计划，是企业的综台集成经营系统。 1 1 3 变价格库存问题的研究现状 取得经济效益是库存管理的目的，而库存物品价格的变化直接影响到经济效益， 因此，围绕价格有变化的物品的库存管理而开展的研究成为一个热点问题。k y l e y l i n 针对对于不同时间到达的顾客，销售商可以制定不同的商品价格以期获得是 大的利润的情况，建立了一个相继动态价格模型，并使用渐近优化启发式策略对模 型求解，该方法不依赖于顾客到达分布的假设，从而拓宽了模型的应用范围。s u d h i r a s h a h 5 】等研究了库存价格和销售价格都发生随机波动的情况。s t e f f e nj o r g e n s o n 6 】 等研究了需求依赖于商品价格和库存的情况，将库存分为中心仓库和零售仓库两级， 并在e 0 q 公式基础上求耿了最优解。y a s u oa d a c h i l 7 等6 1 y u nz e n gw a n g 8 】等都研究 了仓库积压物品价值发生贬值的情形，前者建立了有损耗物品的库存模型，并说明 了它是马尔可夫过程。后者则建立了有限有效期的物品随着库存时间的延长，价 格发生打折的库存模型，并给出最优解。p e n g - s h e n g y o u l 9 1 研究了通过调节服务性产 品的价格来增加销量，以取得最大利润的模型。p l a b a d l l 0 研究了二级销售商在有 促销打折时的库存模型。y o u h u ac h e n 等研究了( s ，s ) 模型中，需求随机且对价格敏 感，固定费用提高, l i s 下降情况下，如何动态地制定价格和库存策略。李乃雄【”】研究 了具有线性变价格物资的库存优化模型。这些围绕价格变化丌展的库存优化研究更 了具有线性变价格物资的库存优化模型。这些围绕价格变化开展的库存优化研究更 2 东北大学硕士学位论文 第一章引言 加符合实际生产和销售的需要，已经带来了巨大的经济效益。 1 2 问题的提出 1 2 1 库存优化的重要性及其在军事工作中的意义 为了维持正常的生产、经营、军事活动，人们需要一定数量的储备资源来支持。 工厂为了能够连续生产，需要储存一定的原材料或半成品；零售商为了满足顾客的 需求，要有足够的库存商品；银行为了进行正常的营业，需要一定的货币金额进行 周转：同样道理，军队为了维持战斗力和满足战备训练需要，也必须贮备一定的军 用物资。因此，库存问题是人类社会在政治、经济、军事等领域中普遍存在着的。 库存即是指维持生产、经营、军事等各项活动中所需的备用物品。库存的存在 有其一定的必然性和目的性，它有助于物流系统的合理化、平衡供求方面的关系、 预防需求和订货周期的不确定性，在某些关键领域起到缓冲、调节的作用。然而库 存也需要投入大量的资金。有资料指出，一家典型的美国公司约有1 ，3 的流动资产用 于库存投资。因此，若能通过合理的库存管理使库存量即使减少很小的百分比，其 经济效益也将是十分显著的。1 9 9 7 年美国的企业和公司花费8 6 2 0 亿美元用于库存、 生产策略与控制管理上。专家们断言：1 9 9 4 年，美国食品杂货业如采用更加有效的 生产与库存系统的管理策略，可至少节省3 0 0 亿美元开支，约占美国当年食品杂货业 总费用的1 0 1 ”】。 库存不仅是企业管理中重要的组成部分，也是遂行军事活动和战备训练的关键 之一。军用物资的库存管理自古以来就受到军事统帅们的重视。如中国古代兵法有 云：“三军未动，粮草先行”，又如“深挖洞、广积粮”曾是明代开国皇帝朱元璋的战 略方针，后来它也成为毛泽东同志战略思想的一部分。这些都说明了军用物资的储 备是否充足对于军事行动和战略决策有着举足轻重的影响。当然，现代军事理论的 发展对军用物资的库存狭策问题提出了更高的要求。受国际和国内大环境的影晌， 我军在战略和战备物资的存贮策略上也不断地进行着改革和调整。从国际形势来看， 一方面邓小平同志通过科学地分析国际局势的发展，明确提出“和平和发展是当今世 界的两大主题”。另一方面霸权主义和强权政治有新的表现。超级大国奉行实力政策， 单边主义倾向突出，或借反恐谋霸权，推行新一轮战略扩张，争夺和控制对世界地 缘政治格局具有重要影响的战略要地和资源重地【4 1 。这决定了近几十年军队的物资 装备的库存主要是为满足战备需要和训练消耗，物资装备的需求是连续稳定的。从 3 东北大学硕士学位论文第一章引言 国内形势分析，由于我国己步入市场经济轨道，部分装备已山原来的专供特供向半 市场化转变，有些军用物资的订购也与市场紧密联系起来，同时我国是爱好和平的 发展中国家，在军费上的投入有限，因此怎样制定最优的军用物资库存控制方法， 使得既能满足部队需求，又能节约军费丌支成为一个重要课题。 1 2 2 选题的背景 本文正是以某型军用飞机的某种航材订购和库存为背景( 出于保密需要，下文中 称之为a 型飞机的b 型航材) ，研究怎样制定b 型航材的库存控制方法，才能达到既满 足正常飞行训练消耗，又能最大限度地节约开支的目的。已知b 型航材有如下特点： ( 1 ) b 型舷材为a 型飞机上的关键部件，若有缺失，则飞机不能飞行，故如库存不 足，将直接影响飞行训练和任务的完成。 ( 2 ) b 型航材为高消耗航材，飞机起降1 0 1 5 次后，陔航材必须报废，然后a 型飞 机要装备上新的b 型航材后才能继续飞行。 ( 3 ) 因为全年的飞行训练计划是在年初制定的，而且训练量尽量服从均匀分布， 故对b 型航材的消耗量也是连续均匀的。 ( 4 ) b 型航材价格舔贵，每件价格可达万元。 ( 5 ) b 型航材的生产和试车受气候因索影响大，导致它的成本在不同季节差异很 大，可达2 0 。因此b 型航材的订购价格随购买月份的不同而呈现出有规律的较大幅 度的变化。 ( 6 ) 一旦订购b 型航材，就要发生一笔较为昂贵的固定费用。 ( 7 ) 库存的b 型航材必须投入一定的人员、场地和费用进行管理、警戒和维护。 从以上特点可以看出：b 型航材的库存在保证飞行训练正常进行和降低购买和 保管费用，节约经费方面起着突出的作用。通过研究合理的控制策略和控制方法， 将b 型航材的订购次数、订购价格和库存控制在合理范围内，从而既能保证战备训 练需要，又能大量节约经费，是一项非常有意义的工作。 1 2 3 问题的提出 尽管b 型航材是一类军用物资，但它的订购和存贮与其它货物没有本质的不同， 所以库存优化的研究成果仍适用于b 型航材的库存优化。在过去的一段时间里，人们 对以货物的订购量和订货周期为变量的库存优化问题做了大量的研究，这些研究对 改善企业的经营管理、节约资金、提高企业的经济效益做出了非常大的贡献，但是 ，4 东北大学硕士学位论文 第一章引言 这些研究多集中于价格恒定的单周期模型或是订购次数已知的多周期模型上，而现 实生活中，商品或产品的价格并不是恒定的，而是受供求关系、自然条件、政策面 或其它可预知因素的影响呈现出有规律的价格变化。例如在北方的建材市场，由于 冬季的施工量大大低于其它季节，对建材的需求量为全年最低，这样的供求关系会 使得建材的价格在冬季降低，有些建材零售商会利用这时的差价补充自己的库存。 国内饲料市场也会由于农产品产量的季节性变化而使饲料价格出现波动。美国联邦 政府每个财政年度的开始( 每年1 0 月1 日) 会使国债市场的价格达到顶点，而每年的 所得税最后支付日( 4 月1 5 日) 又会使价格大幅度降低。可见价格的有规律性变化涉 及到工业、农业、金融业等各个领域。 b 型航材价格波动对b 型航材的库存优化同样有着不可忽视的影响。一方面，航 材管理部门希望在b 型航材价格最低的时候，大量购入。另一方面，航材管理部门 又要尽量降低库存，因为库存航材占用了大量资金，又需要大量人力去管理，并且 库存量大还可能造成航材的腐败缺损。因此如果能够根掘市场的情况和航材的特点 制定合理的阶段性( 如一年) 订购和存贮计划，就能太嘱度她减少订购和存贮费用 的投入。在这种情况下，若在有固定订货周期或是订货次数的基础上研究库存的优 化，而不能“随机应变”地改变订货时间间隔或调整订货次数，则有可能会在高价位 时不得不购进货物，且不可能完全周密地考虑到订货间隔、订货次数和库存量之间 的协调，使库存航材既能满足训练消耗，又能使订货费、可变购买费用及库存费用 三者之和最小。尽管文献 4 】_ 一【1 2 概述了近几年围绕物料价格变化而开展的库存优 化的研究已经取得了一些成果，但是这些研究或过于集中于库存物资的销售价格的 变动，或要求购买价格里线性变化，因此不可避免地存在着局限性，不利于解决论 文涉及的库存优化问题。 基于此，论文以b 型航材的库存优化问题为背景，研究怎样在物资购买价格呈 现出规律性变化的情况下，确定其最优订货次数、每次订货的订购量以及每次订货 到下一次订货的时间间隔，从而使得在满足战备需要的条件下，b 型航材的订货、 购买和存贮三者的总费用最小。 1 3 遗传算法和免疫算法的产生与发展 1 3 1 遗传算法的产生发展 遗传算法是模拟自然界生物进化过程的一类自组织、自适应人工智能技术。它 一5 东北大学硕士学位论文 第一章引言 模拟达尔文的自然进化论与孟德尔的遗传变异理论，具有坚实的生物学基础。 早在二十世纪五十年代，一些生物学家就着手于计算机模拟生物的遗传系统。 1 9 6 2 年，美国h o l l a n d 教授提出了监控程序的概念【”】，即利用群体进化模拟适应性 系统的思想，引进了群体、适应值、选择、交叉、变异等基本概念。1 9 6 7 年，h o l l a n d 教授的学生j d b a g l e y 首次提出“遗传算法”一词【l ”。1 9 6 8 年，h o l l a n d 教授提出模式 理论。1 9 7 5 年，h o l l a n d 教授的专著自然界和人工系统的适应性全面地介绍了 遗传算法，系统地阐述了遗传算法的基本理论和方法，确认了选择、交叉和变异等 遗传算子，为遗传算法奠定了基础。从此，遗传算法在理论研究和实际应用方面都 迅速发展。h o l l a n d 教授以二进制字符集构成的代码串作为染色体表示实际问题，这 种编码方法对所要解决的问题类型几乎没有任何限制，所需要的信息只是每个染色 体的评价值。这种使用简单编码和选择机制的算法能解决复杂问题，通过对染色体 进行迭代处理，发现并保存优秀的染色体，进而逐步发现问题的最优解，这些思想 就是遗传算法的理论雏形。1 9 7 5 年之后，遗传算法作为函数优化器不但在各个领域 得到广泛应用，而且其基本理论也得到了丰富和发展，g o l d b e r g 】、g r e f e n s t e t t e 1 8 1 等许多学者对遗传算法理论的基本框架和遗传算子进行了构建和改进，并将遗传算 法分别应用于工程设计、自动控制、经济金融、博弈问题、机器学习等诸多领域。 1 9 8 0 年，s m i t h 提出了使用变长位串的概念【1 9 1 。在一定程度上为以后的遗传规划奠 定了基础。1 9 8 9 年j o h n r k o z a 将遗传算法用于处理不定长树形字符串或一组程序， 提出了遗传规划( g e n e t i cp r o g r a m m i n g ) 的概念，以后他先后出版了两本遗传规划的专 著 2 0 】【2 l 】，说明了遗传规划能成功地解决一类复杂问题，为基于符号表示的函数学习 问题增添了一个强有力的工具。 随着遗传算法研究和应用的不断深入，1 9 8 5 年，在美国召开了第一届遗传算 法国际会议，即i c g a ( i n t e m a t i o n a lc o n f e r e n c eo ng e n e t i c a l g o r i t h m ) 。从1 9 9 9 年起， i c g a 和g p 的系列会议合并为每年一次的遗传和进化国际会议( g e n e t i ca n d e v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e ，g e c c o ) 。类似会议在欧洲也每隔一年举办一 次。频繁的国际学术活动集中反应了遗传算法的学术意义和应用价值，遗传算法成 为多学科、多领域的重要研究方向。 1 3 2 免疫算法的产生发展 在生命科学领域中。人们己经对遗传与免疫等自然现象进行了广泛而深入的研 究。六十年代，b a g l e y 和r o s e n b e r g 等先驱在对这些研究成果进行分析与理解的基 6 东北大学硕士学位论文 第一章引言 础上，借鉴其相关内容和知识，特别是遗传学方面的理论与概念，并将其成功应用 于工程科学的某些领域，收到了良好的效果。自然免疫系统是复杂的自适应系统， 它有效地使用多种机制防御外部病原体。免疫系统的主要作用是识别身体内的细胞。 人工免疫系统是模仿自然免疫系统功能的种智能方法。 遗传算法是一种具有“生成+ 检测”( g e n e r a t e a n d t e s t ) 的迭代过程的搜索算法。从 理论上分析，迭代过程中，在保留上一代最佳个体的前提下，遗传算法是全局收敛 的。然而，在对算法的实施过程中不难发现两个主要遗传算子都是在一定发生概率 的条件下，随机地、没有指导地迭代搜索。因此它们在为群体中的个体提供了进化 机会的同时。也无可避免地产生了退化的可能。在某些情况下这种退化现象还相当 明显。另一方面，每一个待求的实际问题都会有自身一些基本的、显而易见的特征 信息或知识。然而遗传算法的交叉和变异算子却相对固定。在求解问题时，可变的 灵活程度较小。这无疑对算法的通用性是有益的，但却忽视了求解问题时问题的特 征信息的辅助作用，特别是在求解一些复杂问题时，这种“忽视”所带来的损失往往 就比较明显了。 基于这一思想，将免疫概念及其理论应用于遗传算法。在保留原算法优良特性 的前提下，力图有选择、有目的地利用待求问题中的一些特征信息或知识来抑制其 优化过程中出现的退化现象，这种算法称为免疫算法( i m m u n e a l g o r i t h m 。i a ) 。这种 算法较好地解决了遗传算法中的退化问题。 f a r m e r 等人【22 j 于1 9 8 6 年首先给出了基于免疫网络学说的免疫系统的动态模型， 并探讨了免疫系统与其它人工智能方法的联系，开始了人工免疫系统的研究。1 9 9 6 年1 2 月，在同本举行了免疫性系统的因际专题讨论会，首次提出了“人工免疫系统” 的概念。从此以后，人工免疫系统的研究进入了发展兴盛期，d d a s g u p t a 等认为人 工免疫系统已经成为人工智能领域的理论和应用研究热点，丁永生等人1 2 3 】也较早地 开展了这方面研究。1 9 9 7 年和1 9 9 8 年，i e e es y s t e m s 、m a na n dc y b e r n e t i c s 国际会 议还组织了专题讨论，并成立了“人工免疫系统及应用分会”。这对更多的有关人工 免疫系统的研究成果的出现起到了极大的推动作用。人工免疫系统在控制【2 4 m 5 1 规划 2 6 1 、组合优化f 2 7 】、图像处理1 2 8 m 2 铫、故障诊断f 3 。4 1 等领域得到了广泛应用。 1 。4 论文主要工作 论文主要工作有三方面内容： ( 1 ) 针对问题的背景，即购买价格随时间变化的一类物资，建立了一个以订货次 一7 东北大学硕士学位论文 第一章引言 数、订货间隔和订货量为控制变量，以总的库存费用最小为目标的变价格非周期库 存模型。 ( 2 ) 针对变价格非周期的库存模型，提出了双向搜索免疫遗传算法 ( d o u b l e d i r e c t i o n s e a r c h i n gi m m u n e - g e n e t i ca l g o r i t h m ( d d s i g a ) ) 。该算法以每次订 货到下次订货之间的时间间隔为编码对象，是变长度编码，编码长度表示了全年的 订货次数，因此其长度随问题的变量个数而变化，每个染色体的每组基因位依次表 示每次订货到下一次订货的时间间隔，订货次数越多，编码越长。然后根据码长的 不同，将种群空问划分为若干个子空i l 丑j ，并通过两种交叉算子一一异长交叉和等长 交叉，既在每个子空间中并行进行遗传搜索，同时又在整个神群空间中进行最优子 空间的搜索，从而实现了从码长和基因位两个方向同时进行的“双向”搜索，算法通 过迅速找到最优子空间，从种群空间中淘汰其余子空间，来达到使搜索范围迅速缩 小，最快地找到最优解的目的。 在上述算法的基础上，论文还结合了免疫算法，形成双向搜索免疫遗传算法。 目前关于免疫算法与遗传算法相结合的研究多集中在通过免疫识别来较快地清除某 些抗原( 适应度不高的个体) ，使算法收敛或以更快的速度收敛上面。而本文将免疫 识别和注射疫苗应用于对部分不可行解的处理上，亦可收到较好的效果。论文还给 出了算法的收敛性的证明，并对算法的性能做了简要分析。 ( 3 ) 利用几组典型数据对双向搜索免疫遗传算法进行仿真，结果表明算法能收敛 到最优解。使用算法对本文所研究的具体问题进行库存优化，并与历史数据对比， 表明基于双向搜索免疫遗传算法的变价格非周期库存优化在实际应用中能够达到预 期的效果。 1 5 论文框架 论文具体章节安排如下： 第一章：引言。介绍论文所研究问题的提出、问题的背景、论文研究的意义及 重要性，简述了论文的基本思路和章节的安排。 第二章：变价格非周期库存模型。先对经典的库存模型做了综述，然后针对论 文所研究背景建立一个变价格非周期库存模型。 第三章：遗传算法和免疫算法。介绍了遗传算法与免疫算法的基本思想和基本 概念。 第四章：双向搜索免疫遗传算法。针对第二章建立的模型，提出一种双向搜索 8 东北大学硕士学位论文 第一章引言 免疫遗传算法，详细阐述了算法的相关概念以及选择、交叉、变异算子的设计，利 用马尔可夫链理论对算法的收敛性加以证明，并在最后，对算法的性能做了分析。 第五章：实例与仿真。根据具体问题，介绍了免疫算法的免疫识别和疫苗提取 方法。对论文所提出的模型求出最优解，蜕明算法能取得可观的经济效益。利用双 向搜索免疫遗传算法对几组典型数据进行求解，进步说明了算法能够收敛到最优 解。 第六章：结论与展望。对论文的结果简要总结，并分析了下一步的发展方向。 最后是参考文献、致谢。 东北大学硕士学位论文 第二章变价格非周期库存模型 第二章变价格非周期库存模型 2 1 库存问题的相关概念 库存问题有供一存一销三个环节，通过订货或安排生产，以及到货后的库存， 最后由销售来满足顾客的需求，在这样个系统中，决策者通过控制订货时间的间 隔以及订货数量来调节系统的运行，使得在某种准则下系统的性能达到最优。 一个库存系统有如下的几个要素。 ( 1 ) 需求。需求是库存系统的输出，在一定时间内的需求量可以通过对历史数据 的统计处理获得。或者基于对市场销售最的调查与分析来获得。需求量可以是一个 常量，也可以是随机的。 ( 2 ) 补充供应。货物的不断补充是使得库存系统能够运行下去的基础，它可以通 过订货或者安排生产来获得，影响库存系统运行的因素是订货与到货之间的时间滞 后，理想的简单情形是瞬时交货，这是对供货或者生产能力非常大的一种近似，通 常把滞后时问考虑成常数或者非负随机变量，滞后现象使得库存问题变得复杂化。 ( 3 ) 缺货处理。出于需求或者供货滞后时间可能具有随机性，因此缺货是可能发 生的，对于缺货处理通常采取以下两种方式处理：对于未能完全满足的需求，其不 足部分在订货到达后立即补上，或者对未能全部满足的需求量不再补货供应。 ( 4 ) 盘点方式。一类是连续盘点，任何时刻对于库存量都已知；另类是周期盘 点，在盘点时刻才知道库存水平。不同的盘点方式会影响库存决策。 ( 5 ) 订货策略。订货策略给出何时补充库存，以及补充多少的一个方案，常用的 有以下几种。 ( s ，q ) 策略：连续盘点，一旦库存水平降至s 立即订货，订货量为q ； ( s ，s ) 策略：连续盘点，一旦库存水平降至s 立即订货，订货量为s s ；这种订货 策略适用于缺货损失较低，库存成本较高的物品。 ( r ，n q ) 策略：周期盘点，一旦库存水平降n r 或r 以下，就定购q 数量的商品， 其中n q 是保证定购后的库存超过r 的最小整数，q 是最小订货批量。 ( r ，s ，q ) 策略：周期盘点，一旦库存水平降至s 或s 以下立即订货，订货量为q ； ( r ，s ，s ) 策略：周期盘点，一旦库存水平降至s 或s 以下，订货量为s s 。 ( 6 ) 费用。库存系统中的费用通常包括订货费、库存费和缺货损失费。 ，1o 东北大学硕士学位论文第二章变价格非周期库存模型 订货费的通常形式是：c ( z ) = 乞+ c z ；三? a 其中，z 表示进货量，c 表示货物 单价或单位生产费用，c z 表示可变订货费，k 表示固定订货费用。 ( 7 ) 目标函数。目标函数是选择最优策略的准则。常见的准则是平均费用以及折 扣费用，最优策略选择是使费用函数最小或者利润函数最大。 综上所述，对于单个物品的库存问题的完整描述需要知道需求、供货滞后时间、 缺货处理方式、费用结构、目标函数、以及采取的库存策略，决策者通过何时订货、 订多少货来对系统实施控制。 2 2 基本库存模型 库存模型由许多因素组成，不同情形的组合使得库存模型分类很多。 本节主要从需求的确定性和随机性来分，将库存模型分为两大类：确定性库存 模型和随机性库存模型。 2 2 1 确定性库存模型 最基本的确定性库存模型研究的是一种比较简单的情况，即需求是连续的、确 定的，并且以固定的速率到达，不允许缺货，当库存降至零时，可以立即得到补充， 每次订货量不变，每次的订货费用也不变，单位库存费用不变。模型的目标要求长 期运行下单位时间中的平均费用最低，如下式所示。 鸭n 擀q ) + 聃州 ( 2 ，) 模型中最优订货批量为： q =( 2 2 ) 其中，c l 为单位库存成本，r 为需求到达速率，g 为订货费。这就是著名的经济订 货批量( e o q ) 公式，也叫w i l s o n 公式。该公式在实际中经常被采用，公式简单并且稳 定性好，订货量偏离最佳订货量q 时费用的相对变化不大，即不敏感。 在保持模型确定性需求的基础上，人们研究了各种推广模型。如对于不允许缺 货，生产需一定时间，不能立即补足的模型，最优订购批量为q = 、i l c 坚, ( p 翌- r ) ( p 为 生产速度) ；对于生产时间很短，允许缺货但缺货需补足的模型，最优订购批量为 1 1 犀 东北大学硕士学位论文 第二章变价格非周期库存模型 q = j 2 c ! r c j + c z 。( c 2 为缺货损失) ；对于允许缺货，缺货需补足，生产需一定时 间的模型，最优订购批量为g = | v 2 g c i r p e rc , c 2 + g + 。此外，一些学孝分别从不同 的角度对经济批量模型进行了扩展研究，得到了一系列推广模型。 2 2 2 随机性库存模型 由于随机库存模型更为贴近现实情况，因而也更为人们所重视企业界和研究 者的投入使得随机库存理论得到了很大的发展。 随机库存的基本模型是单周期模型即报童模型( n e w s b o ym o d e l ) 。传统的报童模 型考虑的是单周期、单产品的库存管理问题。最初研究的对象主要是报纸、新鲜食 品等有效期很短的产品，考虑的目标是期望总收益最大。目标要求包括可变订货成 本和销售收入，如下所示： 峄 _ c q + p e 知( 孝) m 艘胁( 亭蚓 ( 2 3 ) 模型中最优订货批量由下式得到：i c = j ；妒( 善) 鸳。 其中c 为单位可变订货成本；p 为单位销售收入；q 为订购量；善是代表需求的随 机变量。 后来的研究不但考虑可变订货成本、缺货成本和库存成本，而且也考虑固定订 货成本，目标要求是期望的总费用最小，如下所示： 哩n c q + 矗r ( q 一跏( 孝) 硝+ p e ( 善一q ) 妒皓埘 ( 2 4 ) 其中c 为单位订货成本；p 为单位缺货成本；h 为单位库存成本；q 是订货量；善是 代表需求的随机变量。 求解该模型可得到最优订货量的函数表达式：巾( q ) ：旦芸，其中左边表示需 、7 口+ 门 求的累积分布。 报童模型研究的是离散时间的库存问题，对于连续时间的库存管理问题，可以 采用( s ，s ) 策略。关于( s ，s ) 策略的研究比较多，如b a s y a m 等研究了随机型提前期具有 服务水平约束下的( s ，s ) 库存管理系统的优化问题，提出了求解的算法，并通过大量 东北大学硕士学位论文 第二章变价格非周期库存模型 的算例对不同服务水平和提盼期服从不同分布的情况进行了比较。 2 3 变价格物资非周期库存一般模型 货物的价格和库存的成本决定了货物的订购和存贮策略。考虑到所研究的是价 格随不同月份呈现出有规律的变化的物品的库存问题，若能在不限定订货周期和订 货次数的情况下建立相应的库存模型，并制定其订购和存贮策略，就能够节约大量 的资金，这是很有意义的。还要说明的是，这旱所讲的价格变化，既包括购买价格 的变化，又包括库存价格的变化。 在建立模型之前，先对下面符号作以说明： n ：订货次数； k ：订货阶段标号，即第k 次订货； g ：次订货费用，假设为固定不变的，与订货量无关； 只：第k 次订货时的货物的价格，是随时问而变化的常量； 2 ：第k 次订货的订货量； r