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

李勇

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

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

李勇

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

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

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

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

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

1.1 配置需求

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

1.2 配置流程

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

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

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

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

1.2.2 通信保障專業(yè)隊(duì)部署點(diǎn)選址

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

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

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

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

2.1 部署點(diǎn)選址模型與算法

2.1.1 選址模型

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

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

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

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

其約束條件為：

2.1.2 模型算法

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

通信設(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è)隊(duì)部署點(diǎn)j承擔(dān)通信設(shè)施i的保障任務(wù)。依照以下的規(guī)則初始化任務(wù)分配矩陣Y=[yij]m×m：矩陣對(duì)角線元素全部定義為1，即yii=1，(i=1,2,…,m)；其余元素定義為：yij=0；通過計(jì)算以后的任務(wù)分配矩陣Y即為最終模型計(jì)算所求的結(jié)果。

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

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

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

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

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

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

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

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

2.2 力量分配模型與算法

2.2.1 力量分配模型

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

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

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

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

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

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

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

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

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

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

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

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

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

其約束條件為：

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

2.2.2 模型算法

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

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

專業(yè)隊(duì)力量分配矩陣X=[xij]m×n。式中xij∈{0， 1}，若xij=1，表示通信保障專業(yè)分隊(duì)i被分配到專業(yè)隊(duì)部署點(diǎn)j；若xij=0，表示通信保障專業(yè)分隊(duì)i沒有被分配到專業(yè)隊(duì)部署點(diǎn)j。

通信保障專業(yè)分隊(duì)人員數(shù)量數(shù)組U=[ui]m。其中ui表示通信保障專業(yè)分隊(duì)i的人員數(shù)量。

通信保障專業(yè)分隊(duì)保障能力數(shù)組V=[vi]m。其中vi∈(0,1)，表示通信保障專業(yè)分隊(duì)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è)隊(duì)部署點(diǎn)任務(wù)分配矩陣Y、專業(yè)隊(duì)部署點(diǎn)承擔(dān)任務(wù)數(shù)量數(shù)組T、通信保障專業(yè)分隊(duì)人員數(shù)量數(shù)組U、通信保障專業(yè)分隊(duì)保障能力數(shù)組V、通信設(shè)施重要性指標(biāo)數(shù)組P、通信設(shè)施保障難度指標(biāo)數(shù)組Q，初始化專業(yè)隊(duì)力量分配矩陣X；

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

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

3 實(shí)例分析

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

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

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

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

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

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

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

從矩陣中可以得出：1號(hào)專業(yè)分隊(duì)被分配到1號(hào)專業(yè)隊(duì)部署點(diǎn)，2、3號(hào)專業(yè)分隊(duì)被分配到2號(hào)專業(yè)隊(duì)部署點(diǎn)，4號(hào)專業(yè)分隊(duì)被分配到3號(hào)專業(yè)隊(duì)部署點(diǎn)，5號(hào)專業(yè)分隊(duì)被分配到5號(hào)專業(yè)隊(duì)部署點(diǎn)，6號(hào)專業(yè)分隊(duì)被分配到4號(hào)專業(yè)隊(duì)部署點(diǎn)。

4 結(jié)束語

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

[1] 李長(zhǎng)生. 軍事運(yùn)籌學(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]. 計(jì)算機(jī)應(yīng)用, 2010, 30(4): 1019-1021.

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

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

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

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

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