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

成 果

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

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

一、指派問題描述

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

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

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

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

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

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

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

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

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

此時,若要求效率極優化,那該問題的數學模型為:

xij=0或1

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

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

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

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

(一)指派問題的定理

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

(二)匈牙利解法

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

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

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

Step1:將系數矩陣進行變換

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

這里出現了前文中提到的m

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

①找到沒有◎的行,并對該行打√;

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

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

④重復以上②和③兩個步驟,直到沒有出現新的打√的行和列為止;

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

令所得直線數為l.。當l.

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

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

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

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

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

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

根據運算出來的解矩陣,最優指派方案如下:

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

最優指派方案如表4:

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

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

四、效果系數λ

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

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

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

五、結論

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