（运筹学与控制论专业论文）随机物流模型的建模及求解方法研究.pdf

摘要 随着科学技术的不断进步，物流管理已经由宏观管理发展到微观管理。 物流模型是实现微观管理的主要手段。物流管理包括规划、实旌与控制等几 方面。物流规划和控制领域包括：客户服务目标、设施选址策略、库存策略、 运输策略、供应链援划等，这些策略的实现依赖于物流模型的建立。物流模型 主要包括确定性模型和不确定性模型两类。不确定模型包括随机模型和模糊模 型两种，其中随机模型是本文研究的重点。通过对随机物流模型的建模和求解， 实现对物流过程的规划与控制，以确保实现企业利润最大化和给客户提供高水 平的服务的双重目标。库存一订货作为物流管理，系统的重要组成部分，也是关 键问题之一其目的是为了保证供应链运行的连续性和应付需求的不确定性。通 过合理的控制策略和控制方法，在保证生产的情况下，将库存控制在合理范围 内，从而可以减少流动资金的占用，缩短生产周期、降低成本。本文把库存 订货问题和供应链分销网络优化问题作为主要的研究对象，使用随机规划理论 进行建模，用基于随机模拟的遗传算法进行求解。 论文共分六章，第一章为绪论，介绍了物流模型的起源、发展以及研究随 机物流模型的目的及意义。第二章介绍了双层规划和随机规划的基本知识。第 三章对基于随机模拟的遗传算法进行了简单的介绍。第四章研究了随机需求情 况下向多个供应商采购的期望值模型及求解算法。第五章研究了供应链中二级 分销网络优化设计的随机规划模型及求解算法。第六章研究了及时条件下订货 策略的随机双层规划模型及求解算法。 本文的主要创新点如下：运用双层规划和随机搜划的理论与方法对物流管 理中的库存订货问题、供应商选择问题和供应链中二级分销网络的优化设计问 题进行研究，建立了基于双层规划和随机规划思想的相关模型并且使用基于随 机模拟的遗传算法对模型进行求解，给出了算例并且对计算结果进行了分析， 得出了相应的结论。 关键词：供应链，二级分销网络，订货策略，双层规划，随机瓶划，遗传 算法，随机模拟 n a b s t r a c t w i t ht h ed e v e l o p m e n to fe c o n o m ya n dt e c h n o l o g y , m o d e ml o g i s t i c s s y s t e mh a s b e e nh a v i n ga ni m p o r t a n te f f e c to nt r a d ei n c r e a s i n g l y a sak i n d o fn e w - d e v e l o p i n gs e r v i c e se n t e r p r i s e ，l o g i s t i c si sr e g a r d e da st h ea r t e r yo f n a t i o n a le c o n o m ya n dt h et h i r d p r o f i ts o u r c eb e s i d e st h el a b o r a n dr a w m a t e r i a l s t h r o u 【g ht h em a n a g e m e n t o fl o g i s t i c s ，t h ee n t e r p r i s ec a no b t a i n t h e t h i r d - p r o f i t s o u r c e w i t ht h e d e v e l o p m e n t o f t e c h n o l o g y , m i c r o - m a n a g e m e n t h a sb e c o m et h em a i nb r a n c ho f l o g i s t i c sm a n a g e m e n t l o g i s t i c sm o d e l sa r ep l a y i n g t h em o s ti m p o r t a n tr o l ei nm i c r o - m a n a g e m e n t l o g i s t i c sm a n a g e m e n ti n c l u d e sp r o g r a m m i n g , p e r f o r m i n ga n dc o n t r o l l i n g a n ds oo n l o g i s t i c sp r o g r a m m i n ga n dc o n t r o l l i n gi n c l u d ec l i e n ts e r v i c ea i m ， e s t a b l i s h m e n ta d d r e s sc h o i c es t r a t e g y ，i n v e n t o r ys t r a t e g y , t r a n s p o r t a t i o n s t r a t e g ya n ds u p p l yc h a i np r o g r a m m i n ga n ds oo n a l lo fw h i c hd e p e n d o n l o g i s t i c sm o d e l s w h i c hi n c l u d ec e r t a i nm o d e la n du n c e r t a i nm o d e l ，t h el a t t e r i st h ee m p h a s i so fm yp a p e r e s t a b l i s h i n gu n c e r t a i np r o g r a m m i n gm o d e l s a c c o r d i n gt ot h er e a lp r o b l e m sa n df i n d i n gt h eb e s ts o l u t i o n sa r em y m a i n w o r ki nt h e p a p e r a s a ni m p o r t a n tp a r to f l o g i s t i c ss y s t e m ，i n v e n t o r y c o s to f l o g i s t i c sc e n t e r si sag r e a tp e r c e n t a g e o ft h et o t a lc o s t r e a s o n a b l ei n v e n t o r y c a nk e e pp r o d u c tw e l l b a l a n c e d t h e r e f o r e ，t h ep e r i o do fp r o d u c tc o u l db e r e d u c e da n dt h ec o s tc o u l db ea l s oc u td o w n it a k et h ei n v e n t o r y - o r d e r i n g o p t i m a lp r o b l e m sa n ds u p p l yc h a i nb i l e v e ld i s t r i b u t i o n n e t w o r ko p t i m a l p r o b l e m s a se x a m p l e si nt h ep a p e h i nt h ef i r s t c h a p t e r ，t h e a i ma n d s i g n i f i c a n c eo fr e s e a r c h i n gt h e l o g i s t i c s m o d e l sa r ci n t r o d u c e d s i m p l y a sw e l la st h es o u r c ea n d d e v e l o p m e n t o f l o g i s t i c sm o d e l s ；t h e b a s i ct h e o r i e so fb i - l e v e l p r o g r a m m i n ga n ds t o c h a s t i cp r o g r a m m i n ga r ei n t r o d u c e di nt h e s e c o n d c h a p t e r ；i nt h et h i r dc h a p t e r , t h eg e n e t i ca l g o r i t h mb a s e d o nt h es t o c h a s t i c s i m u l a t i o ni si n t r o d u c e di nd e t a i l e d ；t h ee x p e c t a t i o nm o d e lo fp l a c i n g o r d e r sw i t hm u l t i s u p p l i e r su n d e rs t o c h a s t i cd e m a n di st h em a i nc o n t e n t o ft h ef o u r t hc h a p t e r i nt h ef i f t hc h a p t e r ，as t o c h a s t i cp r o g r a m m i n gm o d e l f o rb i - l e v e ld i s t r i b u t i o nn e t w o r k d e s i g n i n g i nt h e s u p p l y c h a i ni s e s t a b l i s h e da n dt h em o s to p t i m a ls o l u t i o ni sf o u n db yu s eo ft h eg e n e t i c a l g o r i t h m b a s e do ns t o c h a s t i cs i m u l a t i o n i nt h el a s t c h a p t e r , t h e s t o c h a s t i cb i l e v e lp r o g r a m m i n gm o d e lo f o r d e r i n gs t r a t e g yu n d e rj u s t i n t i m ec o n d i t i o ni st h e k e y c o n t e n t k e yw o r d s ：s u p p l yc h a i n ，o r d e r i n gp o l i c y , b i - l e v e lp r o g r a m m i n g , u n c e r t a i np r o g r a m m i n g , g e n e t i c a l g o r i t h m ，s t o c h a s t i cs i m u l a t i o n 声明 本人郑重声明：本论文的所有研究工作都是在导师一高自友教授 的悉心指导下，由本人独立创作完成。论文中所引用的已知结论均可 参见相应文献，参考文献在论文最后部分列出。特别，未经作者本人 许可，任何擅自更改、抄袭或剽窃本论文之内容的行为，都将承担相 应的学术和法律责任。 j 室銮望盔堂堡兰鱼丝塞 z 1 1 选题背景 第1 章绪论 随着经济全球化趋势的加强，科学技术尤其是信息技术突飞猛进地发展， 企业生产资料的获取与产品营销范围日趋扩大，社会生产、物资流通、商品交 易及其管理方式正在并将继续发生深刻的变革。与此相适应，被普遍认为企业 在降低物质消耗、提高劳动生产率以外的“第三利润源”的现代物流业已在世 界范围内广泛兴起。在经历了几十年触发展后，目前正在成为全球经济发展的 一个重要热点和新的经济增长点，它对于实现经济高效运行，提升企业生产和 效率，降低商品流通成本，提商商品流通效率，改善对消费者的服务，进而增 强工商企业乃至国家经济核心竞争力，调整国家和地区投资环境以及产业结构， 实现可持续发展战略，推进我国经济体制与经济增欧方式的根本性转变都具有 非常重要而深远的意义。它是一种融高新技术为一体的先进的组织方式和管理 技术。物流对于社会经济所起的作用越来越重要，它己成为一个国家和地区经 济综合实力的重要体现( r o n a l dh ，b a n o u ，2 0 0 2 ) 。 物流作为一个富有现代内涵的概念，被定义为“为了符合顾客所需要的必 要条件，所发生的从生产地到销售地的物质、服务、信息的流动过程，以及为 使保管能有效、低成本地进行而从事的计划、实施和控制行为。”进入2 0 世纪 8 0 年代以后，专业化分工进一步深化，对现代物流的研究也进一步细化，世界 各国的物流研究也进入了一个崭新的阶段。相对于经济发达国家而言，中国的 物流技术发展受整个经济发展水平不高、人们对物流的认知观念没有完全形成 等影响，尚处于发展的初始阶段，如物流设施、装备技术水平较低，物流作业 效率不高：信息技术应用水平较低，物流信息系统应用滞后；物流管理水平较 北京交通大学硕士学位论文 低，现代化程度低等。由于专业化、社会化程度不高，物流以及物流技术的发 展尚不能适应国民经济发展的需要( 宋华，胡左浩，2 0 0 0 ) 。加入w t o 将对我国物 流业的发展带来前所未有的巨大机遇；从短期来看，我国加入w t o 后，国际 投资和贸易将大幅度增长更多的国外企业进入我国，更多的我国企业走向世 界，提供了广阔的物流发展空问。从长期来看，物流业发展的本身又将降低贸 易的运输费用，从而对国内统一市场的形成、资源配置效率的提高和区域经济 发展水平差距的缩小带来积极影响，并加速我国参与国际分工和全球经济一体 化的进程，从而为物流业的发展提供持续扩张的市场空间。北京举办2 0 0 8 奥运 会为我国物流发展提供了千载难逢的机遇，从奥运设施建设到奥运会的召开， 始终需要远比平常庞大、复杂的物流系统的支持，在物流设施规划与建设、物 流组织与管理、物流技术创新与应用等方面对北京提出了很高的要求。可以说， 北京奥运会在给我国物流业提供巨大的市场空间的同时，也使我国物流业找到 了高水平服务的参照系，其示范作用将进一步加快我国物流的现代化进程f 高自 友，孙会君，2 0 0 3 ) 。 物流活动包括多个过程，如供货商的选择、运输、仓储及设施规划与选址 等，除了这些直接涉及的功能外，物流活动还影响生产、市场销售、产品设计 决策等诸多方面。库存一订货系统作为物流系统的重要组成部分，其目的是为 了保证供应链运行的连续性和应付不确定需求。它包括的范围很广，既可以指 生产企业为生产需要储备的原材料、生产过程中出现的成品、半成品，也可以 指批发、零售商为满足销售需要而贮备的消费品。库存是保证供应链功能的一 个必要步骤。不同经营组织者根据他们的经营特点执行不同类型的库存决策。 零售商定期维持产成品库存，制造商维持原材料、半成品和产成品库存，服务 组织如修理商店可能维持大量的生活用品库存等。根据供应链中的不同阶段库 存可分为原材料库存、在制品库存、产成品库存、废品库存。库存管理应解决 这样三个问题：什么时候订货，订多少货，向谁订货的问题。因此，库存问题 2 北京交通大学硕士学位论文 与订货问题关系密切。在众多的现代物流研究成果中，定性分析研究较多，缺 少定量研究，另外，确定性的物流模型研究的比较多，非确定性的研究成果比 较少。本硕士论文力求用定量的优化方法来描述和解决现代物流发展过程中的 订货库存问题，同时考虑决策参数为随机变量的情况，为提高物流效率、降 低物流成本、增加物流效益提供了基础理论与方法支持。其主要目的在于使物 流决策部门或物流规划人员用尽可能少的资金，充分发挥物流硬件的潜力，实 现最合理的应用，获得最佳经济效果。 1 2 物流模型的起源和发展 物流( l o g i s t i c s ) 一词来源于军事上的后勤( 宋华，胡左浩，2 0 0 0 ) ，现在已经 成为了一个耳熟能详的词汇。企业物流管理是西方现代管理的重要组成部分， 经过半个多世纪的发展演变，在美国等西方国家已经形成了完善的体系( r o n a l d h b a l l o u , 2 0 0 2 ) 。无论从概念定义，还是从思想内涵来看，以微观企业为研究对 象的企业物流管理与国内传统的以社会物资储运为对象的“宏观物流”有着天 壤之别。已经成为真正意义上的“第三利润源”。企业物流管理的中心任务就是 对整个物流过程进行规划、实施和控制。在物流模型出现以前，计划和控制过 程主要是凭借工作人员的经验来完成，这样的计划和控制不但不精确而且很难 继承( 宋华，胡左浩，2 0 0 0 ) 。运筹学是- f 研究系统优化问题的学问，物流系统的 优化问题已可以应用运筹学的相关理论来解决。运筹学学者很早就已经把物流 过程当中的很多具体问题作为研究对象了，存储论几经成为运筹学的一个重要 分支。库存和订货问题的研究早就成为运筹学学者研究的热点，直到今日，还 不时的涌现出很多相关的优秀研究成果。可以说对物流问题的研究也反过来促 进了运筹学的发展。近些年来，对物流问题的研究已经深入到各个领域，越来 越多的学者把物流问题作为自己的研究对象。物流问题的主要规划领域包括： 北京交通大学硕士学位论文 客户服务目标、设施选址策略、库存策略、运输策略、供应链规划等( r o n a | d h b a l l o u , 2 0 0 2 ) 。物流及供应链管理中供需关系始终贯穿整个过程。因此，供需研 究是物流管理的一个最重要，也是最基本的内容。本论文将以库存、订货和供 应链分销网络的优化问题为主要的物流研究对象。库存成本是供应链成本的重 要组成部分之一，一般占总成本的3 0 以上，因此，要想优化整个物流系统， 就必须要做好库存管理。 库存费用是总的物流费用中重要的部分，它包括物品在保管、运输途中的 维持、缺货费用。库存费用也受其他费用因素影响，例如，采购价格和运输费 率取挟于订单及运输量的大小，这些反过来又影响库存费用。在有些情况下， 当到货时间已知或为保持及时控制进行总量订货时，库存决策可简单确定。 1 3 研究随机物流模型的目的及意义 本文中我们以库存问题为例来说明研究不确定性物流模型的重要性。众所 周知，库存是企业的一项庞大且昂贵的投资。良好的库存管理能够加快资金的 周转速度、提高资金的使用效率、增加投资的收益。对于制造业来说，原材料 短缺将影响生产，导致费用增加，产品短缺。而库存积压将增加仓储，积压资 金，提高成本，减少盈剥。这些都反映了库存管理对企业的重要性。库存管理 是物流管理的核心内容之一，库存的合理优化是众多学者广泛关心的问题。库 存问题经长期研究已得出一些行之有效的模型，大体分两类：第一类叫做确定 性模型，即模型中的数据皆为确定的数值，大多数文章研究的是这类确定性模 型。另一类叫做不确定性模型。在生产实践和管理实践中，几乎所有问题中都 涉及到一些不确定性的变量，这类问题的研究日益得到重视，越来越多的学者 开始把不确定性f - j 题作为自己的研究重点刘宝碇，赵瑞清，2 0 0 d 。随机闯题无论 建模过程还是求解过程都要比确定性问题复杂的多，为了使得我们研究的理论 4 北京交通大学硕士学位论文 更好的指导实践，必须在这方面多做工作，进行深入的研究。 1 3 1 确定性库存模型 确定性条件下的库存是指当一个时期内的产品需求量确定以后，相应的库 存成本就基本上确定了。如果暂时不考虑缺货成本，库存成本由产品成本、存 贮成本和订货成本三部分组成。最经典的订货模型是经济订货批量( e o q ) 模 型，经济订货批量是存货维持与订货相结合使成本最低的补给订货批量。模型 成立需要以下几个假设条件：缺货费用无穷大；当存贮降为零时，可以立即得 到补充；需求是连续的、均匀的；每次订货量不变：单位存贮费不变。由于经 济批量模型需要相当严格的假设才能直接应用，所以在其延伸的模型中往往有 以下诸多假设：不允许缺货，生产需一定时间；允许缺货( 缺货需补充) ，生产 时间很短；允许缺货( 需补足缺货) ，生产需一定时问。不同的假设模型不尽相 同。另外，为了利用特殊的购买形势和单位化特征而必须做出某些调整，与e o q 有关的两种调整分别是：运量费率和数量折扣。我们常看到一种商品有所谓的 零售价、批发价和出厂价，购买同一种商品的数量不同，商品单价也不同，一 般情况下购买数量越多，商品单价越低。在少数情况下，某种商品限额供应超 过限额部分的商品单价要提高( 钱颂迪，2 0 0 0 ) 。 1 3 2 随机性库存模型 随机性库存模型的重要特点是需求为随机的，其概率分布为已知，通常分 为需求是连续和需求是离散两种情况研究。在随机性库存问题中，如果想让商 品既不因缺货而失去销售机会，又不因滞销而过多积压资金，可供选择的策略 主要有三种。第一种策略：定期订货。但订货数量需要根据上一个周期剩下货 物的数量决定订货量。剩下的数量少，可以多订货；剩下的数量多，可以少订 5 北京交通大学硕士学位论文 或者不订货。第二种策略：定点订货，存贮降到某一确定的数量时即订货，不 再考虑问隔的时间。这一数量值称为订货点，每次订货的数量不变。第三种策 略：把定期订货和定点订货综合起来的方法，隔一定时间检查一次存贮，如果 存贮数量高于一个数值s ，则不订货。小于s 时则订货补充存贮，订货量要使 存贮量达到s ，这种策略可以简称为o ，5 ) 存贮策略。存贮策略的优劣，通常 以赢利期望值的大小作为衡量的标准( 钱颂迪，2 0 0 0 ) 。 另一种更为复杂的模型是具有随机需求过程和随机供货时间的库存模型。 由于随机库存模型与排队论和控制论联系紧密，这就加大了其复杂性。 以往的研究模型大多只考虑了供方( 供应商或物流中心) 的利益，而没有 考虑需方( 顾客或物流中心) 的利益。而在现代物流体系中，顾客的需要被放 到了首位，在库存一订货问题中也不应例外。事实上，某个客户的需求不但可 以由多个供应商共同满足，而且由于每个供应商的库存取决于客户的选择行为， 同时这种选择行为在很大程度上具有较高的随机性。 1 4 论文框架 第1 章为绪论部分，简要介绍了现代物流的基本状况，库存一订货联合优 化问题在物流系统中的意义，库存一订货联合优化问题的一般模型和论文的框 架。 第2 章介绍了双层规划、随机规划与随机双层规划在库存一订货联合优化 问题中的应用。 第3 章简要介绍了非数值计算方法一遗传算法和随机模拟方法。 第4 章介绍需求随机情况下向多个供应商采购的期望值模型及求解算法。 第5 章介绍供应链中二级分销网络优化设计的随机规划模型及求解算法 第6 章介绍及时条件下订货策略的随机双层规划模型及求解算法。 6 fi ! 室銮望盔堂堡主堂堡堡塞 第2 章双层规划及随机规划介绍 2 1 双层规划模型的定义和特性 定义2 1 1 一般来说，双层规划模型具有如下形式： 口2 1 ) ( u 2 1 ) r a i n f ( x ，y ) s t g ( x ，y ) s 0 其中y = y ( x ) 由下述规划求得： ( l 2 1 ) m i n ( x ，y ) ， s t g ( x ，y ) s0 ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) 其中x e e “，y e “，f ：e “1 x e “2 ，e 1 ，g ：z 尹z 尹+ l 产， ，：e 町x e ”2 一e 1 ，g ：e 朔1 f 2 呻f 2 。 双层规划模型( p 2 1 ) 是由上层模型( u 2 1 ) 和下层模型( l 2 1 ) 组成， 式( 2 - 1 ) 一( 2 2 ) 构成上层问题，式( 2 - 3 ) 一( 2 - 4 ) 构成下层问题。上层决 策者通过设置x 的值影响下层决策者，因此限制了下层决策者的可行约束集， 上层决策者通过下层决策者的目标函数与下层决策者相互作用。必须注意到： 下层决策变量y 是上层决策变量x 的函数，即y y ( x ) ，这个函数一般被称为 反应函数。 可行性和最优性 假设上层决策者控制的决策变量的集合为zce “，下层决策者控制的决 策变量的集合为yce “，并且假设xn 】，一庐。在双层优化过程中，上层决 7 ：i ! 塞銮望盔芏堡主兰鱼堡塞f 策者首先选择变量x ，这样一来，就会影响下层决策者的可行策略集台。对固 定的x ，下层决策者所要解决的问题变为： m i n ( f ( x ，y ) ：ylx )( 2 - 5 ) s t x ，y e s ； ( x ，y ) ：g ( x ，y ) so ，g ( x ，y ) s o ( 2 - 6 ) 下层决策者的解集属于定义如下盼合理反应集( r a t i o n a lr e a c t i o ns e t ) ： 定义2 1 2 如果对于给定的一个点x c x ，存在唯一的解ye y ，由方程( 2 - 6 ) 所定义的集合s 上f 的合理反应集如下： 啊u ) = x e x ，y y ：( x , y ) e s ，f ( x , y ) = m i n ( f y ) ：y l x ) ) ( 2 - 7 ) 进一步，对于每一个x ，如果存在一个y 使f ( x ，y ) 在所有的点( x ，y ) c s 上唯一最小，那么可定义如下的合理映射： y = 垂，( x )( 2 - 8 ) 上层决策者控制两个变量的问题变为： m i n ( f ( x ，y ) ：( x ，y ) e ( s ) )( 2 - 9 ) 定义2 1 t 3 如果满足y ；中，( x ) ，这里映射中，为点x 处的台理映射，即点y 对点x 来说就是最优的，则称这样的一对点( x ，y ) 是双层规划问题( p 2 1 ) 的 可行解。 定义2 。1 。4 如果( x + ，y ) 满足以下两条就认为( x + ，y ) 是双层规划的最优解。 ( 1 ) ( x ，y ) 是可行的。 ( 2 ) 对所有的( x ，y ) s ，都有： ，( x ，y 。) sf ( x ，y ) 8 北京交通大学硕士学位论文 其中：假设s 为非空有界紧集合( n o n e m p t y a n d c o m p a c t ) 。 设( x + ，y ) 是双层规划的最优解，则其一阶必要条件为 ( 1 ) f ，g ，g 都是一次连续可微函数； ( 2 ) 对x e x ，下层问题( 2 - 3 ) 一( 2 - 4 ) 有唯一解； ( 3 ) 存在l l e e ，使得( x ，y ，u ) 是下列问题的可行解： r a i n 。 f ( x ，y ) x ，y ，p s t g ( x ，y ) s0 v ，f ( x ，y ) 一l iv y g ( x ，y ) 一0 p ( g ( x ，y ) ) 7 = 0 g ( x ，y ) s0 u 0 这里，向量l l 是下层问题的k - t ( k u h n - t u c k e r ) 乘子向量。 实际上，等式( 2 - 1 0 ) 一( 2 1 5 ) 恰好是合理反映集， ) 的一阶必要条件。 2 2 求解双层规划模型的算法概述 到目前为j e ，对于双层规划的求解大约有十几种求解算法。但归纳起来说， 用于求解双层规划问题的算法可以分为四大类，即极点搜索法( e x t r e m ep o i n t s e a r c hm e t h o d ) 、库恩一塔克法( k u h n - t u c k e rm e t h o d ，简称k - t 法) 、下降法 ( d e s c e n t m e t h o d ) 和直接搜索法( d i r e c t s e a r c h m e t h o d ) 和非数值启发式方法， 下面分别加以介绍。 ( 1 ) 极点搜索法：这种方法主要用于求解双层线性规划问题，其基本观点 就是：双层线性规划问题的任何解都出现在一f 层问题的约束集合的极点位置。 9 u 刁 势 q e 北京交通大学硕士学位论文 因此，首先可以利用各种方法来寻找约束空间的极点( 不要求寻找全部极点) ， 然后从中再找出双层规划问题的局部最优解或全局最优解。 ( 2 ) k - t 法：这种方法将双层问题中的下层问题用它的k u h n - t u c k e r 条件 代替，主要用于求解双层线性规划问题，最初用于求解双层线性资源控制问题。 b a r d ( 1 9 8 3 ) 利用外部惩罚函数法将一般的双层规划问题转化为双线性规划问 题；b a r d ( 1 9 8 2 ) 将非凸双层规划问题变换为可分形式，再运用分枝定界方法进 行求解。 ( 3 ) 下降法：这种方法是基于用各种可能的方法得到的下层问题对上层决 策变量的梯度信息，主要用于求解非线性双层规划问题。从本质上讲，这是一 种迭代求解方法，利用得到的下层问题对上层决策变量的梯度信息来产生一系 列使上层目标函数减小的点。h o g a n ( 1 9 7 3 ) 和1t a n i n o ( 1 9 8 4 ) 提出了用方向导数来 求解带有隐函数定义约束的双层规划的方法；而f a l k ( 1 9 9 5 ) 进一步提出了基于 次梯度的下降方法。最具代表性的下降算法是基于灵敏度分析的求解算法，关 于这方面的详细内容，可参考高自友和四兵锋( 2 0 0 2 ) 。 ( 4 ) 直接搜索法：直接使目标函数虽小的方法，如a b d u l a a l 和l e b l a n c ( 1 9 7 9 ) 使用的h o o k e 4 e e v e s 搜索法就属于此类，在搜索解的过程中，这种方法取决于 上层目标函数值的变化。 ( 5 ) 非数值优化方法：近年来，越来越多的学者将随机搜索技术应用到双 层决策问题的求解中，如模拟退火算法( s i m u l a t i o na n n e a l i n g ) 和遗传算法 ( g e n e t i c a l g o r i t h m s ) 。这类非数值优化方法用于求解具体双层规划模型还属于 探索阶段。本文研究的模型都含有随机参数，利用基于随机模拟的遗传算法原 理设计了随机双层规划的求解算法。 综上所述，设计求解非线性双层规划问题算法的核心都是如何获得下层决 策变量对上层决策反应函数的具体形式，从而可以将非线性规划中的许多有效 算法直接应用于求解双层规划模型中。 2 3 随机规划简介 在现实世界中，人们制定决策时会经常碰到不确定性现象。这种不确定现 l o 北京交通大学硕士学位论文 象包括我们所熟悉的两类：一类是随机现象，一类是模糊现象。描述刻画随机 现象的量称为随机变量，描述刻画模糊现象的量称为模糊集。为了方便，我们 不妨把二者称为随机参数和模糊参数。含有随机( 模糊) 参数的数学规划称为 随机( 模期) 规划，二者称为不确定规划。本文将重点介绍随机规划的内容。 一个复杂的决策系统通常具有多维性、多样性、多功能性和多准则性，并 带有随机参数。对于随机规划问题中出现的随机变量，出于不同的管理目的和 技术要求，采用的方法也不尽相同。首先，摄自然的方法是：取这些随机变量 的所对应函数的概率平均值( 数学期望) ，从而把随机规划转化为确定的数学规 划( 只是多了几个多重积分) 。这种在期望值约束f ，使目标函数的概率期望达 到最优的模型通常称为期望值模型。 第二种方法是机会约束规划，由c h a m e s 和c o o p e r ( 1 9 5 9 ) 提出，主要针对 约束条件中含有随机变量，且必须在观测到随机变量的实现之前做出决策的问 题。考虑到所做决策在不利的情况发生时可能不满足条件，而采用一种原则： 即允许所做决策在一定程度上不满足约束条件，但该决策应使约束条件成立的 概率不小于某一置信水平6 t ，对一些特殊情况，机会约束规划问题可以转化为 等价的确定性数学规划问题，但对较复杂的机会约束规划问题，通常很难做到 这一点。本文利用基于随机模拟的遗传算法来求解一般机会约束规划问题以及 机会约束多目标规划和机会约束目标规划问题。 有时，一个复杂的决策系统要涉及到多项任务，称之为事件，决策者往往 希望这些事件实现的概率( 即机会函数) 尽可能的大。为了解决这类问题，刘 宝碇提出了第三种随机规划，即相关机会规划并推广到相关机会多目标规划和 相关机会目标规划。简单地说，相关机会规划是使事件的机会函数在不确定环 境下达到最大值的优化问题。在确定性规划以及期望值模型和机会约束规划中， 当对实际问题建模以后，可行集则实质上已经确定这就可能导致所给定的最 优解在实际执行时根本无法实现，相反，相关机会规划并不假定可行集是确定 的。实际上相关机会规划的可行集描述为所谓的不确定环境。虽然相关机会规 北京交通大学硕士学位论文 划也给出一个确定的解，但这个解只是要求在实际阿题中尽可能地实现。显然， 相关机会规划的这一特点是前面所提到两种随机规划不具有的。然而，这类问 题在现实生活中确实存在。 本章第三节的内容主要参考了刘宝碇和赵瑞清( 2 0 0 1 ) 。 北京交通大学硕士学位论文 第3 章基于随机模拟的遗传算法简介 1 9 世纪中叶，查尔斯达尔文在总结前人进化思想的基础上，用大量的科 学事实证明了生物进化过程在总体上表现为：从低级到高级，从简单到复杂， 从不完善形式到完善形式，从单一适应到多种适应，从低的有序性到高的有序 性，以及沿着物种数目日益增多的方向发展进化。达尔文认为，生物进化的动 力和机制在于自然选择。自然选择是用变异作材料，通过生存斗争实现的。凡 是具有适应环境的有利变异的个体。在生存斗争中将有更多机会生存和繁殖后 代，而适应性较差的个体将被淘汰，因此，生物进化便是“物竞天择适者生 存”的过程。1 9 7 5 年，美国密歇根大学的心理学教授、电子工程学与计算机科 学教授h o l a n d 和他的同事与学生麸同研究了具有开创意义的遗传算法理论和 方法。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、 随机、白适应搜索算法。简单而言，它使用了群体搜索技术，将种群代表一组 问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生 新一代的种群，并逐步使种群进化到包含近似最优解的状态。由于其思想简单、 易于实现以及表现出来的健壮性，遗传算法赢得了许多应用领域，特别是近年 来在问题求解、优化和搜索、机器学习、智能控制、模式识别和人工生命等领 域取得了许多令人鼓舞的成就。以遗传算法为核心的进化算法已与模糊系统 理论、人工神经网络等一起成为计算智能研究中的热点，受到广泛的关注。 3 1 遗传算法的产生与发展 早在2 0 世纪5 0 年代和6 0 年代，就有少数几个计算机科学家独立地进行了 所谓的“人工进化系统”研究，其出发点是进化的思想可以发展成为诲多工程 问题的优化工具。早期的研究形成了遗传算法的雏形，如大多数系统都遵行“适 (j ! 夏至夔查兰墼圭堂笪堡皇 者生存”的仿自然法则，有些系统采用了基于种群的设计方案，并且加入了自 然选择和变异操作，还有一些系统对生物染色体编码进行了抽象处理，应用了 二进制编码。由于缺乏种通用的编码方案，人们只能依赖变异而非交叉来产 生新的基因结构，早期的算法收效甚微。2 0 世纪6 0 年代中期，h o l l a n d 在f r a s e r 和b c r m c r m a n n 等人工作的基础上提出了串位编码技术。这种编码既适用于变 异操作，又适用于交叉操作，并强调将交叉作为主要的遗传操作。随后，h o l l a n d 将该算法用于自然和人工系统的自适应行为的研究中，并于1 9 7 5 年出版了其开 创性著作“a d a p a t a t i o n i nn a t u r a la n d a r t i f i c i a ls y s t e m s ”。以后，h o l l a n d 等人将 该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传算法。 遗传算法的通用编码技术和简单有效的遗传操作为其广泛、成功地应用奠定了 基础。 2 0 世纪8 0 年代中期以来是遗传算法和进化计算的蓬勃发展期。1 9 8 0 年以 来，人们越来越清楚地意识到传统人工智能方法的局限性，而且随着计算机速 度的提高及并行计算机的普及，遗传算法和进化计算对机器速度的要求已不再 是制约其发展的因素。德国d o r t m u n d 大学1 9 9 3 年末的一份研究报告表明，根 据不完全统计，进化算法已在1 6 个大领域、2 5 0 多个小领域中获得了应用。遗 传算法在机器学习、过程控制、经济预测、工程优化等领域取得的成功，己引 起了数学、物理学、化学、生物学、计算机科学、社会科学、经济学及工程应 用等领域专家的极大兴趣。某些学者研究了进化计算的突出行为后声称，进化 计算与混沌理论、分形几何将成为人们研究非线性想象和复杂系统的心得三大 方法，并将与神经网络一起成为人们研究认知过程的重要工具。 3 2 遗传算法的基本思想和一般流程 遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由 1 4 ! ! 塞窒望古堂堡圭堂垡笙皇 经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实 体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现( 即基 因型) 是某种基因组合，它决定了个体的形状的外部表现。因此，在一开始需 要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂， 我们往往进行简化，如二进制编码。初代种群产生之后，按照适者生存和优胜 劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个 体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交叉和变 异，产生出代表新解集的种群。这个过程将导致种群像自然进化一样的后生代 种群比前代更加适应于环境，末代种群中的晟优个体经过解码，可以作为问题 近似最优解。 遗传算法采纳了自然进化模型，如选择、交叉、变异等。计算开始时，一 定数目n 个个体即种群随机地初始化，并计算每个个体的适应度函数，第一代 也即初始化就产生了。如果不满足优化准则，开始新一代的计算。为了产生下 - - 。r t , ，按照适应度选择个体，父代要求基因重组( 交叉) 而产生子代。所有的 子代按一定概率变异。然后子代的适应度又被重新计算，子代被插入到种群中 将父代取而代之，构成新的一代。这一过程循环执行，直到满足优化准则为止。 标准遗传算法的一般流程可描述如下： 第一步随机产生初始种群，个体数目一定，每个个体表示染色体的基因 编码： 第二步计算个体的适应度，并判断是否符合优化准则，若符合，输出最 佳个体及其代表的最优解，并结束计算；否则转向第三步； 第三步依据适应度选择再生个体，适应度高的个体被选中的概率高，适 应度低的个体可能被淘汰； 第四步按照一定的交叉概率和交叉方法，生成新的个体： 第五步按照一定的变异概率和变异方法，生成新的个体： 1 5 ! ! 塞銮望丕芏堡圭兰垡丝塞i 第六步由交叉和变异产生新一代的种群，返回到第二步。 标准遗传算法的流程图描述，如图3 - 1 所示。 3 3 遗传算法的特点 我们知道，传统的优化方法主要有三种：枚举法、启发式算法和搜索算法。 枚举法：枚举出可行解集合内的所有可行解，以求出精确最优解。对于连 续函数，该方法要求先对其进行离散化处理，这样就可能因离散处理而永远达 不到最优解。此外，当枚举空间比较大时，该方法的求解效率比较低，有时甚 至在目前先进计算工具上无法求解。 启发式算法：寻求种能产生可行解的启发式规则，以找到一个最优解或 近似最优解。该方法的求解效率比较高，但对每一个需求解的问题必须找出其 特有的启发式规则，这个启发式规则一股无通用性，不适合于其他问题。 搜索算法：寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜 索操作，以找到问题的最优解或者近似最优解。该方法虽然保证不了一定能够 得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和效 率上达到一种较好的平衡。 随着问题种类的不同以及问题规模豹扩大，要寻求一种能以有限的代价来 解决搜索和优化的通用方法，遗传算法为我们提供了个有效的途径，它不同 于传统的搜索和优化方法。主要区别在于： ( 1 ) 自组织、自适应和自学习性( 智能性) 。应用遗传算法求解问题时， 在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信 息自行组织搜索。由于基于自然的选择镱略为“适者生存，不适应者被淘汰”， 因而适应度大的个体具有较高的生存概率，通常，适应度大的个体具有更适应 环境的基因结构，再通过基因重组和基因突变等遗传操作，就可能产生更适应 1 6 北京交通大学硕士学位论文 环境的后代。进化算法的这种自组织、自适应特征，使它同时具有能根据环境 变化来自动发现环境的特性和规律的能力。自然选择消除了算法设计过程中的 一个最大障碍，即需要事先描述问题的全部特点，并要说明针对问题的不同特 点算法应采取的措施。因此，利用遗传算法的方法，我们可以解决那些复杂的 非结构化问题。 图3 - i 标准遗传算法的优化框图 ( 2 ) 遗传算法的本质并行性。遗传算法按并行方式搜索一种群数目的点，而 不是单点。它的并行性表现在两个方面，一是遗传算法是内在并行的，即遗传 算法本身非常适台大规模并行。最简单的并行方式是让几百甚至数千台计算机 各自进行独立种群的演化计算，运行过程中甚至不进行任何通信( 独立的种群 1 7 北京交通大学硕士学位论文 之间若有少量的通信一般会带来更好的结果) ，等到运算结束时才通信比较，选 取最佳个体。这种并行处理方式对并行系统结构没有什么限制和要求，可以说， 遗传算法适合在目前所有的并行机或分布式系统上进行并行处理，而且对并行 效率没有太大影响。二是遗传算法的内含并行性。由于遗传算法采用种群的方 式组织搜索，因而可同时搜索解空间内的多个区域，并相互交流信息。使用这 种搜索方式，虽然每次只执行与种群规模n 成