曹迎槐 陳煒丹

摘要：該文針對(duì)分配問題的具體特征，一改單位效益指數(shù)法之關(guān)注角度，進(jìn)而獨(dú)創(chuàng)性地提出了單位增益求解思想，結(jié)合異點(diǎn)的概念和特點(diǎn)，詳細(xì)闡述了異點(diǎn)對(duì)增益算法的相關(guān)補(bǔ)充和諸多影響。該算法步驟簡單、可操作性強(qiáng)、不受問題規(guī)模限制，可得最優(yōu)解。

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

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）23-5437-04

在軍事上，用n臺(tái)武器突擊m個(gè)目標(biāo)，若武器擊中這些目標(biāo)的概率可知，試制定分配武器的最佳方案，使突擊總效益最大，這便是火力分配問題。它屬非線性規(guī)劃范疇，常被納入多階段決策問題，是軍事運(yùn)籌學(xué)DP（動(dòng)態(tài)規(guī)劃）理論的經(jīng)典應(yīng)用。使用傳統(tǒng)的DP遞推方法求解之，雖思路清晰，但步驟繁瑣，計(jì)算量大，當(dāng)問題規(guī)模較大時(shí)，計(jì)算量增速驚人[1]。

為避免傳統(tǒng)算法之弊端，筆者曾提出了單位效益指數(shù)法[4]，該算法步驟簡單、可操作性強(qiáng)、基本不受問題規(guī)模之限制。但該算法只能得到近優(yōu)解，稍顯不足。之后，筆者在教學(xué)過程中，通過反復(fù)分析單位效益之局限性，將對(duì)效益的關(guān)注適當(dāng)轉(zhuǎn)變?yōu)閷?duì)單位武器增益之思考，進(jìn)而提出了基于單位增益最優(yōu)化的DP求解算法，經(jīng)過多次實(shí)驗(yàn)和比對(duì)，效果較好。

1 示例

不失一般性，取武器臺(tái)數(shù)n = 6，目標(biāo)個(gè)數(shù)m = 4，據(jù)前期調(diào)查和模擬數(shù)據(jù)統(tǒng)計(jì)，不妨設(shè)為各目標(biāo)分配不同數(shù)量的武器時(shí)的效益情況如表1所示，試研究制定使總效益最大的武器分配方案。

1） 是否可僅從局部出發(fā)，通過一系列局部最優(yōu)的選擇進(jìn)而得到整體最優(yōu)。就該思想而言，當(dāng)然可以采用自頂向下之順序。就是說，可并不從整體最優(yōu)上嚴(yán)加考慮，而僅僅是在某種意義上的局部求取最優(yōu)解。顯然，這就是一種廣泛意義上的貪婪算法之選擇。

2） 常規(guī)的DP求解思想是以目標(biāo)作為階段劃分的依據(jù)，現(xiàn)在將關(guān)注重點(diǎn)從目標(biāo)轉(zhuǎn)向武器，將各臺(tái)武器看成獨(dú)立的個(gè)體，以每分配一臺(tái)武器時(shí)，就考慮選擇一次具體的目標(biāo)之思想來實(shí)施規(guī)劃。當(dāng)然，這就要求必須知道分配給各目標(biāo)單位武器的效益之增益，因此，需要對(duì)所給原始數(shù)據(jù)做相應(yīng)的處理。

2 模型與算法

2.1 單位增益模型

針對(duì)上述問題，我們不妨建立單位增益的最大化模型。

首先進(jìn)行數(shù)據(jù)預(yù)處理?；趎臺(tái)武器和m個(gè)目標(biāo)的一般情況，給第i個(gè)目標(biāo)分配j臺(tái)武器時(shí)，可取得的效益值為vij，則此時(shí)各目標(biāo)的單位武器增益值[aij]，即可表示如下：

2.2 求解算法

看得出，該算法完全是基于局部做最優(yōu)選擇，進(jìn)而期望得到整體最優(yōu)之思想。

2.3 應(yīng)用示例

用該模型對(duì)前面的示例實(shí)施求解，具體過程如下：

首先，據(jù)表1可得到單位增益矩陣如下所示（其中，a i 0 = 0從略）：

最優(yōu)分配方案為P*6 =（2，1，1，2） T，即分別為目標(biāo)1、2、3、4分配武器2臺(tái)、1臺(tái)、1臺(tái)、2臺(tái)，如此可使得總效益值達(dá)到最大，總效益值為76。

2.4 基于單位效益指數(shù)法的求解比較

根據(jù)單位效益指數(shù)法[1]的算法求解思想，不難得出，該問題對(duì)應(yīng)的單位效益指數(shù)矩陣[4]如下所示：

按單位效益指數(shù)法求解之，可得P* =（1，1，3，1） T，即分別為目標(biāo)1、2、3、4分配武器1臺(tái)、1臺(tái)、3臺(tái)、1臺(tái)，該方案對(duì)應(yīng)的總效益為70。

看得出，相對(duì)單位效益指數(shù)法而言，單位增益算法效果還是明顯的。

3 異點(diǎn)分析

3.1 概念引出

就給定的示例而言，該算法確實(shí)得到了該問題的最優(yōu)解，且算法思路清晰，運(yùn)算簡單，操作方便，收斂速度很快，效果良好。但是，該算法仍然存在弊端。

仔細(xì)分析示例之武器的分配過程，不難發(fā)現(xiàn)單位增益矩陣有明顯的特殊性。即，對(duì)于同一個(gè)目標(biāo)而言，在整體上單位增益同武器臺(tái)數(shù)成反相關(guān)。容易理解，如果相關(guān)規(guī)律存在突變情況，將可能影響最后的分配方案。當(dāng)然，也并非只要存在突變情況就必然影響最后的結(jié)果，但當(dāng)突變的幅度嚴(yán)重到一定程度時(shí)，則影響便成必然。我們稱突變發(fā)生的位置為異點(diǎn)。

其實(shí)，如果僅僅有少數(shù)的突變情況出現(xiàn)，可再單獨(dú)以此突變點(diǎn)為分配之落腳點(diǎn)，在得到分配方案之后，再與以該算法得到的方案做比較，選擇其中的優(yōu)者，同樣能保證得到最優(yōu)解（但效率一般會(huì)受影響）。因此，適當(dāng)關(guān)注突變情況，則可大大增強(qiáng)該算法的可靠性。

3.2 異點(diǎn)定位

突變情況存在并不表示分配方案一定得改變，還需要同已求得的結(jié)果做比較。突變到何種程度，才可能會(huì)改變最優(yōu)解，這也是個(gè)靈敏度分析問題，限于篇幅本文只能從略。

1） 異點(diǎn)是行、列中均最大的元素；

2） 給目標(biāo)i，分配j臺(tái)武器，其單位效益最大；

3） 若只能選一個(gè)目標(biāo)，并為之分配j臺(tái)武器，則分配給目標(biāo)i時(shí)，獲得的單位效益值最大；

其實(shí)，在本文示例中并未涉及到異點(diǎn)問題。當(dāng)不存在異點(diǎn)時(shí)，直接利用單位增益解法就可得到唯一的最優(yōu)解。不過，在一般的應(yīng)用中，異點(diǎn)可能并不唯一。直接求解得到的最優(yōu)解也可能未涉及到所有的異點(diǎn)，此刻，再基于異點(diǎn)實(shí)施調(diào)整處理即可。另外，當(dāng)異點(diǎn)多于一個(gè)時(shí)，則最后的最優(yōu)解往往亦可能有多個(gè)。例如：當(dāng)單位效益指數(shù)矩陣如下所示時(shí)：

4 結(jié)束語

本文中一直在強(qiáng)調(diào)上述算法適用于，對(duì)同一目標(biāo)而言，單位增益整體上符合同武器數(shù)成反相關(guān)之情況。當(dāng)然，再現(xiàn)實(shí)生活中還應(yīng)存在著另外一種規(guī)律，即單位增益整體上同分配數(shù)成正相關(guān)的情況。不難發(fā)現(xiàn)，上述模型的適用與否與增益的正、反相關(guān)性無關(guān)，而僅僅是與它的趨勢是否穩(wěn)定有關(guān)，所以，最后均須歸結(jié)到對(duì)異點(diǎn)的進(jìn)一步處理上。

對(duì)于分配問題而言，分配效益有規(guī)可循，其實(shí)際意義也更大。例如，若增益與分配數(shù)成正相關(guān)，說明分配的武器之間通過組合搭配或可產(chǎn)生更大的效益，因此，該算法的實(shí)用性較強(qiáng)。當(dāng)然，基于該算法，如果再增加分配武器時(shí)，以該算法之中間結(jié)果為基礎(chǔ)繼續(xù)計(jì)算。倘若采用傳統(tǒng)的DP處之，則需重頭開始做分配。這也是從局部出發(fā)相較從整體出發(fā)的優(yōu)點(diǎn)之所在。當(dāng)然，如果繼續(xù)異點(diǎn)的相關(guān)分析，并研究其在裝載、可靠性等問題中的應(yīng)用等，現(xiàn)實(shí)意義或許更大。

因水平所限，不足之處難免，敬請各位專家和同行批評(píng)指正！

參考文獻(xiàn)：

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

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

[3] 許創(chuàng)杰，曹迎槐.軍事運(yùn)籌學(xué)[M].北京：國防大學(xué)出版社，1999.

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

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

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

[7] 江敬灼.國防系統(tǒng)分析方法學(xué)教程[M].北京：軍事科學(xué)出版社，2000.

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

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