基于拉格朗日松弛的产能共享讨价还价研究

以制造业产能共享为背景,考虑自利的产能提供方与需求方诉求不一致和市场关系不对等因素,采用Nash讨价还价理论研究共享产能分配策略。为此,首先将传统调度模型与非对称Nash讨价还价模型相结合,构建出本质为非线性整数规划的产能共享模型。继而,设计了基于拉格朗日松弛的求解算法,给出了产能共享的讨价还价分配结果。仿真分析表明,本文方法在大部分情况下能够获得理想的讨价还价结果。当产能提供方目标为min-sum型,其关注所有客户的自利且异质的时效要求,其与客户方的冲突尤其显著;随着其讨价还价能力的增强,其改善是以牺牲客户时效要求为代价的。然而当其讨价还价能力再继续增加,反而导致系统整体效益的波动。因此,博弈各方需要保持合理的讨价还价强度。

基于拉格朗日松弛算法的列车运行图优化

本文主要研究了列车运行图优化问题。在我们所研究的问题当中,根据单线轨道区间的特点,为了使列车保证经济效益同时也要合理地在规定时刻内运行,这就需要我们寻找一个优化的列车运行图。由于在铁路线上运行的列车种类很多导致速度要求也不尽相同,我们主要针对各种速度不同的列车运行图(即非平行运行图)进行展开研究。本文的主要工作是:一是为进一步深入研究该问题,提出了一类基于时–空图构建的列车非平行运行图优化模型;二是针对该模型我们设计相应的启发式拉格朗日松弛算法进行求解;三是通过数值实验对比了标准次梯度法和修正次梯度法的收敛情况。

增强拉格朗日松弛启发式算法分析

随着优化问题复杂度的不断提高,传统的拉格朗日松弛启发式算法已经无法满足现代人工智能的计算需求。为增强拉格朗日松弛启发式算法,本文首先说明了启发式算法的定义以及特点,其次分析了目前拉格朗日松弛启发式算法分析中存在的算法性能不稳定、求解质量难以保证以及计算时间和空间限制等挑战,最后针对具体挑战,采取了一系列创新措施增强拉格朗日松弛启发式算法的性能,实现了对拉格朗日松弛启发式算法性能的提升,以此为相关人员提供实践参考。

基于拉格朗日松弛强化学习算法的自动发电控制

“双碳”目标加速了大规模新能源并网的新型电力系统的发展。传统控制方法无法有效解决分布式电网模式下新能源规模化接入所带来的强随机扰动,从而造成频率不稳定、控制性能标准(control performance standards,CPS)越来越差的问题。为此,该文从二次调频的角度提出一种能够保证具有较高的Q值更新学习率,且无论强随机环境亦或平稳环境均具有更稳定的响应特性的拉格朗日松弛强化学习算法,即重复更新Q学习拉格朗日松弛(repeated update Q-Learning using Lagrangian relaxation,RUQL-LR)算法,来获取多区域协同。对改进的IEEE标准两区域模型和以西南电网为基础的三区域模型进行仿真,验证了所提算法的有效性。该算法不仅能够在很大程度上提高Q值估计准确性,还能使弱耦合动态优化问题分散为多个子问题,以快速获取最优策略,且与多种强化学习算法相比,其Q值估计误差更小,能明显提高电网的频率稳定性。

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

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

绿色VRP的增强拉格朗日松弛启发式算法

针对绿色多车型车辆路径问题(GHFVRP),建立了以最小化车辆固定成本、行驶成本及碳排放成本之和为优化目标的混合整数规划模型(MIP),并提出一种增强拉格朗日松弛启发式算法(ELRHA)进行求解。首先,通过松弛难约束构造对偶问题,并分解为两个子问题,再采用次梯度法更新拉格朗日乘子,求解两个子问题获得原问题的下界;其次,设计一种两阶段启发式算法对下界进行修复及优化,以获得较好可行解并更新问题上界;最后进行仿真实验,实验结果表明:在相同实验环境下对17个算例进行20次测试,ELRHA平均求解间隙为4.49%,相较Gurobi提升3.28%,同时与其它算法对比进一步验证了ELRHA能求解问题高质量上界。可见,ELRHA能有效求解GHFVRP。

基于拉格朗日松弛框架的消防站点选址优化方法

城市火灾可能造成严重的生命财产损失,科学合理的消防站布局可以有效提升消防救援效率并降低系统运行成本。以最小化救援等待损失与消防站点建设成本为目标,将消防车行驶时间作为模型参数,构建消防站固定费用选址的整数规划模型。设计基于拉格朗日松弛框架的精确求解方法,并对算法有效性进行了验证。对天津市津南区消防站布局进行实例优化,并对等待损失成本和消防车行驶时间等参数进行了敏感度分析,为城市消防站点规划提供了更为科学的决策参考。

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

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

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

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

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

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

基于拉格朗日松弛技术的复杂有源配电网分布式状态估计

为了提高复杂有源配电网状态估计问题的计算速度,提出了一种基于拉格朗日松弛技术的复杂有源配电网分布式状态估计方法。建立了复杂有源配电网分区模型,该模型从复杂有源配电网的量测配置情况和分布式并行计算效率角度出发,综合考虑了分区后各子区域的计算速度与精度,利用拉格朗日松弛技术将分区问题中的约束条件吸收到目标函数中,降低了分区模型的求解难度。通过网络解耦技术使各子区域相对独立,可在分布式并行环境下求解该网络的状态估计问题。各子区域选取指数型目标函数状态估计模型,该模型能够自动排除不良数据影响,在保证结果精度的同时有效减小了所求问题的系统规模和雅可比矩阵阶数,提高了状态估计算法效率。仿真算例结果表明,所提方法可实现对复杂有源配电网的合理分区,有效提高了状态估计的计算速度。

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

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

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

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

基于拉格朗日松弛的高速铁路列车运行图新增运行线局部调整模型

给定新增列车理想始发时刻及初始利润,考虑始发时刻调整及全程停时延长造成的罚数,基于时空网络构建以全图运行线总利润最大为目标的整数规划模型,进行拉格朗日松弛,根据松弛解对偶信息设计启发式算法求解各运行线可行解,并通过更新拉格朗日乘子进行迭代优化.以京沪高铁为例进行了验证,结果表明:在算例条件下,相较以理想始发时刻推线求解,该方法能够多增铺6条运行线;随着始发时刻可调整度由10 min增加至60 min,CPLEX的求解时间快速增长,而拉格朗日松弛启发式算法能快速求得高质量的解,除始发时刻可调整度10 min情景,求解效率均高于CPLEX;延长始发时刻可调整度至4 h,最多增铺18条运行线,说明现有框架下京沪高铁能力已接近饱和.

求解无容量设施选址问题的半拉格朗日松弛新方法

无容量设施选址问题(un-capacitated facility location,UFL)是应用于诸多领域的经典组合优化难题,半拉格朗日松弛方法是求解UFL问题的一种精确方法.分析了半拉格朗日松弛方法在求解UFL问题时所具有的性质,在此基础上,对求解UFL问题的半拉格朗日松弛方法进行了一定的理论完善,并探讨了提高半拉格朗日松弛方法求解性能的有效途径.数值计算结果表明:改进方法具有明显的可行性和有效性.

实时无等待HFS调度的一种拉格朗日松弛算法

研究了实时无等待HFS调度问题,并建立一个整数规划模型,提出运用拉格朗日松弛算法来求解.在此算法中,常采用次梯度方法更新拉格朗日乘子,但它随着迭代数的增加收敛速度会减慢,因此设计了一个改进的bund le方法,将以前的次梯度累积到bund le中,以获得一个更好的乘子更新方向.仿真实验表明,与次梯度方法相比,所设计的bund le法不仅在较少的迭代数内得到了更快的收敛速度而且改进了优化性能,对于大规模问题效果更为显著.

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

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

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

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

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

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

利用拉格朗日松弛算法协调多厂供应链生产计划

为了解决多厂供应链生产计划的协调问题,提出了一种基于拉格朗日松弛算法的内部价格协调优化策略。该策略通过松弛工厂之间的物料耦合约束,将整个供应链的生产计划问题分解为多个单厂的生产计划问题。每个工厂只需利用本地信息制定各自的生产计划。为了获取问题的可行解,又提出了一种前溯式可行化方法,通过协调中心对产品内部价格(拉格朗日算子)的迭代更新,实现整个供应链生产计划的协调优化。仿真实验表明,该策略能够较好地协调多厂供应链计划,结果明显优于已有的协调方法。