（管理科学与工程专业论文）基于拉格朗日松弛的带外包受限多产品批量问题研究.pdf

新：研扁雾公) 料毖唇。膨 独创性声明 本人声明所星交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 金日巴互些盔堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者签字：舞匆研签字日期：则年币月刁日 学位论文版权使用授权书 本学位论文作者完全了解 金8 墨王些太堂 有关保留、使用学位论文的规定， 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。 有权 本人 授权 金8 墨王业太堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：者切柳 签字日期：m 1 年斗月刁日 学位论文作者毕业后去向： ：1 ：作单位： 通讯地址： 导师签名： 分名 签字日期：芦t1 年午月巧日 电话： 邮编： 基于拉格朗日松弛的带外包受限多产品批量问题研究 摘要 随着经济全球化的深入，企业间的竞争更加激烈，保持和提升自身的核心 竞争力是企业生存和发展的关键。有效组织生产是提升企业竞争力的重要一环。 经济全球化使企业间的分工更加细化，更强的合作。目前许多企业致力于影响 自身核心竞争力的业务，而将附加值低的非核心业务外包给外部公司。因此， 考虑外包的企业生产计划研究有很强的实际背景。 本文综述了经济批量问题和考虑外包经济批量问题的研究现状，总结了拉 格朗日松弛方法在经济批量问题上的应用。概述了经济批量问题、外包和研究 中用到的拉格朗日松弛算法、动态规划算法和启发式算法。研究了生产能力约 束下的考虑外包的多产品经济批量问题，多种产品的生产受限于随周期变化的 同一生产能力，不允许延期交货，生产成本和外包成本为线性函数。设计了求 解问题的拉格朗日松弛算法，将生产能力受限的约束条件松弛到目标函数中， 转化为个无能力约束的子问题，应用动态规划算法对其求解；使用启发式过 程构造原问题的可行解。仿真实验中，首先针对同一实例与商用软件l i n g o 的结果进行对比，验证了算法的有效性，并给出了一个完整演示算例。接着通 过改变产品种类数和周期数生成不同规模的1 2 组实例，每组实例运行1 0 次， 计算算法平均运行时间和平均相对偶间隙；实验表明，所有问题实例的平均相 对对偶间隙在1 内；算法平均计算时间基本随问题规模成倍数变化。最后通 过选取6 个算例检验算法的上下界随迭代代数的收敛情况，实验表明，产品数 变化未显著影响收敛代数。 关键词：受限经济批量问题；多产品：外包：拉格朗日松弛算法 r e s e a r c ho l lt h em u l t i i t e mc a p a c i t a t e dl o t s i z i n gp r o b l e m w i t ho u t s o u r c i n gb a s e do nl a g r a n g i a nr e l a x a t i o n a b s t r a c t w i t ht h ed e e p e n i n go fe c o n o m i cg l o b a l i z a t i o n ，t h ec o m p e t i t i o n sa m o n ge n t e r p r i s e sb e c o m e m o r ea n dm o r ei n t e n s e ，m a i n t a i n i n ga n dp r o m o t i n gt h ec o r e c o m p e t i t i v e n e s so ft h e e n t e r p r i s e s i st h e k e y t ot h e i rs u r v i v a la n d d e v e l o p m e n t o r g a n i z i n gm a n u f a c t u r e e f f e c t i v e l yi s a l li m p o r t a n t p a r to fe n t e r p r i s e sc o m p e t i t i v e n e s s p r o m o t i o n e c o n o m i c g l o b a l i z a t i o nm a k e st h e d i v i s i o n so fw o r k a m o n ge n t e r p r i s e s m o r ed e t a i l e d ，a n d c o o p e r a t i o nm o r es t r o n g e r a tp r e s e n t ，m a n ye n t e r p r i s e sa p p l yt h e m s e l v e st ot h eb u s i n e s s t h a te f f e c tt h e i rc o r ee o m p e t i t i v e n e s s e s ，a n do u t s o u r c et h en o n - c o r eb u s i n e s s e sw i t hl o w a d d i t i o n a lv a l u et oe x t e r n a lc o m p a n i e s t h e r e f o r e ，i th a sas t r o n gp r a c t i c a lb a c k g r o u n dt o r e s e a r c ht h ep r o d u c t i o np l a n n i n g 、析mo u t s o u r c i n g t h i sp a p e ro v e r v i e w e dt h er e s e a r c hs t a t u so fe c o n o m i cl o t - s i z i n gp r o b l e ma n de c o n o m i c l o t - s i z i n gp r o b l e mw i t ho u t s o u r c i n g ，s u m m a r i z e dt h ea p p l i c a t i o no fl a g r a n g i a nr e l a x a t i o n o ne c o n o m i cl o t - s i z i n gp r o b l e m ab r i e fs u m m a r i z a t i o nw a sg i v e na b o u tb a s i ct h e o r yo f e c o n o m i cl o t - s i z i n gp r o b l e m ，o u t s o u r c i n ga n dt h ea l g o f i t h r nw h i c hi su s e di n r e s e a r c h s t u d i e dm u l t i - i t e m c a p a c i t a t e dl o t - s i z i n gp r o b l e m 晰mo u t s o u r c i n g ，i nw h i c ht h e m a n u f a c t u r eo f m u l t i p l ei t e m si sl i m i t e db yt h ep r o d u c t i o nc a p a c i t yw h i c hc h a n g e sw i mm e p e r i o d ，n o t 、) l ，i t l lb a c k l o g g i n g ，a n dt h ep r o d u c t i o nc o s t sa n do u t s o u r c i n gc o s t si sal i n e a r f u n c t i o n d e s i g n e dl a g r a n g i a nr e l a x a t i o na l g o r i t h mt os o l v et h ep r o b l e m ，t h ec o n s t r a i n t so f p r o d u c t i o nc a p a c i t yw e r er e l a x e di n t oo b j e c t i v ef u n c t i o n ，a n dw e r ed e c o m p o s e si n t o n 。 u n c o n s t r a i n e ds u b p r o b l e m s ，s o l v e db yd y n a m i cp r o g r a m m i n ga l g o r i t h m ；a n du s e dh e u r i s t i c p r o c e d u r e t oc o n s t r u c tt h ef e a s i b l e s o l u t i o no fo r i g i n a lp r o b l e m i nt h es i m u l a t i o n e x p e r i m e n t 。c o m p a r e dt h es a m ee x a m p l ew i t i lt h er e s u l to fc o m m e r c i a ls o f t w a r el i n g o f i r s t l y ，v e r i f i e dt h ea v a i l a b i l i t yo ft h ea l g o r i t h m ，a n ds h o w e da ni n t e g r a ld e m oe x a m p l e t h e ng e n e r a t e d12g r o u p so fe x a m p l e sw i t hd i f f e r e n ts c a l eb yc h a n g i n gt h en u m b e ro f i t e m sa n dt h en u m b e ro fp e r i o d s ，e a c hg r o u po fe x a m p l e sw e r er u nf o r10t i m e s ，c a l c u l a t e d t h ea v e r a g er u n n i n gt i m ea n da v e r a g eg a p ；t h ee x p e r i m e n ts h o w e dt h a t ，t h ea v e r a g eg a p 0 fa l lt h ep r o b l e me x a m p l e sw e r ew i t h i n1 ：t h ea v e r a g ec o m p u t i n gt i m ei s m a i n l y m u l t i p l e sc h a n g ew i t ht h ep r o b l e ms c a l e f i n a l l y ，t h ec o n v e r g e n c eo fu p p e ra n dl o w e r b o u n da l o n gw i t hi t e r a t i o nt i m e sw e r ev e r i f i e d ，t h ee x p e r i m e n ts h o w e dt h a t ，t h ec h a n g eo f t h en u m b e ro fi t e m sd i dn o te f f e c tt h ec o n v e r g e n c ei t e r a t i o nt i m e so b s e r v a b l y 。 k e y w o r d ：c a p a c i t a t e d e c o n o m i c l o t s i z i n gp r o b l e m ；m u l t i - i t e m ；o u t s o u r c i n g ； l a g r a n g i a nr e l a x a t i o n 目录 第一章绪论1 1 1 研究背景与意义 1 2 经济批量问题概述 1 3 国内外研究现状 1 3 1 经济批量问题的研究进展 1 3 2 考虑外包的经济批量问题研究现状 1 3 3 拉格朗日松弛在经济批量问题上应用 1 4 论文主要工作及结构安排 第二章相关问题和方法7 2 1 经济批量问题的基本模型7 2 1 1 单产品批量问题模型7 2 1 2 多产品批量问题模型8 2 2 外包概述1 0 2 3 启发式算法1 2 2 3 1 启发式算法的分类1 2 2 3 2 启发式算法的性能分析1 3 2 4 拉格朗日松弛算法1 4 2 4 1 算法概述1 4 2 4 2 拉格朗日松弛1 4 2 4 3 次梯度优化算法1 5 2 4 4 拉格朗日松弛算法步骤及评价指标1 6 2 5 动态规划算法1 7 第三章问题模型与求解方法1 9 3 1 实际应用背景1 9 3 2 数学模型1 9 3 3 具体解决方案及分析2 0 3 3 1 原问题的l a g r a n g i a n 松弛2 l 3 3 2l a g r a n g i a n 松弛算法2 2 3 3 3 求解子问题的动态规划算法2 3 3 3 4 原问题的可行解构造2 5 第四章仿真实验2 7 4 1 实验概述2 7 4 2 算法有效性验证2 8 4 3 算例3 0 4 4 算法性能和效率验证3 5 4 5 上下界收敛实验3 6 第五章总结与展望4 0 5 1 主要工作总结4 0 i l l 5 2 未来工作展望4 1 参考文献4 2 攻读硕士学位期间发表的论文4 6 插图清单 图1 1 经济批量问题分类图。3 图2 1 多产品经济批量问题分类图。9 图2 2 玎阶段决策过程图1 7 图3 1l a g r a n g i a n 松弛算法流程图。2 1 图3 2 第k 周期生产时示意图2 4 图3 3 第k 周期生产时示意图2 4 图4 1 最优值随迭代次数变化情况3 4 图4 2 相对对偶间隙随产品种类数变化曲线3 6 图4 3n = 1 0 时上下界随迭代次数变化曲线3 7 图4 4n = 2 0 时上下界随迭代次数变化曲线3 7 图4 5n = 4 0 时上下界随迭代次数变化曲线3 7 图4 6n - - 6 0 时上下界随迭代次数变化曲线3 8 图4 7n = 8 0 时上下界随迭代次数变化曲线3 8 图4 8n = 1 0 0 时上下界随迭代次数变化曲线3 8 v 表格清单 表4 1 已知量取值区间的设定2 7 表4 2 初始化数据2 8 表4 3 算法程序运行结果3 0 表4 4l i n g o 运行结果3 0 表4 5 算例原始数据3 1 表4 6 原问题计算结果3 2 表4 7 子问题计算结果3 3 表4 8 算例最终实验结果3 4 表4 - 9 时间周期t 和产品数n 不同时的实验结果3 5 v i 致谢 值此论文完成之际，衷心感谢我的导师钟金宏老师，感谢钟老师三年来对 我的悉心指导和帮助。钟老师渊博的知识、高深的学术造诣、严谨求实的科研 态度、孜孜不倦的工作精神以及谦和的处事风格给我们树立了榜样，使我们受 益匪浅，收获颇丰。 在三年的研究生生活中，研究所的每一位老师都给予我们学习和生活中的 帮助。感谢李兴国老师在学术上给予我的指导，在生活上给予我的帮助，并且 为我们创造了良好的学习环境和学习氛围。感谢顾东晓老师和杨颖老师提出的 许多宝贵意见。 同在研究所的师兄师姐师弟师妹和同学们也给了我很多帮助和温暖。由衷 感谢赵启飞同学在编写程序时给予我重要的帮助，以及在一起学习的七年中的 所有帮助。感谢牛晓玲、薛玉玲、明艳秋、沈丽娜、殷明、范昌勇，在研究所 的每一天都有你们陪伴，大家互相关心、互相帮助，宛如一家人一样，感觉真 好。在此向你们真诚的道谢! 感谢合肥工业大学管理学院给我提供良好的学习环境。感谢父母对我的支 持，你们给了我全部的爱。感觉我的家人给我的温暖。 最后，感谢各位评审专家在百忙之中抽出时间对我的论文进行仔细评阅。 v n 作者：杨柳 2 0 1 1 年4 月 第一章绪论 在企业之间竞争日益激烈的环境下，企业需要与其他不同行业保持合作来 增强自身竞争力。生产制造业是关系国民经济命脉的支柱产业，其商业活动更 加需要不断优化。许多企业在寻求更好的方法在竞争中取得优势时，采用了外 包的方式，既节省了精力去发展其核心业务，又能够使制造成本降低。外包的 实际成功案例也屡见不鲜，可见其在以后的商业活动中将更广泛的被企业所采 纳。同时，制造型企业也在不断寻求降低成本方法，达到集成优化的目的，于 是批量生产在这样的环境下被越来越多的企业所采用。在这样一个环境下，本 文研究了考虑外包的经济批量问题。 1 1 研究背景与意义 如今，科技发展日益突飞猛进，尤其是信息技术，已经普遍运用到人类所 接触到的各个领域，无论是在生产中还是在生活中，信息技术都体现出了其无 可取代的重要性。进入2 l 世纪以来，在科学技术的推动下，全球经济发展迅速。 同时，企业之间的竞争也愈演愈烈，生产的边际成本的不断减少，客户对产品 质量和价格期望值的增加，对订货到交货时间的要求不断缩短，以及企业对利 润的更高追求等一系列在竞争中产生的问题，都迫使企业寻求更好的方式使自 身的商业活动最优化，来取得更强的竞争优势。在这样一个大环境下，制造型 企业只有寻求更好的生产方式进行生产，才能使自身更具竞争力，不至于在优 胜劣汰的环境下被淘汰。 为了达到优化自身的目的，许多制造型企业选择批量生产的方式来降低成 本。因此，批量生产问题也就成为这类企业的生产计划中的关键问题，如何在 批量生产中使成本降到最低成为关键中的关键。这里所说的批量生产，是指按 照一定的方法分批量，分时段进行生产，通过降低不必要的费用，如机器准备 费用等，来降低总生产成本。批量生产的生产任务具有批次多、批量大、不确 定性大等特点。在产品的生产过程中经常会出现资源瓶颈，例如生产设备的使 用冲突，库存的限制等，因此一个优质的生产计划应尽量避免资源的冲突，而 应合理利用资源，使效率达到最高。确定生产批量的大小和生产期的时段是通 过批量生产提高效益的关键。大批量生产的益处是可以减少机器设备的准备时 间和准备费用，并且批量购买原材料可以降低一定的原材料费用，但是也会增 加原材料及产成品的库存费用。所以，必须运用科学的方法并要根据实际情况 如市场需求量，单位库存成本等因素，来确定生产批量的大小。在生产能力受 限的情况下，如何使生产能力更加合理的分配，使生产达到最优化，也是批量 问题研究的一个重要方面。确定批量生产的方法有很多，其中最常用的有：最 小批量法、经济批量法和间隔生产周期法三种。本文研究的方法即为“经济批量 法”。 另一方面，世界已进入了知识经济时代，传统的自给自足的组织模式已经 失去了其优势。将公司部分非主要业务或机能委托给外部公司的业务外包正成 为一种重要的商业组织方式和竞争手段。企业想要在竞争中获得更大的优势， 必须从自身的条件和所处环境出发，发现并培育自己的核心竞争力。越来越多 的企业已经把自己的主要精力放在关键业务上，并将企业中的非核心业务交由 战略合作伙伴来完成，以充分发挥业务外包的优势。 1 2 经济批量问题概述 自从1 9 1 5 年f w h a r r i s 1 】提出经济订货数量( e o q ) 模型至今，关于经济 批量问题( e l s p e c o n o m i cl o t s i z i n ga n ds c h e d u l i n gp r o b l e m ) 的研究已经 有近百年的历史了。但e o q 模型只是针对静态需求的，后来w a g n e r 和w h i t i n l z j 所做的关于经济批量问题的基础性工作才真正开启了众多学者对该主题研究。 它的研究在许多实际应用中有重要价值，尤其是在一些制造型企业的排产计划 中，发挥着很关键的作用。 经济批量问题，一般是指：在一定的较长的规划周期内，每个周期对产品 的需求量是已知的，而这些需求量可以通过提前生产、当期生产或者延迟交货 来满足。最终目的是确定最小的成本( 一般包括生产成本、库存成本、准备费 用等) 来制定生产计划。 根据不同的实际情况，所要研究的经济批量模型是不同的。一般影响批量 问题分类、建模的因素主要有：规划期、产品种类数、产品需求量、生产阶段、 能力约束以及考虑的特殊因素等。规划期：规划期可以分为有限规划期和无限 规划期两种。有限的规划期通常需求是动态的，无限的规划期需求一般为恒定 的。产品种类数：如果研究单产品批量问题，那么只有一种产品。对于多产品 批量问题，则有多种产品。产品需求量：常见的动态需求每个周期都有不同的 需求量，并且是不断变化的已知量。生产阶段：生产阶段可以分为单阶段( 单 级) 和多阶段( 多级) 两种。单级的生产方式指的是最终产品没有经过中间的 半成品，而是直接由原材料或外购的材料制造而成。多级生产系统中，产品需 要经过多道工序完成，产品之间可能存在相互依赖的关系【2 1 。能力约束：是指 生产能力或库存能力等不能足够大到满足所有需求，其大小受到限制。影响生 产能力的因素有很多，如人力、机器、资金等。生产能力不受约束时，称为无 能力约束( u n c a p a c i t a t e d ) ，生产能力受到约束时，称为能力受限( c a p a c i t a t e d ) 。 考虑的特殊因素，就是指除了批量问题模型通用的生产成本、库存成本，启动 成本以外的，在某些特定环境下会加入的因素。如外包、再制造、易腐产品、 延期交货、数量折扣等。 2 经济批量问题可以分为两大类：单级单产品经济批量问题和多产品经济批 量问题。在每种问题中又可分为是否能力受限。见图1 1 。 图l - l 经济批量问题分类图 单产品经济批量问题：产品种类数只有一种的批量问题。每个无能力约束 的单级多产品问题可看作是个( 产品种类数) 单产品问题的集合。 单级多产品经济批量问题：该类问题可总结为，确定规划时段上每周期的 生产量或采购量，以最小的总成本满足规划期上已知的多产品需求1 4 1 。 多级多产品经济批量问题：( m u l t il e v e ll o t s i z i n gp r o b l e m ，m l l p ) 是指 产品的生产或采购等要经过多个阶段( 多道工序) ，需确定多个阶段的生产安排， 以最小总体成本满足已知需求。这里存在依赖性需要( 来自产品材料清单b o m 的各级需求) 和独立需求( 来自外部对最终产品的需求) 1 4 。 1 3 国内外研究现状 1 3 1 经济批量问题的研究进展 ( 1 ) 单产品经济批量问题 许多学者研究了单产品的批量问题，w a g n e r 和w h i t i n l 2 1 介绍了没有能力约 束的单产品批量问题，并提出了动态规划算法的最优方案。w a g e l m a n s 等、 a g g a r w a l 和p a r k 以及f e d e r g r u e n 和t z u r 与最早的w a n g e r - w h i t i n 模型相比都 是在算法复杂性上有所减少。w a g e l m a n s t 5 l 等提出基于动态规划方法来解决 w a g n e r w h i t i n 没有能力约束的情况，其算法复杂度为o ( n l o g n ) ，而f e d e r g r u e n 和t z u r l 6 】在同样的复杂度下使用了相对简单的前向算法来解决普通的动态批量 问题。s t a d t l e r t 7 1 完成了修正模型，这个模型在计划时段完成了需求预测。i o a n n i s g a n a n s 和s o t i r i o sp a p a c h r i s t o s t 8 】提出了一个新的多项式时间算法，并考虑了成 本和需求同时变化的解决方案。 ( 2 ) 多产品经济批量问题 一些作者考虑了w w 算法的多产品情况，他们中的大多数测试了改进后的 遗传算法。f l o r i a n 等【9 】对于单级多产品受限批量问题( c l s p ) 提出了伪多项式 算法，这种算法的复杂度为d ( 严c d ) ，这里c 和d 分别表示平均能力和平均需求， t 代表模型的时段。对于c l s p 的一种特殊情况，即持有成本和边际生产成本 是线性的情况。虽然没有能力约束的批量问题可以以多项式算法解决，但是 b i t r a n 和y a n a s s e 旧】证明了具有线性成本的c l s p 是n p h a r d 问题，他们在c l s p 中引入a ? r a 来表示，其中a ，声，) ，6 分别用来代表建立成本，持有成本， 生产成本和能力约束。这些参数的值可以为z ，c ，n i ，n d ，g ，他们分别代 表零，随时间恒定，随时间不增，随时间不减的情况。以下的c l s p 被证明是 多项式可解的，f l o r i a n 和k l e i n 1 1 】提出对于g g g c 的复杂度为d ( r ) 的算法， 后来v a nh o c s e l 和w a g c l m a n s 1 2 】将其复杂度改进为d ( 尹) 。b i t r a n 和y a n a s s 1 0 1 提出了在n i g 小i n d ，n i g n i c ，c z n d n i 和n d z 小d m i 相应复杂度为 d ( r ) ，d ( r ) ，o ( t l o g t ) 和d ( d 的算法。 1 3 2 考虑外包的经济批量问题研究现状 ( 1 ) 考虑外包的单产品经济批量问题 一些学者在不同方面对外包做出了研究，其中不乏考虑外包的经济批量问 题的文献。单产品研究方面，a k s e n 等【1 3 】考虑了带有外包的无能力约束的单产 品批量问题并在时变线性生产、库存和失去销售成本函数的条件下提出了一个 复杂度为d ( 严) 前向动态规划算法。l i u 等【1 4 】给出了考虑库存能力受限并且允许 短缺的动态批量模型，并提出了一种动态规划算法使问题在d ( t a l o g t ) 时间内可 解的。c h u 等【”】分别考虑了允许延期交货和外包的情况，给出了拟多项式时间 内可解的动态规划算法进行求解。c h u 等【1 6 】考虑了外包能力受限制和有界库存 情形，库存或延期交货成本是一般凹函数，并给出了算法复杂度为d ( 严l o g t ) 的 动态规划算法。z h o n g 等【1 7 】研究了有库存能力限制的允许延期交货和外包混合 模型并提出了算法复杂度为o ( t a l o g t ) 能j 动态规划算法求解模型。h u a n g 等i l 叫 研究了一个新的非减库存能力约束下的允许缺货和转包的企业采购计划模型， 提出了一个基于动念规划的多项式算法。c h u 和c h u 1 9 】研究了考虑有界库存和 外包的单产品动态批量模型，并提出一种动态规划算法在强多项式时间内进行 求解该问题。h u a n g 等f 2 0 】研究了一个非减库存能力约束下的允许延期交货和转 包的单产品动态批量问题并提出了算法复杂度为d ( 严) 的动态规划算法。z h o n g 等【2 1 】研究了一个有界库存能力约束下的允许延期交货和转包的单产品动态批 量问题并提出了算法复杂度为o ( t 4 1 0 9 t ) 孔g 算法。 ( 2 ) 考虑外包的多产品经济批量问题 许多学者对考虑外包的多产品批量问题进行了研究。j o l a y e m i 和 o l o r u n n i w o 2 2 1 提出了这样一种模型：当资源不能满足需求时允许通过转包或使 用库存来满足需求，当资源充足时不允许转包。v a nn o r d c n 和v a nd ev e l d e “刘 考虑了运输能力不足时进行转包的情况建立了多产品批量问题模型。 4 s a m b a s i v a n 和y a h y a t 2 4 】研究了考虑工厂内部转移的多工厂，多项目，多周期， 能力受限的调度问题。杨懿【2 5 】建立了考虑转包成本、运输费用和缺货成本的多 期多产多目标规划模型，并利用加权和法进行求解。彭红军等【2 6 】建立了多目标 的大型煤炭供应链集成决策模型，并提出了用目标规划法求解该多目标决策模 型的策略。吴悦和黎建强【27 】以一家时装制造公司也实际背景，建立了多目标规 划模型，运用了禁忌搜索算法求解。l i a n g 和c h e n g t 2 8 】建立了模糊多目标线性 规划模型，该模型模糊决策更容易解决不确定环境下的多目标、多产品、多周 期的供应链问题。j u n g 等【2 9 】在考虑能力受限及转包因素的情况下建立了多级多 产品批量问题模型，并通过一种基于启发式的遗传算法求得最优解。c o h e n 等 p o j 对生产和原料的全球协作提出了一个标准管理模型。 1 3 3 拉格朗日松弛在经济批量问题上应用 ( 1 ) 单级多产品批量问题 在研究多产品批量问题的文献中，使用l a g r a n g i a n 松弛算法来求解的文章 也很常见。比较早的有t r i g e i r o 等【3 l 】在1 9 8 9 年关注了启动时间在批量问题中的 作用，并提出了用l a g r a n g i a n 松驰算法求解能力受限的单级多产品问题。d i s b y 等【3 2 】研究了基于l a g r a n g i a n 松弛策略的大规模c l s p , 考虑多重资源约束。m i l l a r 等【3 3 】建立了允许缺货的受限多产品批量模型，并使用l a g r a n g i a n 松弛启发式算 法来解决问题。唐立新等【3 4 】基于l a g r a n g i a n 松弛法和新的启发式算法相结合求 解c l s p 问题，通过测试1 0 个问题的仿真实验标明平均相对对偶间隙可达到 2 以内。后又在此基础上构造了新的启发式算法，在用l a g r a n g i a n 松驰问题获 得原问题的可行解时，提出了多回路启发式算法【35 1 。潘常春等【3 6 】针对一类带最 小批量约束的计划问题，提出了基于拉格朗日松弛策略求解算法。通过拉格朗 。日松弛策略，将原问题转为一系列带最小批量约束的动态经济批量w w 子问 题，提出了解决子问题且其时间复杂度d ( 尹) 的最优前向递推算法。鲁奎等p 7 】 数学模型中考虑运输成本，当运输能力不足时，采用外包的方式，且外包情况 下运输工具的使用费用是时变的。在仿真实验中采用了多组数据进行比较，并 在某些变量不变的情况下考虑其他变量的变化情况。在此基础上，又提出不考 虑外包变量的加入的模型，计算方法大致相同【38 1 。r i z k a 等【3 9 】研究了一类需求 为动态变化的多产品批量问题，并且上界和下界共享带分段线性费用的资源。 g r a m a n i 等【4o 】建立了一种耦合的数学模型，提出了一种基于l a g r a n g i a n 松弛算 法的启发式算法解决问题，并证明了结果的有效性。a b s i 等】提出了考虑安全 库存和需求不足的批量模型，并使用带平滑算法的拉格朗日松弛启发式方法来 更新上界值。 ( 2 ) 多级多产品批量问题 z d a m a r 和b a r b a r o s o g l u l 4 2 1 出一种启发式算法来解决动态多级多产品能力 受限批量问题( m l c l s p ) ，通过l a g r a n g i a n 松弛分解难问题成的小的子问题， 更加深入的研究模拟退火算法的能力。设计出两个l a g r a n g i a n 松弛方案，并且 不同模拟退火方案构成l a g r a n g i a n 松弛启发式算法。c h e r t t 4 3 1 研究了需求不确定 的受限多级多产品生产计划问题，其中成本函数是非线性的，并使用一种本地 搜索的方法改进可行解。 1 4 论文主要工作及结构安排 本文主要研究在生产可以外包的情况下，有生产能力约束的单级多产品批 量问题。建立相应的模型并通过拉格朗日松弛算法进行求解，最后通过实验验 证算法的有效性及效率。具体章节安排如下。 第一章，主要介绍了问题的研究背景和研究意义，总结了国内外的研究现 状并做了相关文献综述，概述了经济批量问题。 第二章，概述了外包的概念、起源及在实际中的应用情况，并重点介绍了 生产外包。总结了批量问题的基本模型及分类，以及考虑各种特殊因素的模型， 并重点介绍了本文所用到的几种算法。 第三章，研究了带外包的能力受限多产品批量问题，建立了其数学模型， 并给出了拉格朗日松弛算法解决该问题的具体方案。 第四章，采用v c + + 编码实现算法并进行仿真实验，与商用软件l i n g o 得 出的结果相比较验证算法有效性，并随机生成已知量的方式进行相关实验，验 证并分析算法的性能，最后对实验结果进行分析。 第五章，总结了本篇文章的主要工作，并对今后的可以做的研究方向进行 展望。 6 第二章相关问题和方法 基于本文所涉及的一些问题和算法，本章首先总结几种经济批量问题的基 本模型，接着简单介绍外包理论的基本内容，最后介绍本文所用到的几种算法， 其中着重介绍拉格朗日松弛算法。 2 1 经济批量问题的基本模型 在研究经济批量问题的文献中有多种经济批量( e l s ) 模型的公式及其变 种。下面分别给出一些有代表性的单产品批量问题和多产品批量问题的模型。 2 1 1 单产品批量问题模型 7 m i n i m i s ez = ( s t y , + p t x , + h , t ) ( 2 1 ) t = l s t x t + 矗，一五= 西，t = l ，r ( 2 2 ) 新5 慨t = l ，t ( 2 3 ) y t e 0 ，l ，t = l ，t ( 2 4 ) 而，五芝0 ，t = l ，t ( 2 5 ) 其中，刃第t 周期的需求数量；厶第r 周期末的库存量；s t 第，时段 的准备成本；h t 第f 时段的单位库存成本；p ，第f 周期的单位生产成本： 旎第r 周期的生产数量；y ，第r 周期的生产调整变量；m 很大的正 数。 在基本模型的基础上，可考虑以下要素： ( 1 ) 在不考虑启动成本时，可将约束条件( 2 2 ) 和( 2 3 ) 去掉。将约束条件变 为( 2 6 ) 。 7 m i n i m i s ez = ( 肿+ m ) ( 2 6 ) t = i ( 2