摘要：筆者針對基于傳統(tǒng)DP求解的分配問題之具體特征，曾改變單位效益指數(shù)法[6]之關(guān)注角度，獨(dú)創(chuàng)性地提出了單位增益求解思想[1]。該文就該算法中的異點(diǎn)問題，從其定義和特征入手，對異點(diǎn)的諸多細(xì)節(jié)做了較為詳細(xì)的討論，從而豐富并完善了增益算法的相關(guān)內(nèi)容。

關(guān)鍵詞：運(yùn)籌學(xué)；DP；分配問題；單位效益算法；異點(diǎn)

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）17-0212-03

1 背景

在文獻(xiàn)[1]之單位增益算法中，筆者曾提到異點(diǎn)問題。雖然就給定實(shí)例而言，其增益的突變情況并沒有真正影響到優(yōu)化的最后結(jié)果，但我們可以理解，如果發(fā)生突變的數(shù)值幅度較大時(shí)，必然會對最后的結(jié)果產(chǎn)生直接影響。另外，倘若突變情況相對較少時(shí)，完全可以單獨(dú)針對這些突變數(shù)據(jù)點(diǎn)，作為資源分配著力點(diǎn)，一旦得到一個(gè)具體的資源分配方案，再將其與以該算法得到的方案做比較分析，擇其優(yōu)者，同樣可得到最優(yōu)解。因此，在單位增益整體上符合同網(wǎng)點(diǎn)數(shù)成反相關(guān)之情況下，若能找出個(gè)別突變情況，則可大大增強(qiáng)該算法的可靠性。鑒于篇幅所限，在文獻(xiàn)[1]中并未展開做詳細(xì)討論，本文將就異點(diǎn)問題做進(jìn)一步分析。

2 增益算法簡介

不失一般性，不妨設(shè)n=6，m=4，此刻為各目標(biāo)分配不同資源數(shù)時(shí)的具體效益數(shù)據(jù)，如下面的表1所示，試分析使總效益最大的資源資源分配最優(yōu)化方案。

表1 不同目標(biāo)分配不同資源（資源）數(shù)時(shí)的具體效益想定數(shù)據(jù)統(tǒng)計(jì)表

[分配不同資源數(shù)時(shí)的效益＼&0（部）＼&1（部）＼&2（部）＼&3（部）＼&4（部）＼&5（部）＼&6（部）＼&目標(biāo)1＼&0＼&15＼&27＼&36＼&41＼&43＼&44＼&目標(biāo)2＼&0＼&13＼&23＼&31＼&37＼&40＼&42＼&目標(biāo)3＼&0＼&11＼&20＼&28＼&32＼&35＼&36＼&目標(biāo)4＼&0＼&14＼&25＼&32＼&39＼&43＼&46＼&]

如果采用傳統(tǒng)的DP求解算法處理該問題，一般是通過分階段、定狀態(tài)、取決策、分析狀態(tài)轉(zhuǎn)換圖，再基于該圖按照從后向前的逆推思路來求解之，思路雖然十分清晰，而且也能得到最優(yōu)解，但算法的時(shí)間復(fù)雜度相當(dāng)不理想，效率甚低。為此，我們采用與貪心算法相類似的思路，從另外一個(gè)角度著手，從局部出發(fā)經(jīng)過一系列的最優(yōu)選擇進(jìn)而得到整體最優(yōu)解。

我們知道，常規(guī)的DP求解以為各目標(biāo)分配資源的過程作為階段的劃分標(biāo)準(zhǔn)，我們不妨將這種關(guān)注從目標(biāo)轉(zhuǎn)向資源，即將各個(gè)目標(biāo)看成是相對獨(dú)立的個(gè)體，轉(zhuǎn)而考慮分配每一個(gè)資源時(shí)的策略選擇，即考慮選擇將該資源分配給哪一個(gè)具體的目標(biāo)。顯然，此刻應(yīng)該知道分配每個(gè)資源給各目標(biāo)單位時(shí)，可使總的效益增益情況，我們選此刻的最大增益即可。于是，便需對表1之?dāng)?shù)據(jù)做適當(dāng)處理，不妨建立單位增益的最大化模型，構(gòu)建其對應(yīng)的單位增益矩陣如下所示：

接著再建立目標(biāo)函數(shù)：

其中，S表示獲取的最大總利益，而pi表示給第i個(gè)目標(biāo)分配了pi個(gè)網(wǎng)點(diǎn)。顯然，第j臺資源是建立在已有j-1臺資源的基礎(chǔ)上的。規(guī)定ai0=0，表示不給目標(biāo)i分配資源時(shí)，其效益自然為零。

容易證明，此目標(biāo)函數(shù)與DP傳統(tǒng)求解時(shí)的目標(biāo)函數(shù)等價(jià)。

我們在參考文獻(xiàn)[1]中，假設(shè)，

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

又用P =（p1，p 2，…，p m）表示分配策略向量，即給不同的目標(biāo)分配以不同的資源數(shù)；

而，Dr = {di|di∈Li }為增益方案之集合，就是說在為第r臺資源確定了它的目標(biāo)歸屬之后，再為其多分配1臺資源時(shí)，可能可獲得的增益數(shù)值。

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

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

第2步：取Dr集合中最大元素，記為M，并取下標(biāo)q，pq = pq+1，S=S+d q，r=r+1；

第3步：若r

第4步：顯示并輸出向量P與S。

就上面的想定示例數(shù)據(jù)模型來說，其對應(yīng)的單位增益矩陣如下所示：

通過單位效益求解算法，可得最優(yōu)分配方案為P*6 =（2，1，1，2），即分別為目標(biāo)1，2，3，3分配資源2臺，1臺，1臺，2臺，如此可使得總效益值達(dá)到最大，總效益值為76。具體過程從略，可參考文獻(xiàn)[1，6，8]。通過與單位效益指數(shù)法的求解結(jié)果，以及和使用傳統(tǒng)的DP思想之求解結(jié)果的相互比較，容易理解該算法之有效性[1]。

3 異點(diǎn)分析

3.1 異點(diǎn)定義

就前面給定的想定示例數(shù)據(jù)來說，增益算法確實(shí)得到了該問題的最優(yōu)分配方案，而且算法思路也很清晰，運(yùn)算比較簡單，收斂速度很快。但是，容易看出該求解算法依然弊端顯的。仔細(xì)分析上述想定示例的資源分配具體過程，就容易發(fā)現(xiàn)單位增益矩陣有明顯的特殊性。就是說，對于同一個(gè)目標(biāo)來講，在整體上單位增益數(shù)值同資源數(shù)是成相對溫和的反相關(guān)趨勢的，如下面的圖1和圖2所示。容易看出，較圖2而言，圖1實(shí)質(zhì)上強(qiáng)化了反相關(guān)的變化趨勢，所以，后續(xù)敘述中將盡量采用單位增益數(shù)據(jù)之反相關(guān)數(shù)據(jù)來做分析。

仔細(xì)觀察圖1中的第4行數(shù)據(jù)變化情況，不難看出，在分配數(shù)分別為3和4時(shí)，增益數(shù)值是一樣的，故曲線在該范圍內(nèi)呈水平狀態(tài)，這便是一種相對溫和的異常情況。雖然本例之增益變化情況并未影響最后的結(jié)果，但容易理解，如果變化的趨勢發(fā)生局部突變，甚至存在著正相關(guān)等異常情況，必然會對最后的結(jié)果產(chǎn)生直接影響。我們稱這些反相關(guān)趨勢中的異常情況為異點(diǎn)。

3.2 異點(diǎn)特征分析

按數(shù)據(jù)模型中所包含的異點(diǎn)數(shù)量，可將模型劃分為單異點(diǎn)模型和多異點(diǎn)模型兩大類。

異點(diǎn)突變的方向可以為正，亦可為負(fù)，即突然大幅度地增加或說減少。以此為依據(jù)，可將突然增加的異點(diǎn)稱之為正異點(diǎn)，將突然大幅度減少異點(diǎn)稱之為負(fù)異點(diǎn)。

一般情況下，呈水平變化趨勢的異點(diǎn)，對單位增益求解算法的影響不大，甚至可忽略不計(jì)，因此，可將其稱之為虛異點(diǎn)，而將那些確實(shí)有明顯變化的異點(diǎn)稱之為實(shí)異點(diǎn)。我們后面將重點(diǎn)討論實(shí)異點(diǎn)。

例如，在圖3所示之增益數(shù)據(jù)模型就是個(gè)典型的多異點(diǎn)模型，其中第1行在位置4處，第2行在位置5處，第4行在位置5處均存在異點(diǎn)，且第3個(gè)異點(diǎn)還是虛異點(diǎn)。

而圖4所示之增益數(shù)據(jù)模型則是個(gè)典型的連續(xù)異點(diǎn)分布情況，其中第1行在位置4和5兩處，均超過位置3的值，與負(fù)相關(guān)規(guī)律不符。而在第4行在位置3處和位置5處，均超過其前一位置的值，也存在異常。

3.3 異點(diǎn)定位

其實(shí)，存在異點(diǎn)并不意味著分配方案就一定得做修改，還需要同已求得的結(jié)果做比較分析，但首要任務(wù)是判定模型中異點(diǎn)的存在、位置、數(shù)量和分布情況。一般地，就前面的單位增益矩陣而言，如果aij≤aij+1，則a ij就是異點(diǎn)。當(dāng)aij

經(jīng)該異點(diǎn)定位函數(shù)處理之后，各異點(diǎn)的位置和屬性保存在全局?jǐn)?shù)組ab_position中，其中，第1列存異點(diǎn)所在行，第2列存所在列，第3列存其類型，且0為虛異點(diǎn)，1為實(shí)異點(diǎn)。

其中，ZengYi_D用以存儲增益數(shù)據(jù)模型數(shù)據(jù)，是個(gè)二維數(shù)組；Lines存儲增益數(shù)據(jù)模型的行數(shù)，初值為0； Cols存儲增益數(shù)據(jù)模型的列數(shù)，初值為0；ab_position用以保存異點(diǎn)的位置和屬性，也是個(gè)二維數(shù)組，各列數(shù)值分別為異點(diǎn)所在行、列和虛實(shí)屬性。Count_abnormals保存定位處理完成后，確定的異點(diǎn)個(gè)數(shù)。假設(shè)增益數(shù)據(jù)模型數(shù)據(jù)如圖5所示，則其異點(diǎn)定位結(jié)果如圖6所示。

3.4 負(fù)值與正相關(guān)

當(dāng)增益模型中出現(xiàn)負(fù)值時(shí)，可對該矩陣之所有數(shù)據(jù)均加上該負(fù)值的絕對值，便可將整個(gè)矩陣變成正值，然后再按前述方法做相應(yīng)處理即可。當(dāng)然，求解完成后，尚需對其做還原處理。不過，基于求分配模式最優(yōu)，而非最后的效益值之考慮，即使不還原亦無不可。

通過前面的分析我們知道，異點(diǎn)定位在一定程度上彌補(bǔ)了局部出發(fā)求解可能造成的結(jié)果不準(zhǔn)確之現(xiàn)象（此即瞎子摸象），它只能得到一個(gè)近憂解的不足。若突變情況相對較少，亦可單獨(dú)以異點(diǎn)落腳分配，求解后再與正常方案做比較，擇其優(yōu)者有效。因此，在單位增益整體上符合同網(wǎng)點(diǎn)數(shù)成反相關(guān)之情況下，若能找出個(gè)別突變情況，則可增強(qiáng)算法的魯棒性。

我們強(qiáng)調(diào)增益算法適用于對于同一目標(biāo)分配資源時(shí)，增益模型整體上符合同資源數(shù)呈溫和的反相關(guān)之情況。其實(shí)，在現(xiàn)實(shí)生活中還應(yīng)存在著正相關(guān)的情況，此刻效益追求與資源保障完全相一致，但已無研究之必要，故本文暫且從略，不再贅述。

模型的適用與否，與增益的正相關(guān)還是反相關(guān)性無關(guān)，而僅僅與模型數(shù)據(jù)的趨勢是否穩(wěn)定有關(guān)，所以，最后總是可以歸結(jié)到對異點(diǎn)的分析和處理上來。當(dāng)然，對分配問題來說分配效益有規(guī)可循的實(shí)際意義也相對更大些。

另外，基于增益算法倘若增加分配資源規(guī)模，則可以該算法之中間結(jié)果為基礎(chǔ)繼續(xù)計(jì)算。倘若采用傳統(tǒng)的DP處之，則必須從分階段、定狀態(tài)并取決策開始做分配處理，這也是從局部出發(fā)相較從整體出發(fā)的優(yōu)勢。

鑒于水平所限，不妥和錯(cuò)誤之處難免，敬請各位讀者批評指正。

參考文獻(xiàn)：

[1] 曹迎槐. 基于單位增益最優(yōu)化的DP求解算法[J]. 電腦知識與技術(shù)， 2014（8）.

[2] 曹迎槐. 防空兵火力分配賦零算法[J]. 現(xiàn)代兵種， 2000（11）.

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

[4] 曹迎槐. 單位效益指數(shù)法初探[C. 第十屆軍事系統(tǒng)工程年會， 2000， 10.

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

[6] 曹迎槐. 關(guān)于分配問題的一種新解法[J]. 計(jì)算機(jī)與現(xiàn)代化， 2009（3）.

[7] 錢頌迪. 運(yùn)籌學(xué)[M]. 北京： 清華大學(xué)出版社， 1993.

[8] 曹迎槐. 軍事運(yùn)籌學(xué)[M]. 北京： 國防工業(yè)出版社， 2013.