基于單位增益最優化的DP求解算法

曹迎槐 陳煒丹

摘要：該文針對分配問題的具體特征，一改單位效益指數法之關注角度，進而獨創性地提出了單位增益求解思想，結合異點的概念和特點，詳細闡述了異點對增益算法的相關補充和諸多影響。該算法步驟簡單、可操作性強、不受問題規模限制，可得最優解。

關鍵詞： 分配問題； 運籌學； 單位效益指數；單位增益；異點

中圖分類號：TP312 文獻標識碼：A 文章編號：1009-3044（2014）23-5437-04

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

為避免傳統算法之弊端，筆者曾提出了單位效益指數法[4]，該算法步驟簡單、可操作性強、基本不受問題規模之限制。但該算法只能得到近優解，稍顯不足。之后，筆者在教學過程中，通過反復分析單位效益之局限性，將對效益的關注適當轉變為對單位武器增益之思考，進而提出了基于單位增益最優化的DP求解算法，經過多次實驗和比對，效果較好。

1 示例

不失一般性，取武器臺數n = 6，目標個數m = 4，據前期調查和模擬數據統計，不妨設為各目標分配不同數量的武器時的效益情況如表1所示，試研究制定使總效益最大的武器分配方案。

1） 是否可僅從局部出發，通過一系列局部最優的選擇進而得到整體最優。……