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

李勇

國防信息學院 信息化建設系，湖北 武漢 430010

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

李勇

國防信息學院 信息化建設系，湖北 武漢 430010

合理優(yōu)化配置通信保障專業(yè)隊對于提高通信保障能力十分重要。分析了通信保障專業(yè)隊的實際需求和基本原則，利用線性規(guī)劃理論對通信保障專業(yè)隊配置中的部署點選址和力量分配進行了研究，建立了通信保障專業(yè)隊部署點選址模型和力量分配模型，并對模型算法進行了分析。選址模型和力量分配模型可快速生成部署點選址和力量分配矩陣，輔助制定相關方案。

線性規(guī)劃；配置；P-中值模型；選址

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

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

1.1 配置需求

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

1.2 配置流程

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

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

1.2.1 通信設施重要性評估

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

1.2.2 通信保障專業(yè)隊部署點選址

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

1.2.3 通信保障專業(yè)隊力量分配

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

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

2.1 部署點選址模型與算法

2.1.1 選址模型

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

其目標函數是：

maxi∈N,j∈M(yijdij)≤T式中：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為指定的距離閾值。

其約束條件為：

2.1.2 模型算法

該模型可采用貪婪取走啟發(fā)式算法進行求解。在介紹算法之前，先引入幾個要素：

通信設施重要性指標數組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即為最終模型計算所求的結果。

距離矩陣D=[dij]m×m。式中dij表示通信設施i到通信設施j的距離。

模型求解算法步驟如下，算法流程如圖2所示。

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

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

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

3）確定距離閾值T，建立距離矩陣D；

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

5）返回2），繼續(xù)運行，直到p=0，結束。

2.2 力量分配模型與算法

2.2.1 力量分配模型

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

其數學模型如下：在給定數量和類型的通信保障專業(yè)隊集合以及給定數量的專業(yè)隊部署點（其通信保障任務已確定）集合的條件下，合理分配專業(yè)隊力量，使得專業(yè)隊部署點內的保障人員數量與所承擔的保障任務數量比例之均方差最小或保障能力與所承擔的保障任務難度比例之均方差最小。

其目標函數可根據實際需要選擇以下函數之一：

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

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

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

式中：π1為保障數量權重，π2為保障能力權重。

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

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

ω為所有專業(yè)隊部署點內保障人員的數量與所承擔的保障任務數量之比的平均值，其計算公式為

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

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

ρ為所有專業(yè)隊部署點內保障能力與所承擔的保障任務難度之比的平均值，其計算公式為

其約束條件為：

xij={0,1},i∈M, j∈N，當專業(yè)分隊i分配到專業(yè)隊部署點j時，xij=1；否則，xij=0。

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è)分隊人員數量數組U=[ui]m。其中ui表示通信保障專業(yè)分隊i的人員數量。

通信保障專業(yè)分隊保障能力數組V=[vi]m。其中vi∈(0,1)，表示通信保障專業(yè)分隊i的保障能力指標；

通信設施重要性指標數組P=[pi]l。其中pi∈(0,1)表示通信設施i的重要性指標。

通信設施保障難度指標數組Q=[qi]l。其中qi∈(0,1)表示通信設施i的保障難度指標。

模型求解算法步驟如下：

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

2）逐列調整專業(yè)隊力量分配矩陣X內的要素值，計算目標函數，選擇目標函數值最大的專業(yè)隊力量分配矩陣X；

3）重復2），直到按行全部調整完畢，結束。

3 實例分析

運用文中提出的通信保障力量配置模型和算法，分析某市應急通信保障專業(yè)隊的方法與流程。首先通過網絡節(jié)點分析建立需要通信節(jié)點重要性指標和通信節(jié)點保障難度指標（表1所示），確定專業(yè)隊保障能力指標（表2所示）和通信節(jié)點距離矩陣。

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

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

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

根據專業(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 結束語

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

[1] 李長生. 軍事運籌學教程[M]. 北京: 軍事科學出版社, 2006: 62-136.

[2] 袁亞湘, 孫文瑜. 最優(yōu)化理論與方法[M]. 北京: 科學出版社, 2001: 55-731.

[3] 解可新, 韓立興. 最優(yōu)化方法[M]. 天津: 天津大學出版社, 2001: 38-42.

[4] 高培旺. 高效求解整數線性規(guī)劃問題的分支算法[J]. 計算機應用, 2010, 30(4): 1019-1021.

[5] 范國兵. 投資決策的線性規(guī)劃模型及其應用[J]. 科技與產業(yè), 2010, 10(8): 62-64.

[6] 劉磊. 求解線性規(guī)劃模型算法的實現研究[J]. 電腦知識與技術, 2010, 6(28): 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 Trans on Evolutionary Computation, 2002, 40(6): 458-365.

Research on configuration of communication guarantee special team based on linear programming theory

LI Yong

Department of Informatization Construction, PLA Academy of National Defense Information, Wuhan 430010, China

It is an important question to optimize and configure communication safeguard special team for advancing military communication safeguard ability. Effective requirement and elementary principle for configuring communication safeguard special team were analyzed, and choice for locating position and distribution for safeguard power were researched by making use of the linear programming theory. As a result, location and distribution models for safeguard power were established, and the algorithm of the models was analyzed. The model and algorithm proposed in this paper may be used to rapidly locate position and generate matrix of safeguard power allocation, and help formulate relevant schemes.

linear programming; configuration; p-median model; position-choice

O212.6

A

1009-671X（2014）01-0054-05

10.3969/j.issn.1009-671X.201301014

2013-01-15.

李勇（1978-）, 男, 講師, 博士.

李勇, E-mail: liyongceyua@163.com.