单位增益算法之异点分析

《单位增益算法之异点分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、单位增益算法之异点分析　　摘要：笔者针对基于传统DP求解的分配问题之具体特征，曾改变单位效益指数法[6]之关注角度，独创性地提出了单位增益求解思想[1]。该文就该算法中的异点问题，从其定义和特征入手，对异点的诸多细节做了较为详细的讨论，从而丰富并完善了增益算法的相关内容。　　关键词：运筹学；DP；分配问题；单位效益算法；异点　　中图分类号：TP311文献标识码：A文章编号：1009-3044（2016）17-0212-03　　1背景　　在文献[1]之单位增益算法中，笔者曾提到异点问题。虽然就给定实例而言，其增益的突变情况并没有真正影响到优化的最后结果，但我们可以理解，如果发生突变的数

2、值幅度较大时，必然会对最后的结果产生直接影响。另外，倘若突变情况相对较少时，完全可以单独针对这些突变数据点，作为资源分配着力点，一旦得到一个具体的资源分配方案，再将其与以该算法得到的方案做比较分析，择其优者，同样可得到最优解。因此，在单位增益整体上符合同网点数成反相关之情况下，若能找出个别突变情况，则可大大增强该算法的可靠性。鉴于篇幅所限，在文献[1]中并未展开做详细讨论，本文将就异点问题做进一步分析。　　2增益算法简介7　　不失一般性，不妨设n=6，m=4，此刻为各目标分配不同资源数时的具体效益数据，如下面的表1所示，试分析使总效益最大的资源资源分配最优化方案。　　表1不同目标分配

3、不同资源（资源）数时的具体效益想定数据统计表　　[分配不同资源数时的效益＼&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求解算法处理该问题，一般是通过分阶段、定状态、取决策、分析状态转换图，再基于该图按照从后向前的逆推思路来求解之，思路虽然十分清晰，而且也能得到最优解，

4、但算法的时间复杂度相当不理想，效率甚低。为此，我们采用与贪心算法相类似的思路，从另外一个角度着手，从局部出发经过一系列的最优选择进而得到整体最优解。　　我们知道，常规的DP求解以为各目标分配资源的过程作为阶段的划分标准，我们不妨将这种关注从目标转向资源，即将各个目标看成是相对独立的个体，转而考虑分配每一个资源时的策略选择，即考虑选择将该资源分配给哪一个具体的目标。显然，此刻应该知道分配每个资源给各目标单位时，可使总的效益增益情况，我们选此刻的最大增益即可。于是，便需对表1之数据做适当处理，不妨建立单位增益的最大化模型，构建其对应的单位增益矩阵如下所示：　　接着再建立目标函数：7　　其

5、中，S表示获取的最大总利益，而pi表示给第i个目标分配了pi个网点。显然，第j台资源是建立在已有j-1台资源的基础上的。规定ai0=0，表示不给目标i分配资源时，其效益自然为零。　　容易证明，此目标函数与DP传统求解时的目标函数等价。　　我们在参考文献[1]中，假设，　　Li=（ai1，ai2，ai3，…，ain）；Cj=（a1j，a2j，a3j，…，amj）T；　　又用P=（p1，p2，…，pm）表示分配策略向量，即给不同的目标分配以不同的资源数；　　而，Dr={di

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

7、数值。　　于是，基于单位增益思想的算法求解过程，就可以描述如下：　　第1步：初始化。P=（p1，p2，…，pm）；Dr={di

8、di∈Li}，r=1；S=0；　　第2步：取Dr集合中最大元素，记为M，并取下标q，pq=pq+1，S=S+dq，r=r+1；　　第3步：若r

9、益值为76。具体过程从略，可参考文献[1，6，8]。通过与单位效益指数法的求解结果，以及和使用传统的DP思想之求解结果的相互比较，容易理解该算法之有效性[1]。　　3异点分析　　3.1异点定义　　就前面给定的想定示例数据来说，增益算法确实得到了该问题的最优分配方案，而且算法思路也很清晰，运算比较简单，收敛速度很快。但是，容易看出该求解算法依然弊端显的。仔细分析上述想定示例的资源分配具体过程，就容易发现单位增益矩阵有明显的特殊性。就是说，对于同一个目标来讲，