基于单位增益最优化的DP求解算法

摘要：该文针对分配问题的具体特征，一改单位效益指数法之关注角度，进而独创性地提出了单位增益求解思想，结合异点的概念和特点，详细阐述了异点对增益算法的相关补充和诸多影响。该算法步骤简单、可操作性强、不受问题规模限制，可得最优解。

关键词： 分配问题； 运筹学； 单位效益指数；单位增益；异点

中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2014）23-5437-04

在军事上，用n台武器突击m个目标，若武器击中这些目标的概率可知，试制定分配武器的最佳方案，使突击总效益最大，这便是火力分配问题。它属非线性规划范畴，常被纳入多阶段决策问题，是军事运筹学DP（动态规划）理论的经典应用。使用传统的DP递推方法求解之，虽思路清晰，但步骤繁琐，计算量大，当问题规模较大时，计算量增速惊人[1]。

为避免传统算法之弊端，笔者曾提出了单位效益指数法[4]，该算法步骤简单、可操作性强、基本不受问题规模之限制。但该算法只能得到近优解，稍显不足。之后，笔者在教学过程中，通过反复分析单位效益之局限性，将对效益的关注适当转变为对单位武器增益之思考，进而提出了基于单位增益最优化的DP求解算法，经过多次实验和比对，效果较好。

1 示例

不失一般性，取武器台数n = 6，目标个数m = 4，据前期调查和模拟数据统计，不妨设为各目标分配不同数量的武器时的效益情况如表1所示，试研究制定使总效益最大的武器分配方案。

1） 是否可仅从局部出发，通过一系列局部最优的选择进而得到整体最优。就该思想而言，当然可以采用自顶向下之顺序。就是说，可并不从整体最优上严加考虑，而仅仅是在某种意义上的局部求取最优解。显然，这就是一种广泛意义上的贪婪算法之选择。

2） 常规的DP求解思想是以目标作为阶段划分的依据，现在将关注重点从目标转向武器，将各台武器看成独立的个体，以每分配一台武器时，就考虑选择一次具体的目标之思想来实施规划。当然，这就要求必须知道分配给各目标单位武器的效益之增益，因此，需要对所给原始数据做相应的处理。

2 模型与算法

2.1 单位增益模型

针对上述问题，我们不妨建立单位增益的最大化模型。

首先进行数据预处理。基于n台武器和m个目标的一般情况，给第i个目标分配j台武器时，可取得的效益值为vij，则此时各目标的单位武器增益值[aij]，即可表示如下：

2.2 求解算法

看得出，该算法完全是基于局部做最优选择，进而期望得到整体最优之思想。

2.3 应用示例

用该模型对前面的示例实施求解，具体过程如下：

首先，据表1可得到单位增益矩阵如下所示（其中，a i 0 = 0从略）：

最优分配方案为P*6 =（2，1，1，2） T，即分别为目标1、2、3、4分配武器2台、1台、1台、2台，如此可使得总效益值达到最大，总效益值为76。

2.4 基于单位效益指数法的求解比较

根据单位效益指数法[1]的算法求解思想，不难得出，该问题对应的单位效益指数矩阵[4]如下所示：

按单位效益指数法求解之，可得P* =（1，1，3，1） T，即分别为目标1、2、3、4分配武器1台、1台、3台、1台，该方案对应的总效益为70。

看得出，相对单位效益指数法而言，单位增益算法效果还是明显的。

3 异点分析

3.1 概念引出

就给定的示例而言，该算法确实得到了该问题的最优解，且算法思路清晰，运算简单，操作方便，收敛速度很快，效果良好。但是，该算法仍然存在弊端。

仔细分析示例之武器的分配过程，不难发现单位增益矩阵有明显的特殊性。即，对于同一个目标而言，在整体上单位增益同武器台数成反相关。容易理解，如果相关规律存在突变情况，将可能影响最后的分配方案。当然，也并非只要存在突变情况就必然影响最后的结果，但当突变的幅度严重到一定程度时，则影响便成必然。我们称突变发生的位置为异点。

其实，如果仅仅有少数的突变情况出现，可再单独以此突变点为分配之落脚点，在得到分配方案之后，再与以该算法得到的方案做比较，选择其中的优者，同样能保证得到最优解（但效率一般会受影响）。因此，适当关注突变情况，则可大大增强该算法的可靠性。

3.2 异点定位

突变情况存在并不表示分配方案一定得改变，还需要同已求得的结果做比较。突变到何种程度，才可能会改变最优解，这也是个灵敏度分析问题，限于篇幅本文只能从略。

1） 异点是行、列中均最大的元素；

2） 给目标i，分配j台武器，其单位效益最大；

3） 若只能选一个目标，并为之分配j台武器，则分配给目标i时，获得的单位效益值最大；

其实，在本文示例中并未涉及到异点问题。当不存在异点时，直接利用单位增益解法就可得到唯一的最优解。不过，在一般的应用中，异点可能并不唯一。直接求解得到的最优解也可能未涉及到所有的异点，此刻，再基于异点实施调整处理即可。另外，当异点多于一个时，则最后的最优解往往亦可能有多个。例如：当单位效益指数矩阵如下所示时：

4 结束语

本文中一直在强调上述算法适用于，对同一目标而言，单位增益整体上符合同武器数成反相关之情况。当然，再现实生活中还应存在着另外一种规律，即单位增益整体上同分配数成正相关的情况。不难发现，上述模型的适用与否与增益的正、反相关性无关，而仅仅是与它的趋势是否稳定有关，所以，最后均须归结到对异点的进一步处理上。

对于分配问题而言，分配效益有规可循，其实际意义也更大。例如，若增益与分配数成正相关，说明分配的武器之间通过组合搭配或可产生更大的效益，因此，该算法的实用性较强。当然，基于该算法，如果再增加分配武器时，以该算法之中间结果为基础继续计算。倘若采用传统的DP处之，则需重头开始做分配。这也是从局部出发相较从整体出发的优点之所在。当然，如果继续异点的相关分析，并研究其在装载、可靠性等问题中的应用等，现实意义或许更大。

因水平所限，不足之处难免，敬请各位专家和同行批评指正！

参考文献：

[1] 曹迎槐.军事运筹学[M].北京：国防工业出版社，2013.

[2] 曹迎槐.防空兵火力分配赋零算法[J].现代兵种，2000（11）.

[3] 许创杰，曹迎槐.军事运筹学[M].北京：国防大学出版社，1999.

[4] 曹迎槐.单位效益指数法初探[C].第十届军事系统工程年会，2000.

[5] Przemieck J S.Introduce to mathematical Methods in Defense Analysis[M].New York：Springe，1985.

[6] 曹迎槐.关于分配问题的一种新解法[J].计算机与现代化，2009（3）.

[7] 江敬灼.国防系统分析方法学教程[M].北京：军事科学出版社，2000.

[8] 钱颂迪.运筹学[M].北京：清华大学出版社，1993.

[9] Waltz E，Lines J.Multisensor Data Fusion[M].Ariech Hoase，inc，1989.