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

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

改进的拉格朗日松弛数据关联算法

在多传感器多目标跟踪领域中,当传感器为被动式的,传统的多维分配算法利用拉格朗日松弛算法求解.拉格朗日乘子更新一般用次梯度方法,但每次迭代都要进行多次极小化运算来求对偶解,导致实时性差.针对这个问题,提出了一种改进的基于拉格朗日松弛的数据关联算法,通过代理修正次梯度方法更新拉格朗日乘子,并在允许时间内获得近似解.仿真实验...     

基于广义三维分配的数据互联算法研究

针对多维分配问题中基于次梯度算法的拉格朗日松弛算法每次迭代都要对每个子问题进行最小化运算以更新乘子的缺陷,引入了优化数学里的代理次梯度算法,修改次梯度表达式和乘子更新公式,提出了基于代理次梯度的拉格朗日松弛数据关联算法.在问题规模较大的情况下,节约了计算时间,降低了跟踪丢失率.仿真结果证明了算法的有效性.     

考虑供应损失的战场供应网络设计

通过优化分发节点的位置,以及分发节点或供应节点与作战单元的物资供应关系,来最小化战场物资保障的成本,建立战场供应网络的整数规划模型.设计了拉格朗日启发式算法来求解该问题,最后通过包含20个供应节点、80个候选分发节点和200个作战单元的大规模优化问题验证了算法的有效性,计算结果显示本文设计的求解算法可以在短时间内计算出问题的近似最优解.     

带数据传输的光学卫星成像调度系统关键技术研究

针对光学小卫星成像调度系统设计需求,考虑侧视、存储容量、能量和数据传输等复杂约束,面向小规模问题应用,设计了问题求解流程.建立了顶点和边都带权的成像约束图模型,并提出了基于标记更新最短路算法的复杂约束成像卫星调度算法解决成像方案生成过程;对数传方案生成过程,给出背包模型并采用带回看策略的贪婪启发式方法进行问题求解.实验结果表明,该方法是可行和适用的.     

航天器调度中的资源约束推理方法

资源水平边界的估计是构建资源利用可行计划中的一个基础问题。通过分析航天器资源约束的共享与分离并存、累积与瞬时消耗并存、过度订阅与区间调度并存等特点,提出了资源时间网络、时间约束网络和约束网络相结合的资源约束描述方法;构建了增量式基于包络的资源约束算法和最早开始时间链展开资源约束算法,以快速获取资源一致的柔性解。实例证明,该方法较好地解决了航天器调度的资源约束推理问题。     

分布式多站雷达协同定位功率分配改进凸松弛算法

针对分布式多站雷达协同定位下的功率分配问题,提出一种改进凸松弛的启发式算法。给出了分布式多站雷达定位误差的克劳美罗下界(CRLB),建立功率约束下最小化CRLB迹的功率分配模型。设计了一种改进凸松弛算法,通过迭代修正松弛参数和快速功率调整策略解决非凸优化问题消除松弛带来的误差。仿真实验表明,相对于均匀功率分配算法和基于凸松弛的功率分配算法,改进凸松弛启发式功率分配算法下目标的定位性能更优。     

天基预警系统资源调度方法

对面向导弹预警任务的天基预警系统中的低轨卫星资源调度问题进行了研究.对预警任务的特性进行分析,提出了一种预警任务规划与分解方法以减少任务对资源占用时间的需求;在此基础上建立了该问题的约束满足CSP调度模型;针对该模型变量多、解空间规模庞大的特点以及对求解算法时效性的要求,设计了一种基于局部解空间跳出机制的改进型遗传算法MGA.仿真表明该模型与算法在给定时间内能够得到满意的调度方案.     

基于BDD算法的航天测控系统任务可靠性建模与分析

提出了一种航天测控系统的层次化建模方法,以及测控任务可靠性二元决策图(BDD)分析算法。在模型底层描述了测控系统的结构和任务需求信息,模型顶层将测控资源与任务进行统一,将测控单元任务弧段切割成不同阶段,建立了任务可靠性的故障树模型。采用ITE算法将故障树模型转换为BDD模型,并给出了BDD模型的计算方法。最后,运用实例说明了方法的有效性,进行了测控任务可靠性的灵敏度分析,找出了系统的薄弱环节。     

利用动态规划原理实现多冲量最优交会问题

多冲量最优交会问题是航天领域非常重要的一个研究方向,从运筹学角度将此问题转化为一个多阶段多维动态规划问题,并着重对多阶段二维动态规划进行分析研究。在给出状态方程及指标函数递推公式的基础上,得到了两冲量和三冲量交会问题最优解的求解算法,之后分别通过实例验证了算法的有效性。对于以地心角等参数为决策变量的更高维问题,讨论了利用进化算法等降维方法实现多维动态规划的思想。     

装备维修器材生产路径决策的两阶启发式算法

当前装备供应保障系统中维修器材存在短缺、积压以及配送系统效率低下等问题,亟须对生产、库存和配送作业环节进行集成优化。为客观反映各个决策环节,将该问题公式化为一个混合整数线性规划模型,针对该模型多变量、多约束的特点,提出了一个基于数学规划的两阶启发式算法对其进行求解。结合算例,检验模型的可行性,并选取求解器CPLEX和一个类似的迭代算法与该算法在求解质量和运算时间方面进行对比与分析。结果表明,提出的模型是合理可行的,该算法在求解不同规模实例时表现出优异的性能。     

Lagrangian relaxation approach to the targeting problem

In this paper, we consider a new weapon–target allocation problem with the objective of minimizing the overall firing cost. The problem is formulated as a nonlinear integer programming model. We applied Lagrangian relaxation and a branch‐and‐bound method to the problem after transforming the nonlinear constraints into linear ones. An efficient primal heuristic is developed to find a feasible solution to the problem to facilitate the procedure. In the branch‐and‐bound method, three different branching rules are considered and the performances are evaluated. Computational results using randomly generated data are presented. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 640–653, 1999     

基于速度可控粒子群算法的航天测控系统任务可靠性分配

航天测控系统是一个典型的多阶段任务系统,讨论了可靠性分配时的约束条件和分配目标,构建了其任务可靠性分配模型,针对任务可靠性分配这类复杂的约束组合优化问题,提出了一种速度可控的粒子群优化算法.为克服粒子群算法的早熟问题,该算法引入了速度更新的方向控制规则和尺度控制规则用于增加群体的多样性,并根据两种控制规则,提出了种群粒子的速度更新策略.通过算例仿真,表明算法在用于航天测控系统任务可靠性分配问题时具有分配结果优、收敛速度快等优点.     

导航卫星上行注入任务调度模型及启发式算法

合理安排导航卫星与地面上注站星地链路构建与导航电文上注,对保证星上导航电文的准确性和精确性有着重要意义。对卫星导航系统上行注入过程进行了分析,构建了上行注入任务调度问题的多目标混合整数规划模型,设计了基于规则的启发式求解算法。基于北斗二代和美国的GPS卫星导航系统构建仿真场景,仿真结果验证了模型和算法的正确性、可行性;通过分析仿真结果,得到影响卫星导航系统上行注入任务完成的关键因素。     

Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem

In this paper we propose some non‐greedy heuristics and develop an Augmented‐Neural‐Network (AugNN) formulation for solving the classical open‐shop scheduling problem (OSSP). AugNN is a neural network based meta‐heuristic approach that allows integration of domain‐specific knowledge. The OSSP is framed as a neural network with multiple layers of jobs and machines. Input, output and activation functions are designed to enforce the problem constraints and embed known heuristics to generate a good feasible solution fast. Suitable learning strategies are applied to obtain better neighborhood solutions iteratively. The new heuristics and the AugNN formulation are tested on several benchmark problem instances in the literature and on some new problem instances generated in this study. The results are very competitive with other meta‐heuristic approaches, both in terms of solution quality and computational times. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Computing bounds for the optimal value in linear programming

Consider a standard linear programming problem and suppose that there are bounds available for the decision variables such that those bounds are not violated at an optimal solution of the problem (but they may be violated at some other feasible solutions of the problem). Thus, these bounds may not appear explicitly in the problem, but rather they may have been derived from some prior knowledge about an optimal solution or from the explicit constraints of the problem. In this paper, the bounds on variables are used to compute bounds on the optimal value when the problem is being solved by the simplex method. The latter bounds may then be used as a termination criteria for the simples iterations for the purpose of finding a “sufficiently good” near optimal solution. The bounds proposed are such that the computational effort in evaluating them is insignificant compared to that involved in the simplex iterations. A numerical example is given to demonstrate their performance.     

The fixed charge problem

The fixed charge problem is a nonlinear programming problem of practical interest in business and industry. Yet, until now no computationally feasible exact method of solution for large problems had been developed. In this paper an exact algorithm is presented which is computationally feasible for large problems. The algorithm is based upon a branch and bound approach, with the additional feature that the amount of computer storage required remains constant throughout (for a problem of any given size). Also presented are three suboptimal heuristic algorithms which are of interest because, although they do not guarantee that the true optimal solution will be found, they usually yield very good solutions and are extremely rapid techniques. Computational results are described for several of the heuristic methods and for the branch and bound algorithm.     

Multiple-attribute decision making with partial information: The comparative hypervolume criterion

A new approach is presented for analyzing multiple-attribute decision problems in which the set of actions is finite and the utility function is additive. The problem can be resolved if the decision makers (or group of decision makers) specifies a set of nonnegative weights for the various attributes or criteria, but we here assume that the decision maker(s) cannot provide a numerical value for each such weight. Ordinal information about these weights is therefore obtained from the decision maker(s), and this information is translated into a set of linear constraints which restrict the values of the weights. These constraints are then used to construct a polytope W of feasible weight vectors, and the subsets H_i (polytopes) of W over which each action a_i has the greatest utility are determined. With the Comparative Hypervolume Criterion we calculate for each action the ratio of the hypervolume of H_i to the hypervolume of W and suggest the choice of an action with the largest such ratio. Justification of this choice criterion is given, and a computational method for accurately approximating the hypervolume ratios is described. A simple example is provided to evaluate the efficiency of a computer code developed to implement the method.     

基于逼近理想解排序法的导弹保障性评价研究

保障性评价是实现导弹综合保障目标的重要手段。根据保障性评价指标模型建立了决策判断矩阵,采用层次分析法确定各指标权重,利用逼近理想解排序法对导弹保障性评价进行了定量分析。通过实例分析,这种方法计算简便,可操作性强,有实际应用价值。