基于拉格朗日松弛的供应链计划协调.doc

基于拉格朗日松弛的供应链计划协调 主题八过程先进控制、优化技术研究及应用435基于拉格朗日松弛的供应链计划协调李亚平1赵天智2（1中国石化管道储运分公司信息中心，徐州2210082石化盈科信息技术有限责任公司，北京100007）摘要以流程行业企业的供应链为背景，建立了集成的生产和配送计划模型。 通过分析工厂和配送中心计划决策的关联约束，利用拉格朗日松弛方法松弛关联约束，构造了工厂生产计划子模型和配送中心配送计划子模型的分布决策结构。 基于次梯度优化算法提出了一种优化协调机制，通过迭代优化拉格朗日乘子，实现分布决策下的协调优化。 关键词供应链计划；分布决策；协调机制；拉格朗日松弛Lagrangian RelaxationBased Coordinationfor Supply Chain PlanningLi Yaping1Zhao Tianzhi2(1Sinopec PipelineStorage&Transportation Co.,Ltd Xuzhou2210082Petro-CyberWorks InformationTechnology Co.,Ltd.,Beijing100007,China)Abstract:Coordination ofsupply chainplanning decisionsis oneof thekey issuesin supplychain managementbecause ofthe interdependenciesbetween thesedecisions.In thispaper,an integratedproduction anddistribution planningmodel isestablished fora supplychain inprocess industry.By relaxingthe couplingconstraints viaLagrangian relaxation method,the integratedmodel isdeposed intoproduction anddistribution planningsubmodels,which constructa distributeddecision-making structure.To achievecoordinated planningdecisions underdistributed structure,a coordinationmechanism basedon subgradientoptimization algorithmis presented.By updatingLagrangian mulitpliersiteratively,production anddistribution planningdecisions areled toglobally optimizedgoal.Keywords:SupplyChainPlanning；Distributed Decision；Coordination Mechanism；Lagrangian Relaxation随着供应链概念的提出，供应链管理已成为当今企业提升竞争力的主要途径。 所谓供应链是指由一系列负责采购、生产、分销活动的自主或半自主业务实体组成的网络1。 这些实体成员在供应链中扮演着诸如供应商、生产商、分销商、零售商等角色，彼此之间通过物流、信息流、资金流连接和交互。 供应链管理要求核心业务提升的同时，更强调成员间业务决策协调。 这使得企业间的界限模糊化，从企业内部看，通过外包及放权等方式，职能部门或子主题八过程先进控制、优化技术研究及应用436业务单元具有更独立、更灵活的自主决策权；从企业外部看，企业间通过联盟或信息共享等整合措施增强协作性，关系更紧密。 供应链管理涉及多个自主决策实体成员，每个成员拥有自己的目标、信息、决策权，它们基于各自的局部目标和信息进行各自的优化决策，共同决定着供应链的整体绩效。 然而，由于信息的分布、目标的差异、利益的冲突，成员的个体局部优化决策并不意味供应链整体2。 因此，供应链协调是供应链管理所面临的最主要挑战之一。 目前，供应链3，一是契约协调，主要思想是通过契约机制来平衡供应链成绩效的最优化协调研究主要体现为三个方面员决策激励，使其与供应链整体目标趋于一致，从而提升供应链整体绩效，同时达成“双赢”效果，然而因契约可实现性和建模复杂性，契约协调主要局限于战略层面的分析。 二是基于规则的协调，人工智能领域多主体系统（Multi-Agent System）在供应链建模和仿真方面展现巨大潜力，并发展出一系列基于规则的协调策略，但基于规则的协调方法难以给出问题优化解，且依赖于特定问题。 三是数学优化方法，这是解决计划和调度等运筹问题的传统方法，文4综述了这类问题和方法，这些方法多是假设单一决策者的集中式决策结构的理想情况。 值得一提的是，文5针对生产调度问题提出的分布优化方法，代表了这一研究领域的新方向。 生产和配送是供应链中的核心环节。 在实践中，往往通过库存将二者隔离开来而分别管4，这不仅增加了库存，还造成供需不匹配、供货延迟等问题。 从研究领域看，近年来虽67，但一般都以统一决策权、完全信息的集中式决策为假设，而没有考虑二者的分别决策协调问题。 理然关于生产和配送的集成研究成果逐渐涌现本文结合某大型流程行业企业的供应链计划模型，建立工厂和配送中心的集成的生产和配送计划模型。 从分析模型中工厂和配送中心的关联约束着手，利用拉格朗日松弛技术松弛关联约束，将模型分解为工厂生产计划子模型和配送中心配送计划子模型，从而构造一种针对工厂和配送中心的分布决策结构。 同时，基于次梯度优化算法迭代更新拉格朗日乘子，作为一种协调机制，实现分布决策下的系统全局优化。 1供应链计划模型1.1问题描述本文考察的对象是某大型流程行业企业供应链，包括供应商、工厂、配送中心及客户四个环节，如图1所示。 供应商包括内部供应和外部供应两类，负责供应生产所需各种原材料。 工厂完成从原料到产品的加工，产品的产量依赖于物料单定义的投入产出比例，并受限于工厂装置产能，工厂间不存在物料互供。 工厂生产的产品发送到配送中心，配送中心根据客户的需求负责产品存储和分销。 供应链计划决策包括采购、生产、库存和配送等计划决策。 主题八过程先进控制、优化技术研究及应用437图1供应链结构本文建立的模型仅考虑图1中方框所界定的工厂和配送中心，一方面是因为生产和配送是企业的核心业务，另一方面是因为生产和配送计划模型足以描述本文所提出的协调策略和方法，同时采购等业务可以在此基础上扩展。 1.2供应链计划模型为简化起见，首先提出一些假设条件 （1）忽略产品生产的提前时间，忽略产品从工厂到配送中心的运送时间，即生产和运输可在本周期内完成，模型可以通过定义提前时间容易地考虑该假设。 （2）工厂间不存在物料互供或转运。 （3）运输成本和订货成本仅考虑依赖于数量的变动成本，不考虑固定成本。 （4）库存按期末库存数量计。 （5）不考虑生产准备的产能消耗。 （6）成本参数不随时间变化。 生产和配送计划模型就是给定产品需求及相关模型参数下，确定每个周期的工厂生产、库存、运输及配送中心库存、订货等决策。 模型参数定义如下指标集i:产品，i=1,I l:工厂，l=1,L t:周期，t=1,T k:产能资源类型，k=1,K参数M:足够大的正数，可取需求总量主题八过程先进控制、优化技术研究及应用438a ikl:工厂l生产单位产品i的产能类型k消耗系数Ckl t:在周期t工厂l的产能类型k的可获得数量chi l:工厂l单位库存成本cp i l:工厂l单位生产成本cs i l:工厂l单位生产准备成本ct i l D:工厂单位运输成本ch iD:配送中心单位库存成本cqi D:配送中心单位订货成本决策变量Pi l t:工厂l在周期t的产品i的产量I i l t:工厂l在周期t的产品i的库存水平ilt:工厂l在周期t生产准备变量Ti lt:工厂l在周期t发往配送中心的产品i的数量I iDt:配送中心在周期t的产品i的库存水平Qi Dt:配送中心在周期t的产品i的订货数量根据以上供应链结构及参数定义，建立供应链计划模型M C如下目标函数1minTil iltililtililtilDilDtct TiDiDtch IidiDttiNI lNLCch IcpPcscq Q=?=+ (1)目标函数包括工厂的库存成本、生产成本、生产准备成本、运输成本，及配送中心的库存成本和订货成本。 需要说明的是，运输成本在此计为工厂的成本项，通过变量定义，也可以计为配送中心的成本项。 优化目标即为成本最小化。 约束条件,1,iltil tiltiltilDtIPIT?+=+? (2)主题八过程先进控制、优化技术研究及应用439,iltiltiltPM? (3),ikliltkltia PCklt? (4),1,iD tiDtiDtitIQIdi t?+=+? (5),iDtiltlQTi t=? (6),0,0,1,iltiltiltilDtiltPIT? (7),0,iDtiDtIQi t? (8)其中，约束方程 (2)为工厂库存平衡方程。 式 (3)为工厂的生产准备变量强制性约束，只有在生产准备启动下才能进行生产。 式 (4)为工厂的产能限制约束。 式 (5)为配送中心库存平衡方程。 式 (6)配送中心订货与工厂送货平衡约束。 式 (7)、 (8)分别为工厂决策变量及配送中心决策变量的取值限制，其中生产准备变量为0-1变量。 2基于拉格朗日松弛的分布决策及协调优化2.1基于拉格朗日松弛的模型分解拉格朗日松弛技术是一种通过松弛复杂约束进行迭代优化求解的方法。 具体来说，就是通过拉格朗日乘子将松弛约束作为惩罚项引入目标函数，再通过乘子迭代求解对偶问题，从而获得原问题的优化解。 通过分析发现，在供应链计划模型MC中，除去约束条件 (6)，模型可以分解为工厂和配送中心两部分子模型，即工厂计划决策与配送中心计划决策通过约束 (6)发生关联，故约束 (6)称为关联约束。 为此，针对关联约束 (6)定义拉格朗日乘子it，得到如下拉格朗日松弛函数()minmin()()LRil iltililtililtilDilDtct TiDiDtch IidiDttilitiDtilDttilililtililtililtilDitilDttiliD iDtchIiditiDttiCch IcpPcscq QQTchIcp PcsctTcqQ?=+?+?=+?+ (9)从拉格朗日函数可以看出，目标函数分为工厂和配送中心两部分，于是原问题分解为工厂子模型MP和配送中心子模型MD。 主题八过程先进控制、优化技术研究及应用440工厂子模型（MP）()min()MPil iltililtililtilDitilDttilCchIcp PcsctT=+? (10)s.t. (2), (3), (4), (7)工厂生产计划子模型是典型的有限产能批量大小问题（Capaci tatedLot-Si zing Problem），由于0-1变量的出现使该问题成为N P-hard问题关启发式方法进行求解。 8，可以借鉴文9所综述的有配送中心子模型（MD）()min()MDiD iDtchIiditiDttiCcqQ=+ (11)s.t. (5), (8)配送中心计划子模型可直接通过线性规划方法求解。 子模型与拉格朗日问题的关系为CLR()=CMP()+CMD()。 分解后的子模型间的决策关联关系通过拉格朗日乘子反映，拉格朗日乘子的变化将影响子模型的决策。 通过拉格朗日*，获得最优解，即全局最优决策。 对偶问题求解最优乘子2.2拉格朗日乘子求解及其协调过程根据对偶理论，拉格朗日对偶问题是连续不可微凹函数11。 CLR()的拉格朗日对偶问题为10，次梯度优化算法是求解拉格朗日乘子的有效方法maxl()lDLRCC= (12)基于次梯度算法的乘子迭代式为1()()(),nnnnititits gitll+=+ (13)其中g为次梯度，可以直接从松弛的关联约束获得，即itiDtilDtlgQT=? (14)其中n为迭代次数，s为步长，步长的选取影响迭代过程的收敛性，一般地，根据12nnLRnnitCCsga-= (15)主题八过程先进控制、优化技术研究及应用441选取步长，其中为步长参数，一般取12-2(1,20)，C为原问题的一个上界，LRC为对偶值，即当前的下界解。 有关收敛性分析详见文10。 基于次梯度算法的拉格朗日乘子迭代步骤为 （1）初始化拉格朗日乘子= 0、迭代次数n= 1、步长参数、下界值LRC及上界值C。 （2）求解工厂和配送中心计划决策的子问题MP和MD。 （3）计算新的下界解111()()()nnnLRMPMDCCC?=+，如果拉格朗日解可行，则停止计算，该解即为问题MC最优解，否则，更新下界LRC。 （4）根据当前解计算次梯度和步长，按迭代式 (13)更新拉格朗日乘子。 （5）若满足收敛或停止条件，则停止迭代；否则，返回步骤 （2）。 需要指出，上界解C是通过启发式方法获得的可行解，随启发式方法的不同，也可以迭代更新。 拉格朗日乘子的迭代更新，影响并引导子模型决策趋于全局最优解，因此基于次梯度算法的拉格朗日乘子迭代可以看作一种协调机制，其的更新过程即为决策的协调过程。 而且该协调机制是一种优化协调机制，它引导分布决策达成全局最优决策。 3结论本文建立供应链生产和配送计划模型，提出一种基于拉格朗日松弛方法的分布决策结构及协调机制，该协调机制在供应链成员分布决策结构下可以实现全局最优，为供应链协调提供了一种解决思路。 该协调策略还有几个问题有待解决，首先是拉格朗日乘子的迭代更新任务由哪个角色承担，对于同属一企业的供应链成员，可考虑由企业总部作为协调中心，对于分属不同企业的供应链成员，则需要进一步研究协调任务的分配。 其次，协调机制虽然可以引导分布决策趋于全局最优，但还未考虑决策激励问题，每个成员是否愿意采纳该协调决策，还需激励机制来保证。 最后，就是优化协调机制能否扩展到更多阶段和层次的供应链模型。 这些问题将是今后的研究方向。 主题八过程先进控制、优化技术研究及应用442参考文献1Swaninathan J M,Smith SF,and SadehN M.Modeling supplychain dynamics:A multi-agent approachJ.Decision Sciences,1998,29 (3):607-632.2Tsay AA,Nahmias S,agrawa N.Modeling supplychain contracts:A reviewC.in:TAYUR S,GANESHAN R,and MagazineM,eds.Quantitative Modelsfor SupplyChain Management.Boston:Kluwer,1999,299-336.3赵天智，金以慧.基于依赖关系的供应链协调J.计算机集成制造(CIMS),xx,10 (8):929-933.4Thomas DJ,Griffin PM.Coordinated supplychain managementJ.European Journalof OperationalResearch,1996,94 (1):1-15.5Luh PB,Ni M,Chen H,et al.Price-based approachfor activitycoordination ina supplyworkJ.IEEE Transactionson Roboticsand Automation,xx,19 (2):335-346.6Erenguc,S S,Simpson,N C,and Vakh