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 aij matrice A predstavlja relativnu važnost kriterija i u odnosu na kriterij j. Ako je aij>1, kriterij i je važniji od kriterija j, dok za aij<1 vrijedi obrnuto. Ako su dva kriterija jednake važnosti, onda je aij=1. Zbog konzistentnosti vrijedi aij=1/aji, za svaki i,j. Samim time vrijedi aii=1 za svaki i. Dodatno, zbog tranzitivnosti bi trebalo vrijediti αij=αik⋅α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∈N te Dm,n={1,2,…,m}×{1,2,…,n} Kartezijev produkt. Svako preslikavanje A:Dm,n→F nazivamo matrica tipa m×n nad poljem F.
Elemente matrice A koja ima m redaka i n stupaca, tj. elemente matrice tipa m×n, označavamo s α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=(αij) tablično zapisujemo u obliku:
(1)
A=(α11α12…α1n α21α22…α2n ⋮⋮⋱⋮ αm1αm2…αmn)
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 (α11,α22,…,αnn) elemenata α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×n, a B matrica tipa p×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=(αij) tipa m×n i B=(βij) tipa n×q dvije ulančane matrice nad poljem F. Umnožak matrica A i B definiramo kao matricu C=(γij) nad poljem F, gdje je
γij=n∑k=1αik⋅βkj
za sve i∈1,…,m i sve j∈1,…,q. Matrica C=AB je tipa m×q. Ako matrice A i B nisu ulančane njihov umnožak nije definiran.
Definicija 3. Za kvadratnu matricu A=(αij) reda n nad poljem F determinanta matrice A označava se s det(A) i definira se s
det(A)=∑p∈Sn(−1)I(p)α1p(1)α2p(2)…αnp(n),
gdje se sumira po svim permutacijama p skupa {1,…,n} 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=(αij) tipa m×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≤min{m,n} 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=(αij) kvadratna matrica reda n nad poljem F. Vektor v≠0 nazivamo svojstveni vektor matrice A ako postoji skalar λ∈F takav da vrijedi
Av=λv.
Skalar λ nazivamo svojstvena vrijednost matrice A koja pripada svojstvenom vektoru v. Jednadžba Av=λv se svodi na rješavanje jednadžbe (A−λI)v=0 što je zapravo matrična forma jednog homogenog sustava jednadžbi s n nepoznanica (v1,…,vn). 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 v1=v2=⋯vn=0, a može imati netrivijalna rješenja, tj. rješenja za koja je barem jedan vi≠0,i=1,…,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)<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∈1,…,n vrijedi
(i) |
αij>0 |
(ii) |
αii=1 |
(iii) |
αij=1αji, i≠j. |
Pozitivna recipročna matrica
A reda
n je konzistentna, u Saaty-jevom smislu, ako vrijedi
αij=αik⋅αkj
za sve
i,j,k∈1,…,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) |
λmax=n |
(3) |
Ako svojstvenoj vrijednosti λ=n pripada svojstveni vektor v=(v1,v2,…,vn), onda je aij=vivj. |
Proof.
(1) |
Promotrimo konzistentnu pozitivnu recipročnu matricu A=(αij):
A=(1α12…α1n 1α121…α2n ⋮⋮⋱⋮ 1α1n1α2n…1)
Elementarnim transformacijama (R2) i (R3) nad matricama, tj. množenjem prvog retka s −1α1k=−αk1 i dodavanjem k−tom retku (zbog α1k=1αk1 i αkj=αk1⋅α1j) za sve k∈{2,…,n} dobijemo matricu:
(1α12…α1n 00…0 ⋮⋮⋱⋮ 00…0)
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={k∈N:A je reda k iλmax=k}.
Baza indukcije:
1∈M: det(A−λI)=0 ⇒ 1−λ=0 ⇒ λ=1
Dakle, λmax=1 ⇒ 1∈M.
Pretpostavka indukcije:
n−1∈M
Korak indukcije:
n∈M: det(A−λI)=0 ⇒
|1−λα12α13…α1n−1α1n 1α121−λα23…α2n−1α2n ⋮⋮⋮⋱⋮⋮ 1α1n1α2n1α3n…1αn−1n1−λ |=0.
Pošto je det(A−λ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 −α21=−1α12 i dodamo drugom retku, pomnožimo prvi redak elementom −α31=−1α13 i dodamo trećem retku, ..., pomnožimo prvi redak elementom −αn−1,1=−1α1,n−1 i dodamo (n−1)−om retku. Zbog α1k=1αk1 i αkj=αk1⋅α1j za sve k∈{2,…,n−1} dobivamo matricu:
(1−λα12α13…α1n−1α1n λα12−λ0…00 ⋮⋮⋮⋱⋮⋮ λα1n−100…−λ0 1α1n1α2n1α3n…1αn−1n1−λ)
Sada zadnji redak matrice množimo s −α1n1−λ i dodajemo prvom retku kako bismo poništili element α1n. Ostali elementi prvog retka kada im se doda zadnji redak, prema definiciji (7), izgledaju ovako: α1k−α1n(1−λ)αkn=α1k−α1n⋅αnk1−λ=α1k−α1k1−λ=−α1k⋅λ1−λ za sve k∈{2,…,n−1} te imamo matricu sljedećeg oblika:
(1−λ−11−λ−α12⋅λ1−λ−α13⋅λ1−λ…−α1n−1⋅λ1−λ0 λα12−λ0…00 ⋮⋮⋮⋱⋮⋮ λα1n−100…−λ0 1α1n1α2n1α3n…1αn−1n1−λ)
Preostaje nam još poništiti 2.,…,(n−1)-vi element prvog retka. Zbog toga k−ti redak množimo s −α1k1−λ i dodajemo prvom retku za sve k∈n−1,…,2. Uočimo da su u k−tom retku matrice svi elementi osim prvog (λα1k) i elementa na glavnoj dijagonali (−λ) jednaki 0. Množenjem k−tog retka s −α1k1−λ prvi element u retku transformiramo u −λ1−λ te ga n−2 puta dodajemo prvom elementu prvog retka. Dobivamo matricu:
(2)
B=(1−λ−11−λ−(n−2)⋅λ1−λ00…00 λα12−λ0…00 ⋮⋮⋮⋱⋮⋮ λα1n−100…−λ0 1α1n1α2n1α3n…1αn−1n1−λ)
Njezina determinanta je, prema svojstvu (D2), jednaka umnošku elemenata glavne dijagonale, tj.
(1−λ−11−λ−(n−2)⋅λ1−λ)⋅(−λ)n−2⋅(1−λ)=0.
Sređivanjem ovog izraza dobije se (−1)n−2(λ−n)λn−1=0. Odavde slijedi λ1,…,λn−1=0; λn=n.
Dakle, λmax=n ⇒ n∈M.
Na temelju provedenih koraka matematičke indukcije zaključujemo da je M=N, tj. da tvrdnja propozicije vrijedi za svaki prirodni broj n. |
(3) |
Neka svojstveni vektor v=(v1,v2,…,vn) pripada svojstvenoj vrijednosti λ=n. Elementarnim transformacijama nad sustavom (A−λI)v=0, analognima provednim u koraku indukcije dokaza druge tvrdnje ove propozicije, jednadžba (A−λI)v=0 poprima oblik Bv=0. Uvrštavanjem λ=n u matricu B imamo matrični zapis sustava:
(000…00 nα12−n0…00 ⋮⋮⋮⋱⋮⋮ nα1n−100…−n0 1α1n1α2n1α3n…1αn−1n1−n)⋅(v1 v2 ⋮ vn−1 vn)=0,
odnosno sustav oblika:
nα12v1−nv2=0 ⇒ α12=v1v2 nα13v1−nv3=0 ⇒ α13=v1v3 ⋮ nα1n−1v1−nvn−1=0 ⇒ α1n−1=v1vn−1 1α1nv1+1α2nv2+⋯+1αn−1nvn−1+(1−n)vn=0
Uvrštavanjem αkn=αk1⋅α1n=α1nα1k=α1nvkv1 za sve k=1,…,n−1 u zadnju jednadžbu i sređivanjem imamo:
(n−1)v1α1n+(1−n)vn=0 ⇒ α1n=v1vn.
Zbog konzistencije i prethodnog rezultata vrijedi:
aij=ai1a1j=a1ja1i=v1vjv1vi=vivj
čime je dokazana tvrdnja. |
◼
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=λmax−nn−1,
gdje je λ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. |