Economic subjects | Operational Research » Györgyi Péter - Hálózati optimalizálási modellek

http://www.doksihu Eötvös Loránd University Faculty of Science Györgyi Péter Hálózati optimalizálási modellek BSc szakdolgozat Témavezet®: Frank András, egyetemi tanár Operációkutatási Tanszék Budapest, 2010 http://www.doksihu El®szó Szeretném megköszönni a témavezet®mnek, Frank Andrásnak, hogy a rendszeres konzultációink során irányította munkámat, szakmai és formai észrevételei sokat segítettek a szakdolgozatom elkészítésében. i http://www.doksihu Tartalomjegyzék Bevezet® 1 Jelölések 3 1. Három példa 4 1.1 Van-e még esély a bajnoki címre? 4 1.2 Repül®jegyek szétosztása 5 1.3 Optimális energiapolitika meghatározása 6 2. A probléma felvázolása 8 2.1 A feladat meghatározása 8 2.2 A matematikai modell 9 2.3 A célfüggvény 11 3. A standard eset 12 3.1

Az eset áttekintése 12 3.2 Egy egyszer¶sítési lehet®ség 13 3.3 Az egy sor esete 15 3.4 A hálózati modell 17 4. Az ütközésmentes eset 20 4.1 Egy technikai akadály 20 4.2 Az els® modell 21 4.3 A második modell 23 ii http://www.doksihu TARTALOMJEGYZÉK iii 5. Egy újabb feltétel 27 5.1 A nyúlvány-és-horony kialakítás 27 5.2 A minimális TG-hiba modellezése 29 6. A minimális felbontásszám 31 6.1 Burkard tétele kétsoros mátrixra 31 6.2 Baatar tétele egysoros mátrixra 31 7. Az egészérték¶ség problémája 34 7.1 A kanonikus felbontás 34 7.2 Kanonikus felbontás minimális TG-hiba esetén 36 7.3 Az optimális felbontás

meghatározása 37 Irodalomjegyzék 41 http://www.doksihu Bevezet® Számos gyakorlatban felmerül® probléma jól kezelhet® gráfok segítségével, majd a gráfalgoritmusok gyakran vezetnek a feladat megoldásához. Az optimalizálási feladatok esetén különféle mennyiségek optimumát (minimumát, maximumát) kívánjuk meghatározni. A gráfokon jó néhány optimalizáló algoritmus ismert, ilyen például Dijkstra-algoritmus a legrövidebb út keresésére pozitív élköltségek esetén, vagy a Ford-Fulkerson-algoritmus a maximális folyam meghatározására. Bizonyos esetekben a gráf segítségével jutunk egy lineáris programozási feladathoz, felhasználva a gráf valamilyen nevezetes mátrixát. A szakdolgozatom célja, hogy különféle gyakorlati problémákat visszavezessünk egy már ismert hálózati optimalizálási feladatra. Néhány esetben teljesen természetesen adódik ez a visszavezetés Vannak azonban olyan feladatok, ahol

el®ször nem is gondolnánk az ilyen jelleg¶ megoldásra, pedig sok esetben gyorsabb algoritmust kapunk az eredeti problémára, mint más, közvetlenebb módszerrel. Szakdolgozatom elején bemutatom három egyszer¶ feladat leírását a gráfok segítségével úgy, hogy a kapott gráfon, egy jól ismert algoritmus segítségével, meg tudjuk oldani az eredeti feladatot. A szakdolgozat nagyobbik része egy bonyolultabb problémát ír körül A rákos betegek sugárkezelésénél merül fel egy optimalizálási feladat: egy ismert kiterjedés¶ daganatot akarunk sugárzásnak alávetni, hogy a daganat megsemmisüljön, de az ép sejtek a lehet® legkevésbé károsodjanak. A sugárzás szabályozásában fontos szerepe van egy eszköznek, a Multileaf Collimator-nak Ezen gép beállításai próbáljuk meghatározni úgy, hogy különböz® feltételeknek eleget tegyünk. A 2. fejezetben felvázoljuk a problémát, majd megadjuk egy matematikai modelljét (mátrixok segítségével)

A következ® fejezet a standard esetr®l szól, ezt átírjuk egy minimális költség¶ folyam meghatározásának problémájára A 4 fejezet 1 http://www.doksihu BEVEZETŽ 2 egy, a gyakorlatban fontos, feltételt szab meg nekünk. Ez lényegesen bonyolultabbá teszi a feladatot, azonban a megoldást továbbra is kereshetjük egy minimális folyam képében, igaz most már lényegesen bonyolultabb a gráfunk és mellékfeltételeket is kénytelenek leszünk tenni. Az ezt követ® fejezet Bárász Mihály [5] eredményeit, amelyben egy újabb megkötést tesz számunkra, írja át a folyamproblémára. Az utolsó el®tti fejezet bemutat egy az ugyanebben a környezetben felmerül® feladatot, amelyr®l belátjuk, hogy módszereinkkel kezelhetetlen, hiszen NP-nehéz. Legvégül vázlatosan ismertetünk egy másik módszert, amely egy elméletben fontos eredményt, az egészérték¶séget biztosítja számunkra. http://www.doksihu Jelölések Ha külön nem jelezzük, akkor

egy G = (V, E) gráf csúcsszáma n, élszáma m. Irányított gráf esetén gyakran A-val jelöljük az élek halmazát. A v csúcsba befutó élek halmazát A− (v)-vel, az onnan indulókat A+ (v)-vel jelöljük Az éleken lév® esetleges költségfüggvény c (a nem jelölt éleken az értéke 0), a fels® és alsó korlátokat u(e)-vel és l(e)-vel jelölöm az e élen. Ezek a korlátok alapesetben +∞ illetve −∞ értékeket vesznek fel (természetesen sok esetben az l ≡ 0-t is nyilvánvaló- nak vesszük). A csúcsokon lehetnek feleslegeink illetve igényeink, ezeket az i csúcs esetén bi -vel jelöljük, felesleg esetén bi > 0, igény esetén bi < 0. Egy folyam értékét az e élen x(e)-vel jelöljük, nyilván minden e esetén l(e) ≤ x(e) ≤ u(e). A folyamunknak ki kell elégítenie az igényeinket a feleslegeinkb®l, azaz minden v ∈ V -re bv + P e∈A− (v) x(e) − P e∈A+ (v) x(e) = 0. 3 http://www.doksihu 1. fejezet Három példa Ebben a

fejezetben néhány gyakorlati példán keresztül bemutatjuk a hálózati modellezés hasznosságát, széles alkalmazhatóságát. A fejezet alapvet®en válogatás [3]-ból. Ezen könyvben számos gráfalgoritmusokra találhatóak alkalmazások, most azonban a teljesség igénye nélkül válogatunk közülük. 1.1 Van-e még esély a bajnoki címre? A feladatunk az, hogy baseball bajnokság egy adott pillanatában eldöntsük, hogy van-e még esélye a csapatunknak a végs® gy®zelemre. A bajnokság gy®ztese a legtöbb gy®zelemmel rendelkez® csapat (döntetlen nincs, a holtversenyes gy®zelmünket is elfogadjuk). Jelöljük a csapatokat az 0, 1, 2, , n számokkal, a mi csapatunk legyen a 0. Tegyük fel, hogy az i csapat eddig w(i) darab gy®zelemmel rendelkezik, továbbá azt, hogy az i. és a j capat még g(ij) mérk®zést játszik egymással Nekünk az a legjobb eset, ha a csapatunk minden hátralév® mérk®zését megnyeri, tegyük fel, hogy ekkor w(max) gy®zelme

lesz. A feladatunk egyenérték¶ az alábbi gráfon lév® megengedett folyamproblémával (1. ábra), hiszen, ha van megengedett folyam, akkor van egészérték¶ megengedett folyam is, ennek a jobb oldali része pedig pont egy nekünk jó kimenetelt mutat (az i-b®l (i, j)-be mutató él azt jelenti, hogy az i. csapat hány mérk®zést nyer meg a j . ellen) A másik irány hasonlóan nyilvánvaló 4 http://www.doksihu 1.2 Repül®jegyek szétosztása 5 1. ábra Van-e még gy®zelmi esély? 1.2 Repül®jegyek szétosztása Van egy p kapacitású kis helyi repül®járatunk, amelyik sorban meglátogatja az 1, 2, ., n városokat Tegyük fel, hogy az i városból b(ij) utas akar a j városba menni. A jegyek árát központilag meghatározták: i-b®l j -be f (ij)/f® Feladatunk meghatározni, hogy a különféle jegyekb®l mennyit árusítsunk, hogy a bevételünk maximális legyen, de mindenhol betartsuk a kapacitáskorlátunkat. A probléma megfeleltethet® egy minimális

költség¶ folyamfeladatnak (n = 4 esetén lásd 2 ábrát, más n-re hasonlóan). Minden (i, j) csúcsban vannak az i − j útra váró utasok, akik utaz- nak közülük, azok a baloldali élen "mennek el" (és zetnek nekünk f (ij)-t a jegyért), a többiek a jobboldalin. A repül® az alsó vízszintes éleken halad (az itteni értékek kapacitások, míg a többi költség). Innent®l kezdve az ekvivalencia nyilvánvaló (az egészérték¶ség most is adódik). http://www.doksihu 1.3 Optimális energiapolitika meghatározása 6 2. ábra Repül®jegyek kiosztása n = 4 esetén 1.3 Optimális energiapolitika meghatározása Tegyük fel, hogy az országunk négyféle módon tud energiához jutni: k®olajból, szénb®l, uránból és vízer®m¶b®l. Az ország energiaigénye is négy részre osztható: szükség van elektromos áramra, háztartási olajra, benzinre és gázra. Minden alapanyagból képesek vagyunk bizonyos energiák el®állítására,

például szénb®l tudunk elektromos áramot csinálni, azonban ez az átalakítás veszteséggel jár, amely arányos az átalakítandó mennyiséggel. Célunk, hogy mindenb®l kielégítsük az ország igényét és a lehet® legkevesebbet költsük. Jelöljük az alapanyagainkat 1, 2, 3, 4-gyel, az el®állított energia fajtákat 10 , 20 , 30 , 40 -vel Az i energiahordozóból a(i)-t tudunk vásárolni c(i) áron. Az i-b®l j 0 -be történ® átalakítás költsége c(ij 0 ), az átalakítandó mennyiség m(ij 0 ) része marad meg (a többi veszteség). j 0 -b®l b(j 0 ) igény van A feladatot az általánosított folyamproblémára vezethetjük vissza, amely azt is megengedi, hogy bizonyos (uv) éleken a folyam m(uv)-szeresére változik. A megfelel® gráf most is egyszer¶en adódik (lásd 3. ábra), c-t és b-t az ábrán jelöltük (most csak az igényeinket kell kielégíteni, felesleg maradhat!), az (S, i) éleken a(i) fels®, a (j 0 , T ) éleken b(j 0 ) alsó kapacitás

van. Az (i, j 0 ) "átalakító" éleken m(ij 0 )-szeresére módosítjuk a folyamunkat. A gráfunkon lév® minimális költség¶ folyam mutatja az optimális stratégiánkat. http://www.doksihu 1.3 Optimális energiapolitika meghatározása 3. ábra Energiapolitika meghatározása 7 http://www.doksihu 2. fejezet A probléma felvázolása 2.1 A feladat meghatározása A rákos betegek kezelésének egyik leggyakoribb módszere a sugárkezelés, különösen akkor, ha a tumor jól lokalizálható. Ebben az esetben az a célunk, hogy a sugarak elpusztítsák a rákos sejteket, de közben a létfontosságú ép sejtek ne károsodjanak. A kezelés úgy történik, hogy a betegre több (leggyakrabban 3-7) irányból párhuzamos sugárnyalábot bocsájtunk egy lineáris gyorsító nev¶ géppel (linear accelerator). Annak érdekében, hogy mindenhova a megfelel® mennyiség¶ sugárzás jusson a célterületet minden irányból kis cellákra osztjuk, majd

meghatározzuk, hogy az egyes cellákra mekkora intenzitású sugárzást kívánunk bocsájtani. A megadott intenzitáseloszlás (intenzitástérkép) el®állításához egy sokleveles kollimátor (Multileaf Collimator, továbbiakban MLC) nev¶ eszköz áll rendelkezésünkre. Ez a szerkezet lényegében egy állítható sz¶r®, amely az érkez® sugarat csak bizonyos pozíciókban engedi át. A sz¶r® több (napjainkban általában 20-100) függetlenül mozgó fémnyelvpárból áll, a sugárzás csak az egymással szemben elhelyezked® nyelvek közti területen tud áthaladni (lásd 4. ábra) Az intenzitástérkép el®állításának gyakori módja az úgynevezett step-and-shoot módszer, amely statikus módon m¶ködik: el®ször beállítjuk a nyelveket, majd bekapcsoljuk a sugarat egy megadott ideig, ezután átállítjuk a nyelveket és újra sugározunk, stb. A másik el®állítási módszerrel, miszerint állandó sugárzás mellett folyamatosan mozgatjuk a nyelveket, nem

foglalkozunk. Ebben a fejezetben megadjuk a problémai matemetikai leírását, 8 http://www.doksihu 9 2.2 A matematikai modell bevezetünk néhány kés®bb felhasználra kerül® deníciót, továbbá meghatározzuk, hogy milyen célfüggvényekre kívánunk optimalizálni. 4. ábra Egy MLC ([8]) 2.2 A matematikai modell A feladat matematikai modellje a következ®: adott egy nemnegatív mátrixunk (általában feltehet®, hogy az értékek egészek, jelöljük I -vel és legyen M ∗ N -es, ez az intenzitás mátrix), ezt akarjuk felbontani speciális bináris mátrixok, úgynevezett sorintervallum mátrixok (szegmensek), nemnegatív lineáris kombinációjára (I = PK i=1 (xi ∗ Si )). Ezen Si mátrixok felelnek meg az egyes fémnyelv beállítá- soknak (ott van 1-es, ahova eljut a sugárzás), a együtthatóik pedig azt mutatják, hogy mennyi ideig sugárzunk az adott beállítás mellett. Ez úgy is megfogalmazható, hogy minden i ∈ {1, 2, .M }-re egy S szegmens

i sorához hozzárendelünk egy ([li , ri )) számpárt, ahol li ∈ {1, 2, 3, ., N + 1}; ri ∈ {1, 2, 3, , N + 1}; li ≤ ri és S(i, j) = 1 ⇔ li ≤ j < ri , különben 0. Vagyis li mutatja az i sorban lév® baloldali fémnyelv által az els®, még pont nem lefedett mez®t, míg ri a jobboldali fémnyelv által lefedett els® mez®t mutatja. http://www.doksihu 10 2.2 A matematikai modell 5. ábra Az l=3, r=N-1 eset Példa. Egy példa a felbontásra:  4 4 3    1 6 3    3 4 1    4 4 3  3 6 4 0   1 1 0      0 1 1 0      0  = 3∗ 0 1 0      1 1 1 0    3 0 1 1 0   1 1 1      1 1 0 0      0 +1∗ 1 1 1      1 1 0 0    1 1 1 1 0   0 0 1      0 1 0 0      0 +2∗ 1 0 0      0 0 0 0    0 1 1 0 0    0    0   

0   0 A nyelvek állása ezen szegmensek esetén a következ®: 6. ábra A nyelvek elhelyezkedése a példában A másik megfogalmazás szerint, az els® szegmens esetén l1 = 1, r1 = 3, l2 = 2, r2 = 4, l3 = 2, r3 = 3, l4 = 1, r4 = 4, l5 = 2, r5 = 5. Megjegyzés. A szegmensek és a nyelvbeállítások között nincs bijekció, hiszen a csupa nulla sort több beállítással is elérhetjük. Ez azonban nem jelent gondot a kés®bbiekben, így gyakran használjuk felcserélhet® módon ezen fogalmakat. http://www.doksihu 11 2.3 A célfüggvény 2.3 A célfüggvény Nyilván minden egész elemekb®l álló mátrix el®állítható legfeljebb M ∗ N darab sorintervallum mátrix lineáris kombinációjaként, hiszen az egyetlen egyesb®l és különben csupa nullákból álló mátrixok sorintervallum mátrixok, míg ezen mátrixokat megfelel® együtthatókkal beszorozva az intenzitás mátrix minden egyes eleme tetsz®legesen beállítható. Ezt nevezik triviális

felbontásnak, de ez a gyakorlatban használhatatlan Több célt is ki szoktak t¶zni annak megfelel®en, hogy milyen felbontást kívánunk elérni. A leggyakoribb cél az összsugárzási id® ( PK i=1 xi ) minimalizálása, hiszen ekkor kevesebb sugárzás éri az ép sejteket. A modellünkben az összsugárzási id®t a felbontásban szerepl® együtthatók összege adja, gyakran felbontási id®ként hivatkozunk majd rá (decomposition time, DT). Fontos cél lehet még a kezelés idejének minimalizálása, hiszen ekkor több beteg kezelésére kerülhet sor A kezelési id® jól jellemezhet® a nyelvek beállításához szükséges id® és az összsugárzási id® összegével, azaz a PK i=1 (xi + c(Si , Si−1 )) számmal, ahol c(Si , Si−1 ) az i. elrendezés beállításának az ideje az i − 1-b®l (S0 a kezdeti elrendezés). Ebben az esetben gyakran fel szokták tenni, hogy a nyelvek újrakongurálása konstans id®t vesz igénybe, így jelent®sen

egyszer¶sítve a problémát. Bizonyos esetekben a felbontásszám (K , decomposition cardinality, DC) minimalizálása a cél. Mi alapvet®en a felbontási id® minimumát fogjuk vizsgálni, majd belátjuk, hogy a felbontásszám minimumának meghatározása már nagyon speciális esetben is NP-nehéz (bár vannak jól közelít® heurisztikus algoritmusok). Példa. Az el®bbi példa esetén a felbontásszám 3, míg a felbontási id® 3+1+2 = 6 Triviális felbontásnál a felbontásszám 16 (a nulla elemekhez nem kell külön szegmens), a felbontási id® 4 + 4 + 3 + 1 + 6 + 3 + 3 + 4 + 1 + 4 + 4 + 3 + 3 + 6 + 4 + 3 = 56. Látható már ebben az esetben is, hogy a triviális felbontás lényegesen rosszabb eredményt ad, akármelyik mennyiség szerint vizsgálódunk. http://www.doksihu 3. fejezet A standard eset 3.1 Az eset áttekintése Standard esetnek azt nevezzük, ha az eddigi feltételek mellett nem vezetünk be újabbakat. A legtöbb esetben sajnos kénytelenek

vagyunk további feltételeket szabni, azonban a mostani modellünk is hasznos a gyakorlatban. Léteznek olyan MLC-k, amelyek beállításaiban felhasználják a standard eset eredményeit. Ez lényegesen gyorsabban kapható meg, mint például a következ® fejezetben tárgyalásra kerül® ütközésmentes eset. Ebben a fejezetben bemutatjuk, hogy létezik egy O(M N )-es algoritmus, amely megadja nekünk a minimális összsugárzási id®t. Az algoritmus visszavezeti a feladatot egy adott gráfon való minimális költség¶ folyamproblémára. Ez a fejezet els®sorban Ahuja és Hamacher [1] munkájának eredményeit mutatja be: leegyszer¶sítjük a problémát az M = 1 esetre, majd ennek megoldására megadunk egy hálózati modellt. A feladatunk a minimális összsugárzási id® meghatározása, azaz a következ® feladat megoldása: min z ∗ := PL k=1 xk (1) feltéve, hogy: I= PL k=1 xk Sk (1a) Sk szegmens ∀k ∈ {1, 2, ., L}-re (1b) xk ≥ 0 ∀k ∈ {1, 2, ., L}-re

(1c) 12 http://www.doksihu 13 3.2 Egy egyszer¶sítési lehet®ség Megjegyzés. 1) Itt feltehetjük, hogy L az összes szegmens száma, hiszen a 0 együtthatóval rendelkez® szegmensek nem változtatják meg a minimumot. 2) z ∗ -gal a feladat megoldását, vagyis a legkisebb összsugárzási id®t jelöljük a továbbiakban. 3.2 Egy egyszer¶sítési lehet®ség A probléma nem tartalmaz semmiféle megkötést a sorok között, ezért célszer¶ a feladatot soronként vizsgálni, majd a sorokra kapott eredményekb®l megpróbálni megkonstruálni az (egyik) optimális felbontást. Ezzel a módszerrel M egymástól független feladatot kaptunk. Egy sor esetén a feladatunk a egy adott N dimenziós vektor felbontása olyan N dimenziós 0-1 vektorok nemnegatív lineáris kombinációjára, amelyekben az egyesek egy tömbben szerepelnek. A feladatot minden sor esetén átírjuk egy irányított hálózatban lév® minimális költség¶ folyam problémává. Az így kapott

hálózat meglehet®sen speciális lesz: nem lesz benne kör, de amúgy teljes lesz (ha a csúcsokat 1,2,.-tal jelöljük, akkor minden olyan (i, j) élt behúzunk, ahol i < j ); a költség függvényünk azonosan 1 lesz, míg kapacitás korlátunk semelyik élen se lesz. Be fogjuk bizonyítani, hogy ebben a speciális esetben a minimális költség¶ folyamproblémának a megoldására létezik O(N )-es algoritmus, továbbá, ha ezt mind az M sor esetében megcsináljuk, akkor ezek segítségével az eredeti feladatra adunk egy O(M N )-es algoritmust. Könnyen belátható, hogy nem létezik ennél gyorsabb algoritmus a standard eset megoldására. Az i. sor esetén a feladatunk a következ®: min zi := PL k=1 xk (2) feltéve, hogy: Ii,. = PL k=1 xk rk (2a) rk egysoros szegmens vektor (továbbiakban szegmenssor) ∀k ∈ {1, 2, ., L}-re (2b) xi ≥ 0 ∀i ∈ {1, 2, ., L}-re (2c) Az el®z® megjegyzés 2) pontjához hasonlóan itt is zi -vel jelöljük a kés®bbiekben a

minimumot. A következ® állítás bizonyítása megmutatja, hogy hogyan kaphatjuk meg (1) megoldását úgy, hogy ismerjük minden sor esetén (2) megoldását. http://www.doksihu 14 3.2 Egy egyszer¶sítési lehet®ség Jelölés. zmax :=max {zi : 1 ≤ i ≤ M } Azaz zmax a sorok minimális összsugárzási idejei közül a legnagyobb. Állítás. zmax = z ∗ Vagyis az el®bb deniált mennyiség az I mátrix esetén a legkisebb összsugárzási id®, tehát (1) megoldása megkapható, ha minden sorára megoldjuk (2)-t, majd megkeressük ezek közül a legnagyobbat. Bizonyítás. Nyilvánvaló, hogy (1) megoldása legalább akkora, mint bármely sor esetén (2) megoldása, hiszen ellenkez® esetben I felbontásának megfelel® sora jobb felbontást adna, mint (2), ami viszont ellentmondás, hiszen (2) a legjobb felbontást keresi. Tehát zmax ≤ z ∗ Az egyenl®séget úgy fogjuk bizonyítani, hogy megadjuk I -nek egy olyan felbontását, ahol az összsugárzási id®

éppen zmax . Legyenek ri1 , ri2 , , rip az i sorhoz tartozó szegmenssorok az optimális felbontásban (p i-t®l függ). Ezekhez tartozzanak az xi1 , xi2 , ., xip együtthatók (ekkor nyilván zi = Pp k=1 xk ). I egy optimális felbon- tását egy egyszer¶ algoritmus segítségével kaphatjuk meg. Az els® lépésben minden 1 ≤ i ≤ M esetén kiválasztunk egy tetsz®leges rik1 -t, majd ezeket a szegmenssorokat összerakva megkonstruáljuk S1 -et Ennek együtthatója legyen x1 = minxik1 : 1 ≤ i ≤ M . Ezután lecsökkentjük a kiválasztott szegmenssorok együtthatóját x1 -gyel Amennyiben egy szegmenssor együtthatója 0 lesz (legalább egy ilyen biztosan lesz), akkor azt a szegmenssort elfelejtjük a továbbiakban. Ezután újra kiválasztunk M darab szegmenssort, ezekb®l megkonstruáljuk S2 -t, majd az el®bbihez hasonlóan megadjuk x2 -t, végül újra redukálunk. Ha egy sor esetén már nem tudunk szegmenssort kiválasztani, akkor a csupa nulla sort választjuk. Ezt

addig csináljuk, amíg el nem fogy az összes szegmenssor. A kapott felbontás összege nyilván I lesz, hiszen soronként vizsgálva a (2a) feltétel biztosítja ezt számunkra Tehát (1a) teljesül. (1b) is igaz lesz, hiszen szegmenssorokat összerakva nyilván szegmenst kapunk, míg (1c) triviális. Tegyük fel, hogy zmax = zj Ekkor nyilván az algoritmus segítségével kapott felbontás ideje zj , hiszen az i. sor esetén a hasznos (nem azonosan nulla) szegmenssorok együtthatójának összege zi lesz (ehhez azt használjuk ki, hogy ha egy szegmenssort sugárzunk x ideig, majd y ideig, akkor az összsugárzási id® ugyanakkora lesz, mintha x + y ideig sugároztuk volna). Tehát beláttuk, hogy I -nek http://www.doksihu 15 3.3 Az egy sor esete létezik zmax idej¶ felbontása, viszont ennél jobb nincs, tehát ez a felbontás minimuma, vagyis z ∗ = zmax .  Megjegyzés. Az optimum meghatározása a most belátott állítás segítségével elérhet® O(M N ) id®ben

Ezzel szemben az ehhez tartozó felbontáshoz már több id®re lesz szükség, ugyanis a bizonyításban szerepl® algoritmus nem fut le ennyi id® alatt. Megjegyezzük továbbá, hogy ezt a méretet számos esetben már az output (a szegmenseink) is túllépheti. 3.3 Az egy sor esete Tehát (1) megoldása helyett elegend® megoldani I minden sorára (2)-t, innen az el®bbi algoritmus segítségével megkaphatunk egy optimális felbontást. Mostantól tehát (2)-t próbáljuk megoldani. Az egyszer¶ség kedvéért az i indexeket elhagyjuk, valamint Ii,. helyett egy adott b vektort kell "kikevernünk" a (2a) feltételben A jobb áttekinthet®ség miatt transzponáljuk le az egész feladatunk, tehát rk és b legyenek oszlopvektorok. Feltehet®, hogy semely k-ra nem lesz rk ≡ 0, hiszen ezeket elhagyhatjuk Ezután minden rk -ról el lehet mondani, hogy az els® néhány koordinátája nulla, majd a következ® néhány (legalább egy) egyes, majd a maradék néhány nulla.

rk -t jelöljük ruv -val, ha az els® egyes koordinátája u és az utolsóé v − 1 (u és v megfelel az el®z® fejezetben deniált, a nyelvek állását meghatározó li és ri számoknak). Legyen A = {(u, v) : 1 ≤ u ≤ N, u + 1 ≤ v ≤ N + 1}! Nyilvánvaló, hogy |A| = n + (n − 1) + . + 1 = n(n + 1)/2 A feladatunk tehát a következ®: min z := P (u,v)∈A xuv (3) feltéve, hogy: b= P (u,v)∈A xuv ruv (3a) xuv ≥ 0 ∀(u, v) ∈ A (3b) Példa. N = 3 esetén A = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}, tehát z = x12 + x13 + x14 + x23 + x24 + x34 . A (3a) feltételt mátrixos alakban írjuk fel és már a hálózati modellt el®készítend® beszúrunk egy csupa nulla sort is a végére: http://www.doksihu 16 3.3 Az egy sor esete   1 1    0 1    0 0  0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0              x12 x13 x14 x23 x24 x34       

    =           b1   b2    b3   0 Természetesen a (3b) feltételnek megfelel®en x12 , x13 , x14 , x23 , x24 , x34 ≥ 0 Más N esetén is vegyünk fel egy csupa nulla sort, majd írjuk át a (3a) feltételt úgy, hogy a mátrix minden sorából (az els® sort kivéve) kivonjuk a felette lév® sort. Ha a b vektort is ennek megfelel®en módosítjuk, akkor nyilvánvalóan egy ekvivalens LP feladatot kapunk Jelölje b0 a módosított b vektort A konstrukciónak köszönhet®en (miszerint az egyesek minden oszlopban egy blokkban helyezkednek el) a módosított feladat egy ruv -nak megfelel® oszlopa egy darab egyest tartalmaz az u. sorban és egy darab (-1)-est a v sorban, míg a többi érték nulla lesz Tehát a következ® feladatot kaptuk: min z := P (u,v)∈A xuv (4) feltéve, hogy: b0 = P (u,v)∈A 0 (4a) xuv ruv xuv ≥ 0 ∀(u, v) ∈ A (4b) Példa. Az el®bbi példát (N = 3) folytatva a

következ®t kapjuk:   1 1 1 0 0 0    −1 0 0 1 1 0    0 −1 0 −1 0 1  0 0 −1 0 −1 −1              x12 x13 x14 x23 x24 x34      b1       b2 − b1 =     b3 − b2     −b3          A b ≥ 0 feltételb®l (b vektor eredetileg az I mátrix egyik sora volt, tehát nemnegatív) triviálisan következnek az alábbi észrevételek: http://www.doksihu 17 3.4 A hálózati modell 1. Észrevétel PN +1 2. Észrevétel Pj 3.4 i=1 b0i = 0 0 i=1 bi ≥ 0 minden j ∈ {1, 2, ., N + 1}-re A hálózati modell A kapott lineáris programozási feladatunk egy jól ismert példa a hálózati folyam probléma alkalmazására, például Ahuja és társai is foglalkoznak vele [5] munkájukban. Vezessük be a következ® G = (V, A) irányított gráfot: legyen V = {1, 2, , N + 1} a csúcshalmazunk

és, mint már korábban jeleztük legyen A = {(u, v) :≤ u ≤ N, u + 1 ≤ v ≤ N + 1} az élek halmaza. Minden él költsége legyen 1, míg vala- mennyi él kapacitása legyen ∞ (az alsó kapacitás legyen minden élen 0). A j csúcs feleslege vagy igénye legyen b0j . Példa. N = 3 esetén a következ® gráfot kapjuk: 7. ábra A standard eset gráfja Ha ezen a gráfon megoldunk egy minimális költség¶ folyam problémát, akkor a (4)-gyel egy ekvivalens feladatot oldunk meg, hiszen a (4a) feltétel épp az igények és a feleslegek kiegyenlítését jelenti, míg a (4b) az alsó kapacitásoknak felel meg. A folyam költsége P (u,v)∈A xuv , amely mennyiség minimumát keressük (4)-ben, tehát a folyam probléma és (4) ekvivalens feladatok. Most pedig belátjuk, hogy a mostani minimális költség¶ folyam problémánk megoldható O(N ) lépésben. Az algoritmus hatékonysága a következ® triviális meggyeléseken múlik: http://www.doksihu 3.4 A hálózati

modell 18 3. Észrevétel 1) A hálózatunk körmentes, de amúgy teljes lesz (minden olyan (i, j) élt behúzunk, ahol i < j ) 2) c ≡ 1; u ≡ ∞ Az algoritmusunk a következ® lesz: kiindulunk az üres folyamból, majd kiválasztjuk az els® olyan csúcsot (u), ahol felesleg van (b0u > 0) és az els® olyat (v ), ahol igény van (b0v < 0). A 2 Észrevétel miatt u < v , hiszen különben j = u estén ellentmondást kapnánk Legyen ezt követ®en xuv = min{|b0u |, |b0v |} (itt kihasználtuk a 3. észrevétel 1) pontjának második felét) Végül b0u értékét lecsökkentjük xuv -val, míg b0v értékét megnöveljük xuv -val. Ugyanezeket a lépéseket csináljuk egészen addig, amíg minden b0i nulla nem lesz. A korábban tett két meggyelésünk a módosított b0 értékek mellett is nyilván fennáll. Az els® észrevétel miatt amíg van valahol felesleg, addig lesz valahol igény is, míg a második észrevétel miatt az els® felesleggel rendelkez® csúcs

mindig megel®zi az els® igénnyel rendelkez®t, tehát az algoritmusunk nem akad el. Minden lépés után valamelyik i csúcs esetén bi nulla lesz, tehát az algoritmusunk O(N )-es lesz, hiszen a lépések konstans idej¶ek (az els® felesleget tartalmazó csúcs és az els® igénnyel rendelkez® csúcs meghatározása folyamatosan történik, azaz mindig 1-el növeljük a megfelel® indexet, amíg megfelel® b-vel rendelkez® csúcsot nem találunk, így összesen tart O(N ) ideig). Azt, hogy az algoritmusunk jó úgy bizonyítjuk, hogy ez egy speciális esete az ismert legrövidebb út algoritmusnak. Ez az algoritmus szintén az üres folyamból indul és mindig az éppen aktuális x folyamhoz tartozó G(x) gráfon dolgozik. G(x) csúcsai megegyeznek G csúcsaival és minden A-beli (i, j) élt egy c((i, j)) költség¶ és rj,i = ui,j − xi,j kapacitású (i, j) és egy −c((i, j)) költség¶ rj,i = xi,j kapacitású (j, i) éllel helyettesítünk. Ha egy él kapacitása

nulla, akkor elhagyjuk Az algoritmus minden lépésben G(x) egy felesleggel rendelkez® csúcs és egy igénnyel rendelkez® csúcs között megkeresi a legrövidebb utat, módosítja x-et és b-t, és ezt addig csinálja, amíg b ≡ 0 nem lesz. Nyilvánvaló, hogy a mi algoritmusunk ennek egy egyszer¶bb esete A jobb érthet®ség miatt nézzük csak az algoritmust: http://www.doksihu 3.4 A hálózati modell u := min{w : bw > 0}; v := min{w : bw < 0}; amíg u és v értelmes, addig δ := min{bu , −bv }; xuv := δ ; bu := bu − δ ; bv := bv + δ ; amíg bu ≤ 0, addig u := u + 1; amíg bv ≥ 0, addig v := v + 1; 19 http://www.doksihu 4. fejezet Az ütközésmentes eset 4.1 Egy technikai akadály Bár vannak MLC-k, amelyeknél hasznos az el®z® fejezetben bemutatott módszer, leggyakrabban mégis kénytelenek vagyunk további mellékfeltételeket szabni. Az MLC-k többségénél, technikai okok miatt, a szomszédos sorokban lév®, egymással szemközt

elhelyezked® nyelvek nem nyúlhatnak túl egymáson. Vagyis a korábbi jelölésekkel: ∀i ∈ {2, 3, ., M }-re li ≤ ri−1 és ∀j ∈ {1, 2, , M − 1}-re li ≤ ri+1 Az ilyen beállításoknak megfelel® szegmenseket ütközésmentes szegmenseknek fogjuk hívni. Mint látni fogjuk, ez a feltétel a feladat bonyolultságát jelent®sen megnöveli Ebben a fejezetben bemutatjuk Bolandnak és társainak [6] cikkében tárgyalt eredményét, amely két hálózati modell segítségével is megmutatja, hogy a feladat polinomiális id®ben megoldható. Az els® modell egyegyszer¶ gráfot használ számos mellékfeltétellel, míg a második modell a mellékfeltételek egyszer¶sítését, a hálózatba való beépítését célozza meg. Ebben a modellben egy hálózati folyamproblémát kapunk azzal a mellékfeltétellel, hogy bizonyos éleken a folyamértékek megegyezését követeljük meg. Az így kapott lineáris program LP-megoldóval már hatékonyan (polinomiálisan)

kezelhet®. Összefogalva a következ® feladatot szeretnénk megoldani (L-re most úgy gondolhatunk, mint az összes ütközésmentes szegmens száma): min z ∗ := PL k=1 xk (5) feltéve, hogy: 20 http://www.doksihu 21 4.2 Az els® modell I= PL k=1 xk Sk (5a) Sk ütközésmentes szegmens ∀k ∈ {1, 2, ., L}-re (5b) xk ≥ 0 ∀k ∈ {1, 2, ., L}-re (5c) Deníció. Jelölje H egy adott sorban lév® nyelvpár pozícióinak a halmazát, azaz H = {(u, v) : u ∈ {1, 2, .N + 1}, v ∈ {u, u + 1, , N + 1}} Emlékeztetésül meg- jegyezném, hogy az el®z® fejezetben deniált A halmaz nem engedte meg az u = v esetet, vagyis a csupa nulla sort. 4.2 Az els® modell Vezessük be a következ® G = (V, A) gráfot: legyen V = {(i, l, r) : i ∈ {1, 2, ., M }, (l, r) ∈ H} ∪ {S, T } Egy rögzített (i0 , l0 , r0 ) csúcs annak felel majd meg, hogy az i0 . sorban a baloldali nyelv az l0 pozícióban van, míg a jobboldali az r0 -ban. A gráfot úgy képzeljük el, hogy M

szintje van, minden szinten az adott sorhoz tartozó csúcsok helyezkednek el, míg a 0. szinten az S és az M +1 szinten a T mesterséges csúcs van Két csúcs között akkor húzunk be élt, ha szomszédos szinten vannak és a nekik megfelel® beállítások nem ütköznek. Ezen kívül összekötjük még S -et az összes 1 szinten lév® csúccsal és az összes M . szinten lév® csúcsot összekötjük T -vel, valamint behúzzuk a (T, S) élt Ez utóbbi kivételével minden élt lefele irányítunk, azaz a magasabb szint¶ csúcs fele mutatnak. Összefoglalva (lásd 8 ábra): A = {((i, j, r), (i + 1, l0 , r0 )) : i ∈ {1, 2, ., M − 1}, l ≤ r0 , l0 ≤ r}∪ ∪{(S, (1, l, r)) : (l, r) ∈ H} ∪ {((M, l, r), T ) : (l, r) ∈ H} ∪ {(T, S)} Vegyük észre a következ® két nyilvánvaló állítást: 1. Észrevétel A G gráf a (T, S) élt elhagyva körmentes, vagyis minden kör átmegy a (T, S) élen http://www.doksihu 22 4.2 Az els® modell 2. Észrevétel Minden

G-beli kör megfelel egy ütközésmentes szegmensnek és minden ütközésmentes szegmens megfelel egy G-beli körnek. Példa. M = 4, N = 2 esetén a gráfunk a következ® (az éleknek csak egy része van berajzolva, színessel két adott szegmenshez tartozó kört láthatunk): 8. ábra Az M = 4, N = 2 eset A két színessel jelölt kör az alábbi szegmenseknek felel meg (az els® a piros, a második a kék):    1 0        1 1    ,     0 1      0 0 0 0    1 1    1 0   1 0 Mivel minden ütközésmentes szegmens megfelel egy körnek, ezért egy adott felbontásban szerepl® minden ütközésmentes szegmensnek megfeleltethetünk egy http://www.doksihu 23 4.3 A második modell folyamot oly módon, hogy a neki megfelel® kör éleinek a folyamértéke az ® együtthatója legyen. Ha egy felbontás esetén ezeket a folyamokat összeadjuk (élenként), akkor minden felbontásnak

megfeleltettünk egy folyamot. Példa. Tekintsük az alábbi felbontást:  1 0   0 0   2 0               1 1   5 5   1 1        2∗  = +3∗  1 0   3 2   0 1        3 0 1 0 0 0 Ekkor a következ® folyamot kapjuk: a piros éleken xe = 2 , a kékeken xe = 3, xT S = 5, míg a többi élen x ≡ 0. Az 1. Észrevétel miatt egy felbontásnak megfelel® folyamban a felbontás ideje épp a (T, S) él folyamértéke lesz. Ez adja nekünk a következ® ötletet: vezessünk be egy költségfüggvényt úgy, hogy cT S = 1, míg különben c ≡ 0. Ezáltal egy folyam költsége épp a (T, S) él költsége lesz, vagyis ahhoz, hogy a feladatunk egy minimális folyamprobléma legyen, már csak az (5a) feltételt kell garantálnunk. Ezt az els® modellben a következ® mellékfeltétellel biztosítjuk: Pj l=1 PN +1 P r=j+1 e∈A− (i,l,r)

xe = Iij (6) ∀i ∈ {1, 2, ., M }, ∀j ∈ {1, 2, , N } Emlékeztetésül: A− (i, l, r) az (i, l, r) csúcsba befutó élek halmazát jelöli. A hálózati folyamproblémánk a (6) mellékfeltétellel egy lineáris programozási formulát adnak nekünk, amely segítségével már megkereshetjük az optimális felbontást. A formulában a változók és a feltételek száma polinomiális, így jó algoritmushoz jutottunk. Ezt követ®en érdemes a modellünket átalakítani úgy, hogy minél közelebb kerüljünk egy egyszer¶ folyamproblémához. 4.3 A második modell Célunk elérésének érdekében szükség lesz a mátrix mez®it jelképez® élekre, melyeken a folyamértéket pontosan meg kívánjuk szabni, vagyis ezen éleken az alsó és a fels® http://www.doksihu 24 4.3 A második modell korlátot is Iij -re állítjuk be. Minden szegmensbeállítás egyértelm¶en meghatározza, hogy mely mez®k kapnak sugárzást, így az ezeken a csúcsokon áthaladó

folyamértékekb®l állítjuk össze a megfelel® értékeket. Legyen G0 = (V 0 , A0 ) gráf az alábbi: V 0 := {(i, l, r)1 , (i, l, r)2 : (i, l, r) ∈ V }∪ ∪{(i, j) : i ∈ {1, 2, ., M }, j ∈ {1, 2, , N + 1}} ∪ {S, T } A0 := Aeddigi ∪ Abe ∪ Aki ∪ Aint Aeddigi := {((i, l, r)2 , (i + 1, l0 , r0 )) : i ∈ {1, 2, ., M − 1}, l ≤ r0 , l0 ≤ r}∪ ∪{(T, S)} ∪ {(S, (1, l, r)1 ) : (l, r) ∈ H} ∪ {((M, l, r)2 , T ) : (l, r) ∈ H} ∪ {(T, S)} Abe := {((i, l, r)1 , (i, l)) : (i, l, r)1 ∈ V 0 )} Aki := {((i, r), (i, l, r)2 ) : (i, l, r)2 ∈ V 0 )} Aint := {((i, j), (i, j + 1) : i ∈ {1, 2, .M }, j ∈ {1, 2, , N })} Az intenzitás éleken (utolsó halmaz) fels® és az alsó kapacitás is bevezetünk: ∀e = ((i, j), (i, j + 1)) ∈ Aint : u(e) = l(e) = Ii,j . A többi élre l(e) = 0, u(e) = ∞ c továbbra is csak a (T, S) élen 1, különben 0. Nézzük meg, hogy változott meg a korábbi modellünk! A korábbi csúcsokat kettévágtuk és a keletkezett két

új csúcs között átvezetjük a rajtuk átmen® folyamot azokon az éleken, amelyek azoknak a mez®knek felelnek meg, melyeket sugárzás ér. Ezeken az éleken már beállíthatjuk a kívánt értékeket a kapacitásokkal. Azonban az intenzitás éleken több beállításhoz tartozó kör is keresztülmegy, így ezek összekeveredését csak mellékfeltétellel tudjuk elkerülni: x((i, l, r)1 , (i, l)) = x((i, r), (i, l, r)2 ) (7) ∀(i, l, r) ∈ V A hálózaton a fenti mellékfeltétellel kell minimális költség¶ folyamot keresnünk. Nyilvánvaló, hogy |V 0 | = O(M N 2 ) és |A0 | = O(M N 4 ) (minden szinten O(N 2 ) csúcs van és két szint közötti O(N 2 ) él a domináns tag), tehát polinomiális algoritmussal megkereshet® a legolcsóbb folyam, vagyis polinomiális id®ben megkaphatjuk a minimális összsugárzási id®t és a hozzá tartozó felbontást. http://www.doksihu 4.3 A második modell 25 Megjegyzés. A mellékfeltétel miatt a modell nem biztosítja az

egészérték¶séget Erre valójában nincs is szükség, hiszen a sugárzási id®t nagy pontossággal be tudjuk állítani. Kombinatorikus algoritmusokkal ez az eredmény is elérhet®, vázlatosan bemutatjuk ezt is az utolsó fejezetben Példa. A korábbi példa a kiterjesztett gráfon (az éleknek csak egy része van behúzva; ahol a két kör megegyezik, azokat az éleket lilával jelöltük, továbbá a szemléletesség miatt a kettévágott csúcsokat színeztük az indexelés helyett): http://www.doksihu 26 4.3 A második modell 9. ábra A kib®vített gráf http://www.doksihu 5. fejezet Egy újabb feltétel 5.1 A nyúlvány-és-horony kialakítás A szomszédos sorokban elhelyezked® nyelvek között mindig van egy kis rés, ezért az ilyen jelleg¶ hibák minimalizálása miatt a nyelvek oldala speciális, úgynevezett nyúlvány-és-horony (tongue-and-groove, továbbiakban TG) kialakítású. Ez a kialakítás segíti az érintkez® nyelvek közti

sugárárnyékolást, azonban ha egy élnek csak az egyik oldalán van nyelv, akkor ezen a részen különféle hibák (alul- vagy túlsugárzás) lépnek fel. Ebben a fejezetben a korábbi feltétel (ütközésmentesség) megtartása mellett úgy keressük a minimális összsugárzási id®t, hogy a TG hiba minimális legyen. A problémával [5]-ben találkozhatunk, most azonban az el®z® fejezetben bemutatott modelleket fogjuk úgy módosítani, hogy az újabb feltételnek is megfeleljünk. Deníció. Egy A = (aij )i∈{1,2,,M },j∈{1,2,,N } (nemnegatív) mátrix TG-hibája a következ®: T G(A) = M −1 X N X |aij − ai+1,j | i=1 j=1 Deníció. Azt mondjuk, hogy két M ∗ N -es mátrix (A és B) kompatibilis prolú, ha minden i ∈ {1, 2, ., M − 1} és j ∈ {1, 2, , N } esetén teljesül a következ® két állítás: 1) aij ≤ ai+1,j esetén bij ≤ bi+1,j 27 http://www.doksihu 28 5.1 A nyúlvány-és-horony kialakítás 2) aij ≥ ai+1,j esetén bij ≥ bi+1,j

Az alábbi két észrevétel triviális módon adódik a deníciókból: 1. Észrevétel T G(cA) = cT G(A) (c tetsz®leges valós) 2. Észrevétel T G(A + B) ≤ T G(A) + T G(B) és egyenl®ség akkor és csak akkor van, ha A és B kompatibilis prolú. Deníció. Egy I = PL k=1 xk Sk (nemnegatív) felbontás TG-hibája: T G({xk }, {Sk }) = L X xk T G(Sk ) k=1 Állítás. Legyen I = PL k=1 xk Sk , ahol minden változó nemnegatív. Ekkor: T G(I) ≤ T G({xk }, {Sk }) és egyenl®ség akkor és csak akkor van, ha minden Sk azonos prolú I -vel. Bizonyítás. A két Észrevétel többszöri alkalmazásával az állítás nyilvánvaló  Meghatároztuk tehát, hogy milyen szegmensek szerepelhetnek a felbontásban, ha a TG-hibát minimális szinten kívánjuk tartani. Jelöljük az I -vel kompatibilis prolú, ütközésmentes szegmensek halmazát U (I)-vel. A feladatunk tehát a következ®: min z ∗ := PL k=1 xk (8) feltéve, hogy: I= PL k=1 xk Sk (8a) Sk ∈ U

(I) ∀k ∈ {1, 2, ., L}-re (8b) xk ≥ 0 ∀k ∈ {1, 2, ., L}-re (8c) Bárász Mihály cikkében ([5]) egyrészt átfogalmazza a feladatot egy lineáris programozási feladattá, amely biztosít egy hatékony algoritmust, másrészt mutat egy kombinatorikus algoritmust, amely lineáris id®ben megadja az optimális összsugárzási http://www.doksihu 5.2 A minimális TG-hiba modellezése 29 id®t (lásd az utolsó fejezetben), igaz felbontást nem mutat hozzá (mint a 3. fejezetben említettük, rossz esetben már az output mérete is túl nagy lehet, így nem is létezhet lineáris algoritmus). Ennek az eredménynek els®sorban elméleti jelent®sége van, hiszen különféle heurisztikus algoritmusok eredményességét lehet gyorsan meghatározni. A kombinatorikus algoritmus biztosítja az egészérték¶séget is, ellentétben az el®z® fejezet most bemutatásra kerül® modelljének módosított verziójával Látható tehát, hogy nem mindig érdemes feltétlenül ezt a

módszert követni, bizonyos esetekben más algoritmusok a célravezet®bbek. 5.2 A minimális TG-hiba modellezése Az el®z® fejezetben bemutatott modellek szinte teljesen megfelelnek a mostani feladat ábrázolásához, csupán néhány élt kell elhagynunk, hogy a nem I -kanonikus szegmensek ne fordulhassanak el® a felbontásban. Pontosabban fogalmazva az el®z® fejezet els® modelljében szerepl® A els® részében szerepl® feltétel a következ®kkel (9) egészítend® ki: 1) (l < l0 ) ⇒ ∀j ∈ [l, l0 ) : Iij ≥ Ii+1,j (9a) 2) (l > l0 ) ⇒ ∀j ∈ [l0 , l) : Iij ≤ Ii+1,j (9b) 3) (r < r0 ) ⇒ ∀j ∈ [r, r0 ) : Iij ≤ Ii+1,j (9c) 4) (r > r0 ) ⇒ ∀j ∈ [r0 , r) : Iij ≥ Ii+1,j (9d) Vagyis egy I intenzitásmátrix minimális TG-hibájú ütközésmentes felbontásai közül a minimális összsugárzási id®t adót meghatározásához a következ® G = (V, A) gráfon kell a minimális költség¶ folyamot keresni a (6) mellékfeltétel mellett: V

= {(i, l, r) : i ∈ {1, 2, ., M }, (l, r) ∈ H} ∪ {S, T } A = {((i, j, r), (i + 1, l0 , r0 )) : i ∈ {1, 2, ., M − 1}, l ≤ r0 , l0 ≤ r, (9)}∪ ∪{(S, (1, l, r)) : (l, r) ∈ H} ∪ {((M, l, r), T ) : (l, r) ∈ H} ∪ {(T, S)} http://www.doksihu 30 5.2 A minimális TG-hiba modellezése Példa. M = 2, N = 3 esetén, ha  I= 1 5 2 2 3 4   akkor: 10. ábra A minimális TG-hiba esete Természetesen ezt a modellt is átalakíthatjuk a korábbihoz hasonló módon. Ebben a modellben egyedül Aeddigi -t kell értelemszer¶en módosítani a (9) feltétel segítségével, az így kapott modellben már csak (7) lesz mellékfeltételként. http://www.doksihu 6. fejezet A minimális felbontásszám 6.1 Burkard tétele kétsoros mátrixra Ebben a fejezetben nem a felbontási id®t fogjuk vizsgálni, hanem a felbontásszámot. A problémára 2002-ben adott választ Burkard [6] cikkében, mégpedig negatívat Az alábbi tétel belátásával bizonyította, hogy

a minimális szegmensszámú felbontás meghatározása NP-nehéz: Tétel (Burkard). Legyen a1 , a2 , , an adott Ekkor az alábbi A mátrixnak akkor és csak akkor van felbontása n szegmens nemnegatív kombinációjára, ha létezik az {1, 2, ., n} számoknak olyan {i1 , i2 , , ik } részhalmaza, amelyre ai1 +ai2 ++ain = M.  A= a1 0 a2 0 a3 . an M M M M M M M   Megjegyzés. Az utóbbi probléma ismert NP-nehéz feladat 6.2 Baatar tétele egysoros mátrixra 2005-ben Baatar és társai [4]-ben a következ® tétellel belátták, hogy már egysoros mátrixok esetén is NP-nehéz a feladat: 31 http://www.doksihu 32 6.2 Baatar tétele egysoros mátrixra Tétel. Tekintsük az alábbi két problémát: Felbontásszám probléma (DC) Adott: A = (a1 , a2 , ., aN ), K pozitív egész szám Kérdés: létezik-e I -nak felbontása legfeljebb K darab szegmensre. Hármas particionálás (Three Partitioning, 3-PART) Adott: B, Q, b1 , b2 , ., b3Q pozitív egész

számok, melyekre P3Q j=1 bj = QB és min- den j -re B/4 < bj < B/2. Kérdés: létezik-e a {b1 , ., b3Q } számoknak felosztása T1 , T2 , , TQ hármasokra, hogy P b∈Tq b = B minden q ∈ {1, 2, ., Q}-ra Legyen: 1) N := 4Q 2) ha n ≤ 3Q, akkor an := Pn j=1 bj , különben an := (4Q − n + 1)B 3) K := 3Q Állítás: A két problémára ugyanakkor lesz igen a válasz. Megjegyzés. A hármas particionálás ismert NP-nehéz feladat Bizonyítás. Ha a 3-PART-ra igen a válasz, akkor a következ® felbontása lesz Anak: ha bj ∈ Tq , akkor Sj esetén legyen l = j, r = 3Q + q + 1 (most csak egy sorunk van). xj pedig legyen bj Nyilván K darab szegmensünk lesz és könnyen ellen®rizhet®, hogy el®állítottuk A-t, tehát az egyik iránnyal készen vagyunk. Mivel A els® 3Q eleme monoton növ®, ezért A felbontásában biztosan pontosan K darab szegmens van. Jelöljük a Sq -t intervallumként: Iq = [lq , rq ) (lq és rq l- nek és r-nek felel meg az Sq szegmens

esetén). Vegyünk A-nek azt a {Iq , xq }, q ∈ {1, 2, ., 3Q} (K elem¶) felbontását, amelyre az intervallumok összhossza maximális Az általánosság rovása nélkül feltehetjük, hogy lq = q (az els® 3Q mez® mindegyikében kell kezd®dnie intervallumnak). Figyeljük meg az alábbiakat: 1) Ebben a felbontásban semely p, q ∈ {1, 2, ., 3Q}-ra nem lesz lq = rp , mert különben Ip és Iq helyett vehetnénk Ip ∪ Iq -t min{xp , xq } együtthatóval és Ip -t vagy Iq -t a maradék együtthatóval, így n®ne az intervallumok összhossza. 2) rq > 3Q∀q ∈ {1, 2, ., 3Q}, mivel az els® 3Q mez® mindegyikéb®l indul intervallum, de 1) miatt ezekben a mez®kben nem lehet vége intervallumnak http://www.doksihu 6.2 Baatar tétele egysoros mátrixra 33 3) rq 6= 3Q + 1∀q ∈ {1, 2, ., 3Q}, mert a3Q = a3Q+1 , tehát valamelyik intervallumnak kéne kezd®dnie 3Q + 1-ben is, hogy kiegyenlítsük a két mez®t, de ez nem lehet. 4) Az eddigiek miatt minden intervallum vége

(rq ) a {3Q + 2, 3Q + 3, ., 4Q + 1} halmazban van. Legyen bj ∈ Tq ⇔ rj = 3Q+j +1. A deníciója mutatja, hogy jól particionáltunk (az elemek B -esével csökkennek az utolsó Q mez®n), tehát beláttuk a másik irányt is.  Megjegyzés. Bizonyos speciális alakú mátrixokra (például bináris mátrixokra és konstansszorosaikra) ismert polinomiális algoritmus. Ennek azonban csak elméleti jelent®sége van, a gyakorlatban jól közelít®, heurisztikus algoritmusokat használnak. Egy ilyen algoritmus megtalálható például [4]-ben. http://www.doksihu 7. fejezet Az egészérték¶ség problémája Az utolsó fejezetben felvázoljuk a kombinatorikus módszert, amely biztosítja számunkra az egészérték¶séget is. Mint már említettük erre a gyakorlatban nincs szükség, azonban számos esetben (például a minimális felbontásszám közelítésére) kombinatorikus módszert használnak, továbbá így hasonló problémák megoldásához is jól hasznosítható

algoritmust kapunk. Ebben a részben [4] és [5] segítségével bemutatjuk, hogyan biztosítható az egészérték¶ség az ütközésmentes, illetve a minimális TG-hibájú esetben. Ez a fejezet csak egy vázlatot ad, részletes bizonyítások és a kombinatorikus módszer további felhasználásai a fenti forrásokban találhatóak. 7.1 A kanonikus felbontás Deníció. Egy S szegmens esetén legyen L(S) egy olyan M ∗ (N + 1)-es mátrix, amelyben minden i ∈ {1, 2, ., M } esetén, az i sorban pontosan az li mez®ben van egyes, különben minden eleme nulla. Egy {ck , Sk } felbontás esetén legyen L := P ck ∗L(Sk ), amelyre baloldali végpontok mátrixaként fogunk hivatkozni. Hasonlóan deniáljuk az R mátrixot is (jobboldali végpontok mátrixa). Észrevétel. Könnyen látszik, hogy L és R minden sorösszege megfelel a felbontás idejének. Deníció. Tetsz®leges M ∗ N -es I mátrix esetén legyen I d azaz M ∗ (N + 1)-es mátrix, amire Iijd = Ii1 , ha j =

1; Iij − Ii,j−1 , ha j ∈ {2, 3, ., N }; és −IiN , ha 34 http://www.doksihu 35 7.1 A kanonikus felbontás j = N + 1. Észrevétel. Nyilvánvaló, hogy L − R = I d A következ® tétel segítségével jól jellemezhetjük az L és R mátrixokat: 1. Tétel L és R pontosan akkor tartoznak I egy ütközésmentes felbontásához, ha L − R = I d és minden i = 1, ., M − 1-re és t = 1, , N -re (i) t X j=1 és (ii) t X j=1 lij ≥ t X ri+1,j j=1 li+1,j ≥ t X ri,j j=1 Egy a fenti feltételekkel adott L és R mátrixpár több különböz® felbontáshoz is tartozhat (de ezek ideje ugyanakkora), mi azonban kiemelünk közülük egyet, így megfeleltetjük a speciális felbontásokat és a mátrixpárokat egymásnak. Mostantól tehát elég lesz L és R mátrixokat meghatározni. Deníció. Egy {[xk , yk ]} intervallumrendszer kanonikus, ha nincs két olyan intervalluma, hogy az egyik szigorúan tartalmazza a másikat Egy szegmensrendszer kanonikus, ha

minden sorára megszorítva kanonikus intervallumrendszert kapunk (egy szegmens sora alatt az [li , ri ) intervallumot értjük). Egy ({ck }, {Sk }) felbontás kanonikus, ha a szegmensei kanonikus rendszert alkotnak. L és R segítségével könnyedén megkaphatjuk azt a hozzátartozó kanonikus fel- bontást, amelyben nincsenek nulla együtthatójú szegmensek és amelyben semely szegmens nem szerepel kétszer. Az algoritmusból könnyen látszik, hogy amennyiben L és R elemei egészek, abban az esetben minden részeredmény, így a ck együtt- hatók is egészek lesznek, tehát a kés®bbiekben csak L és R egészérték¶ségével kell foglalkoznunk: http://www.doksihu 36 7.2 Kanonikus felbontás minimális TG-hiba esetén k := 1 amíg L 6= 0 Minden i-re legyen αil az L i. sorának els® nem 0 eleme és li ennek az indexe Hasonlóan deniáljuk R mátrix esetén az αir és az ri változókat. l r Sk := ([li , ri )), ck := min{α1l , ., αM , α1r , ., αM } L i. sorának

li eleméb®l kivonunk ck -t, R-re hasonlóan k := k + 1 7.2 Kanonikus felbontás minimális TG-hiba esetén Ha a TG-hibát is minimalizálni szeretnénk, akkor hasonlóan kell eljárnunk. Az alábbi tétel megmutatja, hogy ezt megtehetjük: 2. Tétel A minimális felbontási idej¶ I -kompatibilis (minimális TG-hibájú) felbontások között van kanonikus Bizonyítás (vázlat). Megmutatjuk, hogy minden felbontáshoz létezik egy kanonikus felbontás is ugyanakkora felbontási id®vel Ha a felbontásunkban van két szegmens (S és S 0 ) melyek nem kanonikusak (azaz van olyan soruk, ahol li < li0 ≤ ri0 < ri , vagy fordítva), akkor ezt a két szegmenst ki tudjuk úgy cserélni (legfeljebb) három szegmensre, hogy a sorokat kicseréljük a [min(li , li0 ), min(ri , ri0 )), [max(li , li0 ), max(ri , ri0 )) sorokra (értsd: ezekben az intervallumukban lesznek egye- sek) és a nagyobb együtthatóval rendelkez® szegmens i. sorára Az így kapott három szegmens már I

-kompatibilis lesz (ez egyszer¶ esetvizsgálattal adódik), továbbá az együtthatók könnyedén beállíthatóak úgy, hogy minden feltételt kielégítsünk. Amíg van a kanonikusságot sért® szegmenspár, addig folyamatosan cserélünk. Az eljárásunk során (feltéve, hogy I egész együtthatós) a P k ck PM i (rk,i −lk,i )2 kifejezés min- den lépésben legalább eggyel csökken, így véges algoritmust kaptunk, tehát készen vagyunk (rk,i illetve lk,i az Sk szegmens esetén jelöli ri -t, illetve li -t).  A fejezet els® tételéhez hasonló tételt kaphatunk a minimális TG-hibájú esetben http://www.doksihu 37 7.3 Az optimális felbontás meghatározása is: 3. Tétel L és R pontosan akkor tartoznak I egy minimális TG-hibájú ütközésmentes felbontásához, ha L − R = I d és minden i = 1, , M − 1-re és t = 1, , N -re (i) t X lij ≥ j=1 és (ii) t X t X ri+1,j j=1 li+1,j ≥ j=1 t X ri,j j=1 ha Ii,t ≤ Ii+1,t , akkor (iii) t X

és (iv) lij ≤ t X j=1 j=1 t X t X rij ≥ j=1 j=1 t X t X li+1,j ri+1,j ha pedig Ii,t ≥ Ii+1,t , akkor (v) és (vi) j=1 t X t X j=1 7.3 lij ≥ j=1 rij ≤ li+1,j ri+1,j j=1 Az optimális felbontás meghatározása A fejezet korábbi részein már beláttuk, hogy egy optimális megoldás el®állításához elegend® meghatározni az L és R mátrixokat. Ezek ismeretében a kanonikus felbontás algoritmusa már biztosít számunkra egy optimális felbontást Azt is beláttuk, hogy az együtthatók egészérték¶ségét L és R egészérték¶sége biztosítja. Ebben a részben egy O(M N )-es algoritmussal el®állítjuk L-t és R-t, továbbá belátjuk, hogy mindkett® elemei egészek lesznek. http://www.doksihu 38 7.3 Az optimális felbontás meghatározása Fogalmazzuk át a problémát: az, hogy L és R nemnegatív, továbbá L − R = I d pont annak felel meg, hogy egy nemnegatív W -re L = I+d + W és R = I−d + W (I+d és I−d I d pozitív

és negatív része koordinátánként). Ez a meggyelés koordinátánként nézve triviális. Tehát elegend® W -t meghatározni Könnyen belátható, hogy az L és R mátrixok jellemzésére használt 1. illetve 3. tétel feltételei mind átírhatóak W segítségével Például (i) esetén a következ®t kapjuk: t X (wij − wi+1,j ) ≥ j=1 t X d ((Ii+1,j )− − (Iijd )+ ) j=1 A többi feltétel is átírható hasonló alakra, így a következ® feladatot kell megoldanunk (a felbontás ideje megegyezik L és R tetsz®leges sorának összegével, amely akkor minimális, ha W tetsz®leges sorösszege minimális): min PM +1 j=1 w1j (10) feltéve, hogy: dit ≤ Pt j=1 (wij − wi+1,j ) ≤ eit Minden i ∈ {1, 2, .M − 1}-re t ∈ {1, 2, , N + 1}-re (10a) W ≥ 0 (10b) A (10a) feltételben dit és eit rögzített I -t®l függ® számok (ütközésmentes esetben (i) és (ii) segítségével kaphatóak meg, míg minimális TG-hiba esetén (i)-(vi)

segítségével). A következ® lemma azt mutatja meg, hogy az optimális W -t megkaphatjuk úgy, hogy oszloponként határozzuk meg: 1. Lemma Ha W (10) egy megengedett megoldása, ennek k oszlopa wk , és w egy olyan nemnegatív M dimenziós oszlopvektor, amely koordinátánként kisebb wk -nál és dik ≤ k−1 X 0 (wij − wi+1,j ) + wi0 − wi+1 ≤ eik j=1 akkor W k. oszlopát w-re, k + 1-et wk+1 − w + wk -ra cserélve szintén megengedett megoldást kapunk ugyanakkora célfüggvénnyel. http://www.doksihu 39 7.3 Az optimális felbontás meghatározása Bizonyítás. Egyedül t = k feltétel esetén változnak (10a)-ban a feltételek, de ennek fennállását a lemma feltétele biztosítja (10b) és a célfüggvény változatlansága triviális.  A lemma miatt W -t meghatározhatjuk oszloponként, ha minden sorban a minimális értéket írjuk be (hamarosan látni fogjuk, hogy ezt megtehetjük). Tehát, ha az els® k − 1 oszlop ismert, akkor a következ® feladat

megoldásával kapjuk wk -t: 0 ) (11) min (w10 , .wM feltéve, hogy: 0 wi+1 − wi0 ≤ Pk−1 − wi+1,j ) − dit (11a) 0 − wi0 ≥ wi+1 Pk−1 − wi+1,j ) − eit (11b) j=1 (wij j=1 (wij wi0 ≥ 0 (11c) ∀i ∈ {1, 2, ., M − 1} (11)-ben a minimumot úgy értjük, hogy minden koordinátájában kisebb egyenl®, mint bármely más megengedett megoldás megfelel® koordinátája. Ha találunk (11)nek megoldását és W k oszlopának ezt véve minden k-ra jó megoldáshoz jutunk, hiszen semelyik koordinátáját nem tudjuk tovább csökkenteni, így a sorösszeg minimális lesz. A feladatunkat kicsit általánosabban fogalmazva a következ®t kell megoldanunk: min (x1 , .xM ) (12) feltéve, hogy: xi+1 − xi ≤ fi (12a) xi+1 − xi ≥ gi (12b) xi ≥ 0 (12c) ∀i ∈ {1, 2, ., M − 1} A következ® lemma biztosítja, hogy lesz koordinátánként minimális megoldásunk: 2. Lemma Ha x és x0 két megoldása (12)-nek, akkor a koordinátánként vett minimumuk is

megoldása lesz (12)-nek. http://www.doksihu 7.3 Az optimális felbontás meghatározása 40 Bizonyítás. Tekintsük (12a)-t egy tetsz®leges i esetén Feltehetjük, hogy xi ≤ x0i Ekkor min{xi+1 , x0i+1 } ≤ xi+1 ≤ xi + fi = min{xi , x0i } + fi . (12b) hasonlóan kapható meg, míg (12c) triviális.  A következ® vázlatos algoritmus el®állítja nekünk az optimális x vektort. Az algoritmus három részb®l fog állni. El®ször egy (12b)-t kielégít® megoldást adunk: x1 = 0, xi = Pi−1 l=1 gl , ha i > 1. Ezután az egész sorozatot megemeljük úgy, hogy a legkisebb eleme 0 legyen (így kielégítjük (12c)-t), az els® 0 el®tti elem indexe legyen k . Végül amíg k ≥ 1, addig az x1 , , xk kezd®szeletet eltoljuk lefele annyival, hogy a feltételeink ((12a) és (12c)) ne sérüljenek. Ha (12a) miatt állunk meg, akkor k-t eggyel csökkentjük, különben a nullává vált elem elé állítjuk. A feltételek fennállása némi esetvizsgálat után

könnyen adódik, míg az optimalitás valamivel bonyolultabban indukcióval jön ki. Nyilvánvaló, hogy ha az elején minden egész volt, akkor a végén is minden az maradt, így W egész együtthatós lesz, ezért L és R is, vagyis a felbontás együtthatói is. Érdemes megjegyezni továbbá, hogy a módszer O(M N ) id®ben adja meg az optimális felbontás idejét (vagyis például L egy sorának összegét), tehát a módszer ilyen téren is optimális. http://www.doksihu Irodalomjegyzék [1] R. K Ahuja, H W Hamacher, A Network Flow Algorithm to Minimize Beam- On Time for Unconstrained Multileaf Collimator Problems in Cancer Radiation Therapy, Networks (2005), 36-41. [2] R. K Ahuja, T L Magnanti, J B Orlin, Network ows: Theory, algorithms, and applications, Prentice-Hall, Englewood Clis, NJ (1993) [3] R. K Ahuja, T L Magnanti, J B Orlin, M R Reddy: Applications of Network Optimalization in: Network models (M. O Ball, T L Magnanti, C L Monma, G. L Nemhauser), Elsevier

(1995) [4] D. Baatar, H W Hamacher, M Ehrgott, G J Woeginger, Decomposition of in- teger matrices and multileaf collimator sequencing, Research Report, Department of Mathematics, University of Kaiserslautern, Germany (2004) [5] Bárász M., Egy daganatos betegségek sugárkezelésénél felmerül® optimalizációs probléma vizsgálata, Publikálatlan kézirat (2006) [6] N. Boland, H W Hamacher, F Lenzen, Minimizing Beam-On Time in Cancer Radiation Treatment Using Multileaf Collimator, Networks 43 (2004) 226-240. [7] R. E Burkard, Open research question section of Oberwolfach conference, (2002) [8] http://varian.mediaroomcom 41