基于線性規(guī)劃的通信保障專業(yè)隊配置方法研究

李勇

（國防信息學院，湖北 武漢430010）

通信保障專業(yè)隊配置是指在現(xiàn)有通信網(wǎng)絡條件下，研究部署通信保障專業(yè)隊伍，并合理配置通信保障專業(yè)隊力量，以期在出現(xiàn)突發(fā)緊急事件，能及時調(diào)度通信保障專業(yè)隊伍，最大限度地保障通信網(wǎng)絡的連通性能.合理優(yōu)化配置通信保障專業(yè)隊對于提高通信保障能力具有十分重要的意義，利用線性規(guī)劃理論可以輔助制定通信保障專業(yè)隊配置方案.

1 通信保障專業(yè)隊配置需求與流程

圖1 通信保障專業(yè)隊配置基本流程圖

1.1 配置需求 通信保障專業(yè)隊配置的主要任務是確定各分隊的部署位置、各部署點承擔的保障任務以及各分隊對應于部署點的力量分配.由于通信保障所涉及的因素較為復雜，目前對于通信保障專業(yè)隊的配置，普遍按照隸屬原則和就近分配原則進行配置和部署.

1.2 配置流程 通信保障專業(yè)隊的配置通常是依據(jù)平時制定的通信保障預案開展和實施的.配置基本步驟如下：首先分析通信網(wǎng)絡結(jié)構(gòu)，根據(jù)對通信設施的毀傷概率和網(wǎng)絡連通性的分析，評價通信網(wǎng)絡中各節(jié)點和鏈路的重要性指標；然后分析各通信設施的位置分布，結(jié)合其重要性指標，選擇專業(yè)隊部署點；最后按照有關的配置原則和現(xiàn)有通信保障力量情況，為各部署點分配專業(yè)隊力量.通信保障專業(yè)隊配置基本流程如圖1所示.

1.2.1 通信設施重要性評估 在通信保障專業(yè)隊配置的影響因素中，最為重要的是各通信設施的重要性程度.因此，通信保障專業(yè)隊配置首先就需要分析通信網(wǎng)絡結(jié)構(gòu)，根據(jù)對現(xiàn)有通信設施的毀傷概率和網(wǎng)絡連通性的分析，評價通信網(wǎng)絡中各節(jié)點和鏈路的重要性指標.

1.2.2 通信保障專業(yè)隊部署點選址 保障專業(yè)隊部署點是指各通信保障專業(yè)分隊按照預先制訂的通信保障預案部署待命的位置，一般是從現(xiàn)有的重要通信設施所在位置中選擇.通信保障專業(yè)隊部署點選擇就是根據(jù)實際情況，合理配置部署點，在充分滿足通信保障任務的前提下盡可能減少各分隊從部署點到達需要保障的任務位置所消耗的時間.

通信保障專業(yè)隊力量分配通信保障專業(yè)隊力量分配是指根據(jù)確定的專業(yè)隊部署點所承擔的通信保障任務以及現(xiàn)有的通信保障力量，為各個部署點分配相應的通信保障專業(yè)分隊，以最大限度地滿足各個部署點所承擔的通信保障任務.

2 通信保障專業(yè)隊配置模型與算法

2.1 部署點選址模型與算法

2.1.1 選址模型 根據(jù)P－中值模型，建立通信保障專業(yè)隊部署點選址數(shù)學模型：在給定數(shù)量和位置的通信設施集合以及距離閾值條件下，從候選位置集合（所有通信設施所在位置的集合）中選擇若干個專業(yè)隊部署點位置，并指派每個部署點負責若干個通信設施的保障任務，使之達到從所有專業(yè)隊部署點位置到相應負責搶修的通信設施所在位置的距離最短且小于指定的閾值.其目標函數(shù)是：

其中，N為n個通信設施，M為m個候選的專業(yè)隊部署點位置，yij為專業(yè)隊部署點任務分配變量，其取值為：yij＝｛0，1｝，i∈N，j∈M，當候選的專業(yè)隊部署點j承擔通信設施i的保障任務時，yij＝1，否則，yij＝0；dij為從通信設施i所在位置到專業(yè)隊部署點位置j的路程，T為指定的距離閾值.

其約束條件為：

yij≤xj，i∈N，j∈M表示沒有選定為專業(yè)隊部署點的候選位置不會承擔任何通信設施的保障任務；

∑j∈M（xj）＝p表示只能選定p個專業(yè)隊部署點；

xj∈｛0，1｝，j∈M，當候選的專業(yè)隊部署點j被定為專業(yè)隊部署點時，xj＝1，否則，xj＝0；

∑j∈M（yij）≥1表示每個通信設施都必須分配至少一個專業(yè)隊部署點.

2.1.2 模型算法 對于該模型的求解，筆者對貪婪算法［2］進行改進后提出了貪婪取走啟發(fā)式算法，利用該算法對模型進行求解.在介紹算法之前，先引入幾個要素：

通信設施重要性指標數(shù)組A＝［ai］m.其中，ai∈（0，1），表示通信設施i的重要性指標.任務分配矩陣Y＝［yij］m×m.其中，yij∈｛0，1｝，若yij＝1，表示候選專業(yè)隊部署點j承擔通信設施i的保障任務.依照以下的規(guī)則初始化任務分配矩陣Y＝［yij］m×m：矩陣對角線元素全部定義為1，即yii＝1，（i＝1，2，…，m）；其余元素定義為：yij＝0；通過計算以后的任務分配矩陣Y即為最終模型計算所求的結(jié)果.距離矩陣D＝［dij］m×m.其中，dij表示通信設施i到通信設施j的距離.

模型求解算法步驟如下：

Step1：建立節(jié)點重要性指標矩陣A，重要性指標取值范圍為（0，1）；

Step2：選擇現(xiàn)有的所有通信節(jié)點設施所在位置為候選位置，共有m個候選位置，每個通信節(jié)點指派其對應的候選位置承擔保障任務，初始化任務分配矩陣Y；

Step3：確定距離閾值T，建立距離矩陣D；

Step4：在A中從小到大依次選擇并取走一個候選專業(yè)隊部署點位置，計算目標函數(shù)，假如將其取走并將它對應的通信節(jié)點設施重新指派后，目標函數(shù)仍然成立，且在其中距離增加量最小，根據(jù)新的任務分配情況修改Y，然后令p＝p－1，進行下一步；假如將其取走并將它對應的通信設施重新指派后，總的距離增加量為最小，但目標函數(shù)不成立，退出循環(huán)，當前任務分配矩陣Y即為所求；

Step5：返回Step2，繼續(xù)運行，直到p＝0，結(jié)束.

算法流程如圖2所示.

圖2 通信保障專業(yè)隊部署點選址算法流程圖

2.2 力量分配模型與算法

2.2.1 力量分配模型 通信保障專業(yè)隊力量分配是指根據(jù)確定的專業(yè)隊部署點所承擔的通信保障任務以及現(xiàn)有的通信保障力量情況，為各個部署點分配相應的保障專業(yè)分隊，以最大限度地滿足各個部署點所承擔的通信保障任務.其數(shù)學模型為：在給定數(shù)量和類型的通信保障專業(yè)隊集合以及給定數(shù)量的專業(yè)隊部署點（其通信保障任務已確定）集合的條件下，合理分配專業(yè)隊力量，使得專業(yè)隊部署點內(nèi)的保障人員數(shù)量與所承擔的保障任務數(shù)量比例之均方差最小或保障能力與所承擔的保障任務難度比例之均方差最小.

其目標函數(shù)可根據(jù)實際的需要選擇以下函數(shù)之一：

1）目標函數(shù)只考慮專業(yè)隊部署點內(nèi)的保障人員數(shù)量與所承擔的保障任務數(shù)量

2）目標函數(shù)只考慮專業(yè)隊部署點內(nèi)的保障能力與所承擔的保障任務難度

3）目標函數(shù)綜合考慮專業(yè)隊部署點內(nèi)的保障人員數(shù)量與所承擔的保障任務以及保障能力與所承擔的保障任務難度

其中：π1為保障數(shù)量權(quán)重，π2為保障能力權(quán)重.

ωj為第j個專業(yè)隊部署點內(nèi)專業(yè)隊保障人員數(shù)量與所承擔的保障任務數(shù)量之比，其計算公式為：

其中M為m個通信保障專業(yè)分隊，N為n個通信保障專業(yè)隊部署點，L為l個通信設施，ui表示第i個通信保障專業(yè)分隊的人員數(shù)量.

ρj為第j個專業(yè)隊部署點內(nèi)的通信保障專業(yè)分隊保障能力與所承擔的保障任務難度之比，其計算公式為：

其中M為m個通信保障專業(yè)分隊，L為l個通信設施，vi表示第i個通信保障專業(yè)分隊的保障能力指標，pi表示第i個通信設施的重要性指標，qi表示第i個通信設施的保障難度指標.

其約束條件為：

xij＝｛0，1｝，i∈M，j∈N，當專業(yè)分隊i分配到專業(yè)隊部署點j時，xij＝1，否則，xij＝0；

yjk＝｛0，1｝，j∈N，k∈L，當專業(yè)隊部署點j承擔通信設施k的保障任務時，yjk＝1，否則，yjk＝0；

∑xij＝1表示每個通信保障專業(yè)分隊必須被分配且只能分配到一個專業(yè)隊部署點.

2.2.2 模型算法 對于上述模型，可以采用遍歷算法進行求解.在介紹算法之前，先引入以下幾個要素：

專業(yè)隊部署點任務分配矩陣Y＝［yjk］n×l.其中，yjk∈｛0，1｝，若yjk＝1，表示專業(yè)隊部署點j承擔通信設施k的搶修任務；若yjk＝0，表示專業(yè)隊部署點j不承擔通信設施k的搶修任務；

專業(yè)隊力量分配矩陣X＝［xij］m×n.其中，xij∈｛0，1｝，若xij＝1，表示通信保障專業(yè)分隊i被分配到專業(yè)隊部署點j；若xij＝0，表示通信保障專業(yè)分隊i沒有被分配到專業(yè)隊部署點j；

通信保障專業(yè)分隊人員數(shù)量數(shù)組U＝［ui］m.其中，ui表示通信保障專業(yè)分隊i的人員數(shù)量；

通信保障專業(yè)分隊保障能力數(shù)組V＝［vi］m.其中，vi∈（0，1），表示通信保障專業(yè)分隊i的保障能力指標；

通信設施重要性指標數(shù)組P＝［pi］l.其中，pi∈（0，1），表示通信設施i的重要性指標；

通信設施保障難度指標數(shù)組Q＝［qi］l.其中，qi∈（0，1），表示通信設施i的保障難度指標；

模型求解算法步驟如下：

Step1：建立專業(yè)隊部署點任務分配矩陣Y、專業(yè)隊部署點承擔任務數(shù)量數(shù)組T、通信保障專業(yè)分隊人員數(shù)量數(shù)組U、通信保障專業(yè)分隊保障能力數(shù)組V、通信設施重要性指標數(shù)組P、通信設施保障難度指標數(shù)組Q，初始化專業(yè)隊力量分配矩陣X；

Step2：逐列調(diào)整專業(yè)隊力量分配矩陣X內(nèi)的要素值，計算目標函數(shù)，選擇目標函數(shù)值最大的專業(yè)隊力量分配矩陣X；

Step3：重復Step2，直到按行全部調(diào)整完畢，結(jié)束.

3 實例分析

運用提出的通信保障力量配置模型和算法，分析XX市應急通信保障專業(yè)隊的方法與流程.

首先通過網(wǎng)絡節(jié)點分析建立需要通信節(jié)點重要性指標和通信節(jié)點保障難度指標（表1所示），確定專業(yè)隊保障能力指標（表2所示）和通信節(jié)點距離矩陣.

表1 通信節(jié)點重要性與保障難度指標

表2 專業(yè)隊保障能力指標

通信節(jié)點距離矩陣：

根據(jù)專業(yè)隊部署點選址模型算法可得出任務分配矩陣Y：

從矩陣中可以得出：分別在1，5，7，9，11這5個通信設施位置附近設置專業(yè)隊部署點，依次將其編為1，2，3，4，5號專業(yè)隊部署點，其中1號專業(yè)隊部署點負責1，2，3號通信設施的搶修任務，2號專業(yè)隊部署點負責3，4，5，6號通信設施的搶修任務，3號專業(yè)隊部署點負責6，7，8號通信設施的搶修任務，4號專業(yè)隊部署點負責8，9，10號通信設施的搶修任務，5號專業(yè)隊部署點負責11，12號通信設施的搶修任務.

通過專業(yè)隊力量分配模型算法得出專業(yè)隊力量分配矩陣：

從矩陣中可以得出：1號專業(yè)分隊被分配到1號專業(yè)隊部署點，2、3號專業(yè)分隊被分配到2號專業(yè)隊部署點，4號專業(yè)分隊被分配到3號專業(yè)隊部署點，5號專業(yè)分隊被分配到5號專業(yè)隊部署點，6號專業(yè)分隊被分配到4號專業(yè)隊部署點.

4 結(jié)論

運用線性規(guī)劃理論，建立通信保障專業(yè)隊的部署點選址模型和力量分配模型，可以輔助快速制定科學合理的通信保障任務分配和通信保障力量分配方案，使通信保障方案能最大限度地滿足任務需求，提高通信搶修能力.

［1］李長生.軍事運籌學教程［M］.北京：軍事科學出版社，2006.

［2］袁亞湘，孫文瑜.最優(yōu)化理論與方法［M］.北京：科學出版社，2001.

［3］解可新，韓立興.最優(yōu)化方法［M］.天津：天津大學出版社，2001.

［4］高培旺.高效求解整數(shù)線性規(guī)劃問題的分支算法［J］.計算機應用，2010，30（4）：1019－1021.

［5］范國兵.投資決策的線性規(guī)劃模型及其應用［J］.科技與產(chǎn)業(yè)，2010，10（8）：62－64

［6］劉磊，王東雷，劉明.求解線性規(guī)劃模型算法的實現(xiàn)研究［J］.電腦知識與技術，2010，28（6）：8146－8148

［7］鄭國用.反恐兵力分配運籌方法輔助決策研究［J］.武警學院學報，2008（4）：94－96.

［8］盧厚清，袁輝，劉誠.基于連續(xù)覆蓋的城市消防站布局優(yōu)化［J］.計算機應用，2012（3）：852－855.

［9］花文健，李炳杰.應急機動通信兵力派遣問題的通用模型［J］.空軍工程大學學報：自然科學版，2003（8）：38－40.

［10］Stutzle T，Dorigo M.A short convergence proof for a class of ant colony optimization algorithm［J］.IEEE，2002，6（40）：458－365.