一种求解混合整数非线性规划的新算法

针对混合整数非线性规划求解难的问题,本文给出了一种新的求解策略--混合序列差异演化算法,该算法采取混合编码的形式以便处理连续变量、整数变量以及混合整数变量的优化问题.最后通过数例检验算法的优越性,仿真结果表明该算法求解效率高、收敛速度快、全局搜索能力强.     

实施饱和攻击的反舰导弹武器目标分配

反舰导弹实际战术使用中,为提高突防概率,主要是采取饱和攻击的作战模式。首先通过对多弹多平台协同作战的要素分析,建立了多指标混合最优化目标分配模型。将火力分配目标决策与航路规划决策过程相结合,提出一种多发射平台、多约束下对目标实施饱和攻击的分配实施方法。仿真结果表明,所建立的模型计算快速,特别适合战场环境下目标分配问题的实时求解,可为部队发射平台配置和火力分配提供依据与参考。     

基于仿真的武器-目标分配问题求解方法

武器-目标分配问题是一种NP问题.分析了武器-目标分配问题的特点,把武器-目标分配问题转化为加权运输问题,把不同权系数下运输问题的精确解作为原问题的近似解,权系数不同时运输问题的解对应原问题的目标函数值不同,可把武器-目标分配问题的目标函数看作权系数的函数.采用仿真方法产生权系数,计算相应运输问题的解及其对应的武器-目标分配问题的目标函数值,进行迭代搜索,逐步改进武器-目标分配问题的解,得到较好的近似解.实验结果表明:提出的仿真方法计算所得解的质量较高,是求解武器-目标分配问题的一种有效方法.     

一种求解整数-非线性规划问题的演化算法

混合整数非线性规划问题为一类富有挑战性的难解问题。本文设计一个混合演化算法求解混合整数非线性规划问题，对于不同变量分别使用二进制和实数编码策略，将约束优化问题转换为多目标优化问题。数值实验验证了算法的有效性、稳健性和通用性。     

一种混合整数双层线性规划的全局优化方法

通过求得下层问题的对偶问题可行域上的极点,将上层所有变量为0 1型变量和下层所有变量为连续型变量的双层线性规划转化为有限个混合整数线性规划问题,从而用求解混合整数线性规划的方法获得问题的全局最优解.由于下层问题的对偶问题可行域只有有限个极点,所提出的方法具有全局收敛性.     

一种求解混合非线性整数规划的支撑超平面方法

给出一种在可行域边界生成支撑超平面(Supporting Hyper Plane, SHP)的方法来求解凸混合整数非线性(Mixed Integer Nonlinear Programming, MINLP)问题.扩展切平面(Extended Cutting Plane, ECP)算法作为求解混合整数非线性规划的一种重要方法 ,在算法结构上简单,鲁棒性强,但是该算法收敛速度慢,特别是当被求解问题非线性程度比较高时.SHP算法在每次迭代过程中对可行域的估计比 ECP算法更准确(更小), 从而加快了算法的收敛速度.和ECP方法相比, SHP算法有效的提高了求解MINLP问题的效率,数值试验显示了该方法的有效性.     

整数规划的一种线性规划解法

根据凸分析理论和单纯形法原理，提出了整数规划的一个线性规划解法。该方法主旨是将整数规划问题的离散的可行集填充成一个连续的单纯形，这样原整数规划问题就化为该单纯形上的一个新的线性规划问题。利用单纯形法求解该线性规划问题，便可得到整数规划的最优解。且进一步提出并证明了指派问题的线性规划解法。     

求解整数规划问题的微粒群算法

针对整数规划问题的特点,提出了一种在整数空间中进行进化计算的PSO算法,使微粒群的进化限于整数空间.仿真实验结果验证了方法的正确性与有效性.     

基于整数规划的超视距空战目标分配模型研究

针对超视距编队协同空战中的目标分配问题,通过建立现代空战的微分对策模型,将超视距多机协同空战的目标分配分为编队分组和编队内单机目标分配两步完成,重点研究了编队分组对抗策略,设计建立了以交战强度排序为依据,以"不重不漏"为原则的基于整数规划的超视距空战编队目标分配模型。仿真算例验证了所建模型的有效性和准确性。     

基于双层规划的攻击无人机协同目标分配优化

针对攻击无人机编队协同作战的背景,提出了基于双层规划的攻击无人机协同目标分配模型。分别以打击效果最大化和飞行航线最短作为模型的上下层目标,并贴近战场环境将目标优先程度、目标打击效果上下限以及打击时间窗口等因素作为模型约束。利用直觉模糊双层规划(intuitionistic fuzzy bilevel programming, IFBLP)理论对构建的协同目标分配双层混合整数规划模型进行了转化,并采用粒子群优化(particle swarm optimization, PSO)方法对其进行求解,给出了具体求解步骤。算例结果证明IFBLP理论能够有效解决所构建的双层混合整数规划模型。     

整数规划的旋转矢量法

针对整数规划问题的求解,改造了基本旋转矢量方法中的旋转因子和收缩因子。旋转因子的选取保证了矢量旋转过程中矢径长度不变,矢径的收缩策略的选取能保证最大范围地搜索解空间。多点旋转矢量法采用多矢量同时旋转的思想,在算法实施中基于优胜劣汰的原则引入了矢径舍弃系数和种群保留系数两个控制参数,极大地提高了计算效率和求解精度。最后,通过整数规划算例验证了该方法的有效性,表明对于维数较高的整数规划问题效果也很好。     

约束规划求解集装箱装卸系统集成调度问题

集装箱码头装卸系统中的岸桥、集卡和场桥的集成调度问题本质上是有阻塞、准备时间可分离并且依赖操作顺序的三阶段混合流水车间调度问题,现有文献多采用启发式算法求解该问题.本文先建立了一个紧凑的混合整数规划模型,然后从约束规划的角度建模求解该问题,提出了一个约束规划模型,以区间变量作为决策变量,并采用"扩展操作任务"的概念来定义区间决策变量以提升求解效率.为了展示约束规划的建模灵活性,还扩展了模型以考虑机器效率不同的因素.数值实验显示约束规划模型能够在很短的时间内对大规模算例求出高质量的解.     

ALLOCATING REPAIRABLE SYSTEM＇S RELIABILITY SUBJECT TO MINIMAL TOTAL COST - AN INTEGER PROGRAMMING APPROACH

Reliability allocation problem is commonly treated using a closed-form expression relating the cost to reliability. A recent approach has introduced the use of discrete integer technique for un-repairable systems. This research addresses the allocation problem for repairable systems. It presents an integer formulation for finding the optimum selection of components based on the integer values of their Mean Time to Failure （MTTF） and Mean Time to Repair （MTTR）. The objective is to minimize the total cost under a system reliability constraint, in addition to other physical constraints. Although, a closed-form expression relating the cost to reliability may not be a linear; however, in this research, the objective function will always be linear regardless of the shape of the equivalent continuous closed-form function. An example is solved using the proposed method and compared with the solution of the continuous closed-form version. The formulation for all possible system configurations, components and subsystems are also considered.     

求QoS路由的整数线性规划方法

QoS路由的任务是在网络中寻找一条满足多个约束条件的路径使网络资源的利用达到最优. 该问题是一个NP-完全问题. 提出了一种新的基于整数线性规划模型选择路由的方法. 思路是将复杂约束引入到目标函数作为罚项, 得到一个松弛整数线性规划问题. 因为约束系数矩阵是全幺模矩阵, 松弛问题可以通过线性规划很快地求解. 拉格朗日乘子的调整用罚函数的方法很容易计算. 数值实验表明提出的方法是有效的.     

Optimal set integer programming algorithm for multiple maneuvering targets tracking in clutter

The aim of this paper is to solve the problems of multitarget tracking in clutter. Firstly, the data association of measurement-to-target is formulated as an integer programming problem. Through using the linear programming (LP) based branchand-bound method and adjusting the constraint conditions, an optimal set integer programming (OSIP) algorithm is then proposed for tracking multiple non-maneuvering targets in clutter. For the case of maneuvering targets, this paper introduces the OSIP algorithm into the filtering step of the interacting multiple model (IMM) algorithm resulting in the IMM based on OSIP algorithm. Extensive Monte Carlo simulations show that the presented algorithms can obtain superior estimations even in the case of high density noises.     

两层广义线性规划

给出二层广义线性规划最优解极点可达性的一个充分条件 .此外 ,利用容许集的极点与下层问题可行集的极点间的关系给出“第 k最好”算法的一种快捷、方便的实现 .算例表明算法是有效的 .     

Global convergent algorithm for the bilevel linear fractional-linear programming based on modified convex simplex method

A global convergent algorithm is proposed to solve bilevel linear fractional-linear programming,which is a special class of bilevel programming.In our algorithm,replacing the lower level problem by its dual gap equaling to zero,the bilevel linear fractional-linear programming is transformed into a traditional single level programming problem,which can be transformed into a series of linear fractional programming problem.Thus,the modified convex simplex method is used to solve the infinite linear fractional programming to obtain the global convergent solution of the original bilevel linear fractional-linear programming.Finally,an example demonstrates the feasibility of the proposed algorithm.     

A novel mixed integer programming formulation and progressively stochastic search for capacitated lot sizing

The capacitated multi-level lot sizing problem is to schedule a number of different items with a bill-of-materials structure over a horizon of finite periods.To advance techniques of solving this class of problems,this paper proposes a new mixed integer programming formulation.Theoretical proofs and computational tests are provided to show that this formulation is able to provide better linear programming relaxation lower bounds than a previously-proposed strong mixed integer programming formulation.Based on the new strong formulation,a progressively stochastic search approach is proposed for solving the problem.Computational results showed that the approach generates high quality solutions,especially for problems of large sizes.     

求解大规模VCVRP问题的快速动态规划算法

车辆路径问题是一类典型的组合优化问题,大部分研究都只考虑车辆能力固定的情形,实际中受货物形状特性及客户需求变化,车辆的能力是受限变化的,针对能力受限变化的车辆路径问题(varied capacitated vehicle routing problem,VCVRP),基于动态规划理论,提出一种求解大规模VCVRP问题的快速动态规划算法.该算法以传统的最佳适应降序算法(best fit decreasing,BFD)和最小生成树(minimum spanning tree,MST)算法为基础,引入K步回溯,短途优先原则,实现了VCVRP中的货物装箱问题和路由选择问题的近似解耦.同时给出了该算法的优化目标车辆旅程的理论上界,短途优先原则的局部最小的理论分析与证明.最后以乘用车物流运输案例为背景,给出了计算实例,并从算法参数与算例规模多个角度进行求解质量与算法性能的分析.