一类混合整数二层线性规划问题的等价形式

考虑一类上层所有变量为0-1型变量和下层所有变量为连续型变量的混合整数二层线性规划问题(MI-BLPP),把该问题松弛为一个特殊的二层线性规划问题(BLPP2),证明了BLPP2与MIBLPP具有相同的最优解,最后给出了数值算例验证了结论是正确可行的。

分组密码复杂线性层可分性传播的MILP刻画方法

混合整数线性规划(MILP)作为一种自动化搜索工具,被广泛地应用于搜索分组密码的差分、线性、积分等密码性质.提出一种基于动态选取策略构建MILP模型的新技术,该技术在不同的条件下采用不同的约束不等式刻画密码性质的传播.具体地,从可分性出发根据输入可分性汉明重量的不同,分别采用不同的方法构建线性层可分性传播的MILP模型.最后,将该技术应用于搜索uBlock和Saturnin算法的积分区分器.实验结果表明:对于uBlock128算法,该技术可以搜索到比之前最优区分器多32个平衡比特的8轮积分区分器.除此之外,搜索到uBlock128和uBlock256算法比之前最优区分器更长一轮的9和10轮积分区分器.对于Saturnin256算法,同样搜索到比之前最优区分器更长一轮的9轮积分区分器.

基于滚动时域优化的无人飞行器轨迹规划

给出了寻求无人飞行器的最优轨迹的一种方法,其问题描述为使飞行器从初始状态飞行到目标状态,同时避免撞到障碍物。基于混合整数规划的滚动时域优化方法用来求解飞行器的轨迹规划问题。给出的仿真结果显示此方法的有效性以及在复杂环境下的可实时计算性。

基于滚动时域混合整数线性规划的汽车紧急避让问题求解方法

为了提高汽车高速紧急避让行驶安全性,提出一种汽车紧急避让问题求解方法.基于滚动时域混合整数线性规划(RHC-MILP),通过引入逻辑变量和连续变量的混合形式的线性约束来描述障碍物避让约束,对车辆的动态特性进行线性近似,建立离散时间模型;以整数变量描述车辆和障碍物之间的相对位置,以安全顺利避开障碍物性能指标作为代价函数,建立混合整数规划,并采用滚动时域控制策略进行求解.仿真和实车试验结果表明,该方法能够求解汽车的紧急避让问题,具有求解精度高,求解时间短的优势,并且仿真值和试验值的变化趋势基本一致,从而验证了该方法的正确性和可行性.

基于滚动规划的泊位和岸桥分配集成模型研究

泊位分配(BA),岸桥配置(QCA)及岸桥调度(QCS)是三个基本的岸边决策问题。提出了一个基于混合整数线性规划的BA和QCA的集成模型,模型综合考虑了货轮优先权,理想泊位及处理时间三个方面的因素。在实际生产数据上的运行结果表明该模型具有决策支持的潜在能力。

基于干扰管理的无线网络跨层算法研究和设计

采用贪心策略设计了一种基于干扰管理的无线网络跨层算法。首先建立了基于干扰管理的无线网络跨层设计模型,该模型是一个混合整数规划模型,无法在多项式时间内求解。为此在保证最大化信噪比的前提下,通过研究瓶颈节点对网络吞吐量的影响,提出了一种基于贪心策略的跨层设计算法。该算法通过迭代不断扩大瓶颈节点的数据传输率,进而优化整个网络的吞吐量。仿真结果表明该算法在优化效果上比已有算法提高了29.10%,在运算速度上比已有算法有成百倍的提高。

考虑风电消纳及不确定性的负荷聚合商运行策略

针对“碳达峰、碳中和”背景下新能源大规模并网而引发的风电消纳困难问题,提出了一种考虑风电消纳及不确定性负荷聚合商日前-日内两阶段的经济调度模型。首先分析了考虑风电消纳的负荷聚合商源荷协同运行模式,提出了考虑用能特性与不确定性的柔性负荷响应模型;并基于风电场的消纳需求,以柔性负荷调度成本最小为目标,建立日前-日内两阶段的负荷聚合商经济调度模型;最后采用三角模糊数表征柔性负荷功率的不确定性,采用清晰等价转化求解混合整数线性规划问题。仿真算例验证了该模型能够有效提高风电消纳水平,减少由柔性负荷不确定性带来的影响。

基于滚动变时间窗的重组批处理机调度研究

针对具有等待时间限制和工件动态到达的重组批处理机调度问题,以拖延时间和最小为目标,提出基于滚动变时间窗的三层混合调度算法。该调度算法是应用滚动时域策略,将重组批处理机调度问题分解为许多变时间窗的子问题;每个子问题调度分三层执行:即产生触发并传递参数、重组批及排序、派工并更新参数。通过实时调度仿真平台和CPLEX平台进行实例验证,结果表明基于滚动变时间窗的三层混合调度算法能够在较短计算时间内获得满意优化解。

改进的混合整数线性模型优化化工厂多层设备布局

化工设备布局是设计化工厂的重要环节,对优化生产管理、整合土地与水电资源、减少输送能耗、降低事故风险以及保证人员安全有着重要的意义。化工设备布局中最常见的是多层设备布局。本文通过对工艺流程特点以及设备特殊性进行分析,预处理某些设备的布置,考虑设备间安全距离,建立改进的混合整数线性规划模型(MILP),用数学规划法求解。将该方法应用于某原油蒸馏工艺流程的布局优化,相较于文献报道的不加入这些工程因素的数学规划方法,模型变量得到了减少,降低求解复杂度,求解时间缩短了38.8%,且布局方案更符合工厂实际,验证了所提方法的有效性和实用性。

面向产品族优化时间窗下可重入批处理机调度

在半导体晶圆制造系统中,具有不确定交货时间窗和不相容产品族的可重入批处理机优化调度是NP-难问题。针对该问题,提出面向产品族的三层滚动混合整数线性规划模型的优化调度算法,其优化目标是提前和误工的时间总和最小。该算法是基于时间序列模型和事件模型的混合分解策略,在可重入批处理机空闲、可用的事件触发下,将整个调度时间轴分解为滚动的时间域;每个时间域对应一个子问题;每个子问题分解为三层:排序、派工和更新;半导体晶圆制造系统实时调度仿真平台用于派工、更新和时域滚动,混合整数线性规划模型用于排序。通过6种典型情形实例验证,结果表明面向产品族的三层滚动混合整数线性规划模型能够在较短计算时间内获得较好优化解。

区间通过能力临时失效条件下高速列车运行调整方法

[目的]分析高速列车运行模式及高速列车在运行过程中受到的多种外界干扰,在区间通过能力临时失效干扰的前提下,为高速列车运行调整提供一种可行的建模及求解方法。[方法]确定高速列车运行调整优化的目标函数,结合高速列车运行的实际情况,将列车运行调整过程转化成相应约束条件,建立区间通过能力临时失效条件下高速列车运行调整混合整数线性规划模型。同时,设计滚动时域算法对模型分阶段进行求解,力争在较短时间内给出调整方案。[结果]基于部分京沪高速铁路列车运行图数据,对所提出的模型与算法进行仿真验证与分析。[结论]仿真试验证明,采取调整方法可有效减小干扰对列车运行秩序的影响。

基于区域控制的航空器滑行轨迹优化模型

针对现有模型解决航空器滑行轨迹优化时冲突约束能力不足问题,提出了一种新的混合整数线性规划(mixed integer linear programming,MILP)模型。利用区域划分和区域公共节点网络构建层次化滑行道结构模型,提高了滑行道建模精度,并在此基础上应用区域控制规则实现对滑行道的无冲突占用。同时,基于滚动时域策略对复杂的滑行轨迹优化问题分阶段求解,提高了滑行规划模块的灵活性和求解速度。实验结果表明,利用该模型能够有效回避滑行冲突,降低平均滑行时间和距离,提高场面运行效率。

含冰蓄冷空调的冷热电联供型微网多时间尺度优化调度

冷热电联供型微网(CCHP-MG)对实现能源可持续发展和构建绿色低碳社会具有重要的应用价值,而内部复杂的能源结构与设备耦合关系、可再生能源的消纳和负荷波动的平抑给其优化运行带来了挑战。文中提出含冰蓄冷空调的CCHP-MG多时间尺度优化调度模型,研究冰蓄冷空调的不同运行方式对优化调度的影响。日前计划中通过多场景描述可再生能源的不确定性,侧重于一个运行优化周期内CCHP-MG的经济运行;日内调度基于日前计划方案,根据冷热电在不同时间尺度上的相关性和互补性,提出考虑冷热负荷变化的双层滚动优化平抑模型,求解各联供设备的调整出力。仿真结果表明:冰蓄冷空调的运行方式关系到CCHP-MG的综合效益的提高;多时间尺度优化调度模型不仅可以满足用户的冷、热、电能的需求,还能有效平抑日内阶段供需侧随机性波动,实现CCHP-MG经济及稳定运行。行带来了挑战。文中提出含冰蓄冷空调的CCHP-MG多时间尺度优化调度模型,研究冰蓄冷空调的不同运行方式对优化调度的影响。日前计划中通过多场景描述可再生能源的不确定性,侧重于一个运行优化周期内CCHP-MG的经济运行;日内调度基于日前计划方案,根据冷热电在不同时间尺度上的相关性和互补性,提出考虑冷热负荷变化的双层滚动优化平抑模型,求解各联供设备的调整出力。仿真结果表明:冰蓄冷空调的运行方式关系到CCHP-MG的综合效益的提高;多时间尺度优化调度模型不仅可以满足用户的冷、热、电能的需求,还能有效平抑日内阶段供需侧随机性波动,实现CCHP-MG经济及稳定运行。

多类型煤炭海运运输库存管理一体化模型

针对大型发电集团煤炭采购海运总成本较高、库存积压严重的问题,提出海运运输库存管理一体化的三层混合整数规划模型。该模型基于多配送中心至多电厂码头的物流配送网络,考虑实际海运中复杂的船舶构成及电厂码头靠泊限制,采用混合整数规划方法,以调度周期内发电集团总部煤炭采购运输成本总和最小作为第一优化目标,以船运公司航次运行总费用最小为第二优化目标,并考虑电厂码头库存成本及库存不平衡惩罚,采用分层序列优化方法对该模型进行求解。基于国内某大型发电集团及其下属12个电厂的实验结果表明:该模型在避免煤炭短缺及库存爆仓的同时,降低供应链系统总费用800万元,减少由等待泊位引起的滞期费用195万元,降低电厂码头平均库存量30%;分层模型可有效降低由统一建模带来的管理难度及求解复杂度,特别适用于多电厂码头的复杂煤炭海运问题。

基于三层编码遗传算法求解同种产品存在多个工件的FJSP

以往对于柔性作业车间调度的研究,未考虑一种产品存在多个相同工件,这不符合车间的实际情况.为了克服这一缺陷,同时考虑柔性作业车间调度过程中机器负载及空载状态的能耗,建立了低碳柔性作业车间调度的多目标混合整数规划数学模型,以机器能耗成本和总完工时间成本加权和最小为目标.根据所建模型的特点,在二层编码遗传算法的基础上,提出三层编码遗传算法,增加一层用于表示同种产品的不同工件.同时对于三层编码遗传算法的交叉和变异算子进行重新设计,并运用柔性作业车间调度的测试算例进行算法有效性的验证.然后,运用该算法求解同种产品存在多个工件的柔性车间调度问题.最后通过取不同的权重得到101组不同的解,并基于数据包络分析得到其中的非支配解,绘制Pareto前沿线,验证该算法的有效性.

整数DEA问题的求解方法与改进

整数数据包络分析(IDEA)是一种用于当投入产出指标为整数时,分析决策单元(DMU)相对效率的评价方法。我们针对传统LV模型和KKM模型存在无法得到最优改进点和高估效率值的不足,提出RKKM模型和RDI模型。基于RKKM模型和RDI模型我们进一步提出"三步法"来解决IDEA问题。"三步法"的第一步和第二步分别求解RKKM模型和RDI模型来得到各自的最优值,第三步通过对比这两个模型的最优值来得到每个DMU最终的最优投影点。为了验证"三步法"的先进性,以伊朗42所高校效率评价的经典算例测算、对比上述各模型的数值效果,发现"三步法"有效解决了传统IDEA模型的不足。"三步法"不仅拥有坚实的理论基础,而且计算上容易实现,因此它可以作为解决IDEA问题的一个重要的工具。