svojstvena vrijednost

Matematičke osnove AHP metode odlučivanja

 
Benković, Martina
martina_benkovic@hotmail.com
Keček, Damira
Sveučilište Sjever
damira.kecek@unin.hr
Munđar, Dušan
Sveučilište u Zagrebu
Fakultet organizacije i informatike
dusan.mundjar@foi.hr

Sažetak


U analitičkom pristupu donošenju odluka jedna od najkorištenijih metoda za rješavanje problema višekriterijskog odlučivanja je metoda Analitički hijerarhijski proces (eng. Analytical Hierarchy Process, AHP). U ovom radu navedene su osnove matričnog računa s ključnim pojmovima i rezultatima linearne algebre potrebnima za razumijevanje matematičke osnove AHP metode.

1Uvod

U procesu odlučivanja donositelj odluke suočen je s problemom izbora najbolje alternative, što znači da mora izabrati jednu između dvije ili više dostupnih alternativa, uzimajući u obzir sve relevantne kriterije kako bi se postigao unaprijed zadani cilj. U području višekriterijskog odlučivanja za donošenje odluka koriste se razne metode, kao što su familija metoda ELECTRE (fr. ELimination Et Choix Traduisant la REalité), metoda PROMETHEE (eng. Preference Ranking Organization METHod for Enrichment of Evaluations), metoda TOPSIS (eng. Technique for Order of Preference by Similarity to Ideal Solution), a jedna od najviše primijenjenih metoda višekriterijskog odlučivanja je metoda AHP - Analitički hijerarhijski proces (eng. Analytical Hierarchy Process). Utemeljitelj AHP metode je Thomas L. Saaty. Više o navedenim metodama čitatelj može pronaći u [2].

U AHP metodi višekriterijski problem odlučivanja je hijerarhijski strukturiran. Problem odlučivanja dekomponira se na potprobleme koji se nezavisno analiziraju. Na određenoj razini hijerarhije svaki se element (kriterij ili alternativa) uspoređuje sa svakim elementom te iste razine. [4] Rezultati usporedbe po parovima prikazuju se kvadratnom matricom usporedbi, matricom A reda m, gdje je m broj promatranih kriterija ili alternativa. Element a_{ij} matrice A predstavlja relativnu važnost kriterija i u odnosu na kriterij j. Ako je a_{ij}\gt 1, kriterij i je važniji od kriterija j, dok za a_{ij}\lt 1 vrijedi obrnuto. Ako su dva kriterija jednake važnosti, onda je a_{ij}=1. Zbog konzistentnosti vrijedi a_{ij}=1/a_{ji}, za svaki i,j. Samim time vrijedi a_{ii}=1 za svaki i. Dodatno, zbog tranzitivnosti bi trebalo vrijediti \alpha_{ij}=\alpha_{ik}\cdot\alpha_{kj}, za svaki i,j,k. Preferencije donositelja odluke (relativna važnost) izražavaju se Saatyevom skalom relativne važnosti brojevima od 1 do 9, kao što je prikazano u Tablici 1. Više o vrijednostima Saatyeve skale relativne važnosti čitatelj može vidjeti u [6].

 



Intenzitet važnosti Interpretacija
1 kriteriji i i j su jednake važnosti
3 kriterij i je blago važniji od kriterija j
5 kriterij i je važniji od kriterija j
7 kriterij i is strogo važniji od kriterija j
9 kriterij i is apsolutno strogo važniji od kriterija j
2,4,6,8 međuvrijednosti
Tablica 1: Interpretacija relativne važnosti dva kriterija

 

Iz procjene relativnih važnosti elemenata odgovarajuće razine hijerarhije računaju se lokalne težine kriterija i alternativa na temelju kojih se odabire optimalna alternativa. Navedeni izračuni bazirani su na metodi svojstvenog vektora [3].

U nastavku rada dane su neke osnove matričnog računa te se dokazuju neka svojstva matrica sa prije spomenutim svojstvima.

2Neke osnove matričnog računa

Temeljni matematički alat koji se koristi u AHP metodi su matrice, stoga navodimo osnovne definicije i rezultate vezane uz matrice polazeći od željenih svojstava matrica.

Definicija 1. Neka je F polje, m,n\in\mathbb{N} te D_{m,n}=\lbrace 1,2,\ldots,m\rbrace \times\lbrace 1,2,\ldots,n\rbrace Kartezijev produkt. Svako preslikavanje A:D_{m,n}\to F nazivamo matrica tipa m\times n nad poljem F.


Elemente matrice A koja ima m redaka i n stupaca, tj. elemente matrice tipa m\times n, označavamo s \alpha_{ij} (element polja F pridružen paru (i,j) koji se u tabličnom zapisu nalazi na presjeku i-tog retka i j-tog stupca), a matricu A=(\alpha_{ij}) tablično zapisujemo u obliku:

(1)
A=\left(\begin{matrix} \alpha_{11} &\alpha_{12} &\ldots &\alpha_{1n}\\\ \alpha_{21} &\alpha_{22} &\ldots &\alpha_{2n}\\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\\ \alpha_{m1} &\alpha_{m2} &\ldots &\alpha_{mn} \end{matrix}\right)

Matrica koja ima jednak broj redaka i stupaca naziva se kvadratna matrica reda n. Za kvadratnu matricu možemo definirati glavnu dijagonalu kao n-torku (\alpha_{11},\alpha_{22},\ldots,\alpha_{nn}) elemenata \alpha_{ij} matrice A za čije indekse vrijedi i=j. Jedinična matrica reda n, u oznaci I, je kvadratna matrica kojoj su elementi na glavnoj dijagonali 1, a ostali elementi matrice su 0. Matrica koja ima samo jedan stupac naziva se vektor stupac, koju u nastavku rada zovemo vektor. Uređeni par matrica (A,B), gdje je A matrica tipa m\times n, a B matrica tipa p\times q je ulančan ako druga matrica, matrica B, ima toliko redaka koliko prva matrica, matrica A, ima stupaca, odnosno ako je n=p.

Definicija 2. Neka su A=(\alpha_{ij}) tipa m\times n i B=(\beta_{ij}) tipa n\times q dvije ulančane matrice nad poljem F. Umnožak matrica A i B definiramo kao matricu C=(\gamma_{ij}) nad poljem F, gdje je
\gamma_{ij}=\sum_{k=1}^{n}\alpha_{ik}\cdot\beta_{kj}
za sve i\in{1,\ldots,m} i sve j\in{1,\ldots,q}. Matrica C=A\,B je tipa m\times q. Ako matrice A i B nisu ulančane njihov umnožak nije definiran.

Definicija 3. Za kvadratnu matricu A=(\alpha_{ij}) reda n nad poljem F determinanta matrice A označava se s \det(A) i definira se s
\det(A)=\sum_{p\in S_{n}}(-1)^{I(p)}\alpha_{1p(1)}\alpha_{2p(2)}\dots\alpha_{np(n)},
gdje se sumira po svim permutacijama p skupa \lbrace 1,\ldots,n\rbrace te gdje je I(p) broj inverzija permutacije.


U nastavku navodimo neka svojstva determinanti koja ćemo koristiti u izračunavanju istih:

(D1) Ako se neki redak ili stupac matrice sastoji samo od nula, determinanta te matrice jednaka je nuli.
(D2) Ako je A trokutasta matrica (elementi iznad ili ispod glavne dijagonale su jednaki nuli), tada joj je determinanta jednaka produktu elemenata njezine glavne dijagonale.

Više o svojstvima determinanti matrice vidjeti primjerice u [1].

Definicija 4. Kvadratna matrica čija je determinanta različita od nule naziva se regularna matrica. Singularna matrica je kvadratna matrica čija je determinanta jednaka nuli.


Ako u matrici A=(\alpha_{ij}) tipa m\times n proizvoljno uklonimo nekoliko njenih redaka i nekoliko stupaca dobivamo matricu koju nazivamo podmatrica matrice A. Kažemo da matrica A ima rang k, k \leq \text{min}\lbrace m,n\rbrace ako među kvadratnim podmatricama matrice A postoji barem jedna regularna podmatrica reda k, dok su sve kvadratne podmatrice reda većeg od k, ako postoje, singularne. Tada pišemo: r(A)=k, gdje je r(A) oznaka za rang matrice A.

Za određivanje ranga matrice koriste se elementarne transformacije nad matricom. Tri su tipa elementarnih transformacija: (R1) zamjena dvaju stupaca (redaka) matrice, (R2) množenje nekog stupca (retka) matrice skalarom različitim od nule i (R3) dodavanje nekog stupca (retka) matrice nekog drugom stupcu (retku) te matrice. [1]

Definicija 5. Neka je A=(\alpha_{ij}) kvadratna matrica reda n nad poljem F. Vektor v\neq 0 nazivamo svojstveni vektor matrice A ako postoji skalar \lambda\in F takav da vrijedi
Av=\lambda v.

Skalar \lambda nazivamo svojstvena vrijednost matrice A koja pripada svojstvenom vektoru v. Jednadžba Av=\lambda v se svodi na rješavanje jednadžbe (A-\lambda I)v=0 što je zapravo matrična forma jednog homogenog sustava jednadžbi s n nepoznanica (v_{1},\dots,v_{n}). Sustav jednadžbi može se riješiti Gauss-Jordanovom metodom eliminacije korištenjem elementarnih transformacija nad sustavom: (J1) zamjena poretka dviju jednadžbi u sustavu, (J2) množenje neke jednadžbe sustava skalarom različitim od nule, (J3) pribrajanje neke jednadžbe sustava nekoj drugoj jednadžbi sustava. Homogeni sustav uvijek ima trivijalno rješenje v_{1}=v_{2}=\cdots v_{n}=0, a može imati netrivijalna rješenja, tj. rješenja za koja je barem jedan v_{i}\neq 0,\,i=1,\dots,n.

Propozicija 6. Homogeni sustav ima
(1) samo trivijalno rješenje, ako i samo ako je r(A)=n;
(2) netrivijalna rješenja, ako i samo ako je r(A)\lt n.

3Svojstva pozitivnih recipročnih matrica

U AHP metodi pozitivne recipročne matrice se pojavljuju kao matrice usporedbi kriterija i alternativa u parovima. Stoga u nastavku navodimo definiciju pozitivnih recipročnih matrica te uvodimo pojam konzistentnosti za iste. [7]

Definicija 7. Kvadratna matrica A reda n zove se pozitivna recipročna matrica ako za sve i,j\in{1,\ldots,n} vrijedi
(i) {\alpha}_{ij}{\gt}{0}
(ii) {\alpha}_{ii}=1
(iii) {\alpha}_{ij}=\frac{1}{{\alpha}_{ji}},~i{\neq}j.
Pozitivna recipročna matrica A reda n je konzistentna, u Saaty-jevom smislu, ako vrijedi
\alpha_{ij}=\alpha_{ik}\cdot\alpha_{kj}
za sve i,j,k\in{1,\ldots,n}.


U nastavku dokazujemo neka svojstva konzistentnih pozitivnih recipročnih matrica.

Propozicija 8. Za konzistentnu pozitivnu recipročnu matricu A reda n vrijedi:
(1) r(A)=1
(2) \lambda_{max}=n
(3) Ako svojstvenoj vrijednosti \lambda=n pripada svojstveni vektor v=(v_{1},v_{2},\ldots,v_{n}), onda je a_{ij}=\frac{v_{i}}{v_{j}}.

Proof.\,
 

(1) Promotrimo konzistentnu pozitivnu recipročnu matricu A=(\alpha_{ij}):
A=\left(\begin{matrix} 1 &\alpha_{12} &\ldots &\alpha_{1n}\\\ \frac{1}{\alpha_{12}}&1&\ldots&\alpha_{2n}\\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\\ \frac{1}{\alpha_{1n}} &\frac{1}{\alpha_{2n}}&{\ldots}&1 \end{matrix}\right)
Elementarnim transformacijama (R2) i (R3) nad matricama, tj. množenjem prvog retka s -\frac{1}{\alpha_{1k}}=-\alpha_{k1} i dodavanjem k-tom retku (zbog \alpha_{1k}=\frac{1}{\alpha_{k1}} i \alpha_{kj}=\alpha_{k1}\cdot\alpha_{1j}) za sve k\in\lbrace 2,\ldots,n\rbrace dobijemo matricu:
\left(\begin{matrix} 1&\alpha_{12}&{\ldots}&\alpha_{1n}\\\ 0&0&{\ldots}&0\\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\\ 0&0&{\ldots}&0 \end{matrix}\right)
Kako su, prema svojstvu (D1), sve kvadratne podmatrice drugog reda pa do (n-1)-og reda matrice A singularne, zaključujemo da je r(A)=1.
(2) Drugu tvrdnju dokazat ćemo matematičkom indukcijom.
Neka je M=\lbrace k\in\mathbb{N}:A\text{ je reda k i}\lambda_{max}=k\rbrace.
Baza indukcije:
1\in M: \det(A-\lambda I)=0 \ \ \Rightarrow \ \ 1-\lambda=0\ \ \Rightarrow \ \ \lambda=1
Dakle, \lambda_{max}=1\ \ \Rightarrow\ \ 1\in M.
Pretpostavka indukcije:
n-1\in M
Korak indukcije:
n\in M: \det(A-\lambda I)=0 \ \ \Rightarrow
\left|\begin{matrix} 1-\lambda &\alpha_{12}&\alpha_{13}&\dots&\alpha_{1n-1} &\alpha_{1n}\\\ \frac{1}{\alpha_{12}} &1-\lambda&\alpha_{23}&\dots&\alpha_{2n-1} &\alpha_{2n}\\\ \vdots &\vdots&\vdots&\ddots&\vdots &\vdots\\\ \frac{1}{\alpha_{1n}}&\frac{1}{\alpha_{2n}}&\frac{1}{\alpha_{3n}}&\dots&\frac{1}{\alpha_{n-1n}} &1-\lambda\\\ \end{matrix}\right|=0.
Pošto je \det(A-\lambda I)=0 elementarne transformacije nad matricom ne mijenjaju determinantu matrice. Elementarnim transformacijama (R2) i (R3) dobivamo donje trokutastu matricu, tj. matricu u kojoj su elementi iznad glavne dijagonale jednaki 0. Pomnožimo prvi redak elementom -\alpha_{21}=-\frac{1}{\alpha_{12}} i dodamo drugom retku, pomnožimo prvi redak elementom -\alpha_{31}=-\frac{1}{\alpha_{13}} i dodamo trećem retku, ..., pomnožimo prvi redak elementom -\alpha_{n-1,1}=-\frac{1}{\alpha_{1,n-1}} i dodamo (n-1)-om retku. Zbog \alpha_{1k}=\frac{1}{\alpha_{k1}} i \alpha_{kj}=\alpha_{k1}\cdot\alpha_{1j} za sve k\in\lbrace 2,\ldots,n-1\rbrace dobivamo matricu:
\left(\begin{matrix} 1-\lambda &\alpha_{12}&\alpha_{13}&\dots&\alpha_{1n-1} &\alpha_{1n} \\\ \frac{\lambda}{\alpha_{12}} &-\lambda&0&\dots&0 &0\\\ \vdots &\vdots&\vdots&\ddots&\vdots &\vdots\\\ \frac{\lambda}{\alpha_{1n-1}}&0&0&\dots&-\lambda &0\\\ \frac{1}{\alpha_{1n}}&\frac{1}{\alpha_{2n}}&\frac{1}{\alpha_{3n}}&\dots&\frac{1}{\alpha_{n-1n}} &1-\lambda \end{matrix}\right)
Sada zadnji redak matrice množimo s -\frac{\alpha_{1n}}{1-\lambda} i dodajemo prvom retku kako bismo poništili element \alpha_{1n}. Ostali elementi prvog retka kada im se doda zadnji redak, prema definiciji (7), izgledaju ovako: \alpha_{1k}-\frac{\alpha_{1n}}{(1-\lambda)\alpha_{kn}}=\alpha_{1k}-\frac{\alpha_{1n}\cdot\alpha_{nk}}{1-\lambda}=\alpha_{1k}-\frac{\alpha_{1k}}{1-\lambda}=-\frac{\alpha_{1k}\cdot\lambda}{1-\lambda} za sve k\in\lbrace 2,\ldots,n-1\rbrace te imamo matricu sljedećeg oblika:
\left(\begin{matrix} 1-\lambda-\frac{1}{1-\lambda} &-\frac{\alpha_{12}\cdot\lambda}{1-\lambda}&-\frac{\alpha_{13}\cdot\lambda}{1-\lambda}&\dots&-\frac{\alpha_{1n-1}\cdot\lambda}{1-\lambda} &0 \\\ \frac{\lambda}{\alpha_{12}} &-\lambda&0&\dots&0 &0\\\ \vdots &\vdots&\vdots&\ddots&\vdots &\vdots\\\ \frac{\lambda}{\alpha_{1n-1}}&0&0&\dots&-\lambda &0\\\ \frac{1}{\alpha_{1n}}&\frac{1}{\alpha_{2n}}&\frac{1}{\alpha_{3n}}&\dots&\frac{1}{\alpha_{n-1n}} &1-\lambda \end{matrix}\right)

Preostaje nam još poništiti 2.,\ldots,(n-1)-vi element prvog retka. Zbog toga k-ti redak množimo s -\frac{\alpha_{1k}}{1-\lambda} i dodajemo prvom retku za sve k\in{n-1,\ldots,2}. Uočimo da su u k-tom retku matrice svi elementi osim prvog (\frac{\lambda}{\alpha_{1k}}) i elementa na glavnoj dijagonali (-\lambda) jednaki 0. Množenjem k-tog retka s -\frac{\alpha_{1k}}{1-\lambda} prvi element u retku transformiramo u -\frac{\lambda}{1-\lambda} te ga n-2 puta dodajemo prvom elementu prvog retka. Dobivamo matricu:
(2)
B=\left(\begin{matrix} 1-\lambda-\frac{1}{1-\lambda}-(n-2)\cdot\frac{\lambda}{1-\lambda} &0&0&\dots&0 &0 \\\ \frac{\lambda}{\alpha_{12}} &-\lambda&0&\dots&0 &0\\\ \vdots &\vdots&\vdots&\ddots&\vdots &\vdots\\\ \frac{\lambda}{\alpha_{1n-1}}&0&0&\dots&-\lambda &0\\\ \frac{1}{\alpha_{1n}}&\frac{1}{\alpha_{2n}}&\frac{1}{\alpha_{3n}}&\dots&\frac{1}{\alpha_{n-1n}} &1-\lambda \end{matrix}\right)

Njezina determinanta je, prema svojstvu (D2), jednaka umnošku elemenata glavne dijagonale, tj.
\left(1-\lambda-\frac{1}{1-\lambda}-(n-2)\cdot\frac{\lambda}{1-\lambda}\right)\cdot(-\lambda)^{n-2}\cdot(1-\lambda)=0.
Sređivanjem ovog izraza dobije se (-1)^{n-2}(\lambda-n)\lambda^{n-1}=0. Odavde slijedi \lambda_{1},\ldots,\lambda_{n-1}=0;\ \ \lambda_{n}=n.
Dakle, \lambda_{max}=n\ \ \Rightarrow\ \ n\in M.
Na temelju provedenih koraka matematičke indukcije zaključujemo da je M=\mathbb{N}, tj. da tvrdnja propozicije vrijedi za svaki prirodni broj n.
(3) Neka svojstveni vektor v=(v_{1},v_{2},\ldots,v_{n}) pripada svojstvenoj vrijednosti \lambda=n. Elementarnim transformacijama nad sustavom (A-\lambda I)v=0, analognima provednim u koraku indukcije dokaza druge tvrdnje ove propozicije, jednadžba (A-\lambda I)v=0 poprima oblik Bv=0. Uvrštavanjem \lambda=n u matricu B imamo matrični zapis sustava:
\left(\begin{matrix} 0 &0&0&\dots&0 &0 \\\ \frac{n}{\alpha_{12}} &-n&0&\dots&0 &0\\\ \vdots &\vdots&\vdots&\ddots&\vdots &\vdots\\\ \frac{n}{\alpha_{1n-1}}&0&0&\dots&-n &0\\\ \frac{1}{\alpha_{1n}}&\frac{1}{\alpha_{2n}}&\frac{1}{\alpha_{3n}}&\dots&\frac{1}{\alpha_{n-1n}} &1-n \end{matrix}\right)\cdot \left(\begin{matrix} v_{1}\\\ v_{2}\\\ \vdots\\\ v_{n-1}\\\ v_{n} \end{matrix}\right)=0,
odnosno sustav oblika:
\begin{matrix} \frac{n}{\alpha_{12}}v_{1}-nv_{2}=0\ \ \Rightarrow\ \ \alpha_{12}=\frac{v_{1}}{v_{2}}\\\ \frac{n}{\alpha_{13}}v_{1}-nv_{3}=0\ \ \Rightarrow\ \ \alpha_{13}=\frac{v_{1}}{v_{3}}\\\ \vdots\\\ \frac{n}{\alpha_{1n-1}}v_{1}-nv_{n-1}=0\ \ \Rightarrow\ \ \alpha_{1n-1}=\frac{v_{1}}{v_{n-1}}\\\ \frac{1}{\alpha_{1n}}v_{1}+\frac{1}{\alpha_{2n}}v_{2}+\dots+\frac{1}{\alpha_{n-1n}}v_{n-1}+(1-n)v_{n}=0 \end{matrix}
Uvrštavanjem \alpha_{kn}=\alpha_{k1}\cdot\alpha_{1n}=\frac{\alpha_{1n}}{\alpha_{1k}}=\alpha_{1n}\frac{v_{k}}{v_{1}} za sve k=1,\dots,n-1 u zadnju jednadžbu i sređivanjem imamo:
\frac{(n-1)v_{1}}{\alpha_{1n}}+(1-n)v_{n}=0\ \ \Rightarrow\ \ \alpha_{1n}=\frac{v_{1}}{v_{n}}.
Zbog konzistencije i prethodnog rezultata vrijedi:
a_{ij}=a_{i1}a_{1j}=\frac{a_{1j}}{a_{1i}}=\dfrac{\frac{v_{1}}{v_{j}}}{\frac{v_{1}}{v_{i}}}=\frac{v_{i}}{v_{j}}
čime je dokazana tvrdnja.
\ \blacksquare


Pozitivne recipročne matrice predstavljaju informacije o usporedbama kriterija i alternativa u kojima je donositelj odluke u potpunosti konzistentan. U ovom radu je pokazano da u slučaju potpune konzistencije takve matrice imaju jedinstvenu svojstvenu vrijednost koja je jednaka redu matrice. Svako odstupanje od konzistencije utječe na promjenu svojstvenih vrijednosti koja služi kao sugestija donositelju odluke da preispita svoje preferencije. AHP metodom definiran je indikator konzistencije C.I. (eng. consistency index) sa

C.I=\frac{\lambda_{\max}-n}{n-1},

gdje je \lambda_{\max} najveća svojstvena vrijednost matrice usporedbi, a n broj alternativa ili kriterija koji se uspoređuju. Više o provođenju AHP metode može se naći primjerice u knjizi [5].

Bibliografija
[1] K. Horvatić, Linearna algebra, II. dio, Prirodoslovno-matematički fakultet, Matematički odjel, Sveučilište u Zagrebu, Zagreb, 1999.
[2] T. Hunjak, Mathematical foundations of the methods for multicriterial decision making, Mathematical Communications, 2(1997), 161–169.
[3] T.L. Satty, Decision-making with the AHP: Why is the principal eigenvector necessary, European Journal of Operational Research, 145(2003), 85–91.
[4] T.L. Saaty, Decision making with the analytic hierarchy process, Int. J. Services Sciences, 1(2008), 83-98
[5] T.L. Satty, The Analytic Hierarchy Process, Planning, Piority Setting, Resource Allocation, RWS, Pittsburg, 1996.
[6] T.L. Satty, M.S. Ozdemir, Why the Magic Number Seven Plus or Minus Two, Mathematical and Computer Modelling, 38(2003), 233-244.
[7] S. Shiraishi, T. Obata, M. Daigo Properties of a positive reciprocal matrix and their application to AHP, Journal of the Operations Research, 41(1998), 161–169.