Matematika | Felsőoktatás » Nem teljesen kitöltött páros összehasonlítás mátrixok, A sajátvektor módszer kiterjesztése a nem teljesen kitöltött esetre

Nem teljesen kitöltött páros összehasonlítás mátrixok: A sajátvektor módszer kiterjesztése a nem teljesen kitöltött esetre 1 Nem teljesen kitöltött páros összehasonlítás mátrixok Számos oka lehet annak, hogy egy páros összehasonlítás mátrix néhány eleme hiányzik. Ha a döntéshozó idejét és figyelmét csak szűkre szabott korlátok között tudjuk igénybe venni, akkor könnyen előfordulhat, hogy nincs lehetőség az összes szempontpár vagy alternatívapár közötti arány lekérdezésére. A nem teljesen kitöltött páros összehasonlítás mátrix csak annyiban különbözik a (teljesen kitöltött) páros összehasonlítás mátrixtól, hogy néhány eleme hiányzik. A következő felírásban a hiányzó elemek helyére ∗-ot teszünk:   1 a12 ∗ . a1n  1/a12 1 a23 . ∗     1/a23 1 . a3n  (1) A= ∗ .  . . .  . . .  . .  . . 1/a1n ∗ 1/a3n . 1 A fenti objektum még nem egy matematikai

fogalom, hiszen minden lineáris algebrai definíció, művelet és állítás olyan mátrixokra van értelmezve, amelyeknek minden eleme adott. A problémát könnyen áthidalhatjuk, ha a főátló fölötti hiányzó elemeket az x1 , x2 , . , xd ∈ R+ változókkal helyettesítjük, a nekik megfelelő főátló alattiakat pedig a reciprokaikkal: 1/x1 , 1/x2 , . , 1/xd A mátrixban tehát összesen 2d hiányzó, illetve most már változóval jelölt elem van. Jelölje   1 a12 x1 . a1n  1/a12 1 a23 . xd     1 . a3n  A(x) = A(x1 , x2 , . , xd ) =  1/x1 1/a23 (2) ,  .  . . . . .   . . . 1/a1n 1/xd 1/a3n . 1 1 ahol x = (x1 , x2 , . , xd )T ∈ Rd+ A fentieknek megfelelően az (2) alakot nem teljesen kitöltött páros összehasonlítás mátrixnak hívjuk. Ez tekinthető egy mátrixosztálynak is, amelynek minden realizációja (az (x1 , x2 , . , xd ) változók mindegyikének valamilyen pozitív értéket adunk)

egy-egy páros összehasonlítás mátrixot eredményez A továbbiakban a páros összehasonlítás mátrix fogalmát a teljesen kitöltött páros összehasonlítás mátrixokra használjuk, míg a nem teljesen kitöltött páros összehasonlítás mátrix fogalmát a fentebb definiált nem teljesen kitöltött páros összehasonlítás mátrixra. A nyelvi logika ellenére a páros összehasonlítás mátrix fogalma nem bővebb, mint a nem teljesen kitöltött páros összehasonlítás mátrix fogalma (a „nem teljesen kitöltött” jelző tehát most nem szűkítést jelent.) A két halmaz közötti tartalmazás csak a fenti realizációs formában értelmezhető, ekkor viszont éppen a nem teljesen kitöltött mátrixok fogalma a bővebb. Mind döntéselméleti, mind alkalmazási szempontból az alábbi kérdések tűnnek fontosnak és izgalmasnak: • Hogyan számítsuk ki a súlyvektort; • Hogyan számítsuk ki az inkonzisztenciát Természetesen adódik még az a kérdés

is, hogy milyen értékek beírásával lehet valamilyen szempontból optimálisan kitölteni a mátrixot. Ezt a kérdést önmagában nem tartjuk elsődleges fontosságúnak, bár megjegyezzük, hogy a későbbiekben tárgyalt algoritmusok mintegy melléktermékeként ez is megoldódik és bizonyos információk kiolvashatók az eredményekből. 1.1 Gráf reprezentáció Amikor a döntéshozót arra kérjük, hogy hasonlítsa össze páronként n szempont fontosságát, akkor minden egyes összehasonlítás során egyfajta reláció, viszony megállapítása történik. Minden egyes reláció egy arányszám formájában jelenik meg, jelesül a két szempont fontosságának hányadosaként vagy legalábbis annak becsléseként. Két, még össze nem hasonlított szempont között tehát nincs semmilyen közvetlen reláció Közvetett persze lehet, ha a további szempontokkal való összehasonlításokat is figyelembe vesszük. A fentiek alapján természetesen adódik a gráfokkal

való kapcsolat. Legyen A egy n×n-es nem teljesen kitöltött páros összehasonlítás mátrix. Ehhez két gráfot definiálunk az alábbiak szerint: G := (V, E), ahol V = {1, 2, . , n}, minden csúcs egy-egy összehasonlítandó elemnek (például szempontnak) felel meg; E = {e(i, j) | aij (és aji ) adott és i 6= j}, az irányítatlan élek a mátrix ismert 2 elemeinek felelnek meg. Ahol hiányzó elem van a mátrixban, a neki megfelelő él sincs behúzva a gráfban. G egy irányítatlan gráf −−− −−− − − − G := (V, E ), ahol E = {e(i, j) | aij adott és i 6= j}∪{e(i, i) | i = 1, 2, . , n}, az irányított élek a mátrix ismert elemeinek felelnek meg. Ahol hiányzó − elem van a mátrixban, a neki megfelelő él sincs behúzva a gráfban. G egy irányított gráf, amelyet úgy is megkaphatunk, hogy a G gráf minden élét megduplázzuk és ellentétes irányítással látjuk el, ezen kívül minden csúcshoz behúzunk egy önmagába visszafutó

hurokélt. 1. példa: Legyen C egy 6 × 6-os nem teljesen kitöltött páros összehasonlítás mátrix:   1 a12 a13 ∗ ∗ a16 a21 1 a23 ∗ ∗ ∗   a31 a32 1 a34 a35 a36   . C=  ∗ ∗ a 1 ∗ ∗ 43   ∗ ∗ a53 ∗ 1 a56  a61 ∗ a63 ∗ a65 1 − Ekkor a C-hez tartozó G és G gráfokat az 1. és 2 ábra mutatja 3 1. ábra: a C-hez tartozó G irányítatlan gráf − 2. ábra: a C-hez tartozó G irányított gráf 1. megjegyzés: A (teljesen kitöltött) páros összehasonlítás mátrixhoz − tartozó G gráf az n csúcsú teljes gráf, míg a G gráf az előbbi G gráf odavissza irányított változata, kiegészítve a csúcsokra illeszkedő hurokélekkel. 4 2 A sajátvektor módszer kiterjesztése a nem teljesen kitöltött páros összehasonlítás mátrixokra Az AHP módszertanban láttuk, hogy a Saaty-féle CR inkonzisztencia mérőszám és a legnagyobb sajátérték között közvetlen kapcsolat van:

egymás pozitív lineáris transzformáltjai. Minél nagyobb a legnagyobb sajátérték értéke, annál magasabb a CR inkonzisztencia szintje. A fentiekből kiindulva egy nem teljesen kitöltött páros összehasonlítás mátrixhoz azokat a kitöltő elemeket fogjuk megkeresni, amelyekkel teljessé téve a mátrixot a legnagyobb sajátértéke minimális lesz. Formálisan: min λmax (A(x)). x>0 (3) Erről a feladatról fogjuk megmutatni, hogy bár általában nem konvex, de mindig átírható konvexszé, sőt egy természetes feltétel teljesülése esetén szigorúan konvexszé. Paraméterezzük a (2) formában megadott A(x) = A(x1 , x2 , . , xd ) nem teljesen kitöltött páros összehasonlítás mátrix hiányzó elemeit az alábbiak szerint: xi = eyi , (i = 1, 2, . , d) Az így keletkező mátrixot jelölje B: A(x) = B(y) = B(y1 , y2, . , yd ) (4) 1. definíció: Legyen C ⊆ Rk egy konvex halmaz és f : C R+ Egy f függvényt logkonvex nek nevezünk, ha a log f :

C R konvex függvény. Könnyen látható, hogy egy logkonvex függvény egyúttal konvex is. 1. állítás: A (4) formában megadott B(y) mátrix legnagyobb sajátértéke (mint y függvénye) logkonvex, így konvex is. A bizonyítást Kingman tételéből vezetjük le. 1. tétel (Kingman-tétel): Jelöljük aij (t)-vel (i, j = 1, 2, , n) az A ∈ Rn×n mátrix elemeit. Ha az aij (t) függvények logkonvex függvényei t-nek, akkor λmax (A(t)) is logkonvex, így konvex is. Az 1. állítás bizonyításához elég a logkonvexitást megmutatni az y tér egyenesei mentén. Egy tetszőleges, az y terében futó egyenes mentén a páros összehasonlítás mátrix így írható fel:   B(t) = ecij t+dij i,j=1,.,n , (5) 5 ahol t egy skalár változó, továbbá cij , dij ∈ R. Jegyezzük meg, hogy az (5) képlet pontosan akkor eredményez páros összehasonlítás mátrixot minden tre, ha cii = dii = 0; és cij = −cji , dij = −dji érvényes minden i, j-re. Igaz továbbá,

hogy ha aij értéke adott, akkor cij = 0, és dij = log aij . Az egyenes paraméterezéséből a Kingman-tétel ismeretében tehát adódik az 1. állítás 1. következmény: A konvex optimalizálás eszközei alkalmazhatók a (3) sajátértéke minimalizálási feladatra. 2. állítás: λmax (B(y)) egy tetszőleges, az y terében futó egyenes mentén vagy szigorúan konvex, vagy konstans. A 2. állítás bizonyítása: Tekintsük az egyenes (5) paraméterezését és legyen g(t) = λmax (B(t)), t ∈ R. A g függvény logkonvex. Azt fogjuk megmutatni, hogy vagy szigorúan konvex, vagy konstans Tegyük fel, hogy g nem szigorúan konvex. Ekkor létezik t1 , t2 ∈ R, t1 < t2 és 0 < κ0 < 1, amelyre g(κ0 t1 + (1 − κ0 )t2 ) = κ0 g(t1 ) + (1 − κ0 )g(t2 ). (6) Mivel a logaritmus függvény szigorúan konkáv, a (6) alapján kapjuk, hogy log g(κ0 t1 + (1 − κ0 )t2 ) = log(κ0 g(t1 ) + (1 − κ0 )g(t2 )) ≥ ≥ κ0 log g(t1 ) + (1 − κ0 ) log g(t2 ), (7)

sőt, a (7) egyenlőtlenség pontosan akkor teljesül egyenlőséggel, ha g(t1 ) = g(t2 ). Másrészt, a g logkonvexitásából következően log g(κ0 t1 + (1 − κ0 )t2 ) ≤ κ0 log g(t1 ) + (1 − κ0 ) log g(t2 ), (8) (7)-ből és (8)-ből következően g(t1) = g(t2 ), és ha figyelembe vesszük (6)-t is, akkor: g(κ0 t1 + (1 − κ0 )t2 ) = g(t1) = g(t2). Mivel g konvex, g(t) értéke konstans a [t1 , t2 ] intervallumon. Legyen Λ = g(t1 ). Ekkor Λ a g minimumértéke az egész R valós egyenesen. Legyen S = {t ∈ R|g(t) = Λ}. 6 (9) Nyilván [t1 , t2 ] ⊆ S, S konvex és zárt részhalmaza R-nek. Sőt, mivel t1 < t2 , ezért S belseje nem üres. Ha S = R, akkor kész vagyunk. Ha nem, akkor vagy max{t|t ∈ S} < ∞, vagy min{t|t ∈ S} > −∞. A két eset analóg egymással, ezért csak az elsőt tárgyaljuk. t = max{t|t ∈ S} < ∞. Mivel Λ = g(t) = λmax (B(t)), ∀t ∈ S, ezért det(B(t) − ΛI) = 0, ∀t ∈ S. (10) A (5) paraméterezésből

adódóan det(B(t) − ΛI) = α0 + L X αl eβl t , (11) l=1 ahol L és αl , βl értékei a determináns kifejtéséből adódnak és csak B(t)-től, illetve Λ-tól függenek. Legyen p(t) = α0 + L X αl eβl t . l=1 p(t) egy analitikus függvény, amely a [t1 , t2 ] intervallumon végig nullát vesz fel. Az analitikus függvényekre vonatkozó értékunicitási tétel szerint ekkor p(t) = det(B(t) − ΛI) = 0 minden t ∈ R − re. Ez azt jelenti, hogy Λ sajátértéke B(t)-nek minden t ∈ R-re. Mivel azonban egy pozitív elemű mátrix Perron sajátértékének multiplicitása 1, másrészt a sajátértékek folytonos függvényei t-nek (a multiplicitásokat figyelembe véve is), ezért az nem fordulhat elő, hogy Λ a t = t pontban még Perron sajátérték, de valamely t > t-re már nem. Kaptuk tehát, hogy a t < ∞ feltevés ellentmondásra vezetett, így S = R és g(t) = λmax (B(t)) = Λ minden t ∈ R-re. Ezzel a 2 állítás bizonyítását befejeztük

2. tétel: A (3) optimalizálási feladat megoldása akkor és csak akkor egyértelmű, ha a nem teljesen kitöltött páros összehasonlítás mátrixhoz tartozó G gráf összefüggő. A 2. tétel bizonyítása: A szükségesség elemi lineáris algebrai úton igazolható. Ha G nem összefüggő, akkor az A nem teljesen kitöltött páros 7 összehasonlítás mátrix sor- és oszlopcserékkel hozható:  J X  D=  X′ K az alábbi dekomponált alakra   ,  (12) ahol a J, K négyzetes mátrixok tartalmazzák az eredeti A mátrix összes ismert elemét, míg X-ben csak változók szerepelnek. X′ -vel jelöljük az X elemenkénti reciprokaiból transzponálással képzett mátrixot. Jegyezzük meg, hogy a J, K mátrixokban is lehetnek változók. Tegyük fel, hogy J mérete u × u. Legyen α > 0 tetszőleges skalát és P = diag(α, α, . , α, 1, 1, , 1) Ekkor a P mátrixszal végrehajtott hasonlósági | {z } | {z } u n−u transzformáció a

következőt eredményezi:  J  PDP−1 = E =   1 · (X′ ) α α · (X) K   ,  Az X változómátrix tetszőlegesen rögzített értéke mellett az A, D és E mátrixok hasonlóak. Mivel α > 0 tetszőleges, ezért az A mátrixot végtelen sokféleképpen ki lehet úgy tölteni, hogy ugyanazokat a sajátértékeket kapjuk, közöttük a legnagyobbat. Az elégségességhez a korábban bevezetett gráf reprezentációt használjuk fel. Az i0 , i1 , . , ik−1 , i0 egész számokból álló sorozatot k hosszú zárt sétának nevezzük, ha 0 < ij ≤ n teljesül j = 0, . , k − 1 esetén Legyen A = [aij ] egy n×n-es mátrix és γ = i0 , i1 , . , ik−1 , i0 egy zárt séta A γ séta vγ -val jelölt értékét az A mátrix γ menti elemeinek szorzataként definiáljuk: vγ := ai0 i1 ai1 i2 · · · aik−1 i0 . 2. lemma: Legyen A = [aij ] egy pozitív elemű n × n-es mátrix és 1 γ = i0 , i1 , . ik−1 , i0 egy k hosszú zárt séta

Ekkor λmax (A) ≥ (vγ ) k A 2. lemma bizonyítása: Felhasználjuk a p λmax (A) = lim m T r(Am) m∞ 8 összefüggést. P Legyen m = ℓk, ahol ℓ egy pozitív egész szám. Ekkor T r(Am) = δ vδ , ahol az összegzés az összes m hosszú δ zárt sétára történik, amelyből összesen nm darab van. A feltevéseink szerint az összegben minden tag pozitív Legyen δ ∗ az a séta, amely a γ séta ℓ-szeri egymásutánja („ℓ-szerese”). Ez is egy m hosszú zárt séta és vδ∗ = vγℓ . Kapjuk tehát, hogy q p √ √ m T r(Am ) > m vδ∗ = ℓk vγℓ = k vγ . Ha ℓ ∞, akkor kapjuk a 2. lemma állítását  3. lemma Legyen az A nem teljesen kitöltött páros összehasonlítás mátrixhoz tartozó G gráf összefüggő Legyen továbbá xh , (1 ≤ h ≤ d) egyike a hiányzó elemeknek és jelölje ennek a pozícióját (l, m). Ekkor (   k1 ) 1 1 λmax (A(x)) ≥ max (Kxh ) k , , Kxh ahol k > 1 egész szám, K > 0, továbbá k és K értéke

csak az ismert mátrixelemektől és l, m-től függ, xh értékétől nem. A 3. lemma bizonyítása: Mivel G összefüggő, ezért valamilyen kra létezik egy G-beli l = i0 , i1 , , ik−1 = m út, amely összeköti l-t m-mel Megjegyezzük, hogy az air ir+1 , r = 0, . , k − 1 értékei mind ismertek Aban Definiáljuk a k hosszúságú γ zárt sétát az alábbiak szerint: γ := i0 , i1 , . , ik−1 , i0 A 2. lemma alapján 1 1 λmax (A(x)) ≥ (vγ ) k = (K · xh ) k , ahol K = ai0 i1 ai1 i2 · · · aik−2 ik−1 egy pozitív konstans, amely független az xi , (i = 1, 2, . , d) változók értékeitől A λmax (A(x)) ≥  1 Kxh  k1 egyenlőtlenség a fenti gondolat megismétlésével adódik, amelyet a γ séta megfordítására alkalmazunk. Ezzel a 3 lemmát bebizonyítottuk  Rátérünk a 2. tétel bizonyítására Érdeklődésünk középpontjában a Λ := min λmax (A), érték áll, ahol a minimumot az összes olyan teljesen kitöltött 9 mátrix

alapján számítjuk, amelyek az A nem teljesen kitöltött páros összehasonlítás mátrix realizációi. Másképp fogalmazva: a hiányzó elemeket megtestesítő xh (h = 1, 2, , d) változók helyére az összes lehetséges módon pozitív értékű bij -ket írunk, arra ügyelve, hogy a reciprocitás (bij bji = 1) megmaradjon. Az összes ilyen kitöltés közül kiválasztjuk az(oka)t, amely(ek)re a Perron sajátérték a legkisebb. A korábbiakhoz hasonlóan az x1 = ey1 , x2 = ey2 , . xd = eyd . (13) paraméterezést alkalmazzuk. Ily módon A(x) = B(y), tehát ez utóbbi már az Rd -beli y = (y1 , . , yd) vektorral van paraméterezve Legyen Λ := min{λmax (B(y)) : y ∈ Rd }, (14) S = {y ∈ Rd : λmax (B(y)) = Λ}. (15) és A G gráf összefüggőségéből következik, hogy a Λ definíciójában szereplő minimum felvétetik. Tegyügy fel ugyanis indirekt, hogy csak az infimum létezik, ekkor létezik egy Rd -beli, {y(i) }i=1,.,∞ , vektorsorozat, hogy lim

λmax (B(y(i) )) = Λ i∞ és (i) sup{yh }i=1,.,∞ = ∞, vagy (i) inf{yh }i=1,.,∞ = −∞ (16) (17) valamilyen h (1 ≤ h ≤ d) értékre. A páros összehasonlítás mátrix reciprok tulajdonságából következően (16) és (17) ugyanazt jelentik, ezért elegendő közülük a (16)-t tekinteni. Az esetlegesen szükséges átindexelést követően most már feltehetjük, hogy (i) lim yh = ∞, i∞ (i) (i) ami az xh = eyh választással ellentmond a 3. lemmának, hiszen Λ egy rögzített véges szám. Belátjuk, hogy ha |S| > 1, akkor a G gráf nem összefüggő. Legyen p, q ∈ Rd két különböző pont az S halmazban. Jelölje L a p és q pontokon áthaladó egyenest. A 2 állításból következik, hogy az egész egyenes is benne 10 van S-ben: L ⊆ S L ⊆ S miatt létezik egy (l, m) pozíció az A felső háromszög részmátrixában, hogy tetszőleges M > 0-hoz az A mátrixnak létezik olyan C = [cij ]-vel jelölt kitöltése, amelyre λmax (C) =

Λ és clm > M. Ez viszont az xh = clm választással ellentmond a 3 lemmának, hiszen λmax (C) tetszőlegesen nagy lehet, ha clm elég nagy. Ezzel a 2 tételt is beláttuk 3. következmény: Ha a nem teljesen kitöltött páros összehasonlítás mátrixhoz tartozó G gráf összefüggő, akkor a (13) paraméterezéssel a (3) feladat egy szigorúan konvex optimalizálási feladattá írható át. 2. megjegyzés: A Perron sajátérték nem konvex függvénye a mátrixelemeknek Tekintsük a Q 3 × 3-as páros összehasonlítás mátrixot az x változó függvényében:   1 2 x Q = 1/2 1 4  . 1/x 1/4 1 A 3.a ábra mutatja a λmax (Q(x)) függvény képét Ha viszont az x = et exponenciális paraméterezést alkalmazzuk, akkor λmax (Q(et )) már konvex függvénye lesz t-nek (3.b ábra) 3.a ábra A x 7 λmax (Q(x)) függvény nem konvex 3.b ábra t 7 λmax (Q(et )) függvény konvex Forrás: Bozóki, S., Fülöp, J, Rónyai, L [2010]: On optimal completions of

incomplete pairwise comparison matrices, Mathematical and Computer Modelling, 52, pp.318-333 DOI 101016/jmcm201002047 11