郭皇皇，趙忠文，于 堯，李張?jiān)?/p>

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

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

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

郭皇皇，趙忠文，于 堯，李張?jiān)?/p>

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

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

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

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

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

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

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

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

定義1.1：用有向圖G=(V，E)表示指標(biāo)體系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)表示指標(biāo)體系T的影響關(guān)系，對于任意er∈E，采用0～9打分法進(jìn)行賦權(quán)，權(quán)值越高，表示從屬關(guān)系越大。則稱加權(quán)有向圖G是指標(biāo)體系T的加權(quán)影響關(guān)系。

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

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

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

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

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

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

本文以v1作為指標(biāo)體系T的目標(biāo)。

算法1：

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

2) 驗(yàn)證鄰接矩陣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))，采用貪婪的思路，從每一個(gè)圈中刪除權(quán)重最小的邊，由于貪婪的思路無后向性，這樣保證了局部最優(yōu)解的存在。將每一個(gè)局部最優(yōu)解合起來，形成一個(gè)整體上的最優(yōu)解，最終形成一個(gè)指標(biāo)間無循環(huán)關(guān)系的指標(biāo)體系。

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

算法2：

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

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

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

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

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

流程如圖2。

圖2 算法2流程

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

2 應(yīng)用實(shí)例

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

圖3 供應(yīng)商評價(jià)指標(biāo)體系

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

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

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

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

由圖4得到的指標(biāo)體系，通過可達(dá)矩陣P′可得到各個(gè)指標(biāo)的判斷矩陣，如下：

上述判斷矩陣都通過了一致性檢驗(yàn)，進(jìn)而可以得到各個(gè)指標(biāo)的權(quán)重。

3 結(jié)論

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

[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 項(xiàng)目風(fēng)險(xiǎn)評價(jià)研究[J].項(xiàng)目管理技術(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é)點(diǎn)重要性評估方法[J].南京航空航天大學(xué)學(xué)報(bào),2013,45(3):429-434.

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

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

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

[11]白朝陽,張冠男,沈靈麗.基于網(wǎng)絡(luò)層次分析法 (ANP) 的機(jī)床行業(yè)重點(diǎn)商業(yè)型供應(yīng)商評價(jià)方法研究[J].制造業(yè)自動化,2014,36(2):146-151.

(責(zé)任編輯 楊繼森)

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

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