基于動態(tài)規(guī)劃的海上編隊偵察預(yù)警任務(wù)分配?

（海軍大連艦艇學(xué)院作戰(zhàn)軟件與仿真研究所 大連 116018）

1 引言

偵察預(yù)警是海上編隊掌握海戰(zhàn)場態(tài)勢的重要基礎(chǔ)，由于海戰(zhàn)場情況復(fù)雜，威脅方向多，需要多個區(qū)域同時偵察［1］。海上編隊可執(zhí)行偵察預(yù)警任務(wù)的兵力包括艦艇［2］和預(yù)警機［3～5］，艦艇單次可執(zhí)行任務(wù)時間長，但是預(yù)警探測距離相對較短；預(yù)警機單次執(zhí)行任務(wù)時間短，預(yù)警探測距離遠于艦艇。當同時有多個區(qū)域需要偵察時，此時需要合理進行任務(wù)分配。線性規(guī)劃一般可以用于解決任務(wù)分配問題［6］，但是由于在偵察預(yù)警任務(wù)分配時，如果偵察區(qū)域要求的執(zhí)行任務(wù)時間較長，此時必須要安排兩架次以上預(yù)警機才能有效完成任務(wù)，這使得在進行線性規(guī)劃前確定目標函數(shù)很困難。動態(tài)規(guī)劃是軍事運籌學(xué)中一種重要的方法，主要解決的是多階段決策問題［7～9］，如果把偵察預(yù)警任務(wù)分配轉(zhuǎn)化為多階段決策問題，那么可以應(yīng)用動態(tài)規(guī)劃方法求解偵察預(yù)警任務(wù)分配的最優(yōu)方案。

2 動態(tài)規(guī)劃相關(guān)理論

2.1 多階段決策問題

圖1 狀態(tài)轉(zhuǎn)移圖

當某類問題能夠分為多個相互聯(lián)系的階段，每個階段都需要采取決策，各個階段的決策依賴于當前面臨的狀態(tài)，而且又能影響后續(xù)的發(fā)展，稱之為多階段決策問題，如圖1所示。當各階段的決策確定后，可得到一個決策序列，稱之為策略。多階段決策問題的目標就是求解最優(yōu)策略［10～11］。

2.2 動態(tài)規(guī)劃相關(guān)概念

動態(tài)規(guī)劃是一種解決多階段決策問題的方法，基于多階段決策問題的動態(tài)規(guī)劃包含以下要素［12］：

1）階段與階段變量：將問題分為若干階段，階段變量為描述階段的變量，用k表示。

2）狀態(tài)與狀態(tài)變量：狀態(tài)是各階段開始所處的客觀條件，狀態(tài)變量為描述狀態(tài)的變量，第k階段的狀態(tài)變量用xk表示，狀態(tài)變量集合用Xk表示。

3）決策與決策變量：決策表示某階段時可作出的決定，決策變量為描述決策的變量，第k階段的決策變量用uk表示，決策變量的全體成為允許決策集合，記為Dk。

4）策略與最優(yōu)策略：策略指的是一個按順序排列的決策組成的組合，由過程k階段開始到終止狀態(tài)的過程的決策函數(shù)序列成為k子過程策略，記為Pk（xk）。

5）狀態(tài)轉(zhuǎn)移方程：如果已知第k階段狀態(tài)變量xk，并給定決策變量uk，則xk+1也可以隨之確定，且存在狀態(tài)轉(zhuǎn)移方程Tk，滿足 xk+1=Tk（xk，uk）。

6）指標函數(shù)和最優(yōu)值函數(shù)：指標函數(shù)用來衡量所選策略的優(yōu)劣，用Vk表示，該指標函數(shù)滿足：

其中指標函數(shù)的最優(yōu)值稱為最優(yōu)值函數(shù)，用fk（xk）表示。

3 偵察預(yù)警任務(wù)分配求解

3.1 任務(wù)分配預(yù)期目標

一般來說，海上編隊有可執(zhí)行偵察預(yù)警任務(wù)的艦艇和預(yù)警機若干，需要同時偵察的目標區(qū)域多個。由于預(yù)警機的單次執(zhí)行任務(wù)時間較短，艦艇單次執(zhí)行任務(wù)時間較長，另外預(yù)警機可以多架次配合執(zhí)行任務(wù)，當偵察區(qū)域的任務(wù)時長不同時，兵力執(zhí)行任務(wù)的方式和預(yù)警效果都會變化。單偵察區(qū)域目標可以選擇的兵力為單機，雙機，三機，單艦，對于上述四種兵力：當偵察區(qū)域的偵察要求時長在8h以內(nèi)，兵力對應(yīng)的預(yù)警效果量化值為a1、a2、a3和a4；當偵察區(qū)域的偵察要求時長在（8h，16h）區(qū)間以內(nèi)，兵力對應(yīng)的預(yù)警效果量化值為b1、b2、b3和b4；當偵察區(qū)域的偵察要求時長在（16h，24h）區(qū)間以內(nèi)，兵力對應(yīng)的預(yù)警效果量化值為 c1、c2、c3和c4；當偵察區(qū)域的偵察要求時長大于24h，兵力對應(yīng)的預(yù)警效果量化值d1、d2、d3和d4。

偵察預(yù)警任務(wù)分配的預(yù)期目標就是利用海上編隊兵力實現(xiàn)對偵察區(qū)域最好的預(yù)警效果。

3.2 基于動態(tài)規(guī)劃建模

通過將偵察預(yù)警任務(wù)分配問題轉(zhuǎn)化為多階段決策問題，可對該問題進行動態(tài)規(guī)劃建模。

1）確定過程的階段：設(shè)需要同時偵察的目標區(qū)域有n個，可以將對n個偵察區(qū)域的兵力分配看成n個階段決策過程，確定對第k個偵察區(qū)域分配的兵力類型和數(shù)量看成第k階段的決策，k=1，2，…n。

2）確定狀態(tài)變量xk：為可分配至第k，k+1，…n個偵察區(qū)域的兵力類型和數(shù)量，狀態(tài)變量集合為Xk。

3）確定決策變量uk：為第k階段對第k個偵察區(qū)域分配的兵力類型和數(shù)量。

4）確定允許決策集合Dk：第k階段至少分配一個兵力，且不分配兩種類型兵力。

5）確定狀態(tài)轉(zhuǎn)移方程：在偵察預(yù)警任務(wù)分配問題中，狀態(tài)變量和決策變量間滿足一下關(guān)系：xk+1=xk-uk，k=1，2，…n。

6）確定過程指標函數(shù)Vk：在多階段決策過程過程中，第k階段投入的兵力類型和數(shù)量不同時，會產(chǎn)生不同的預(yù)警效果，即為該階段的指標函數(shù)vk，vk是狀態(tài)變量xk與決策變量uk的函數(shù)，對于偵察預(yù)警的任務(wù)分配問題，指標函數(shù)Vk滿足求和形式：

7）確定最優(yōu)指標函數(shù)fk（xk）：為了獲得最佳預(yù)警效果，最優(yōu)值指標函數(shù)應(yīng)取過程指標函數(shù)Vk的最大值，即

3.3 獲取最優(yōu)任務(wù)分配方案

基于對偵察預(yù)警任務(wù)分配的動態(tài)規(guī)劃建模，求取最優(yōu)任務(wù)分配方案可以轉(zhuǎn)化以下方程式的求解

式（4）為遞推方程，遞推過程從k=n開始，利用兵力在不同偵察要求時長的預(yù)警效果量化值確定階段指標函數(shù)，逐階段逆推，直到求出f1（x1），可得到偵察預(yù)警任務(wù)分配的最優(yōu)策略。

4 舉例分析

4.1 問題描述

已知單個偵察區(qū)域目標可以選擇的兵力為單機，雙機，三機，單艦。當偵察區(qū)域的偵察要求時長在8h以內(nèi)，兵力對應(yīng)的預(yù)警效果量化值為0.5，0.4，0.05，0.05；當偵察區(qū)域的偵察要求時長在（8h，16h）區(qū)間內(nèi)，兵力對應(yīng)的預(yù)警效果量化值為0.1，0.2，0.6，0.1；當偵察區(qū)域的偵察要求時長在（16h，24h）區(qū)間內(nèi)，兵力對應(yīng)的預(yù)警效果量化值為0.05，0.15，0.5，0.3；當偵察區(qū)域的偵察要求時長大于24h，兵力對應(yīng)的預(yù)警效果量化值為0.01，0.09，0.3，0.6。海上編隊可分配的偵察預(yù)警兵力為三個預(yù)警機和一個艦艇，需要偵察的區(qū)域目標有三個，其中要求的偵察時長分別是10h，18h和26h，如何合理分配偵察預(yù)警兵力，使得總體預(yù)警效果最好。

4.2 問題求解

根據(jù)問題描述，有三個偵察目標區(qū)域，因此該問題可轉(zhuǎn)換為三階段決策問題，初始條件：n=3，x1為3個飛機和1個艦艇。設(shè)定第一階段對偵察時長為10h的偵察區(qū)域兵力分配進行決策，第二階段對對偵察時長為18h的偵察區(qū)域兵力分配進行決策，第三階段對偵察時長為26h的偵察區(qū)域兵力分配進行決策，狀態(tài)轉(zhuǎn)移圖如圖2所示。

圖2 偵察預(yù)警任務(wù)分配狀態(tài)轉(zhuǎn)移圖

下面根據(jù)式（4）采用逆序法求解。

1）k=3時，此時對偵察時長為26h的偵察區(qū)域兵力分配進行決策，若還有偵察兵力為x3，且分配到該偵察區(qū)域的兵力為u3，則該階段最大的偵察預(yù)警效果為

又因為f4（x4）=0，所以

因為允許決策集合要保證各階段至少分配一個兵力且不同時分配兩種不同類型兵力，因此決策變量集合X3滿足：

允許決策集合D3滿足：

根據(jù)以上分析，結(jié)合偵察區(qū)域的偵察要求時長大于24h的兵力預(yù)警效果量化值，可得到k=3時的偵察預(yù)警效果表，如表1所示。

表1 k=3時偵察預(yù)警效果表

2）k=2時，此時對偵察時長為18h的偵察區(qū)域兵力分配進行決策，若還有偵察兵力為x2，且分配到該偵察區(qū)域的兵力為u2，則該階段最大的偵察預(yù)警效果為

根據(jù)允許決策集合規(guī)則，決策變量集合X2滿足：

允許決策集合D2滿足：

表2 k=2時偵察預(yù)警效果表

根據(jù)以上分析，結(jié)合偵察區(qū)域的偵察要求時長在區(qū)間（16h，24h）的兵力預(yù)警效果量化值，可得到k=2時的偵察預(yù)警效果表，如表2所示。

3）k=1時，此時對偵察時長為10h的偵察區(qū)域兵力分配進行決策，若還有偵察兵力為x1，且分配到該偵察區(qū)域的兵力為u1，則該階段最大的偵察預(yù)警效果為

根據(jù)允許決策集合規(guī)則，決策變量集合X1滿足：

允許決策集合D1滿足：

根據(jù)以上分析，結(jié)合偵察區(qū)域的偵察要求時長在區(qū)間（8h，16h）的兵力預(yù)警效果量化值，可得到k=1時的偵察預(yù)警效果表，如表3所示。

表3 k=1時偵察預(yù)警效果表

此時最大偵察預(yù)警效果為0.85，對應(yīng)的最優(yōu)任務(wù)分配策略為偵察時長為10h的偵察區(qū)域分配兩個飛機，偵察時長為18h的偵察區(qū)域分配一個飛機，偵察時長為26h的偵察區(qū)域分配一個艦艇。

5 結(jié)語

海上編隊可執(zhí)行偵察預(yù)警任務(wù)的兵力包括艦艇和預(yù)警機，不同兵力的偵察預(yù)警效果隨單次執(zhí)行任務(wù)時長的不同會有所變化，同時當偵察區(qū)域的偵察要求時長過長時，當同時有多個區(qū)域需要偵察時，這些情況會給偵察預(yù)警任務(wù)分配帶來困難。線性規(guī)劃方法是一個較好地解決任務(wù)分配問題的方法，但是無法在進行線性規(guī)劃前確定目標函數(shù)。

本文利用動態(tài)規(guī)劃方法將偵察預(yù)警任務(wù)分配轉(zhuǎn)化為多階段決策問題，借助于動態(tài)規(guī)劃相關(guān)理論，明確了偵察預(yù)警任務(wù)分配的預(yù)期目標，構(gòu)建了偵察預(yù)警任務(wù)分配動態(tài)規(guī)劃模型，通過遞推方程可求解得到偵察預(yù)警任務(wù)分配的最優(yōu)方案。最后通過一個具體分配案例驗證了上述方法，通過計算得到了偵察預(yù)警任務(wù)分配的最優(yōu)方案，該方法可為海上編隊輔助決策軟件設(shè)計提供參考。