一种求解WTA问题的二次松弛方法  

Method of 2-phase-relaxation for solving WTA problem

作　　者：武欣嵘[1] 倪明放[1] 于战科[1] 陈敏[1] 

机构地区：[1]解放军理工大学通信工程学院,江苏南京210007

出　　处：《解放军理工大学学报（自然科学版）》2012年第6期599-603,共5页Journal of PLA University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(71971136)

摘　　要：为了求解联合作战中的武器-目标分配问题(WTA),在简要介绍WTA模型的基础上,根据WTA模型特征,利用松驰理论和方法,先将模型松弛为混合整数线性规划问题,然后利用Lagrange松弛,将模型分解为2个子问题:线性规划子问题和整数规划子问题,利用全单模矩阵特性求解整数规划子问题,并根据2个子问题的关系调整参数范围。理论证明该方法可以快速有效地给出改善的WTA问题的可行解。数值实验结果表明该方法对不同规模的WTA问题都有较好效果,适合不同战场环境下联合作战对WTA问题求解的实时性要求。Weapon-target assignment（WTA） problem is important in joint-operation and is NP complete. WTA problem was introduced briefly. Then based on relaxation theories and methods, WTA problem was relaxed into a mixed integer linear programming. Lagrange relaxation was introduced and the WTA prob- lem decomposed into two sub-problems, linear programming and mixed integer linear programming. The integer linear programming was solved based on totally unimodular matrix, and the parameters＂ scale modi- fied according to the relationship among them. The proposed method is feasible and effective. Computa- tional results also verify that it is effective not only for small scale but also for large scale of WTA prob- lem.

关 键 词：武器目标分配 Lagrange松弛 整数规划 罚函数 

分 类 号：O22[理学—运筹学与控制论] TB114.1[理学—数学]