Programozás | Programozás-elmélet » Lóránt László - Optimalizálási algoritmusok összehasonlítása a Template Method tervezési minta segítségével

http://www.doksihu Optimalizálási algoritmusok összehasonlítása a Template Method tervezési minta segítségével Készítette: László Lóránt Témavezető: Darvay Zsolt Kolozsvár 2006 http://www.doksihu Tartalomjegyzék Tartalomjegyzék . 2 Bevezető. 3 1. Optimalizálási feladat 4 1.1 Primál-duál trajektóriakövető algoritmus 4 1.2 Az elmozdulásvektor meghatározása 10 2. Lineáris egyenletrendszerek 12 2.1 Rendezési heurisztikák 12 3. Tervezési minták 13 3.1 A Template Method tervezési minta 13 3.2 A Strategy tervezési minta 16 4. Adatok 19 4.1 Az MPS fájlformátum 19 4.2 Az adatok beolvasása 21 Könyvészet:. 24 http://www.doksihu Bevezető Ennek a dolgozatnak a célja egy olyan objektumorientált program készítése, amely alkalmas a lineáris optimalizálási (LP) feladatok megoldására ([2, 12, 13]). Ezeket, a feladatokat általában olyan kódokkal oldják meg, amelyek nem használják ki az objektumorientált programozásban rejlő

lehetőségeket. Az alacsonyabb szintű megközelítés előnye elsősorban a végrehajtás gyorsasága. A számítógépek rohamos fejlődése azonban lehetővé teszi azt, hogy a sebesség helyett egyre inkább más tényezőkre helyezzük a hangsúlyt. A dolgozatban tervezési mintákat használunk, annak érdekében, hogy könnyen változtatható, továbbfejleszthető programot hozzunk létre. Ez által lehetőség nyílik arra, hogy olyan algoritmusokat hasonlítsunk össze, amelyek csak kissé térnek el egymástól. Erre az összehasonlításra a hagyományos kódokkal nem volna lehetőség. A változtathatóságot több szempont szerint valósítjuk meg. Például sűrűmátrixot, vagy ritkamátrixot használhatunk az adatok tárolására. Egy másik lehetőség az elmozdulásvektor kiszámítási módszerének a változtathatóvá tétele. Továbbá, a lineáris egyenletrendszerek megoldási módszerének az egyszerű kicserélését is megvalósíthatjuk. A szakirodalomban

nem találkozunk erre a témára vonatkozó olyan objektumorientált programmal, amely tervezési mintákra alapszik. A programban két tervezési mintát ([1, 3, 7, 8]) használunk a Template Method (Sablon függvény) és a Strategy (Stratégia) tervezési mintákat. Az adatok tárolására .MPS kiterjesztésű fájlokat használunk, ami standardnak számít a lineáris programozási feladatok megoldására, ezért a bemeneti állományok hordozhatóknak tekinthetők a különböző LP megoldók között. A dolgozatban egy olyan egyéni módszert is bemutatunk, amely az .MPS fájlformátum helyességének az ellenőrzésére lexikális és szintaktikai elemzőket használ. Az első fejezet a programban használt algoritmust és az elmozdulásvektor számítási módszereit írja le. A következő fejezet a szimmetrikus lineáris egyenletrendszerek megoldására vonatkozó heurisztikákat tárgyalja. Ez által a megoldás hatékonysága növelhető A harmadik fejezet a programban

használt tervezési minták rövid leírását tartalmazza. 3 http://www.doksihu Az utolsó fejezetben olvashatunk a bemeneti adatok tárolására használt fájlformátumról, illetve ennek helyességének ellenőrzésére használt lexikális és szintaktikai elemzőkről ([4]). 1. Optimalizálási feladat Ebben a részben olvashatunk a programban használt algoritmusról, az elméleti hátteréről és az elmozdulásvektor kiszámításának a módszereiről. 1.1 Primál-duál trajektóriakövető algoritmus Tekintsük a következő lineáris optimalizálási feladatot, standard formában: min c T x, Ax = b, x ≥ 0, (P) ahol, A ∈ ℜ mxn , rang ( A) = m , b ∈ ℜ m , és c ∈ ℜ n . Ennek a feladatnak a duálisa a következő: max b T y, A T y + z = c, z ≥ 0. (D) A továbbiakban feltételezzük, hogy a következő feltétel, az úgynevezett belső pont feltétel fennáll. ( ) Létezik x 0 , y 0 , z 0 , úgy, hogy: Ax 0 = b, x 0 > 0, A T y 0 + z 0 = c, z 0

> 0. A fenti feladatok optimális megoldását a következő egyenletrendszer segítségével határozhatjuk meg: Ax = b, x ≥ 0, A T y + z = c, z ≥ 0, xz = 0. Megengedettségi feltételnek nevezzük az előbbi egyenletrendszer első két feltételét, ez biztosítja azt, hogy a kapott vektorok megengedett megoldások lesznek. 4 http://www.doksihu Az utolsó egyenlet az úgynevezett komplementaritási feltétel. A belsőpontos módszerek esetében a komplementaritási feltételt általában egy parametrizált egyenlettel helyettesítjük. Így a következő rendszert kapjuk: Ax = b, x ≥ 0, A T y + z = c, z ≥ 0, xz = µ e, ahol, µ > 0 és e = [1,1,  ,1] T elemének értéke eggyel egy olyan n dimenziós vektor, amelynek minden egyenlő. Minden rögzített µ >0 az előbbi egyenletrendszernek egy egyértelmű megoldását határozza meg, ezt a pontot pedig µcentrumnak nevezzük. Az így kapott µ-centrumok halmaza, a µ > 0 paraméterek

értékeire egy analitikus görbét határoz meg, amit centrális útnak hívunk. Ez az algoritmus a centrális út követését igyekszik megvalósítani. A különböző µcentrumokat a Newton módszerrel közelítjük meg A Newton módszer alkalmazása úgy történik, hogy az aktuális pontból kiindulva, úgynevezett elmozdulásvektorokat határozunk meg annak érdekében, hogy a centrális utat megközelítő következő vektort megkapjuk. A következő ábra d pontjában láthatjuk a centrális utat, az ábra többi pontjaiban pedig különböző µ-centrumokat láthatunk ([13]): 1. ábra: Centrális út A programban használt algoritmus ([2, 5]): ( ) Adott x 0 ∈ P, x 0 > 0, y 0 , z 0 ∈ D, z 0 > 0 5 http://www.doksihu Tehát Ax 0 = b és AT y 0 + z 0 = c És adott 0 < σ < 1,0 < ρ < 1 k := 0 Repeat µ k +1 := σ ( x k )T z k n X k := diag ( x k ) Z k := diag ( z k ) v( µ k +1 ) := µ k +1e − x k z k dy k := −( AZ k−1 X k AT ) −1 AZ

k−1v( µ k +1 ) dz k := − AT dy k dz k := − Z k−1 (v( µ k +1 ) − X k dz k )  xik | dxik < 0,1 ≤ i ≤ n  k   dxi  α P := min −  zik | dzik < 0,1 ≤ i ≤ n  k   dzi  α D := min − x k +1 := x k + ρα P dx k y k +1 := y k + ρα D dy k z k +1 := z k + ρα D dz k k := k + 1 Until STOP Mivel végig belső pontokat határozunk meg, a dualitási rés nem válhat zéróvá, de elég közel jutunk az optimális megoldáshoz, ha a dualitási rés kisebb lesz egy bizonyos ε-nál. Az algoritmus megállásához a következő feltételt vizsgáljuk: cT x − bT y 1 + cT x ≤ε A továbbiakban egy konkrét példa keretében vizsgáljuk az algoritmust. Tekintsük az alábbi lineáris programozási feladatot: 6 http://www.doksihu minimalizáljuk: 19 x1 + 15 x 2 + 61x3 + 4 x 4 + 6 x5 + 31x6 az alábbi feltételek mellett: x1 − 5 x 2 − 6 x3 − 6 x 4 − 6 x5 + 7 x6 = −86 − 4 x1 + 3x 2 − 2 x3 + 7 x 4 + 6 x5 + 4 x6 = 58

x1 + x 2 − 6 x3 − 6 x 4 − x5 − 5 x6 = −18 A feladatot mátrix formában a következőképpen kapjuk: minimalizáljuk c T x Ax = b x ≥ 0 , ahol, x ∈ ℜ n , b ∈ ℜ m , és ahol A kezdeti megengedett megoldások a következők: Ezekkel a kezdeti értékekkel az algoritmus az alábbi lépéseket követi. Első iteráció: Ismerve az x0 és z 0 kezdeti vektorokat, az X és Z diagonálmátrixok a következők: X=diag( x1 , x 2 , x3 , x 4 , x5 , x6 )=diag (1,4,2,2,6,1) Z=diag ( z1 , z 2 , z 3 , z 4 , z 5 , z 6 ) =diag (7,8,3,9,3,1) Ezekre a kezdeti vektorokra a primál és a duál célfüggvények, valamint a dualitási rés és a korlát paraméter, μ a következő értékeket kapják: c T x = 276.0 b T y = 194.0 rés = z T x = 82.0000 µ = 01 rés = 1.3667 n 7 http://www.doksihu Következik az AZ −1 XAT mátrix és a v(µ ) segédvektor megadása, melyek a következő értékeket kapják: A dy elmozdulásvektor értékét a (AZ −1 ) XAT dy = − AZ

−1v(µ ) lineáris egyenletrendszerből kapjuk, amely a következő: a dz elmozdulásvektor értéke a következő: és a dx pedig a következő értéket veszi fel: Használva az aránytesztet, megkapjuk a primál vektorra vonatkozó lépés méretét:  xi (k ) : ∀dxi (k ) < 0, és∀1 ≤ i ≤ n  =   dxi (k ) = min{4.9240,184265,20926,633250} = 20926  α p = min − és hasonlóan a duál vektor esetén a következőt kapjuk: 8 http://www.doksihu  z i (k ) : ∀dz i (k ) < 0, és∀1 ≤ i ≤ n =  dz i (k )  = min{1.6620,09723,13928,22412,09440} = 09440  α d = min − A következő lépésben meghatározzuk az x, y és z vektorok új értékeit: Ami még az első iteráció végén hátra maradt az a primál és a duál célfüggvények, a dualitási rés és a μ kiszámítása. J dual = b T y = 255.1123 J primal = c T x = 264.7623 µ = 0.1 rés = z T x = 9.6500 rés = 0.1608 n Most már kezdődhet egy új

iterációs ciklus. A következő táblázatokban az iterációk során kapott eredményeket foglaltuk össze. Iteráció y1 y2 y3 1 -6,7037 -5,9459 -1,3029 2 -6,8831 -6,0962 -1,2426 3 -6,9097 -6,1130 -1,2181 4 -6,9120 -6,1148 -1,2162 5 -6,9122 -6,1149 -1,2162 6 -6,9122 -6,1149 -1,2162 9 http://www.doksihu Iteráció x1 x2 x3 x4 x5 x6 1 0,5963 4,5658 1,7842 0,1000 7,6136 0,9686 2 0,0298 4,6259 2,2351 0,0107 7,9310 0,2628 3 0,0081 4,4872 2,3707 0,0040 8,2053 0,0131 4 4,1052* 10 −4 4,4871 2,3775 2,0027* 10 −4 8,2147 0,0015 5 3,8129* 10 −5 4,4865 2,3783 1,9414* 10 −5 8,2161 7,6128 6 1,9717* 10 −6 4,4865 2,3784 9,7071* 10 −7 8,2162 6,6178* 10 −7 Iteráció z1 z2 z3 z4 z5 z6 1 3,2230 0,6218 1,0685 5,3988 0,1500 1,3430 2 2,7410 0,1156 0,0534 5,3746 0,0358 0,9900 3 2,6758 0,0087 0,0070 5,3329 0,0018 0,9936 4 2,6692 4,3616* 10 −4 8,4553* 10 −4 5,3313 2,4902* 10 −4

0,9937 5 2,6689 2,3544* 10 −5 4,3357* 10 −5 5,3311 1,2451* 10 −5 0,9933 6 2,6689 1,1772* 10 −6 2,2704* 10 −6 5,3311 6,6211* 10 −6 0,9932 1.2 Az elmozdulásvektor meghatározása A Template Method tervezési minta segítségével számítjuk ki az elmozdulásvektor értékét, amivel a harmadik fejezetben ismerkedhetünk meg. Az elmozdulásvektor meghatározásához használt algoritmusokat a Template Method a Modszer1, a Modszer2 és a Modszerfi alosztályokban tárolja. Az előző pontban megadott algoritmus keretében a különböző módszerek a v( µ ) vektor változásában tükröződnek ([6, 9, 10, 11]). A Modszer1 és Modszer2 alosztályok a v( µ ) vektorra vonatkozóan a következő két számítási módszert tartalmazzák: • µ *e − x z • 2* ( µ *xz − xz ) A Modszerfi egy másik tervezési minta segítségével választja ki az elmozdulásvektor kiszámításának a módszerét, ez a tervezési minta a Stratégia, amit szintén a

harmadik fejezetben tárgyalunk részletesebben. Az alábbi osztálydiagram a 10 http://www.doksihu Stratégia tervezési mintára jellemző, ezen belül látható a Modszerfi osztály, amely meghatározza a harmadik számítási módot. Vegyük észre, hogy ez a módszer általánosabb és könnyen változtatható. Ha új elmozdulásvektorra szeretnénk áttérni, akkor megváltoztathatjuk φa üggvényt f az á ltal, hogy származtatott osztályt hozhatunk létre a Fi osztályból. A ModszerFi Vkiszamitasa metódusa a következő képlet alapján számítja ki a v( µ ) vektort ([6]): • µ*  x*z    µ   x*z   ϕ ′  µ  ϕ (1) − ϕ  A φ és φ’ függvények a fifuggv és a fideriv metódusoknak felelnek meg. Az értékek kiszámításához a Stratégia tervezési mintát használjuk fel. Annak függvényében, hogy milyen stratégiát választunk, a fifuggv és fideriv metódusok a neki megfelelő érétkeket

térítik vissza. Például a NegyzetGyok osztály fifuggv metódusa a kapott érték négyzetgyökét téríti vissza, míg az Azonos osztály fifuggv metódusa a kapott értéket téríti vissza. A deriváltaknál pedig, az Azonos osztály 11 http://www.doksihu fideriv metódusa egyet térít vissza. Továbbá a Negyzetgyök osztály fideriv metódusa a négyzetgyök deriváltjának az értékét adja vissza. 2. Lineáris egyenletrendszerek 2.1 Rendezési heurisztikák A belsőpontos lineáris programozásban használt algoritmusokban, minden iteráció során egy szimmetrikus egyenletrendszer megoldására van szükség. A következő példán keresztül mutatjuk be, hogy hogyan lehet javítani a szimmetrikus egyenletrendszer megoldásának a teljesítményén. Ennek érdekében rendezési heurisztikákat használunk. Vegyünk egy olyan lineáris programozási feladatot, ahol az A mátrix öt sorral és tíz oszloppal rendelkezik, és jelöljük X-el a mátrix azon elemeit,

amelyek zérótól különböznek. Adott az A mátrix a következő képen: A szimmetrikus egyenletrendszer, amit az algoritmus megold, az AD 2 AT x = y alakú, ahol a használt D diagonálmátrix és a vektorok az algoritmushoz tartoznak. A szimmetrikus AD 2 AT mátrix a következő képen írható le: Ennek a mátrixnak a Cholesky faktorizációja teljesen sűrű lesz mivel a mátrix első sora nagyon sűrű. Ezt a következő ábra is mutatja: 12 http://www.doksihu Ahogy a példában is láttuk, hiába van elég ritka mátrixunk, ha az első sor sűrű, akkor az L Cholesky faktorizáció teljesen sűrű lesz. Hogy jobb teljesítményt érjünk el, ezért permutációkat és rendezéseket hajtunk végre az AD 2 AT mátrix sorain. Amint tudjuk, ebben a példában az A mátrix első sora okozza a problémát, ezért az egyenletrendszer első egyenletét kicseréljük az ötödik egyenlettel, vagyis az A mátrix első sorát kicseréljük az utolsóval, így az AD 2 AT

mátrix a következő képen fog kinézni: Hasonlóan, most kicseréljük az első oszlopot az ötödik oszloppal és elérünk a módosított AD 2 AT mátrix alakjához, amit a következő ábrán láthatunk is: Ebből a mátrixból a következő Cholesky faktorizációt kapjuk: A szimmetrikus egyenletrendszerek újrarendezésének a problémája a fenti okok miatt a figyelem központjába került. Mivel a problémának nincsen analitikus megoldása, különböző eredményes heurisztikákat dolgoztak ki. Ezek közül a leggyakrabban használt két rendező heurisztika a minimum-degree és a minimumlocal-fill-in. 3. Tervezési minták Ebben a fejezetben, a programban használt tervezési mintákat mutatjuk be. 3.1 A Template Method tervezési minta 13 http://www.doksihu (Sablon függvény) Az alábbiakban láthatjuk a Template Method célját, szerkezetét, a résztvevő osztályokat és az osztályok közötti együttműködést. Cél: • elkészíti egy algoritmus

vázát, az algoritmus egyes lépéseit alosztályokra ruházza át és ezek a lépések felülbírálhatók az algoritmus szerkezetének módosulása nélkül. Feladat: Vegyünk egy olyan példát, ahol létrehozzuk a Document és az Appplication osztályokat. Az Application osztály a létező dokumentumokat nyitja meg, míg a Document objektum a beolvasott dokumentum információit tartalmazza. Az alosztályok az alkalmazásban végzett műveleteknek megfelelőek lehetnek, például ha kiíratni akarunk a képernyőre, akkor létre lehet hozni a DrawingApplication és a DrawingDocument alosztályokat. Az elvont Application osztály meghatároz egy algoritmust egy dokumentum megnyitásához és olvasásához az OpenDocument metódusban: void Application::OpenDocument (const char* name) { if (!CanOpenDocument(name)) { // cannot handle this document return; 14 http://www.doksihu } Document* doc = DoCreateDocument(); if (doc) { docs->AddDocument(doc);

AboutToOpenDocument(doc); doc->Open(); doc->DoRead(); } } Az OpenDocument metódus meghatároz minden lépést a dokumentum megnyitásához és így az OpenDocument egy Template Method. Szerkezet: Résztvevők: • AbstractClass: o absztrakt primitív műveleteket határoz meg, amelyeket konkrét alosztályok valósítanak meg. Ezek képezik az algoritmus egyes lépéseit. o Egy sablonfüggvényt ad meg, ugyanakkor meghatározva egy algoritmus vázát is. A sablonfüggvény meghívja a primitív műveleteket, melyek az AbstractClass által megadott műveletek vagy más objektumok műveletei. • ConcreteClass: 15 http://www.doksihu o megvalósítja az elvont műveleteket, az által, hogy a származtatott osztályban megadja az algoritmus specifikus lépéseit. Együttműkődés: • a ConcreteClass implementálja az algoritmus változó lépéseit, míg az AbstractClass az algoritmus rögzített lépéseit valósítja meg. A programban használt szerkezet: A szamitasok

metódus tartalmazza a primál-duál trajektóriakövető algoritmust. Ebben az esetben, a Template Method a szamitasok metódus, mivel ő tartalmazza az algoritmus vázát és az elmozdulásvektorok kiszámításához szükséges v( µ ) vektor meghatározását, pedig átruházza a Modszer1, vagy a Modszer2, vagy a ModszerFi alosztályokra. A Vkiszamitasa metódus segítségével, pedig kiszámítjuk az elmozdulásvektor értékét. 3.2 A Strategy tervezési minta (Stratégia) A stratégia tervezési mintát a lineáris egyenletrendszer megoldási algoritmusának a kiválasztására és az elmozdulásvektor kiszámításánál a φ függvény típusának a kiválasztására használjuk. A következőkben a stratégia tervezési minta célját, szerkezetét, a résztvevő osztályokat és az osztályok közötti együttműködés rövid leírását olvashatjuk. Cél: 16 http://www.doksihu • egy algoritmus család meghatározása, úgy, hogy az algoritmusokat

különkülön egységbe zárjuk és egymással felcserélhetővé tesszük, ez által az algoritmus az őt felhasználó ügyféltől függetlenül változtatható. Szerkezet: Résztvevők: • Strategy: o Meghatároz egy egységes interfészt az összes algoritmus számára. A Context felhasználja ezt az interfészt, a ConcreteStrategy által megadott algoritmus meghívására. • ConcreteStrategy: o implementálja az algoritmust a Strategy interfész segítségével • Context: o a ConcreteStrategy által van kialakítva o egy hivatkozást tartalmaz egy Strategy objektumra o egy interfészt határozhat meg, amely lehetővé teszi a Strategy számára, hogy elérje az adatait Együttműködés: • a Strategy és a Context értekeznek, hogy megvalósítsák a kiválasztott algoritmust. Amikor az algoritmusra hivatkoznak, akkor a Context átad minden olyan adatot a Strategynek, amelyre szüksége van az algoritmusnak. Alternatív megoldásként a Context átadható

paraméterként a Strategy metódusainak. Így a Stratégia akármikor hivatkozhat a Contextre, mikor szükség van rá. • A Context továbbítja az ügyfelek kéréseit a Strategy-hez. Általában az ügyfelek létrehoznak egy ConcreteStrategy objektumot, mit átadnak a Contextnek és ezek után az ügyfelek kimondottan csak a Contexttel 17 http://www.doksihu kommunikálnak. Sokszor egy egész ConcreteStrategy osztály-család áll egy ügyfél rendelkezésére, ahonnan az ügyfél választhat. A programban használt szerkezetek: A v( µ ) vektor kiszámításánál használjuk az előbbi szerkezetet. A lineáris egyenletrendszer megoldásához használjuk az előző ábrán látható szerkezetet. A megold metódus, tartalmazza a lineáris egyenletrendszer megoldásához szükséges algoritmust, amely három féle lehet és könnyen változtatható. 18 http://www.doksihu 4. Adatok Ebben a fejezetben vizsgáljuk az adatok tárolását és a feldolgozását. 4.1 Az MPS

fájlformátum A fájlformátum az IBM Mathematical Programming System-ből származik és szabványosnak tekinthető a lineáris programozás modellek adatainak a tárolására. A ritka mátrixok hatékony tárolási módszerének lehet nevezni, mert a használt A mátrix zérótól különböző értékeit tárolja csak. Olvasható formátum és a legfontosabb, hogy a legtöbb rendszer felismeri. Az adatok hordozhatóak a különböző rendszerek között Az MPS formátum felosztja a modell elemeit különböző adatszakaszokra. Ezeket, a szakaszokat a következő ábrán láthatjuk: NAME ROWS COLUMNS RHS ENDATA Az első sorban a NAME mező található, amit a lineáris programozási modell nevének a megadására használunk. A szakaszok az ábrán látható sorrendben követik egymást, minden szakasznak van egy neve, ami az első oszlopban kell legyen, abban a sorban ahol az illető szakasz kezdődik. A neki megfelelő adatok a szakasznév utáni sorban kezdődnek. Az adatok

tárolása oszlopfüggő, vagyis meg van szabva minden elemnek az oszlopa. Ha ez nincsen betartva, akkor már nem hordoztatható a fájl a rendszerek között. Az utolsó sor az MPS fájlban az ENDDATA, mely az MPS fájl végét mutatja. Az említett szakaszokon kívül az MPS állomány még tartalmazhatja az alábbi szakaszokat: RANGES és BOUNDS. Ha ezek léteznek, akkor az RHS szakaszt követően lesznek megadva. 19 http://www.doksihu A szakaszok tartalma: • ROWS: o ez a szakasz a mátrix sorainak a típusait adja meg, amelyek a következők lehetnek:  N, a célfüggvényt jelenti  L, <= egyenlőtlenséget jelent  G, >= egyenlőtlenséget jelent  E, egyenlőséget jelent o az oszlophelyezések: •  2-3: a bejegyzés típusát tartalmazza  5-12: a sornak megfelelő nevet tartalmazza COLUMNS: o ez a szakasz tartalmazza a zérótól különböző elemeket, megadva a sor és oszlop indexeket o az adatok elhelyezése:  5-12 oszlop: egy

szót tartalmaz, mely az oszlopindexet fogja jelenteni  15-22 oszlop: egy szót tartalmaz, mely a sorindexet fogja jelenteni  25-36 oszlop: egy számot tartalmaz, amely az oszlopindexnek és a sorindexnek megfelelő értéket fogja jelenteni  40-47 oszlop: egy másik sorindexre utaló szót tartalmaz ez a sorrész  50-61 oszlop: az előbbi sorindexnek megfelelő értékét tartalmazza ez a rész o a 40-61. oszlopokba írt adatok opcionálisak, és fel lehet használni a hely jobb kihasználására, egy sorba való két elem írásával • RHS: o ez a szakasz tartalmazza a jobboldali, b vektort és a felépítése megegyezik a COLUMNS felépítésével, azzal a különbséggel, hogy a sor nevének a változója az rhs elemet azonosítja és minden sornak más sorazonosítót, használunk. • RANGES: 20 http://www.doksihu o ezt a szakaszt akkor használjuk, ha szükség van a jobboldali vektorra vonatkozó tartomány tárolására. A szerkezete megegyezik az

RHS szakasz szerkezetével. • BOUNDS: o Ezt a szakaszt akkor használjuk, amikor a megoldás vektor elemeinek a határai jelen vannak Példa: Maximalizáljuk 3 x1 + 2 x 2 2 x1 + x 2 ≤ 16 x1 + 3 x 2 ≤ 24 x1 + x 2 ≤ 10 x1 , x 2 ≥ 0 Az MPS fájl: NAME PLAN ROWS N OBJ L SOR1 L SOR2 L SOR3 COLUMNS OSZL1 SOR1 2.00 OSZL1 SOR3 1.00 OSZL1 OBJ OSZL1 SOR1 1.00 OSZL1 SOR3 1.00 OSZL1 OBJ 2.00 RHS SOR1 16.00 RHS SOR3 10.00 SOR2 1.00 SOR2 3.00 3.00 RHS SOR2 24.00 ENDATA 4.2 Az adatok beolvasása 21 http://www.doksihu Az adatok *.MPS kiterjesztésű fájlban találhatók Az adatok beolvasásához a lexikális és a szintaktikus elemzést használom. A lexikális elemzőnek két alapvető feladata van: • az elemzendő karaktersorozat egységekre bontása és egy szimbólumsorozat előállítása, illetve a szimbólumok szövegének, típusának és helyének a meghatározása. A lexikális elemző a bemeneti karaktersorozatot tehát egy

szimbólumsorozattá alakítja át. • annak az eldöntése, hogy a sorozat tartalmaz-e lexikális hibákat vagy sem. A lexikális elemzést egy véges determenisztikus automatával végezzük. Az automata 4 állapottal és 11 állapotátmenettel rendelkezik. Az automata jellegzetessége, hogy tartalmaz egy semleges állapotot (NONE), amely egyben a kezdőállapot is, az automata ide lépik vissza, valahányszor egy fehér karaktert talál. Az elemzéshez a program egy puffert használ, amiben mindig azt a karaktersorozatot őrzi meg, amelyet a későbbiekben menteni szeretne. Például, egy azonosító esetén meg kell jegyeznünk annak nevét. A fehérkaraktereket figyelmen kívül hagyjuk. Átmenetek: 1. None-None: ‘ ’,#13,#10,#9 2. None-Number: ‘0’’9’,’’,’-’ 3. None-Identifier: ‘A’’Z’ 4. None-Fatal error: Not(‘A’’Z’,’0’’9’,’ ‘,#13,#10, #9) 5. Number-None: ‘ ‘,#13,#10,#9 6. Number-Number: ‘0’’9’,’’ 7.

Number-Identifier: ‘A’’Z’ 8. Number Fatal error: Not(‘0’’9’,’A’’Z’,’ ‘,#13, #10,#9) 9. Identifier-Identifier: ‘0’’9’,’A’’Z’ 10. Identifier-None: ‘ ‘,#13,#10,#9 11. Identifier-Fatal error: Not(‘09’,’A’’Z’,’ ‘,#13, #10,#9) A következő ábrán látható a lexikális elemzéshez használt véges determinisztikus automata. 22 http://www.doksihu 8 6 Number 2 1 5 Fatalerror 7 None 3 4 Identifier 10 11 Miután az adatfájl lexikális elemeit meghatároztuk, következik a szintaktikus elemzése, és ha nincs hiba, akkor az adatok továbbküldése a programhoz. A szintaktikus elemző feladata az adatfájl struktúrájának a felismerése és az adatok kiolvasása, vagyis a mátrix és a vektorok feltöltése. Az adatfájlt a lexikális elemző egy terminális szimbólumokból álló sorozattá alakítja, ez lesz a szintaktikus elemzés bemeneti adata. A szintaktikus elemző feladata eldönteni, hogy ez a

szimbólumsorozat a nyelv egy mondata-e. 23 9 http://www.doksihu Könyvészet: [1] * : Data & object factory in design patterns (http://www.dofactorycom/Patterns/Patternsaspx) [2] A. Arbel Exploring Interior-Point Linear Programming: Algorithms and Software The MIT Press, 1993. [3] J.W Cooper The Design Patterns Java Companion Addison-Wessley Design Patterns Series, 1998. [4] Z. Csörnyei Fordítási algoritmusok, Erdélyi Tankönyvtanács, Kolozsvár, 2002 [5] Zs. Darvay Belső pontos módszerek a lineáris programozásban Elte, Budapest 1997. [6] Zs. Darvay Egy új prediktor-korrektor algoritmus a lineáris programozásban Alkalmazott matematikai lapok, 22:135-161, 2005. [7] B. Eckel Thinking in Patterns Online Book 2003 [8] E. Gamma, R Helm, R Jhonson, and J Vlissides Design Patterns: Elements of Reusable Object-Oriented Software, Addison Wesley, 1995. [9] J. Peng, C Roos, and T Terlaky A new and efficient large-update interior-point method for linear optimization. Journal

of Computational Technologies, 6(4):61–80, 2001. [10] J. Peng, C Roos, and T Terlaky A new class of polynomial primaldual methods for linear and semidefinite optimization. European Journal of Operational Research, 143:234–256, 2002. [11] J. Peng, C Roos, and T Terlaky Self-Regular Functions: a New Paradigm for Primal-Dual Interior-Point Methods. Princeton University Press, 2002 [12] C. Roos, T Terlaky, and J-Ph Vial Theory and Algorithms for Linear Optimization. An Interior Approach John Wiley & Sons, Chichester, UK, 1997 [13] R. J Vanderbei Linear Programming: Foundations and Extensions International Series in Operations Research & Management Science, Springer, 2001. 24