郭皇皇，赵忠文，于 尧，李张元

(装备学院 复杂电子系统仿真实验室， 北京 101416)

【基础理论与应用研究】

基于图论的指标体系优化方法研究

郭皇皇，赵忠文，于 尧，李张元

(装备学院 复杂电子系统仿真实验室， 北京 101416)

针对指标体系中指标间存在相互作用，采用层次分析法难以对其进行评估，提出了基于图论的指标体系优化方法，设计了基于最短路径的简化指标相互作用算法和基于可达矩阵的指标层次化算法；将复杂的指标体系简化为层次结构，有效地对指标体系优化。

指标体系；最短路径；层次结构；图论

采用层次分析法[1]解决评估问题，主要是构建层次结构的指标体系。当影响元素不多的时候，建立层次结构的指标体系比较简单。但当影响元素很多且相互关系复杂时，建立具有层次结构的指标体系有一定的难度，也难以保证指标体系的合理性。

针对这一问题，王莲芬[2]引入了图论的相关理论，并设计了一个内部无循环结构的有向图转为层次结构的算法。针对指标间存在相互作用，Satty提出了ANP，但ANP理论复杂，计算量大[3-6]。

针对指标体系内指标间存在相互作用，即指标间影响关系存在循环作用，本文引入了图论的相关理论，设计了一套算法，较为合理地去除了指标间的循环作用，将指标整理成层次结构，目前已经取得了一定的效果。

1 基于图论的指标体系优化方法

本文将指标作为加权有向图[7]中的点，将指标之间的影响关系作为加权有向图中的边，建立基于图论的指标体系有向图模型。

定义1.1：用有向图G=(V，E)表示指标体系T的影响关系，其中V=(v1,v2,…,vn)为影响元素的集合，E=(e1,e2,…,en)为从属关系的集合，其中，式子eij=(vi,vj)表示vj从属于vi，vi，vj∈V,eij∈E,i，j=1,2,…,n。

定义1.2：设有向图G=(V,E)表示指标体系T的影响关系，对于任意er∈E，采用0～9打分法进行赋权，权值越高，表示从属关系越大。则称加权有向图G是指标体系T的加权影响关系。

定义1.5：设加权有向图G是指标体系T的加权影响关系，G=(V,E)的可达矩阵为P=(pij)，vi的后项集为：R(vi)={vj|pij>0,vj∈V}，vi的前项集为：A(vi)={vj|pji>0,vj∈V}。

定理1：指标体系T转化为加权有向图G=(V,E)，满足如下两个条件时，该转化为合理的。

条件1：若vi∈V是指标体系T的目标，则vi的后项集R(vi)=V{vi}；

条件2：若vi∈V，则有pii=0，若pij>0，则pji=0。

证明：条件1说明指标体系T只存在一个目标，若不满足条件1，说明指标体系T存在多个目标。条件2说明影响元素之间不应该存在循环作用关系，否则不能合理地转化为加权的单向图。

在实际情况中，影响元素之间往往存在相互作用关系，指标体系T想要合理地转变为加权单向图G，必须减少影响元素之间的相互作用。因此，设计如下算法1，以解决影响元素之间的相互作用。

本文以v1作为指标体系T的目标。

算法1：

1) 根据加权单向图G=(V,E)，得到邻接矩阵[8]A=(aij)；

2) 验证邻接矩阵A中的∀ai1是否为0，i=1,2,…,n，若是，则转到第3步；否则令ai1=0为0，再转到第三步；

流程如图1。

该算法的基本思想：利用Dijkstara算法，寻找加权有向图中的圈(环)，删除圈中权值最小的边，直到加权有向图G=(V,E)中不包含有向圈(有向环)。

合理性解释：该算法利用Dijkstara算法逐步找到加权有向图中的有向圈(环)，采用贪婪的思路，从每一个圈中删除权重最小的边，由于贪婪的思路无后向性，这样保证了局部最优解的存在。将每一个局部最优解合起来，形成一个整体上的最优解，最终形成一个指标间无循环关系的指标体系。

在算法1的作用下，指标体系T合理地转化为加权有向图G=(V,E)。为了将指标体系T转化为合理的层间关系，设计如下的算法2。

算法2：

设加权有向图G=(V,E)是指标体系T的一个合理的加权影响关系，矩阵A是加权有向图G=(V,E)的邻接矩阵，P=(pij)是加权有向图G=(V,E)的可达矩阵。

1) 令k=1,P(k)=P；

2) 找出P(k)中整列为0的列，并设其标号为：k1,k2,…，km,记Qk={vk1,vk2,…,vkm},Qk的含义表示为：前项集为空集的点的集合。各个点的后项集为：R(vki),i=1,2,…,n；

3) 划去P(k)中的第k1,k2,…,km列，以及k1,k2,…,km列对应的行，在保持原有行列标号的情况下，形成新的矩阵P(k+1)；

4) 对矩阵P(k+1)进行判断，若矩阵P(k+1)为0矩阵或收缩为0，则结束；反之，令k=k+1，转到2)。

流程如图2。

图2 算法2流程

通过算法2，可以清楚地梳理指标体系中影响元素之间的层间关系，从而建立合理的层次结构。

2 应用实例

设指标体系T的一个加权影响关系G=(V,E)如图3所示[10-11]：

图3 供应商评价指标体系

通过对指标体系T进行检验，只有满足定理1才能转化为合理的加权影响关系G=(V,E)。由定义1.4得到G=(V,E)的可达矩阵P：

可以发现可达矩阵P满足定理1中的条件1，但不满足条件2。通过算法1进行处理，得到新的加权影响关系G′(V,E)=G(V,E{v16v7})，通过检验G′(V,E)是指标体系T的一个合理的加权影响关系。计算得到G′(V,E)的可达矩阵P′：

由算法2对G′(V,E)进行整理，得到具有层次结构的指标体系T，如图4所示。

图4 供应商评价指标体系层次结构

由图4得到的指标体系，通过可达矩阵P′可得到各个指标的判断矩阵，如下：

上述判断矩阵都通过了一致性检验，进而可以得到各个指标的权重。

3 结论

本文提出了基于图论的指标体系优化方法，把一个指标间影响关系存在循环作用的指标体系，采用加权有向图表示。通过算法1，将指标体系转化为合理的加权有向图，采用最短路径的思想破除指标间影响关系的循环作用。通过算法2，将合理的加权有向图转化为层次结构，进而得到具有层次结构的指标体系。通过对供应商评价问题进行验证，得到层次结构的指标体系，验证了算法的可行性。为处理指标体系指标间影响关系存在循环作用提供了一种新的方法。由于算法1采用贪婪的思路，得到整体的最优解，而不是从全局出发得到的全局最优解。下一步将对算法进行改进以设计出更好的算法。

[1] SAATY T L,VARGAS L G.Models,methods,concepts & applications of the analytic hierarchy process[M].Springer Science & Business Media,2012.

[2] 王莲芬,许树柏.层次分析法引论[M].北京：中国人民大学出版社,1990.

[3] ERGU D,KOU G,SHI Y,et al.Analytic network process in risk assessment and decision analysis[J].Computers & Operations Research,2014,42(10):58-74.

[4] 张玮,张卫东.基于网络层次分析法 (ANP) 的 PPP 项目风险评价研究[J].项目管理技术,2012,10(10):84-88.

[5] ZHANG X,DENG Y,CHAN F T S,et al.Supplier selection based on evidence theory and analytic network process[J].Proceedings of the Institution of Mechanical Engineers,Part B:Journal of Engineering Manufacture,2016,230(3):562-573.

[6] VAN HORENBEEK A,PINTELON L.Development of a maintenance performance measurement framework—using the analytic network process (ANP) for maintenance performance indicator selection[J].Omega,2014,42(1):33-46.

[7] 张琨,李配配,朱保平,等.基于 PageRank 的有向加权复杂网络节点重要性评估方法[J].南京航空航天大学学报,2013,45(3):429-434.

[8] 岳秋菊,朱正平,达文姣,等.基于图的邻接矩阵求其距离矩阵的算法与实现[J].自动化与仪器仪表,2013 (1):139-140.

[9] 王智广,王兴会,李妍.一种基于 Dijkstra 最短路径算法的改进算法[J].内蒙古师范大学学报(自然科学版),2012,41(2):195-200.

[10]董聪聪.基于AHP和模糊综合评判法的学校消防安全评估[J].重庆工商大学学报(自然科学版)，2016,33(2):74-75.

[11]白朝阳,张冠男,沈灵丽.基于网络层次分析法 (ANP) 的机床行业重点商业型供应商评价方法研究[J].制造业自动化,2014,36(2):146-151.

(责任编辑 杨继森)

Research on Optimization Method of Index System Based on Graph Theory

GUO Huanghuang, ZHAO Zhongwen, YU Yao, LI Zhangyuan

(Science and Technology on Complex Electronic System Simulation Laboratory,Academy of Equipment, Beijing 101416, China)

It is difficult to assess the index system by using AHP in which there are some interactions. This paper aims to provide a method of optimizing the index system by employing graph theory. And then it designs two algorithms, which are the algorithm of simplifying the interactions by using shortest path and the algorithm of index hierarchy based on the reachable matrix. This method can simplify the complex index system into a hierarchical structure, and effectively optimize the index system.

index system; shortest path; hierarchy; graph theory

2017-03-25；

2017-05-10

郭皇皇(1993—)，男，硕士研究生，主要从事信息系统技术与应用研究。

赵忠文(1974—)，男，硕士，副研究员，主要从事信息系统技术与应用研究。

10.11809/scbgxb2017.08.039

format:GUO Huanghuang, ZHAO Zhongwen, YU Yao, et al.Research on Optimization Method of Index System Based on Graph Theory[J].Journal of Ordnance Equipment Engineering,2017(8):183-187.

E257

A

2096-2304(2017)08-0183-05

本文引用格式：郭皇皇，赵忠文，于尧，等.基于图论的指标体系优化方法研究[J].兵器装备工程学报，2017(8):183-187.