李勇

國防信息學(xué)院 信息化建設(shè)系，湖北 武漢 430010

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

李勇

國防信息學(xué)院 信息化建設(shè)系，湖北 武漢 430010

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

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

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

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

1.1 配置需求

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

1.2 配置流程

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

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

1.2.1 通信設(shè)施重要性評估

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

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

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

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

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

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

2.1 部署點選址模型與算法

2.1.1 選址模型

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

其目標(biāo)函數(shù)是：

maxi∈N,j∈M(yijdij)≤T式中：N為n個通信設(shè)施，M為m個候選的專業(yè)隊部署點位置，yij為專業(yè)隊部署點任務(wù)分配變量，其取值為：

yij={0， 1},i∈N，j∈M。當(dāng)候選的專業(yè)隊部署點j承擔(dān)通信設(shè)施i的保障任務(wù)時，yij=1，否則，yij=0；dij為從通信設(shè)施i所在位置到專業(yè)隊部署點位置j的路程，T為指定的距離閾值。

其約束條件為：

2.1.2 模型算法

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

通信設(shè)施重要性指標(biāo)數(shù)組A=[ai]m。其中，ai∈(0， 1)，表示通信設(shè)施i的重要性指標(biāo)。

任務(wù)分配矩陣Y=[yij]m×m。其中，yij∈{0， 1}，若yij=1，表示候選專業(yè)隊部署點j承擔(dān)通信設(shè)施i的保障任務(wù)。依照以下的規(guī)則初始化任務(wù)分配矩陣Y=[yij]m×m：矩陣對角線元素全部定義為1，即yii=1，(i=1,2,…,m)；其余元素定義為：yij=0；通過計算以后的任務(wù)分配矩陣Y即為最終模型計算所求的結(jié)果。

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

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

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

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

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

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

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

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

2.2 力量分配模型與算法

2.2.1 力量分配模型

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

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

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

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

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

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

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

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

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

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

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

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

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

其約束條件為：

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

2.2.2 模型算法

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

專業(yè)隊部署點任務(wù)分配矩陣Y=[yjk]n×l。其中，yjk∈{0， 1}，若yjk=1，表示專業(yè)隊部署點j承擔(dān)通信設(shè)施k的搶修任務(wù)；若yjk=0，表示專業(yè)隊部署點j不承擔(dān)通信設(shè)施k的搶修任務(wù)。

專業(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的保障能力指標(biāo)；

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

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

模型求解算法步驟如下：

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

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

3）重復(fù)2），直到按行全部調(diào)整完畢，結(jié)束。

3 實例分析

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

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

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

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

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

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

通過專業(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è)隊的部署點選址模型和力量分配模型，可以輔助快速制定科學(xué)合理的通信保障任務(wù)分配和通信保障力量分配方案，使通信保障方案能最大限度地滿足任務(wù)需求，提高通信搶修能力。

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

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

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

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

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

[6] 劉磊. 求解線性規(guī)劃模型算法的實現(xiàn)研究[J]. 電腦知識與技術(shù), 2010, 6(28): 8146-8148.

[7] 鄭國用. 反恐兵力分配運籌方法輔助決策研究[J]. 武警學(xué)院學(xué)報, 2008(4): 94-96.

[8] 盧厚清. 基于連續(xù)覆蓋的城市消防站布局優(yōu)化[J]. 計算機應(yīng)用, 2012(3): 852-855.

[9] 花文健, 李炳杰. 應(yīng)急機動通信兵力派遣問題的通用模型[J]. 空軍工程大學(xué)學(xué)報: 自然科學(xué)版, 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.