关于武器目标分配问题的精确与启发式解法研究论文

简介：
本文探讨了武器目标分配问题的求解策略，通过比较分析精确算法和启发式算法的有效性，旨在为该领域提供新的视角及优化方案。 武器目标分配（WTA）问题是国防领域运筹学应用中的一个核心问题。该问题涉及将n种不同类型的武器最优地配置给m个不同的目标，以使这些目标在所有交战后的总预期生存价值最小化。WTA可以表述为非线性整数规划问题，并且已被证明是NP完全的难题。对于小规模的问题实例（例如20种武器和20个目标），没有已知的方法能够精确求解。 尽管已经提出了多种启发式方法来解决这类问题，但由于缺乏有效的评估手段，我们无法准确衡量这些启发式算法所生成解决方案的质量。本段落提出了一套新的方法论框架，包括线性规划、整数规划以及基于网络流的下限技术，并通过它们开发了若干种分支定界算法以应对WTA挑战。 此外，文中还介绍了一个基于网络流构造试探法与超大规模邻域（VLSN）搜索算法。实验结果表明，我们的方法可以对中等规模的问题实例实现最优求解（最多80个武器和目标），并且对于更大规模的场景也能在几秒内找到接近最优的结果（最多200种武器和目标）。