摘要
研究了编队卫星对地观测调度问题。分别建立了基于问题自然描述和基于有向图描述的两类整数规划模型,运用整数规划凸包理论比较了两类模型与各自对应的线性松弛模型之间的最优值差异,得出了基于有向图描述的线性松弛模型更接近于原问题凸包的结论,并基于有向图描述模型设计了不完全分支定界算法。最后,在随机生成的仿真算例下,运用ILOG CPLEX实现了该算法,实验结果表明了模型及算法的有效性,并验证了对于两类整数规划模型的边界分析。
This paper researches the scheduling problem of earth observation satellites formation.It builds two integer programming models,one is based on the natural description of the original problem and the other is based on a directed-graph formulation.Based on the convex polytope theory of integer programming,this paper compares the respective optimal-solution-value gaps between the two models and their respective linear relaxations,and makes the conclusion that the linear relaxation of the directed-graph formulation is closer to the convex polytope of the original problem.Besides,this paper designs an incomplete branch and bound algorithm based on the directed-graph formulation and implements the algorithm through ILOG CPLEX on randomly generated problem instances.Computation results show the effectiveness of the model and the algorithm,and validate the theoretical gaps-analysis of the two integer programming models.
出处
《系统工程与电子技术》
EI
CSCD
北大核心
2010年第8期1689-1694,共6页
Systems Engineering and Electronics
基金
国家自然科学基金(70601035
70801062)资助课题
关键词
卫星观测调度
整数规划
凸包理论
分支定界
earth observation scheduling
integer programming
convex polytope theory
branch and bound
