带最小批量约束的计划问题及其拉格朗日松弛算法

针对一类带最小批量约束的计划问题,提出了基于拉格朗日松弛策略求解算法.通过拉格明日松弛策略,将原问题转为一系列带最小批量约束的动态经济批量W-W(Wagner-Whitin)子问题.提出了解决子问题且其时间复杂度O(T^3)的最优前向递推算法.对于拉格朗日对偶问题,用次梯度算法求解,获得原问题的下界.若对偶问题的解是不可行的,通过固定装设变量,求解一个剩余的线性规划问题来进行可行化处理.最后,数据仿真验证了算法的有效性.

一种基于拉格朗日松弛的时延约束多播路由算法

提出了一种基于拉格朗日松弛方法的时延约束最小代价多播路由算法(LR-DLMA)。该算法充分利用拉格朗日松弛方法的特点,通过构建封闭图,对封闭图进行拉格朗日松弛求得满足条件的多播树。仿真实验结果表明本算法性能稳定,其代价性能接近性能最好的BSMA算法,并具有快速、低时延的特点。

基于改进拉格朗日松弛算法的电力通信网络负载均衡优化策略研究

针对传统电力通信网络路由策略存在的负载分布不均和丢包率较高等问题,基于软件定义网络,提出了一种基于改进拉格朗日松弛算法的电力通信网络QoS路由策略。以链路时延、可用带宽和丢包率为约束建立路由模型,并采用改进的拉格朗日松弛算法进行路径选择。通过仿真与传统路由方法进行对比,验证了该方法的可行性。结果表明,与传统路由策略相比,该方法能够规划出符合QoS要求的路径,负载分布更加均衡,有效降低了业务丢包率,丢包率由45%降低到0.1%,具有一定的实用价值。

改进拉格朗日松弛算法的机组组合研究

为提高计算效率,并针对传统拉格朗日松弛算法(LR)在优化过程中存在对偶间隙不能收敛的问题,提出了一种改进的拉格朗日松弛算法(LR CMSCA)以优化大规模机组组合问题。首先通过正弦余弦算法(SCA)优化拉格朗日乘子的更新路径,以缓解振荡现象;然后在SCA中引入柯西变异算子对当前粒子进行干扰,尽可能避免陷入局部最优,并引入自适应权重更新策略,使粒子更快逼近最优解;最后利用不同机组规模的电力系统进行仿真计算,并将计算结果与其他算法进行比较。结果表明,该方法在计算结果上具有优势,且有实际应用价值。

基于拉格朗日松弛法的时延约束组播路由算法

通过对时延约束组播路由网络模型的分析,提出了一种基于拉格朗日松弛法的时延约束的低代价组播路由算法(LR-DLMR)。由于封闭图对原网络的多播不可达问题,该算法并没有构建原网络的封闭图,从而有效利用了链路中间节点信息。仿真实验结果表明本算法具有良好的稳定性,有较低的代价和时延。

一种基于拉格朗日与时间解耦的超大规模SCUC求解框架

安全约束机组组合(security constrained unit commitment,SCUC)是电网出清场景中最为广泛使用的一类模型。建立了一种针对超大规模SCUC现货市场出清问题的求解框架,首先提出了SCUC问题的时间解耦求解方法,通过缩小问题的规模来加快求解速度;其次针对时间解耦后模型的子问题提出了拉格朗日松弛求解技术,在不影响求解准确度的情况下,有效降低了关键困难约束的求解难度。数值实验证明,所提出的框架极大地提升了求解效率,且十分稳定。

基于拉格朗日松弛与最大分支算法的卫星成像调度算法

成像调度算法是卫星成像规划中的关键部分之一。建立了卫星成像调度问题的0-1整数规划模型,该问题具有NP完全特性。提出了一种基于拉格朗日松弛与最大分支算法的多项式时间复杂度的优化算法。该算法可以计算出接近最优解的上界及可行解,并给出可行解的优化度。基于该算法提出了一种先验可行解条件下改进上界及可行解的二次优化算法。实验结果表明,该算法在时间性、优化度等方面取得满意的结果。

基于拉格朗日松弛和遗传算法的供应链协同计划

研究了多级供应链伙伴间的生产计划协调优化问题。对集成性多阶段约束生产批量计划模型增加了关联约束和相关需求约束。基于模型的加可分性结构,利用拉格朗日松弛技术将其分解为成员独立的子问题。应用遗传算法更新拉格朗日乘子来协调成员决策,在不干涉成员决策权和私有信息的前提下,实现了多级供应链生产计划的协调优化。仿真实验证明了基于拉格朗日松弛技术与遗传算法的计划协同模式和协调方法的优越性和鲁棒性。

利用模糊次梯度算法求解拉格朗日松弛对偶问题

针对利用次梯度算法处理拉格朗日松弛对偶问题时,计算过程容易出现振荡,求解效率较低的问题,首先提出了一种基于模糊理论的次梯度算法,利用隶属度函数给出迭代过程中所有次梯度的合适权重,并将它们线性加权得到新的迭代方向;其次证明了算法的收敛性;最后通过仿真实验验证了该方法的有效性.

技术站配流与调机运用综合问题的拉格朗日松弛算法

技术站调度问题中配流与调机运用是关系密切的两个基础问题。基于单机器调度和资源分配理论,构建单解单编技术站配流与调机运用综合问题的混合整数线性规划模型,同时确定出发列车的编组内容和调机的解编任务,使得出发列车满足列车编组要求,且车辆在站加权总停留时间最小。设计拉格朗日松弛算法松弛掉连接约束,将原问题分解为解体子问题、配流子问题和编组子问题,对偶问题采用传统次梯度优化算法求解。最后,采用既有文献算例对该算法的有效性进行测试,结果表明:与分支定界算法相比,该算法能够实现计算质量和时间的较好折中。

多传感器多目标数据互联中的拉格朗日松弛算法研究

拉格朗日松弛算法在现代优化启发式算法中占有重要地位，本文对多维分配问题的拉格朗日松弛算法进行研究，重点研究松弛次序对数据互联结果的影响。研究方法是针对不同测量误差情况下进行计算机仿真实验。结果表明，多传感器多目标数据互联的拉格朗日松弛算法中，松弛探测效果较好的传感器的观测数据，有助于提高目标关联的准确率，且算法的计算量相应减少。该结论使多维分配问题的拉格朗日松弛算法能满足工程上对数据进行实时处理，具有实际应用价值。

带批和离散机柔性流水车间问题的混合异步次梯度优化的拉格朗日松弛算法

为有效解决串行批调度问题,提出了一个混合异步次梯度优化的拉格朗日松弛算法,来求解带批和离散机的柔性流水车间问题(FFSP),目标是最小化总加权完成时间。该问题来源于钢铁业的炼钢-连铸-热轧一体化生产过程,为了加快算法的求解速度,扩大求解规模,在拉格朗日松弛优化算法中引入异步次梯度优化,每次迭代仅最优求解一个批级子问题,而其他子问题的解仍维持为前一次迭代的值,以此获取一个合理的乘子更新方向,大大缩短了每次迭代所消耗的运行时间。通过与基于批解耦和次梯度法的拉格朗日松弛算法的实验对比,说明了无论是实际生产数据还是随机产生的大规模数据,所提出的改进拉格朗日松弛算法都能获得具有竞争性的结果,对于较大规模问题,它在解的质量和收敛速度方面的优势更加明显。

大规模货物列车运行图优化编制的一种拉格朗日松弛启发式算法

针对货物列车运行图优化编制规模庞大、精确求解困难的问题,构造时空网络将列车运行线铺画描述为路径求解问题,将各类约束转化为时空网络节点选择限制,建立整数规划模型。该问题本质在于疏解各列车运行线潜在冲突。对原模型进行拉格朗日松弛,将列车运行线潜在冲突表示为各节点罚数,设计启发式算法并通过拉格朗日乘子更新迭代求解。以京九线北京西至阜阳区段为例,对该区段711条运行线中的439条货物列车运行线进行了优化编制实验。结果表明,在满足运行线铺画条数的前提下,全图货物列车平均旅行速度由39.28 km/h提升至41.81~43.72 km/h,所提出的算法是解决大规模列车运行图编制的一种有效算法。

拉格朗日松弛算法在平台罗经多故障诊断技术中的应用研究

最优多故障诊断问题是一个NP-hard问题。针对平台罗经这一复杂系统,采用有向图描述元件与测试点间的因果依赖关系,并建立系统的多信号模型。在考虑元件发生故障的先验概率的前提下,提出一种基于拉格朗日算法(LRA)和子梯度优化算法(SOA)近最优多故障诊断算法,并在某型平台罗经的方位稳定系统多故障诊断中得到应用。结果表明:该方法相对于传统的单故障诊断方法诊断速度快,适用于平台罗经这类大型复杂系统的多故障诊断。

冷链物流越库调度的拉格朗日松弛算法

为了提高冷链物流的运输效率,解决越库在冷链物流中的应用问题,提出了基于拉格朗日松弛算法的冷链物流的越库调度方法.首先进行了问题域的描述并做出了具体假设,基于问题域以最小化卡车等待时间和越库内部运输成本为目标,建立越库调度的整数规划数学模型.然后,提出了针对越库调度模型的拉格朗日松弛算法,松弛复杂约束后根据决策变量将松弛问题分解为若干子问题,采用次梯度算法求解松弛模型.最后,对各种不同规模的越库模型进行仿真实验,并与传统的贪婪算法进行对比,结果表明,所提出的调度算法适用于问题的求解,并可以在较短时间内获得良好的近优解.

利用拉格朗日松弛算法求解三维分配问题

将拉格朗日松弛算法与最优求解算法的复杂性进行了分析比较,并将该算法应用于求解3-D分配问题,分析与算例结果表明,该算法可大幅度降低3-D分配问题的求解计算量,是求解3-D分配问题的一种有效算法.

拉格朗日松弛对偶问题的一个改进次梯度算法

拉格朗日松弛法是处理整数优化问题的一个重要方法。针对利用次梯度算法求解拉格朗日松弛对偶问题时容易出现收敛速度较慢及计算效率低等问题,对次梯度算法进行了改进:结合当前次梯度和历史次梯度的线性组合给出新的迭代方向,然后决定合适步长。同时证明了算法的收敛性及有效的消除迭代过程中的锯齿现象。将改进的拉格朗日松弛的次梯度算法用于解决TSP问题,数值计算结果表明,改进的次梯度算法比普通次梯度算法收敛较快,说明了改进算法的有效性。

基于拉格朗日松弛算法的终端区飞机排序研究

终端区飞机排序问题是减少航班延误、降低成本的关键技术。考虑机型运行成本和飞机总延误时间,建立一个0~1整数规划模型。因其是一个组合优化问题,多约束相互制约,采用拉格朗日松弛算法将复杂约束转换为线性约束进行求解。仿真结果表明,求得的进近队列延误小、延误成本低、无冲突,且拉格朗日松弛算法计算得到的结果更为可靠,符合实际运行需求,结果优于传统的启发式算法。

等待时间受限的HFSP及其拉格朗日松弛算法

等待时间受限的混合流水车间调度问题(HFSP)广泛存在于钢铁生产,玻璃加工和塑料等行业。目前,关于等待时间受限的HFSP的研究较少。首先建立了等待时间受限的混合流水车间调度问题模型,然后设计了基于工件分解策略的拉格朗日松弛算法来进行求解。该算法通过将机器容量约束松弛到目标函数中,将得到的松弛问题进而分解为一系列易于求解的工件级子问题来进行求解。最后对设计的算法进行仿真验证,测试结果表明所设计的拉格朗日松弛算法能够在较短的时间内产生较好的近优解。

需准备时间的FFS调度的一种拉格朗日松弛算法

针对需调度顺序相关准备时间的柔性流水车间生产调度问题,建立以成本最小化为目标的整数规划模型,用基于拉格朗日松弛的方法来求解。在常用的次梯度算法处理拉格朗日对偶问题时,迭代过程易出现振荡,严重影响了收敛效率。因此,利用了隶属度函数给出迭代过程中所有次梯度的合适权重,将它们线性加权得到新的迭代方向。最后通过算例表明,此算法有效的减少了迭代次数,提高了算法的优化性能。