基于指派问题的公安情报决策方法

成 果

(广东警官学院 侦查系,广州 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]。

五、结论

综合以上对实践调研所获数据的建模、分析和运算,本文的结论体现在对于实际警务工作的意义:公安情报决策工作可以运用求和型指派问题数学模型来解决任务分派问题,据此得到的分派结果是可行且科学的,决策者根据数学模型计算出来的结果安排警力以达到使用警力优化的目的。本文另一个主要内容是对加入效果系数改进模型的思考。综合效果系数运算,使指派问题在公安情报决策工作中能得到科学运用,计算结果不仅考虑消耗时间,也考虑了工作完成效果,能够完善公安情报工作决策机制,有利于公安机关情报研判预警、整体合成作战平台建设,为健全完善“情报、指挥、勤务、舆情”一体化实战化运行机制助力。