Analitikus hierarchia eljárás. Módszertani alapok, algoritmus és számpélda

Analitikus hierarchia eljárás

Módszertani alapok, algoritmus és számpélda

Készítette: Dr. Kiss Ferenc 2009.

Tartalom

Az Analitikus Hierarchia eljárás ................................................................................................ 3 Alapelvek és a szempontrendszer kialakítása ........................................................................ 3 Az algoritmus lépései ............................................................................................................. 7 A konzisztencia mérése.......................................................................................................... 8 Példa szempontrendszer ....................................................................................................... 10 Az iterációs számítás lépései................................................................................................ 11 A kapott modell értékelése................................................................................................... 15 Hasznossági függvények ...................................................................................................... 15 Irodalom ................................................................................................................................... 17

2

Az Analitikus Hierarchia eljárás Alapelvek és a szempontrendszer kialakítása Az Analytical Hierarchy Process (AHP) eljárás kifejlesztése Saaty nevéhez fűződik. Azon az elven alapul, hogy amikor egy adott dologról döntünk, akkor valójában sok részlet információt, tényezőt veszünk figyelembe, és ezen a részletek, valamint a döntési feladat között egy információ-hierarchia húzódik meg. Ezen összefüggésrendszer ismerete segíti a döntés meghozatalát. Más megfogalmazásban: A döntéshozók — amikor egy döntés meghozatalára készülve elemezniük kell a helyzetet és a lehetőségeket — rendszerint egymással összefüggésben levő tényezők — mint például rendelkezésre álló pénz és egyéb erőforrások, tervezett eredmények, piaci helyzet, árfolyamok — sokrétű, bonyolult rendszerével találják szemben magukat. Amikor a szempontok, vagy a rendszer elemei és egymással való kapcsolatai túlzottan sokan vannak ahhoz, hogy egyszerre át lehessen tekinteni azokat, természetes módon csoportokba soroljuk őket egyes tulajdonságaik alapján. Ennek a folyamatnak a többszöri megismétlésével a csoportokat — vagy még inkább az azokat meghatározó közös tulajdonságokat — az ismeretrendszer újabb szintjének elemeiként vizsgáljuk tovább. Ezeket az elemeket más szempont szerint besorolva újabb, magasabb hierarchia szintet alkotunk, míg végül eljutunk a rendszer legfelső eleméhez, amely a döntési probléma általános megfogalmazását illetve a döntés átfogó célját takarja. Az így kialakított ismeretrendszer a valóság modellje, lehetővé teszi az egyes alkotóelemek teljes rendszerre gyakorolt hatásának vizsgálatát. A hierarchia elemzése során megválaszolandó legfontosabb kérdés az, hogy a legalsó szinten található elemek milyen módon hatnak a legfelső szintű tényezőre. Mivel ez a hatás általában nem azonos az összes tényező esetében, meg kell határozni a súlyukat, vagy más néven intenzitásukat, prioritásukat. Egy probléma hierarchikus struktúrába (gráfba) való rendezése az AHP leglényegesebb lépése. E modell építéséhez szakértők bevonására van szükség, akik meghatározzák a problémához leginkább illeszkedő leképezést. Egy általános probléma m-szintű hierarchiája látható a következő ábrán.

3

1. szint

Döntési probléma

2. szint

Döntési jellemző (-csoport) 1.

Döntési szempont (-csoport) 2.

..................

Döntési szempont (-csoport) n.

3. szint

Részletezettebb döntési szempont (alcsoport) 1.

Részletezettebb döntési szempont (alcsoport) 2.

..................

Részletezettebb döntési szempont (alcsoport) k.

Elemi döntési szempont 1.

Elemi döntési szempont 2.

..................

Elemi döntési szempont n.

Döntési változat 1.

Döntési változat 2.

..................

Döntési változat l.

: : m. szint

1. ábra. A Saaty-féle hierarchia egy általános problémára

Az egyes csomópontok közötti kapcsolat erősségét egy-egy [0;1] intervallumba eső számérték jelzi. Ezek megállapításához a szakértőknek el kell végezniük az összes páros összehasonlítást, esetenként megítélve az adott két jellemző (szempont) egymáshoz viszonyított fontosságát, azaz hatásának erősségét a hierarchiában közvetlenül felettük állóra vonatkozóan.1 Az összemérések során minden vizsgált páros egyik tagjához az 1, 2, 3, ..., 9 pozitív egészszámok valamelyikét kell rendelni az alábbi táblázatnak megfelelően, míg a másik tagjához a kiválasztott érték reciprokát. 1. táblázat. A Saaty fontossági értékek értelmezése

Fontossági érték abszolút skálán 1 3 5 7 9 2,4,6,8 1

Értelmezés

Magyarázat

Mindkét tényező egyformán fontos a cél szempontjából A tapasztalatok alapján az egyik tényező kis Mérsékelten preferált mértékben preferált a másikhoz képest A tapasztalatok alapján az egyik tényező lényegesen Erősen preferált preferált a másikhoz képest Az egyik tényező olyannyira erősen preferált a Nagyon erősen preferált másikhoz képest, hogy ez a gyakorlatban is világosan megmutatkozik Rendkívüli módon A gyakorlati példák alapján az egyik tényező a lehető preferált legnagyobb mértékben preferált a másikhoz képest Köztes értékek A fenti preferenciák közti kompromisszumos Egyformán preferált

E vizsgálatok módszereiről, lebonyolításáról, kiértékeléséről bővebben lásd például [1] .

4

lehetőségek

(Ez összhangban van Miller híres megfigyelésével is, hogy általában az emberek egyszerre 7±2 dologra tudnak egyszerre figyelni. Valójában azonban ezzel a trükkel egy 17 elemű skálán értékelünk, átlépve szubjektív megítélésünk korlátait!) A szakértők munkájához kérdőívek állíthatók össze, a Ross-féle keverési tábla segítségével. Az egyes számpárok azt jelentik, hogy milyen sorrendben melyik szempontokat kell összevetni és értékelni a fenti 1-9-ig terjedő értékkel úgy, hogy a fontosabb mellé írjuk az értéket, míg a kevésbé fontos mellé a reciprokot. 2. táblázat. Ross-féle keverési tábla

Szempontszám

Kevert szempontpárok

2

21

3

2 1, 3 2, 1 3

4

1 2, 4 1, 3 2, 1 3, 2 4, 3 4

5

1 2, 5 3, 4 1, 3 2, 4 5, 1 3, 2 4, 5 1, 3 4, 2 5

6

1 2, 6 4, 5 1, 3 2, 5 6, 1 3, 2 4, 6 1, 4 3, 5 2, 1 4, 3 5, 2 6, 4 5, 3 6

7

8

1 2, 7 3, 6 4, 5 1, 3 2, 4 7, 5 6, 1 3, 2 4, 7 5, 6 1, 4 3, 5 2, 6 7, 1 4, 3 5, 2 6, 7 1, 4 5, 3 6, 2 7 1 2, 8 4, 7 5, 6 1, 3 2, 5 8, 6 7, 1 3, 2 4, 8 6, 7 1, 4 3, 5 2, 7 8, 1 4, 3 5, 2 6, 8 1, 5 4, 6 3, 7 2, 1 5, 4 6, 3 7, 2 8, 5 6, 4 7, 3 8 1 2, 9 3, 8 4, 7 5, 6 1, 3 2, 4 9, 5 8, 6 7, 1 3, 2 4, 9 5, 8 6, 7 1, 4 3, 5 2, 6 9,

9

7 8, 1 4, 3 5, 2 6, 9 7, 8 1, 5 4, 6 3, 7 2, 8 9, 1 5, 4 6, 3 7, 2 8, 9 1, 5 6, 4 7, 3 8, 2 9

5

A kapott fontossági értékekkel minden hierarchia szintre felírható az úgynevezett S Saatymátrix az alábbi alakban:

(1)

⎡ w1 ⎢w ⎢ 1 ⎢ w2 S = ⎢ w1 ⎢ : ⎢ ⎢ wn ⎢⎣ w1

w1 ⎤ wn ⎥ ⎥ w2 ⎥ ... wn ⎥ , : ⎥ ⎥ wn ⎥ ... wn ⎥⎦

w1 w2 w2 w2 : wn w2

...

ahol: wi jelenti az adott szinten elhelyezkedő n darab szempont közül az i. szempont relatív súlyértéket; n jelenti az adott hierarchia szinten elhelyezkedő szempontok számát. Az S egy pozitív reciprok mátrix, és jellemző tulajdonsága, hogy Sij ⋅ S jk = Sik

’

valamint S⋅w = n⋅w,

ahol:

S a Saaty mátrix; w a súlyszámok vektora.

Megmutatható, hogy egy pozitív reciprok mátrixban az együtthatók kis perturbációja a sajátértékeknek csak kis perturbációját okozza, ezáltal a sajátvektor érzéketlen a bírálatban bekövetkező kis változásokra [1] . Az S mátrix Lmax legnagyobb sajátértékéhez tartozó w sajátvektor elemei megadják a hierarchia összeköttetéseinek súlyait. A w vektor értéke az (S – nI) = 0 egyenlet megoldásaként adódik. Az AHP-re alapuló modell e súlyszámoknak a csomópontokra történő kiszámításával nyerhető.

6

Az algoritmus lépései 1. Azonosítsuk S mátrix méretét, azaz n-et. 2. Vegyünk fel egy tetszőleges ε > 0 számot. ε-nal írjuk elő a λmax hibáját. Ez az algoritmus leállítója olyan értelemben, hogy ha az iterálásnál a λmax utolsó két közelítésének különbségének abszolút értéke kisebb mint ε, akkor az utolsó közelítést fogadjuk el λmax-nak. 3. Vegyünk fel egy n méretű csupa egyest tartalmazó ⎡1⎤ ⎢1⎥ v°= ⎢ ⎥ ⎢M ⎥ ⎢⎥ ⎣1⎦

1 2 vektort. M n

4. Szorozzuk meg a v° vektorral az S mátrixot jobbról, ekkor egy y1 vektort kapunk: y1 = Sv° 5. λ1max = max y1, (azaz a λmax első közelítése), amely egyenlő az y1 eredményvektor maximális elemével. Legyen k=1. 6. Legyen v k =

1

λ

k max

y k egy vektor. (Ez yk vektortól annyiban különbözik, hogy

maximális eleme 1. Erre a maximum normára csak azért van szükség, hogy az iteráció gyorsabb legyen.) 7. Szorozzuk meg az S mátrixot jobbról a vk vektorral ekkor yk+1 vektort kapunk eredményül: yk+1=Svk. +1 8. Legyen λkmax = max y k +1

9. Hasonlítsuk össze az előbbi sajátérték közelítéssel az előírt ε>0 hibakorlát figyelembe +1 − λkmax < ε , akkor hajtsuk végre a 10. pontban leírtakat, ha a vételével. Ha λkmax feltétel nem teljesül, akkor pedig k=k+1 legyen és menjünk vissza a 6. pontra. +1 10. λ max = λkmax azaz a k+1. közelítést fogadjuk el az S mátrix sajátértékének.

Sajátvektorát, w-t pedig úgy kapjuk meg, hogy az yk+1 elosztjuk elemeinek összegével, azaz 1 w= n y k +1 ∑ yik +1 i =1

7

A konzisztencia mérése Megmutatható, hogy minden lehetséges esetben Lmax ≥ n, és bevezethető az alábbi mérőszám a döntési konzisztencia mérésére:

CI =

Lmax − n . n −1

Saaty és Mariano megmutatta, hogy a CI ≤ 10% nagyon jó értéknek tekinthető [5] . Azonban a következő évek gyakorlati tapasztalatai, valamint más szerzők publikációi alapján bevezethető az alábbi pontosítás.

CR =

CI , RI

ahol RI a véletlenszerű konzisztencia index, melynek értéke a mátrix méretétől függ, és nagyszámú szimuláció lefuttatásával került becslésre. A 2. táblázatban található a véletlenszerű konzisztencia index 1 és 10 közti méretű mátrixokra Saaty 500 fős mintán végzett kísérletei alapján. 3. táblázat. Átlagos véletlenszerű konzisztencia index (Saaty, 2000 alapján)

A mátrix mérete (n)

Véletlenszerű konzisztencia index (RI)

1 2 3 4 5 6 7 8 9 10

0

0,15 0,52 0,89 1,11 1,25 1,35 1,4 1,45 1,49

Az elfogadható konzisztencia érték (CR) a mátrix méretén múlik; egy 3x3-as mátrix estén az érték felső határa 0,05, egy 4x4-es mátrix estén 0,08, míg ennél nagyobb mátrixok esetén (n>= 5) az elfogadható érték maximuma 0,1 (Saaty, [5] , Cheng and Li,[1] ). Amennyiben CR értéke kisebb vagy egyenlő ezen határértékkel, a mátrixon belüli bírálatok elfogadhatóak, azaz konzisztensek. Ezzel szemben amennyiben a CR meghaladja az elfogadható értéket a mátrixban szereplő bírálatok közt olyan mértékű inkonzisztencia lépett, amely szükségessé teszi a becslési folyamat áttekintését, átszervezését és javítását. A páronkénti összehasonlításokat újra kell értékelni. 8

Segíthet a probléma megoldásában a hierarchia átszervezése is; például az érintett elemek egy másik (általánosabb) elem alá való csoportosítása (Crowe et al., [2] ). Az elfogadható konzisztencia index azt jelzi, hogy a bírálatok megalapozottak voltak, és segítenek annak biztosításban, hogy a végső súlyok tényleg a valóságnak megfelelő erőviszonyokat képviseljék.

9

Példa szempontrendszer Az alábbi számpélda az algoritmus működését mutatja egy egyszerű hitelképességi döntési modellen. A modellbe bevont szempontok a következők: 4. táblázat. Döntési szempontok hitelképesség elbírálása során Hitelképesség 1 Kérelmező pénzügyi adatai 2 Referenciák 3 Személyes adatok 4 Munkahellyel kapcsolatos adatok 5 Egyéb adatok 6 A hitel felhasználási célja

A fenti szempontcsoporthoz előállítható a szakértői értékelő kérdőív a szempontok súlyainak meghatározásához (kevert szempontpárok 6 szempontra a Ross-féle keverési tábla alapján: 1 2, 6 4, 5 1, 3 2, 5 6, 1 3, 2 4, 6 1, 4 3, 5 2, 1 4, 3 5, 2 6, 4 5, 3 6). A fent bemutatott kitöltési útmutató alapján egy szakértő ki is töltötte az alábbiak szerint. 5. táblázat. Kitöltött szakértői kérdőív 1. Szempont Kérelmező pénzügyi adatai A hitel felhasználási célja Egyéb adatok Személyes adatok Egyéb adatok Kérelmező pénzügyi adatai Referenciák A hitel felhasználási célja Munkahellyel kapcsolatos adatok Egyéb adatok Kérelmező pénzügyi adatai Személyes adatok Referenciák Munkahellyel kapcsolatos adatok Személyes adatok

Fontosság 2. Szempont 7 Referenciák 1 Munkahellyel kapcsolatos adatok Kérelmező pénzügyi adatai Referenciák A hitel felhasználási célja 5 Személyes adatok Munkahellyel kapcsolatos adatok Kérelmező pénzügyi adatai 1 Személyes adatok Referenciák 4 Munkahellyel kapcsolatos adatok Egyéb adatok 1 A hitel felhasználási célja 2 Egyéb adatok 3 A hitel felhasználási célja

10

Fontosság

4 7 2 7 6 4 4

Az iterációs számítás lépései

Kérelmező pénzügyi adatai Referenciák Személyes adatok Munkahellyel kapcsolatos adatok Egyéb adatok A hitel felhasználási célja ε=0,001

Kérelmező pénzügyi adatai Referenciák Személyes adatok Munkahellyel kapcsolatos adatok Egyéb adatok A hitel felhasználási célja

Kérelmező Munkahellyel A hitel pénzügyi Referen- Személyes kapcsolatos Egyéb felhasznáadatai adatok ciák adatok adatok lási célja 1 7 5 4 4 6 0,142857 1 0,142857 0,142857 4 1 0,2 7 1 1 0,25 3 * 0,25 0,25 0,166667

7 0,25 1

1 4 0,333333

1 0,5 1

2 1 2

1 0,5 1

v0

y1 1 27 1 6,428571 1 = 12,45 1 1 1

12,25 6,5 5,5

λ1max 27

v1 1 0,238095 0,461111

w1 38,50% 9,17% 17,75%

0,453704 0,240741 0,203704

17,47% 9,27% 7,84%

Kérelmező Munkahellyel A hitel pénzügyi Referen- Személyes kapcsolatos Egyéb felhasznáadatai ciák adatok adatok adatok lási célja v1 y2 λ2max v2 ∆λmax w2 1 7 5 4 4 6 1 8,972222 8,972222 1 18,02778 40,71% 0,142857 1 0,142857 0,142857 4 1 0,238095 1,678307 0,187056 7,61% 0,2 7 1 1 0,25 3 * 0,461111 = 3,452778 0,38483 15,67% 0,25 0,25 0,166667

7 0,25 1

1 4 0,333333

1 0,5 1

2 1 2

11

1 0,5 1

0,453704 0,240741 0,203704

3,516667 2,723413 1,697354

0,39195 0,303538 0,189179

15,96% 12,36% 7,70%




Kérelmező Munkahellyel A hitel pénzügyi Referen-- Személyes kapcsolatos Egyéb felhasznáadatai ciák adatok adatok adatok lási célja v2 y3 λ3max v3 ∆λmax w3 1 7 5 4 4 6 1 8,150568 8,150568 1 0,821655 40,44% 0,142857 1 0,142857 0,142857 4 1 0,187056 1,844213 0,226268 9,15% 0,2 7 1 1 0,25 3 * 0,38483 = 2,929592 0,359434 14,53% 0,25 0,25 0,166667

7 0,25 1

1 4 0,333333

1 0,5 1

2 1 2

1 0,5 1

0,39195 0,303538 0,189179

3,132427 2,430186 1,670205

Kérelmező Munkahellyel A hitel pénzügyi Referen- Személyes kapcsolatos Egyéb felhasznáadatai adatok ciák adatok adatok lási célja v3 y4 λ4max 1 7 5 4 4 6 1 8,340487 8,340487 0,142857 1 0,142857 0,142857 4 1 0,226268 1,872941 0,2 7 1 1 0,25 3 * 0,359434 = 3,216928 0,25 0,25 0,166667

7 0,25 1

1 4 0,333333

1 0,5 1

2 1 2

1 0,5 1

Kérelmező Munkahellyel A hitel pénzügyi Referen- Személyes kapcsolatos Egyéb felhasznáadatai ciák adatok adatok adatok lási célja 1 7 5 4 4 6 0,142857 1 0,142857 0,142857 4 1 0,2 7 1 1 0,25 3 * 0,25 0,25 0,166667

7 0,25 1

1 4 0,333333

1 0,5 1

2 1 2

12

1 0,5 1

0,38432 0,298162 0,204919

3,378873 2,337085 1,698308

0,38432 0,298162 0,204919

15,54% 12,06% 8,29%

v4

∆λmax w4 1 0,189919 40,01% 0,22456 8,99% 0,3857 15,43% 0,405117 0,28021 0,203622

16,21% 11,21% 8,15%

v4

y5 λ5max v5 ∆λmax w5 1 8,463462 8,463462 1 0,122975 40,28% 0,22456 1,804852 0,213252 8,59% 0,3857 = 3,243657 0,383254 15,44% 0,405117 0,28021 0,203622

3,37678 2,43352 1,688952

0,398983 0,287532 0,199558

16,07% 11,58% 8,04%





7 0,25 1

1 4 0,333333

1 0,5 1

2 1 2

1 0,5 1

0,398983 0,287532 0,199558

3,299626 2,423133 1,681277

0,395049 0,290111 0,201291

15,93% 11,69% 8,11%

Kérelmező Munkahellyel A hitel pénzügyi Referen- Személyes kapcsolatos Egyéb felhasznáadatai adatok ciák adatok adatok lási célja v6 y7 λ7max v7 ∆λmax w7 1 7 5 4 4 6 1 8,354648 8,354648 1 0,002201 40,22% 0,142857 1 0,142857 0,142857 4 1 0,217606 1,832433 0,219331 8,82% 0,2 7 1 1 0,25 3 * 0,376603 = 3,171299 0,379585 15,27% 0,25 0,25 0,166667

7 0,25 1

1 4 0,333333

1 0,5 1

2 1 2

1 0,5 1

0,395049 0,290111 0,201291

3,326409 2,399096 1,686369

0,398151 0,287157 0,201848

16,02% 11,55% 8,12%


7 0,25 1

1 4 0,333333

1 0,5 1

2 1 2

13

1 0,5 1

0,398151 0,287157 0,201848

3,339215 2,410329 1,686839

0,39821 0,287438 0,20116

16,03% 11,57% 8,10%



Kérelmező pénzügyi adatai Munkahellyel kapcsolatos adatok


7 0,25 1

1 4 0,333333

1 0,5 1

2 1 2

1 0,5 1

0,39821 0,287438 0,20116

3,327133 2,413343 1,685223

0,397303 0,288185 0,201238

16,00% 11,60% 8,10%

Kérelmező Munkahellyel A hitel pénzügyi Referen- Személyes kapcsolatos Egyéb felhasznáadatai adatok ciák adatok adatok lási célja v9 y10 λ10max v10 ∆λmax w10 1 7 5 4 4 6 1 8,369333 8,369333 1 0,004953 40,25% 0,142857 1 0,142857 0,142857 4 1 0,21763 1,825409 0,218107 8,78% 0,2 7 1 1 0,25 3 * 0,379308 = 3,175782 0,379455 15,27% 0,25 0,25 0,166667

7 0,25 1

1 4 0,333333

1 0,5 1

40,25%

CI=

0,473867

16,00%

CR=

0,379093

2 1 2

>

14

1 0,5 1

0,1

0,397303 0,288185 0,201238

3,32763 2,409096 1,685644

0,397598 0,287848 0,201407

16,00% 11,59% 8,11%

A kapott modell értékelése Amennyiben az egyes csomópontokban számított súlyrendszer erősen szélsőséges, felvethető a modell egyszerűsítésének lehetősége. Ha egy szempont súlya az adott csoportban nem éri el az egyébként az adott csoportra számítható átlag súlyérték 10%-át, megvizsgálható, hogy e szempont elhanyagolásával járó modell egyszerűsödés okoz-e lényeges változásokat az összképben. (pl. egy 5 szempontot tartalmazó csomópontban az elmélet átlagsúly 100/5=20%, ha valamelyik érték 2% alatt van, vizsgálandó.)

Hasznossági függvények A döntési modell teljes kidolgozásához az egyes szempontokhoz tartozó hasznossági függvények meghatározása szükséges. A hasznossági függvények az adott szemponthoz tartozó értékkészlet lehetséges elemeihez hozzárendeli a döntéshozó értékítéletét. Minden esetben legalább egy értékhez hozzárendeli a 100 pontos maximumot, és legalább egy értékhez a 0 pontos minimumot. Amennyiben a döntéshozók illetve a modellt fejlesztő szakértők ettől eltérő függvényt adnak meg, a függvényt normálni kell egységes, pl. a 0-100-as skálára. Természetesen a hasznossági függvény lehet folytonos vagy diszkrét a mérési skála függvényében A fenti példában szereplő „A hitelfelvétel célja” szempont hasznossági függvénye az alábbi lehet egy áruhitelező cég üzleti céljainak megfelelően: 6. táblázat. A hasznossági függvény alapadatai

Konyhai gép

60

Hifi és elektronika

100

TV

70

Kerti eszköz

40

Bútor

30

Egyéb

0

15

100 90 80 70 60 50 40 30 20 10 0 Konyhai gép

Hifi és elektronika

TV

Kerti eszköz

2. ábra: Példa hasznossági függvényre

16

Bútor

Egyéb

Irodalom [1] Cheng, E.W.L. and Li, H.: Information priority-setting for better resource allocation using analytic hierarchy process (AHP). Information Management and Computer Security, 2001, Vol. 9 Iss. 2, pp. 61-70. [2] Crowe, T. J., Noble, J. S. and Machimada, J.S.: Multi-attribute analysis of ISO 9000 registration using AHP. International Journal of Quality and Reliability Management, 1998, Vol 15 Iss.2, pp. 205-222. [3] Kindler József, Papp Ottó: Komplex rendszerek vizsgálata. Műszaki Könyvkiadó, 1977. [4] Saaty, T.L.: The Analytic Hierarchy Process. McGraw-Hill, New York, 1980. [5] Saaty, T.L.: Fundamentals of Decision Making and Priority Theory. 2nd ed. Pittsburgh, PA: RWS Publications. 2000 [6] Saaty, T.L. and R.S. Mariano: Rationing Energy to Industries: Priorities and InputOutput Dependence. Energy Systems and Policy, 1979 Winter

17

Analitikus hierarchia eljárás. Módszertani alapok, algoritmus és számpélda

Recommend Documents