基于指派問題的公安情報決策方法

成 果

(廣東警官學院 偵查系,廣州 510440)

新時代公安情報工作具有“警務實戰(zhàn)指揮中樞”職能作用,涵蓋防風險、保安全、護穩(wěn)定各項措施,是全力以赴維護國家政治安全、社會穩(wěn)定的保障。公安情報決策是公安情報工作中極為關(guān)鍵的一環(huán),它直接決定著公安情報價值。為實現(xiàn)預警防范功能,研究公安情報決策方法,將運籌學的指派問題應用到公安情報決策當中,不斷完善定量方法群,為決策者提供科學依據(jù)。

一、指派問題描述

指派問題(assignment problem)又稱分派問題或者任務分配問題,由Gross.C提出[1]。在運籌學中,組合優(yōu)化理論是關(guān)于人員(機器或資源)與任務(產(chǎn)品)之間的匹配最優(yōu)化問題。由于這一問題廣泛存在,各行各業(yè)學者研究了許多解決各類指派問題的算法。這些算法從目標函數(shù)來看,分為兩類:一類為求和型指派問題(the sum assignment problem),另一類為瓶頸指派問題(bottleneck assignment problem)。前者目標函數(shù)結(jié)果是使完成各項任務所花時間總和最小,后者目標函數(shù)的結(jié)果是使完成各項任務中所花時間最大者最小。

結(jié)合公安情報決策工作實際,求和型指派問題出現(xiàn)較多。求和型指派問題是:指定委派n人去完成n項工作任務,因每個人所擅長的領(lǐng)域不同,完成任務所花時間也不同,如何指派使完成n項工作任務的時間最少。具體應用到公安情報決策領(lǐng)域:指定n個民警研判n份情報,由于每人專長不同,研判時間有所不同,如何指派民警使得各項研判任務在最短時間內(nèi)完成。

二、公安情報決策中指派問題的數(shù)學模型

指派問題特點是一對一,除了人的工作分配問題外,機器工作分配、選址問題、如何派遣警力、圍堵指定路口等,均屬于這一類問題。在公安情報決策中,指派問題可以轉(zhuǎn)化成相應的數(shù)學模型尋求解決方法。如在具體情境下,某總隊業(yè)務工作涉及不同情報研判,如何安排相應人員研判,需要有科學依據(jù)支撐決策者的安排工作。根據(jù)筆者在T省公安廳某總隊調(diào)研時獲取數(shù)據(jù),模型中設置變量為:民警人數(shù)、情報種類、不同人研判不同種類情報所需時間。為了探究警力優(yōu)化使用,本研究將民警人數(shù)與情報種類比例定為1∶1,選取研判時間為自變量進行演算。

有4份不同情報,分別是A、B、C、D4份情報,由甲、乙、丙、丁4位民警處理,研判4份情報所需要時間如表1所示。

表1 甲、乙、丙、丁四位民警研判4份情報所需時間(h)

表2 甲、乙、丙、丁、戊5位民警研判5類專題情報所需時間(h)

表3 甲、乙、丙、丁、戊5位民警研判5類專題情報指派方案一

在公安工作中,類似問題還有n條執(zhí)勤路線,如何指派給n人巡邏。解決相應指派問題,都需先制定類似表1的表格,此表格還可以采用系數(shù)矩陣、效率矩陣表示。用某元素cij(i,j=1,2,…,n),表示分派第i個人去完成第j項任務的效率(效率指時間或成本)。再引入變量xij,而xij的取值是1或0,同時令

此時,若要求效率極優(yōu)化,那該問題的數(shù)學模型為:

xij=0或1

指派問題的解矩陣,每行或每列只能有一個元素為1,其余均為0的n階方陣,如下就是表1的一個解矩陣。

這個矩陣表示:指派民警甲研判B情報,民警乙研判C情報,而A情報和D情報分別由民警丙和民警丁來進行研判。當然,這個矩陣并非最優(yōu)解,這個指派方法也并非最優(yōu)指派方法。

三、指派問題在公安情報決策中的應用

為了獲得指派問題數(shù)學模型最優(yōu)解,即獲得指派問題最優(yōu)指派方法,就必須了解指派問題的定理及其解法。

(一)指派問題的定理

指派問題的定理為:設(cij)是指派問題的效率矩陣,cij≥0,i,j=1,2,…,n。假設從矩陣(cij)的某一行或某一列元素中,依次減去該行或者該列的最小元素,得到一個新矩陣(bij),此時,原問題具有和以新矩陣(bij)為效率矩陣的指派問題相同的最優(yōu)解。利用該定理,可使原效率矩陣變換為含有更多0元素的效率矩陣,經(jīng)過轉(zhuǎn)變后,保持最優(yōu)解不變。在效率矩陣中,位于不同行不同列的0元素(以下簡稱:獨立的0元素),因為獨立的0元素關(guān)系到目標函數(shù)最優(yōu)解。若在效率矩陣中能找到n個獨立的0元素,令解矩陣中這些n個獨立的0元素的取值為1,同時令其他元素取值為0,將其代入到目標函數(shù),計算的函數(shù)值一定是最小的。這個最小值就是原問題的最優(yōu)解,也是變換后的效率矩陣所對應分派問題的最優(yōu)解。

(二)匈牙利解法

1955年,庫恩(W.W.Kuhn)提出了一種指派問題的解法,該解法最初源于匈牙利數(shù)學家康尼(D.K?nig)?？的彡P(guān)于矩陣中0元素的定理,只要矩陣變換操作就能求出模型最優(yōu)解,即效率矩陣中獨立0元素的最多個數(shù),如果等于覆蓋所有0元素的最少直線數(shù),便能得到最優(yōu)解,這個解法也被稱之為匈牙利解法。一直以來,匈牙利解法(HA)被公認為是指派問題的標準解法[2-3]。

(三)利用匈牙利解法運算公安情報決策中的指派問題

將匈牙利解法運用到公安情報決策工作中碰到的指派問題,得出指派任務最優(yōu)解,提高工作效率。筆者在Z市公安局某處鍛煉時發(fā)現(xiàn),該處各科室領(lǐng)導及處領(lǐng)導在做決策時,經(jīng)常遇到業(yè)務指派問題。例如,該處負責全市11個區(qū)專題情報的分析研判,將研判內(nèi)容、結(jié)論寫成研判報告呈交給相應級別領(lǐng)導后,再下發(fā)傳達到相應區(qū)分局。專題情報內(nèi)容有A、B、C、D、E共5類專題情報,如何將這5類專題情報科學分派給科室5位民警,以達到工作效率最大化。將這一類問題轉(zhuǎn)化成指派問題的數(shù)學模型。經(jīng)統(tǒng)計,甲、乙、丙、丁、戊5位民警,從收集→研判→呈交研判報告→下達到相應區(qū)分局,5類專題情報分別用時如下:

Step1:將系數(shù)矩陣進行變換

Step2:變換后,矩陣每一行每一列都有0元素,按第2步進行試指派,得

這里出現(xiàn)了前文中提到的m

Step3:嘗試作出最少的直線來覆蓋所有的0元素。此步的目的是確定該效率矩陣中可以找到最多的獨立0元素。接下來按照以下步驟進行:

①找到?jīng)]有◎的行,并對該行打√;

②找出已打√的行中,對該行中包含有0元素的列,打上√;

③此時,獲得了打√的列,找出這些列中含有◎的行,并打上√;

④重復以上②和③兩個步驟,直到?jīng)]有出現(xiàn)新的打√的行和列為止;

⑤在矩陣中找出沒有打√的行和打√的列,對沒有打√的行畫上橫線,打√的列畫上縱線。此時,便得出可以覆蓋矩陣中所有獨立0元素的最少直線。

令所得直線數(shù)為l.。當l.

Step4:當l.=n時,此時返回到第2步,嘗試別的指派方案。

對由第1、2步所求得的矩陣進行第3步的工作,對第5行旁打√,由于該行第1列含有0元素,在第1列下面打√,而此時第1列中第3行含有◎的元素,所以要在第3行旁打√。檢查整個矩陣,發(fā)現(xiàn)已經(jīng)不能再打√。找出沒有打√的行與打√的列,畫上直線,以此覆蓋矩陣中的0元素。得出以下結(jié)果:

由于l.=4<5(n=5),所以應繼續(xù)變換以上矩陣,轉(zhuǎn)回到第4步。

Step5:此步的目的是增加0元素。做如下運算,找出沒有被直線覆蓋的部分,在此部分中找到最小元素,令打√行各元素都減去此最小元素,相反地,令打√列的各元素中都加上此最小元素,目的是變換之后的0元素與原來矩陣中0元素的位置一致。意味著新的效率矩陣與原問題具有同一最優(yōu)解。在此情況下,如果已經(jīng)得到n個獨立的0元素,則原問題運算出了最優(yōu)解,如果沒有,需要返回到上文中的第3步重復進行[4]。

在沒有被直線覆蓋的部分中尋找最小元素,此矩陣為2。按照以上方法,在打√的各行中減去最小元素2,在打√的各列中加上最小元素2,并按照上文第2步,找到所有獨立的0元素,此時得到以下新矩陣:

這時已經(jīng)找到了n個不同行不同列的0元素,問題的最優(yōu)解也已運算出,具體如下:

根據(jù)運算出來的解矩陣,最優(yōu)指派方案如下:

即甲研判B專題情報,乙研判D專題情報,丙研判E情報,丁研判C專題情報,戊研判A專題情報。本算例還可得出另一個最優(yōu)解:

最優(yōu)指派方案如表4:

表4 甲、乙、丙、丁、戊5位民警研判5類專題情報指派方案二

即甲研判B專題情報,乙研判C專題情報,丙研判E情報,丁研判D專題情報,戊研判A專題情報。經(jīng)計算,以上兩個指派方案所需總時間都是32h。

四、效果系數(shù)λ

在公安情報決策中運用指派問題方法,可以更科學、合理地指派人員和任務,提高公安情報工作效率。但以上將相應的問題轉(zhuǎn)化成指派問題的數(shù)學模型來解決時,只考慮到各人在完成此項任務的時間,并未考慮到各人完成此項任務的水平優(yōu)劣。在某些情況下,一個人完成該項任務較快并不意味著完成該項任務較好,時間與水平并不成正相關(guān)。

改進指派問題在公安情報決策中如何運用數(shù)學模型需要反思。結(jié)合公安情報工作實際情況,將矩陣中所需時間乘以相應系數(shù)。完成一項任務的水平優(yōu)劣劃分為五個等級:A(很好)、B(好)、C(一般)、D(差)、E(很差),相應系數(shù)可取值為0.5、0.8、1.0、1.2、1.5,稱之為效果系數(shù)λ。

在運算前評判每個人完成該項任務的優(yōu)劣,根據(jù)判斷標準乘以相應系數(shù)進行調(diào)整。例如,甲在研判A類專題情報需12h,但是其完成研判報告科學性較強,準確率較高,總體完成任務水平較好,那么可以乘以系數(shù)0.8,再將計算后的結(jié)果9.6填入到相應矩陣中運算。相反,若完成研判報告科學性較弱,準確率較低,總體完成任務水平較差,那么可以乘以系數(shù)1.2再計算。當然,此步需要對各個被指派人員進行前期的考察,統(tǒng)計其工作完成效果,決策者才能根據(jù)之前表現(xiàn),來對完成某項任務的水平優(yōu)劣定檔[5]。

五、結(jié)論

綜合以上對實踐調(diào)研所獲數(shù)據(jù)的建模、分析和運算,本文的結(jié)論體現(xiàn)在對于實際警務工作的意義:公安情報決策工作可以運用求和型指派問題數(shù)學模型來解決任務分派問題,據(jù)此得到的分派結(jié)果是可行且科學的,決策者根據(jù)數(shù)學模型計算出來的結(jié)果安排警力以達到使用警力優(yōu)化的目的。本文另一個主要內(nèi)容是對加入效果系數(shù)改進模型的思考。綜合效果系數(shù)運算,使指派問題在公安情報決策工作中能得到科學運用,計算結(jié)果不僅考慮消耗時間,也考慮了工作完成效果,能夠完善公安情報工作決策機制,有利于公安機關(guān)情報研判預警、整體合成作戰(zhàn)平臺建設,為健全完善“情報、指揮、勤務、輿情”一體化實戰(zhàn)化運行機制助力。