A matematikai modellezés hatása nemlineáris optimalizálási feladatok megoldásának hatékonyságára

Előnézet	PDF (disszertáció) Download (1MB) | Előnézet
Előnézet	PDF (tézisfüzet) Download (470kB) | Előnézet
Előnézet	PDF (tézisfüzet) Download (468kB) | Előnézet

Absztrakt (kivonat) idegen nyelven

Az optimalizálási problémák matematikai modellezése során hozott döntések jelentős mértékben befolyásolhatják az alkalmazott megoldó hatékonyságát, a feladat komplexitását. Egy optimalizálási feladat átfogalmazása azonban sokszor az egyéni intuíción túlmutató automatikus módszerekkel is lehetséges. A lineáris programozási feladatok szimplex módszer számára legelőnyösebb formájának felírása például már az 1970-es években is foglalkoztatta a matematikusokat. Ezek a korai eredmények mára az AMPL előfeldolgozóba épülve szinte észrevétlenül hasznosulnak. Számos kutatás foglalkozik napjainkban a (vegyes-)egészértékű programozási feladatok kedvezőbb, ill. adott körülmények között megoldható alakba történő átfogalmazásának lehetőségeivel, habár ezek az átalakítások általában bizonyos feltételek relaxációjával és a feladat dimenziójának növelésével járnak együtt. Meglepően csekély számú publikáció koncentrál azonban a nemlineáris optimalizálási feladatok ekvivalens átalakításait eredményező, automatizálható szimbolikus eljárásokra. Erre a területre fókuszál dolgozatom első fele. A fellelhető szakirodalom elméleti eredményeinek ismeretében feltételezhető volt, hogy napjaink nagytudású számítógépes algebra rendszerei alkalmasak egy szimbolikus, tehát a számítási pontosságot garantáló, nemlineáris optimalizálási feladatok ekvivalens átírásait megadó alkalmazás létrehozására, amely lehetőséget ad a korábban publikált algoritmusok integrálására, tesztelésére, továbbá inspirációt nyújthat ezek továbbfejlesztéséhez. Ezzel a céllal elkészült egy, a feltétel nélküli nemlineáris optimalizálási feladatokon nemlineáris koordináta-transzformációkat végrehajtó Maple program. Alapos tesztelés során felderítettem azokat a specifikus területeket, amelyek egy ilyen algoritmus implementálása során kritikusak lehetnek, és megállapítottam, hogy a Maple rendszer néhány dokumentálatlan hibája és általános felhasználásra tervezett, a konkrét célnak nem megfelelő minőségben megvalósított funkciója komoly akadályokat állít a bővítés elé. Tanulmányoztam a rendelkezésre álló kereskedelmi és szabad szoftveres alternatívákat, és a programozó számára nyújtott rugalmassága, erős fejlesztői háttere és a legújabb matematikai eredményeket felvonultató saját, széles körű funkcionalitása miatt a Mathematica programot találtam a legjobb alapnak a további fejlesztések számára. Ez alapján korábbi programunkat további funkciókkal bővítve átültettem Mathematica alá, és empirikus úton bizonyítottam, hogy előfeldolgozóként alkalmazva az általunk javasolt szimbolikus transzformációk hasznosak egy klasszikus (numerikus) heurisztikus megoldó számára. Új elméleti eredmények születtek a párhuzamosan végrehajtható nemlineáris koordináta-transzformációkkal és a feladathoz adott feltételekkel kapcsolatban, továbbá készítettem egy online demonstrációs oldalt az eljárás bemutatására. Az értekezés második felében egy konkrét feladathoz, az elosztott tartalom-megosztó rendszerekben felmerülő méltányos (max-min fair) sávszélesség-kiosztás problémájához kapcsolódó modellezési kérdéseket vizsgáltam. A feladatra sikerült egy új, egzakt matematikai programozási modellt adnom, és az ezen alapuló algoritmus helyességét elméleti úton bizonyítanom. Elkészült az algoritmus AMPL nyelvű megvalósítása, aminek a teljesítményét numerikus tesztek révén összehasonlítottam a feladat megoldására korábban létező programmal. Az eredmény több tekintetben pozitív. Az implementáció során, részben az elméleti eredményekhez kapcsolódóan, számos modellezési ötlet merült fel, ezért az értekezésben egy külön fejezet foglalkozik ezen technikák hatáselemzésével. A max-min méltányos erőforrás-kiosztást előállító modell tizenkét változatát hasonlítottam össze egy kiterjedt numerikus tesztelés során, két professzionális megoldó és huszonhét nagyméretű tesztfeladat bevonásával.

Tétel nézet