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

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

基于拉格朗日对偶松弛的多区域柔性直流互联电网无功优化

现有方法对互联后的电网进行无功优化时难以满足大规模电网实时计算、快速反应的需要,并且面临全网数据收集的难题。为了解决上述问题,采用分解协调算法的思想,提出一种基于拉格朗日对偶松弛的多区域柔性直流互联电网无功优化方法。首先根据支路潮流模型,利用二阶锥松弛和二次旋转锥松弛方法建立了多区域柔性直流互联电网的集中式无功优化模型。然后利用拉格朗日对偶松弛理论在集中式优化模型的基础上,提出了可以并行计算的多区域柔性直流互联电网无功优化方法。通过算例计算,验证了所提算法的有效性和正确性。此外,还对比分析了所述的分解协调算法和基于交替方向乘子法(ADMM)的分布式优化算法的计算结果,证明所用算法在计算时间上更具优势。

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

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

基于拉格朗日的高速铁路车站作业优化

本文从Job-Shop调度角度出发,以列车为待加工的'工件',将车站接车进路、到发线和发车进路看作'加工机器',列车在车站的走行与停站看做不同的'作业工序',把高速铁路车站作业问题抽象成Job-Shop车间调度优化,以设备能力、冲突进路、停站时间为空间和时间约束,以最小化到发线的占用时间为优化目标,建立高速铁路车站作业优化模型.采用拉格朗日方法松弛原模型的约束条件,建立车站技术作业问题的拉格朗日对偶松弛问题,设计了高速铁路车站作业优化模型算法.并以高速铁路的某一车站为实例进行验证,实例表明,该算法可以有效地化解车站作业进路冲突和实现到发线运用时间的最小化.

电动汽车充电站有序充电调度的分散式优化

大量电动汽车无序充电会给电力系统尤其是配电系统的安全与经济运行带来影响甚至挑战。针对集中式优化与控制方法的不足和固定电价策略的缺陷,基于拉格朗日松弛法,将传统的电动汽车充电站有序充电调度集中式优化问题分解为N个子问题(N为需充电电动汽车数量),提出了有序充电调度的分散式优化策略。优化模型以充电站收益最大为目标函数,考虑了用户用电需求、充电时间、变压器容量等约束和充电站分时电价策略。为验证所提方法的有效性,采用蒙特卡洛法模拟电动汽车充电需求,对采用集中式优化和分散式优化策略的有序充电和无序充电情形,以及充电站售电固定电价和分时电价模式下的充电站收益、削峰填谷效果、计算效率等进行仿真计算和分析。结果表明,所提方法相比于无序充电及充电站固定电价策略,可显著提高收益;相比于集中式优化,计算效率更高;充电站采用售电分时电价虽有"填谷"效果,但平抑负荷波动效果并不十分理想。

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

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

基于拉格朗日松弛的航天测控调度上界求解算法

通过分析航天测控调度问题的测控需求,建立了航天测控调度0-1整数规划模型,运用拉格朗日松弛方法对模型中的设备约束和卫星约束进行了松弛,运用次梯度优化算法求得了拉格朗日对偶问题的上界。最后,通过对两个场景的试验分析,证明了运用次梯度优化算法求得的上界的有效性。

考虑滞时电量的水电中期调度拉格朗日松弛方法

针对梯级水电站群中期调度水流滞时问题,引入滞时电量概念,建立了梯级水电站群中期调度期末蓄能最大模型;采用基于两阶段次梯度法乘子更新策略的拉格朗日松弛方法进行模型求解,第一阶段通过系数递增策略快速确定乘子初始值,第二阶段采用递减策略加快算法收敛速度。以澜沧江中下游梯级6座水电站群中期优化调度为实例进行仿真,结果表明,所提出的求解方法能提供较好的求解质量;考虑滞时电量能提高水电系统的期末蓄能,中期调度需充分考虑调度结果的后效性。

基于拉格朗日法的空调系统不确定性分析

为了研究建筑物中人行为对建筑能耗的影响,本文研究了建筑物中的不确定性,分析了不同工况下的制冷系统能耗情况并采用拉格朗日松弛法对冷水机组和制冷系统进行优化调度。实验显示,优化前冷水机组与制冷系统的能耗值分别为157 680 kW和210 240 kW。采用拉格朗日松弛法优化后的能耗值分别为149 422 kW和198 993 kW,节约的能耗值分别为8 258 kW和11 247 kW,节能率为5.2%和5.3%。而采用传统的顺序启停算法优化后的能耗值分别为149 422 kW,198 993 kW,节约的能耗值分别为5 203 kW,5 676 kW节能率为3.3%和2.7%。结果表明,拉格朗日松弛法节能效果好于顺序启停优化策略。利用该优化策略进行优化控制,既可满足建筑的冷负荷需求,又可降低系统能耗。

考虑需求侧响应的电气设备调度混合分散式优化

为了缓解用能持续增加对电力系统造成的负担和解决大规模电气设备联合调度时的优化计算问题,提出了考虑需求侧响应的大规模可控用电设备和储能设备的混合分散式优化调度方法。首先,建立可控用电设备负荷和储能设备的数学模型,在此基础上,构建了以系统和各设备运行特性为约束,以系统购电费用、用户不满意度费用和储能设备损耗费用之和最小为目标函数的混合整数非线性集中式优化数学模型。其次,针对此高维、多目标和多约束且难于求解的非线性集中式优化模型,采用拉格朗日松弛法将其分解为两个子问题,即分别对应可控电气设备负荷的优化调度问题和储能设备的优化调度问题。对于前者又可进一步分解为各可控电气设备负荷的优化调度子问题,并通过内点法求解计算;对于后者又可分解为各个储能设备问题的混合整数线性优化调度子问题,并通过Benders分解法并行求解计算。然后,为了验证所提混合分散式优化方法的有效性及其优越性,基于算例,对比分析集中式和分散式优化调度时的目标函数值和电气设备优化调度结果,不同规模电气设备对集中式和分散式优化方法计算效率的影响。根据结果可见,所提优化调度方法与集中式优化方法的目标函数值基本一致,但所提方法对应的电气设备优化调度结果可以很好地响应分时电价策略,储能设备削峰填谷效果好;而且,所提混合分散式优化方法可以降低优化问题的求解复杂度,计算效率高,几乎不受电气设备规模的影响。

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

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

航天TT&C调度的拉格朗日松弛策略

根据航天遥测、跟踪和指挥(TT&C)调度的测控需求,建立航天测控调度问题的0-1整数规划模型,运用(λ,ν)、(μ,ν)和(λ,μ)3种策略对模型中的约束进行松弛,通过次梯度优化算法求得每种松弛问题的上界。利用2个场景验证上界(目标函数值)的有效性,调度结果表明,3种松弛策略中以次梯度优化算法得到的上界差别最小。

分散架构下多虚拟电厂分布式协同优化调度

双碳战略与电力市场改革背景下,未来配电网中将形成多虚拟电厂共存的格局。为实现利益主体各异的多虚拟电厂协调优化调度,该文基于“信息分离、决策协同”思想,提出一种基于拉格朗日对偶松弛的多虚拟电厂分布式协调优化调度方法。首先,构建多虚拟电厂分布式协调优化控制机制;接着,构建多虚拟电厂多时段协调优化调度模型,基于供需关系构建虚拟电厂间交易电价函数;然后,利用拉格朗日对偶松弛理论对优化模型进行松弛,将原问题转为多虚拟电厂分布式优化问题,并采用分布式部分可观测的马尔科夫决策过程将日前多时段协调优化调度问题重构为实时优化调度问题,基于改进量子遗传算法对优化问题进行求解;最后,通过仿真计算验证了所提方法的有效性。

改进拉格朗日松弛算法在多故障诊断中的应用

为解决单故障策略可能出现的误诊和漏诊问题,从多故障的征兆出发,建立表征故障-测试依赖关系的多信号模型图,基于后验概率最大的思想,借助单故障诊断树的测试序列,采用拉格朗日松弛与次梯度优化方法求解多故障问题。进一步对次梯度算法的迭代步长提出改进,在设备研制初期传感器信息不足的情况下,对多故障进行准确定位。实例结果验证了该方法能够有效地排除隐含故障和伪故障,改进算法具有更好的诊断效率。

基于拉格朗日松弛的水灾逃生路径规划

研究了假设路段通行时间为随机变量的交通网络约束最短路径问题。建立0-1整数规划模型,求出最小期望通行时间路径。除流量平衡和路段通行能力约束外,还引入了唯一通路选择约束以保证最终只能生成最优路径。然后,提出了拉格朗日松弛法对难约束进行松弛处理,并将松弛模型分解成两个子问题。结合次梯度算法、标号修正算法和k-最短路径算法设计了一个算法框架,以最小化上下界的差距寻找近似最优解,用改进的算法框架进行求解。最后将该框架应用于龙岩市新罗区进行了计算试验。结果表明,该算法能够找到相对间隙较小的高质量解,验证了该方法的有效性。

航天测控调度问题的拉格朗日启发式算法

通过分析航天测控调度问题的测控需求,建立了航天测控调度0-1整数规划模型,运用拉格朗日松弛方法对模型中的任务约束和设备约束进行了松弛,运用次梯度优化算法求得了航天测控调度问题上界,同时得到了决策变量对应的拉格朗日权重,可以作为决策变量在最优解中是否被调度的启发式信息,对拉格朗日权重进行分析,提出了求解问题可行解的拉格朗日启发式算法。最后,通过对两个场景的试验分析验证了拉格朗日启发式算法所求可行解的优越性。

考虑需求侧管理和碳交易的电-气互联网络分散式低碳经济调度

在能源互联网和低碳背景下,提出一种考虑需求侧管理(demand side management, DSM)和碳交易的电-气互联网络分散式低碳经济调度模型。首先,根据碳交易市场的实际情况建立阶梯型碳交易机制,并利用电转气(power to gas, P2G)的低碳特性,得到P2G参与碳交易市场的激励机制;其次,由现有DSM的机理与实现方式,在负荷侧考虑不同的DSM来最大化地协调网络的低碳性与经济性;然后,根据所建模型的非凸特性,对气网潮流进行二阶锥松弛且采用连续锥规划算法对松弛间隙进行检验,逐步缩小气潮流的仿真误差,保证松弛的严格性。为了满足不同决策主体的分散自治权与信息私密性,在上述基础上建立分散式优化模型并引入基于嵌套连续锥规划的同步交替方向乘子法(synchronous-alternating direction method of multipliers, S-ADMM)进行求解;最后,通过算例仿真对不同场景下网络的调度结果及不同的调度策略下的运行结果进行比较分析。结果表明,在阶梯型碳交易机制下,虽然总碳交易成本增加了0.02%,但碳排量、运行成本分别减少了4.53%和3.74%;DSM参与到所提模型中使碳排量、弃风量分别降低了9.87%和75.4%,进而有效地提升了电-气互联网络的低碳经济性。

面向航班高峰期的机场地勤车辆多阶段优化调度方法

在航班运行高峰时段内,地面服务需求更加集中,机场可调度的地勤车辆数量有限,可能引发航班延误,导致机场多方面损失。针对该问题,研究了地勤车辆多阶段优化调度方法,重点考虑摆渡车和加油车2种地勤保障车路由与时间窗口限制,以航班准点率及延误时间为评价指标进行优化调度。构建了具有4类节点和5类弧的容量-费用网络G1,通过设置合适弧容量及费用参数,确定最小费用流规划模型;采用拉格朗日松弛启发式算法对模型求解,通过不断寻优,设置对偶间隙初值、容许误差,最大迭代次数,输出预测结果;深入分析高峰时段的航班运行状态,构建基于时空网络的整数线性规划模型,优化第一阶段未服务航班的总延误时间;结合最小化最大值定理,构建单航班服务延误模型,将单个航班延误造成的损失降到最低。最后,基于实际航班数据,结合机坪平面布局开展仿真实验和验证,结果表明:利用优化调度得到加油车和摆渡车准时服务的最大航班数分别为30,131架·次,待服务航班的最小总延误时间分别为223,542 min,航班总延误下降21.56%,显著缩短航班延误时间,提升了机场场面的整体运行效率。

求解多维背包问题的蚁群-拉格朗日松弛混合优化算法

针对多维背包问题(MKP)NP-hard、约束强的特点,提出一种高效的蚁群-拉格朗日松弛(LR)混合优化算法.该算法以蚁群优化(ACO)为基本框架,并基于LR对偶信息定义了一种MKP效用指标.ACO使得整体算法具有全局搜索能力,所设计的效用指标将MKP的优化目标与约束条件有机地融合在一起.该指标一方面可以用来定义MKP核问题,降低问题规模;另一方面,可以用作ACO的启发因子,引导算法在有希望的解区域中强化搜索.在大量标准算例上的测试结果表明,所提出算法的鲁棒性较好;与其他已有算法相比,在求解质量和求解效率方面均具有很强的竞争力.

公共场所疏散引导人静态布局优化算法及其应用

采用最大覆盖选址问题的求解思路,提出了公共场所疏散引导人静态布局优化的拉格朗日松弛算法.结合引导人静态布局的特点,重点探讨了考虑和不考虑公共场所中被疏散人员分布状况的两种情况下的优化布局,并在MA-ESM模型的支持下,通过与人为布设引导人方式的模拟结果进行对比,评价了这两种优化布局的模拟效果。结果表明:引导人静态布局的优化不仅有利于充分发挥每个引导人的作用,提高疏散效率,而且可以确定布设引导人的最佳位置和特定公共场所中所需引导人的最大数量;同时考虑公共场所内被疏散人员分布状况下的优化布局能够有的放矢地调度引导人,提高引导效率。