基于圖論的指標體系優(yōu)化方法研究

郭皇皇，趙忠文，于 堯，李張元

(裝備學(xué)院 復(fù)雜電子系統(tǒng)仿真實驗室， 北京 101416)

【基礎(chǔ)理論與應(yīng)用研究】

基于圖論的指標體系優(yōu)化方法研究

郭皇皇，趙忠文，于 堯，李張元

(裝備學(xué)院 復(fù)雜電子系統(tǒng)仿真實驗室， 北京 101416)

針對指標體系中指標間存在相互作用，采用層次分析法難以對其進行評估，提出了基于圖論的指標體系優(yōu)化方法，設(shè)計了基于最短路徑的簡化指標相互作用算法和基于可達矩陣的指標層次化算法；將復(fù)雜的指標體系簡化為層次結(jié)構(gòu)，有效地對指標體系優(yōu)化。

指標體系；最短路徑；層次結(jié)構(gòu)；圖論

采用層次分析法[1]解決評估問題，主要是構(gòu)建層次結(jié)構(gòu)的指標體系。當影響元素不多的時候，建立層次結(jié)構(gòu)的指標體系比較簡單。但當影響元素很多且相互關(guān)系復(fù)雜時，建立具有層次結(jié)構(gòu)的指標體系有一定的難度，也難以保證指標體系的合理性。

針對這一問題，王蓮芬[2]引入了圖論的相關(guān)理論，并設(shè)計了一個內(nèi)部無循環(huán)結(jié)構(gòu)的有向圖轉(zhuǎn)為層次結(jié)構(gòu)的算法。針對指標間存在相互作用，Satty提出了ANP，但ANP理論復(fù)雜，計算量大[3-6]。

針對指標體系內(nèi)指標間存在相互作用，即指標間影響關(guān)系存在循環(huán)作用，本文引入了圖論的相關(guān)理論，設(shè)計了一套算法，較為合理地去除了指標間的循環(huán)作用，將指標整理成層次結(jié)構(gòu)，目前已經(jīng)取得了一定的效果。

1 基于圖論的指標體系優(yōu)化方法

本文將指標作為加權(quán)有向圖[7]中的點，將指標之間的影響關(guān)系作為加權(quán)有向圖中的邊，建立基于圖論的指標體系有向圖模型。

定義1.1：用有向圖G=(V，E)表示指標體系T的影響關(guān)系，其中V=(v1,v2,…,vn)為影響元素的集合，E=(e1,e2,…,en)為從屬關(guān)系的集合，其中，式子eij=(vi,vj)表示vj從屬于vi，vi，vj∈V,eij∈E,i，j=1,2,…,n。

定義1.2：設(shè)有向圖G=(V,E)表示指標體系T的影響關(guān)系，對于任意er∈E，采用0～9打分法進行賦權(quán)，權(quán)值越高，表示從屬關(guān)系越大。則稱加權(quán)有向圖G是指標體系T的加權(quán)影響關(guān)系。

定義1.5：設(shè)加權(quán)有向圖G是指標體系T的加權(quán)影響關(guān)系，G=(V,E)的可達矩陣為P=(pij)，vi的后項集為：R(vi)={vj|pij>0,vj∈V}，vi的前項集為：A(vi)={vj|pji>0,vj∈V}。

定理1：指標體系T轉(zhuǎn)化為加權(quán)有向圖G=(V,E)，滿足如下兩個條件時，該轉(zhuǎn)化為合理的。

條件1：若vi∈V是指標體系T的目標，則vi的后項集R(vi)=V{vi}；

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

證明：條件1說明指標體系T只存在一個目標，若不滿足條件1，說明指標體系T存在多個目標。條件2說明影響元素之間不應(yīng)該存在循環(huán)作用關(guān)系，否則不能合理地轉(zhuǎn)化為加權(quán)的單向圖。

在實際情況中，影響元素之間往往存在相互作用關(guān)系，指標體系T想要合理地轉(zhuǎn)變?yōu)榧訖?quán)單向圖G，必須減少影響元素之間的相互作用。因此，設(shè)計如下算法1，以解決影響元素之間的相互作用。

本文以v1作為指標體系T的目標。

算法1：

1) 根據(jù)加權(quán)單向圖G=(V,E)，得到鄰接矩陣[8]A=(aij)；

2) 驗證鄰接矩陣A中的?ai1是否為0，i=1,2,…,n，若是，則轉(zhuǎn)到第3步；否則令ai1=0為0，再轉(zhuǎn)到第三步；

流程如圖1。

該算法的基本思想：利用Dijkstara算法，尋找加權(quán)有向圖中的圈(環(huán))，刪除圈中權(quán)值最小的邊，直到加權(quán)有向圖G=(V,E)中不包含有向圈(有向環(huán))。

合理性解釋：該算法利用Dijkstara算法逐步找到加權(quán)有向圖中的有向圈(環(huán))，采用貪婪的思路，從每一個圈中刪除權(quán)重最小的邊，由于貪婪的思路無后向性，這樣保證了局部最優(yōu)解的存在。將每一個局部最優(yōu)解合起來，形成一個整體上的最優(yōu)解，最終形成一個指標間無循環(huán)關(guān)系的指標體系。

在算法1的作用下，指標體系T合理地轉(zhuǎn)化為加權(quán)有向圖G=(V,E)。為了將指標體系T轉(zhuǎn)化為合理的層間關(guān)系，設(shè)計如下的算法2。

算法2：

設(shè)加權(quán)有向圖G=(V,E)是指標體系T的一個合理的加權(quán)影響關(guān)系，矩陣A是加權(quán)有向圖G=(V,E)的鄰接矩陣，P=(pij)是加權(quán)有向圖G=(V,E)的可達矩陣。

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

2) 找出P(k)中整列為0的列，并設(shè)其標號為：k1,k2,…，km,記Qk={vk1,vk2,…,vkm},Qk的含義表示為：前項集為空集的點的集合。各個點的后項集為：R(vki),i=1,2,…,n；

3) 劃去P(k)中的第k1,k2,…,km列，以及k1,k2,…,km列對應(yīng)的行，在保持原有行列標號的情況下，形成新的矩陣P(k+1)；

4) 對矩陣P(k+1)進行判斷，若矩陣P(k+1)為0矩陣或收縮為0，則結(jié)束；反之，令k=k+1，轉(zhuǎn)到2)。

流程如圖2。

圖2 算法2流程

通過算法2，可以清楚地梳理指標體系中影響元素之間的層間關(guān)系，從而建立合理的層次結(jié)構(gòu)。

2 應(yīng)用實例

設(shè)指標體系T的一個加權(quán)影響關(guān)系G=(V,E)如圖3所示[10-11]：

圖3 供應(yīng)商評價指標體系

通過對指標體系T進行檢驗，只有滿足定理1才能轉(zhuǎn)化為合理的加權(quán)影響關(guān)系G=(V,E)。由定義1.4得到G=(V,E)的可達矩陣P：

可以發(fā)現(xiàn)可達矩陣P滿足定理1中的條件1，但不滿足條件2。通過算法1進行處理，得到新的加權(quán)影響關(guān)系G′(V,E)=G(V,E{v16v7})，通過檢驗G′(V,E)是指標體系T的一個合理的加權(quán)影響關(guān)系。計算得到G′(V,E)的可達矩陣P′：

由算法2對G′(V,E)進行整理，得到具有層次結(jié)構(gòu)的指標體系T，如圖4所示。

圖4 供應(yīng)商評價指標體系層次結(jié)構(gòu)

由圖4得到的指標體系，通過可達矩陣P′可得到各個指標的判斷矩陣，如下：

上述判斷矩陣都通過了一致性檢驗，進而可以得到各個指標的權(quán)重。

3 結(jié)論

本文提出了基于圖論的指標體系優(yōu)化方法，把一個指標間影響關(guān)系存在循環(huán)作用的指標體系，采用加權(quán)有向圖表示。通過算法1，將指標體系轉(zhuǎn)化為合理的加權(quán)有向圖，采用最短路徑的思想破除指標間影響關(guān)系的循環(huán)作用。通過算法2，將合理的加權(quán)有向圖轉(zhuǎn)化為層次結(jié)構(gòu)，進而得到具有層次結(jié)構(gòu)的指標體系。通過對供應(yīng)商評價問題進行驗證，得到層次結(jié)構(gòu)的指標體系，驗證了算法的可行性。為處理指標體系指標間影響關(guān)系存在循環(huán)作用提供了一種新的方法。由于算法1采用貪婪的思路，得到整體的最優(yōu)解，而不是從全局出發(fā)得到的全局最優(yōu)解。下一步將對算法進行改進以設(shè)計出更好的算法。

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

[2] 王蓮芬,許樹柏.層次分析法引論[M].北京：中國人民大學(xué)出版社,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] 張瑋,張衛(wèi)東.基于網(wǎng)絡(luò)層次分析法 (ANP) 的 PPP 項目風(fēng)險評價研究[J].項目管理技術(shù),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 的有向加權(quán)復(fù)雜網(wǎng)絡(luò)節(jié)點重要性評估方法[J].南京航空航天大學(xué)學(xué)報,2013,45(3):429-434.

[8] 岳秋菊,朱正平,達文姣,等.基于圖的鄰接矩陣求其距離矩陣的算法與實現(xiàn)[J].自動化與儀器儀表,2013 (1):139-140.

[9] 王智廣,王興會,李妍.一種基于 Dijkstra 最短路徑算法的改進算法[J].內(nèi)蒙古師范大學(xué)學(xué)報(自然科學(xué)版),2012,41(2):195-200.

[10]董聰聰.基于AHP和模糊綜合評判法的學(xué)校消防安全評估[J].重慶工商大學(xué)學(xué)報(自然科學(xué)版)，2016,33(2):74-75.

[11]白朝陽,張冠男,沈靈麗.基于網(wǎng)絡(luò)層次分析法 (ANP) 的機床行業(yè)重點商業(yè)型供應(yīng)商評價方法研究[J].制造業(yè)自動化,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—)，男，碩士研究生，主要從事信息系統(tǒng)技術(shù)與應(yīng)用研究。

趙忠文(1974—)，男，碩士，副研究員，主要從事信息系統(tǒng)技術(shù)與應(yīng)用研究。

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

本文引用格式：郭皇皇，趙忠文，于堯，等.基于圖論的指標體系優(yōu)化方法研究[J].兵器裝備工程學(xué)報，2017(8):183-187.