单位增益算法之异点分析

摘要：笔者针对基于传统DP求解的分配问题之具体特征，曾改变单位效益指数法[6]之关注角度，独创性地提出了单位增益求解思想[1]。该文就该算法中的异点问题，从其定义和特征入手，对异点的诸多细节做了较为详细的讨论，从而丰富并完善了增益算法的相关内容。

关键词：运筹学；DP；分配问题；单位效益算法；异点

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）17-0212-03

1 背景

在文献[1]之单位增益算法中，笔者曾提到异点问题。虽然就给定实例而言，其增益的突变情况并没有真正影响到优化的最后结果，但我们可以理解，如果发生突变的数值幅度较大时，必然会对最后的结果产生直接影响。另外，倘若突变情况相对较少时，完全可以单独针对这些突变数据点，作为资源分配着力点，一旦得到一个具体的资源分配方案，再将其与以该算法得到的方案做比较分析，择其优者，同样可得到最优解。因此，在单位增益整体上符合同网点数成反相关之情况下，若能找出个别突变情况，则可大大增强该算法的可靠性。鉴于篇幅所限，在文献[1]中并未展开做详细讨论，本文将就异点问题做进一步分析。

2 增益算法简介

不失一般性，不妨设n=6，m=4，此刻为各目标分配不同资源数时的具体效益数据，如下面的表1所示，试分析使总效益最大的资源资源分配最优化方案。

表1 不同目标分配不同资源（资源）数时的具体效益想定数据统计表

[分配不同资源数时的效益＼&0（部）＼&1（部）＼&2（部）＼&3（部）＼&4（部）＼&5（部）＼&6（部）＼&目标1＼&0＼&15＼&27＼&36＼&41＼&43＼&44＼&目标2＼&0＼&13＼&23＼&31＼&37＼&40＼&42＼&目标3＼&0＼&11＼&20＼&28＼&32＼&35＼&36＼&目标4＼&0＼&14＼&25＼&32＼&39＼&43＼&46＼&]

如果采用传统的DP求解算法处理该问题，一般是通过分阶段、定状态、取决策、分析状态转换图，再基于该图按照从后向前的逆推思路来求解之，思路虽然十分清晰，而且也能得到最优解，但算法的时间复杂度相当不理想，效率甚低。为此，我们采用与贪心算法相类似的思路，从另外一个角度着手，从局部出发经过一系列的最优选择进而得到整体最优解。

我们知道，常规的DP求解以为各目标分配资源的过程作为阶段的划分标准，我们不妨将这种关注从目标转向资源，即将各个目标看成是相对独立的个体，转而考虑分配每一个资源时的策略选择，即考虑选择将该资源分配给哪一个具体的目标。显然，此刻应该知道分配每个资源给各目标单位时，可使总的效益增益情况，我们选此刻的最大增益即可。于是，便需对表1之数据做适当处理，不妨建立单位增益的最大化模型，构建其对应的单位增益矩阵如下所示：

接着再建立目标函数：

其中，S表示获取的最大总利益，而pi表示给第i个目标分配了pi个网点。显然，第j台资源是建立在已有j-1台资源的基础上的。规定ai0=0，表示不给目标i分配资源时，其效益自然为零。

容易证明，此目标函数与DP传统求解时的目标函数等价。

我们在参考文献[1]中，假设，

Li =（ai1，ai2，ai3，…，ain）；Cj =（a 1j，a 2j，a 3j，…，a mj）T；

又用P =（p1，p 2，…，p m）表示分配策略向量，即给不同的目标分配以不同的资源数；

而，Dr = {di|di∈Li }为增益方案之集合，就是说在为第r台资源确定了它的目标归属之后，再为其多分配1台资源时，可能可获得的增益数值。

于是，基于单位增益思想的算法求解过程，就可以描述如下：

第1步：初始化。P =（p1，p 2，…，p m）； Dr = {di|d i∈Li }，r = 1；S=0；

第2步：取Dr集合中最大元素，记为M，并取下标q，pq = pq+1，S=S+d q，r=r+1；

第3步：若r

第4步：显示并输出向量P与S。

就上面的想定示例数据模型来说，其对应的单位增益矩阵如下所示：

通过单位效益求解算法，可得最优分配方案为P*6 =（2，1，1，2），即分别为目标1，2，3，3分配资源2台，1台，1台，2台，如此可使得总效益值达到最大，总效益值为76。具体过程从略，可参考文献[1，6，8]。通过与单位效益指数法的求解结果，以及和使用传统的DP思想之求解结果的相互比较，容易理解该算法之有效性[1]。

3 异点分析

3.1 异点定义

就前面给定的想定示例数据来说，增益算法确实得到了该问题的最优分配方案，而且算法思路也很清晰，运算比较简单，收敛速度很快。但是，容易看出该求解算法依然弊端显的。仔细分析上述想定示例的资源分配具体过程，就容易发现单位增益矩阵有明显的特殊性。就是说，对于同一个目标来讲，在整体上单位增益数值同资源数是成相对温和的反相关趋势的，如下面的图1和图2所示。容易看出，较图2而言，图1实质上强化了反相关的变化趋势，所以，后续叙述中将尽量采用单位增益数据之反相关数据来做分析。

仔细观察图1中的第4行数据变化情况，不难看出，在分配数分别为3和4时，增益数值是一样的，故曲线在该范围内呈水平状态，这便是一种相对温和的异常情况。虽然本例之增益变化情况并未影响最后的结果，但容易理解，如果变化的趋势发生局部突变，甚至存在着正相关等异常情况，必然会对最后的结果产生直接影响。我们称这些反相关趋势中的异常情况为异点。

3.2 异点特征分析

按数据模型中所包含的异点数量，可将模型划分为单异点模型和多异点模型两大类。

异点突变的方向可以为正，亦可为负，即突然大幅度地增加或说减少。以此为依据，可将突然增加的异点称之为正异点，将突然大幅度减少异点称之为负异点。

一般情况下，呈水平变化趋势的异点，对单位增益求解算法的影响不大，甚至可忽略不计，因此，可将其称之为虚异点，而将那些确实有明显变化的异点称之为实异点。我们后面将重点讨论实异点。

例如，在图3所示之增益数据模型就是个典型的多异点模型，其中第1行在位置4处，第2行在位置5处，第4行在位置5处均存在异点，且第3个异点还是虚异点。

而图4所示之增益数据模型则是个典型的连续异点分布情况，其中第1行在位置4和5两处，均超过位置3的值，与负相关规律不符。而在第4行在位置3处和位置5处，均超过其前一位置的值，也存在异常。

3.3 异点定位

其实，存在异点并不意味着分配方案就一定得做修改，还需要同已求得的结果做比较分析，但首要任务是判定模型中异点的存在、位置、数量和分布情况。一般地，就前面的单位增益矩阵而言，如果aij≤aij+1，则a ij就是异点。当aij

经该异点定位函数处理之后，各异点的位置和属性保存在全局数组ab_position中，其中，第1列存异点所在行，第2列存所在列，第3列存其类型，且0为虚异点，1为实异点。

其中，ZengYi_D用以存储增益数据模型数据，是个二维数组；Lines存储增益数据模型的行数，初值为0； Cols存储增益数据模型的列数，初值为0；ab_position用以保存异点的位置和属性，也是个二维数组，各列数值分别为异点所在行、列和虚实属性。Count_abnormals保存定位处理完成后，确定的异点个数。假设增益数据模型数据如图5所示，则其异点定位结果如图6所示。

3.4 负值与正相关

当增益模型中出现负值时，可对该矩阵之所有数据均加上该负值的绝对值，便可将整个矩阵变成正值，然后再按前述方法做相应处理即可。当然，求解完成后，尚需对其做还原处理。不过，基于求分配模式最优，而非最后的效益值之考虑，即使不还原亦无不可。

通过前面的分析我们知道，异点定位在一定程度上弥补了局部出发求解可能造成的结果不准确之现象（此即瞎子摸象），它只能得到一个近忧解的不足。若突变情况相对较少，亦可单独以异点落脚分配，求解后再与正常方案做比较，择其优者有效。因此，在单位增益整体上符合同网点数成反相关之情况下，若能找出个别突变情况，则可增强算法的鲁棒性。

我们强调增益算法适用于对于同一目标分配资源时，增益模型整体上符合同资源数呈温和的反相关之情况。其实，在现实生活中还应存在着正相关的情况，此刻效益追求与资源保障完全相一致，但已无研究之必要，故本文暂且从略，不再赘述。

模型的适用与否，与增益的正相关还是反相关性无关，而仅仅与模型数据的趋势是否稳定有关，所以，最后总是可以归结到对异点的分析和处理上来。当然，对分配问题来说分配效益有规可循的实际意义也相对更大些。

另外，基于增益算法倘若增加分配资源规模，则可以该算法之中间结果为基础继续计算。倘若采用传统的DP处之，则必须从分阶段、定状态并取决策开始做分配处理，这也是从局部出发相较从整体出发的优势。

鉴于水平所限，不妥和错误之处难免，敬请各位读者批评指正。

参考文献：

[1] 曹迎槐. 基于单位增益最优化的DP求解算法[J]. 电脑知识与技术， 2014（8）.

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

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

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

[5] Przemieck J S. Introduce to mathematical Methods in Defense Analysis[C]. 1985.

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

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

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