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

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

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

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

分支定价方法求解带二维装箱约束的车辆路径问题

面向家具、电器等货物的物流配送场景,研究带二维装箱约束的车辆路径问题(2L–CVRP),构建了2L–CVRP的混合整数线性规划模型.为求解大规模2L–CVRP,构建了该问题集合划分模型,提出基于分支定价的方法.针对分支节点的松弛模型,基于列生成策略将其分解为线性规划主问题、带资源和二维装箱约束的最短路径子问题,并提出基于ng-route松弛策略的标签算法和基于禁忌搜索的装箱算法有效求解复杂子问题.仿真结果表明,提出的方法可高效求解大规模2L–CVRP,其中ng-route松弛策略能有效提升算法求解效率,研究成果为装箱约束下大规模车辆路径问题的高效求解提供了有效途径.

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

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

潮汐干线交通信号协调控制模型

为缓解城市布局等问题导致的潮汐交通拥堵现象,提出了一种潮汐交通状态下的干线信号协调控制策略.依据交通供需关系及交通量进出平衡,构建了以干线吞吐量最大化为优化目标的混合整数线性规划模型.基于冲击波理论,构建了以过饱和方向车均延误最小化为优化目标的二次规划模型.通过引入松弛变量实现可变带宽绿波的分段优化,构建了以非饱和方向带宽最大化为目标的混合整数线性规划模型.采用三阶段优化方法求解模型,获得潮汐干线的最优控制方案.算例结果表明,本文提出的模型能优化干线吞吐量,控制过饱和方向的延误,并为非饱和方向提供可变带宽绿波,从而满足潮汐交通需求.

求解机组组合问题的分段线性近似方法

提出一种求解机组组合问题的分段线性近似方法。利用区域非均匀取点的分段线性方法将机组组合问题近似为混合整数线性规划问题进行求解。数值结果表明,所提方法优于混合整数二次规划方法和区域均匀取点的分段线性方法,能有效求解大规模的机组组合问题,可获得高质量的次优解。

求解二次分配问题的新的流量模型

二次分配问题是具有广泛应用背景的经典组合优化难题之一。本文在二次分配问题已有线性化模型的基础上,提出了一种新的基于流量的线性化模型。数值试验结果表明,新模型无论从时间上还是计算节点数都更具有优势。

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

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

考虑储能参与调频的风储联合运行优化策略

储能系统与风电场联合运行,不但可减小风电场的弃风,还可参与电网的辅助服务。以风储电站的总收益最大为目标,考虑储能用于减小弃风和参与电网二次调频服务,建立了电池储能系统和风电场联合运行的优化模型。该模型考虑了电池寿命损耗和储能剩余电量水平对调频表现的影响。通过约束转换,将模型转换为易于求解的混合整数线性规划问题。基于实际风电场运行数据设计算例并进行仿真分析,结果表明所提出的方法可有效提高储能的利用率和风储联合体的效益。

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

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

基于延迟策略的库存管理优化算法设计

多级库存优化问题是供应链管理理论和实践当中一个重要议题,它制约着供应链整体性能的提高。本文分析了一类带延迟策略的库存优化模型,即二层整数规划模型,并设计出一类混合遗传算法来求解该模型。数值模拟表明本文所得结果与已有结果相比,不仅使得供应链整体库存效益有所提高,且对各库存分点的最优库存量作了更为合理的调整。

基于赠送式捆绑销售的分销系统优化模型研究

以实现分销系统合作伙伴双赢为目标，在市场需求不确定情况下，运用二层非线性混合整数规划模型，研究了一个处于上层的分销商。在采取赠送式捆绑销售策略时的最佳捆绑方式及一个作为下层的零售商的最佳订货批量问题。设计一种基于遗传算法的求解方法，并针对仿真算例求解，验证了模型的有效性。结果表明，由分销商提出的捆绑销售策略有利于提高分销商和零售商利润。

新能源场站共享储能提供调频服务的日前优化策略

针对在新能源场站聚集地区配置大规模共享储能,研究储能系统的优化运行问题,使其在承担多个新能源机组一次调频义务的前提下,最大限度利用自身调节能力参与辅助服务市场,提供二次调频等服务。基于调频服务市场规则,保证调频服务质量的前提下,以储能系统利润最大化为目标,综合考虑储能寿命、电量维持等因素,建立了储能系统在日前市场的调频容量与基准功率申报决策模型,并将其转换为混合整数线性规划的形式,能够使用成熟软件进行求解。利用历史数据进行仿真验证,结果表明所提出的方法能够有效利用储能系统的能量、功率容量,在承担新能源场站一次调频义务的同时,具有提供二次调频、参与峰谷套利从而获取收益的能力。

数学优化的行业标准-ILOG CPLEX

基本算法 为解决要求极高的数学优化问题，需要相关基础算法具备最快、最可靠的实现方式。ILOG CPLEX就是在满足这种需求的情况下应运而生的。ILOG CPLEX提供了灵活、高性能的优化器，可解决线性规划（linear programming）问题、二次规划（quadratic programming）问题、二次约束规划（quadratically constrained programming）问题以及混合整数规划（mixed integer programming）问题。

考虑沿海转运的我国进口LNG海运网络优化

基于目前我国进口LNG运输船以长期租船为主的现状,同时考虑在进口LNG海运网络中加入沿海二程转运,建立以海上运输总成本最小为目标的混合整数线性规划模型,对我国进口LNG海运网络进行优化。在海运网络中分析我国使用中小型LNG运输船进行沿海二程转运的经济性,并在沿海二程转运经济的情况下找出合适的枢纽港,得出沿海二程转运所需的船队配置。从优化结果可知:对我国沿海一些有船型限制的中小型LNG接收站,可采用沿海二程转运方式来满足其需求,能有效降低我国进口LNG的海运成本。

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

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

临界饱和状态交通干线协调控制模型

为提升临界饱和状态下干线车流通行效率,提出了一种基于冲击波理论的干线双向信号协调控制方法。首先,建立了考虑车速变化、转向比例、车道变化等因素的干线交通流模型,分析了临界饱和交通干线交通流运行状态与各参数间的关系。第二,构建了以干线双向通过量最大化为优化目标的混合整数线性规划模型,通过优化干线公共周期和各交叉口绿信比以提高干线通行能力。第三,构建了以延误最小化为优化目标的二次规划模型,并提出了相应的求解算法,通过优化相位差和相位方案实现了干线交叉口的信号协调。临界饱和交通干线协调控制模型由通过量最大化模型和延误最小化模型构成,考虑各交叉口间的制约影响关系,有效避免了排队滞留、溢出、交叉口“死锁”等现象。采用两阶段优化方法,通过通过量最大化模型优化周期及绿信比,继而应用延误最小化模型优化交叉口相位方案及相位差,获得干线系统双向信号协调最优控制方案。最后,应用临界饱和交通状态干线协调控制模型对南京市中山东路10个交叉口进行了信号协调优化,并对优化结果进行了仿真分析。结果表明:临界饱和交通状态干线协调控制模型能对双向临界饱和干线的信号控制方案进行优化,与对照方案相比,优化方案的双向总交通量提升了21.9%,车均延误降低了63.1%,通行能力与服务水平提升显著。