Thesis

Continuous Optimization
pdf ps

Lineáris Optimalizálás: elmélet és primál-duál belsőpontos algoritmusok [in Hungarian], M.Sc. Thesis, by Nagy Marianna[pdf]  [ps]

A szakdolgozat célja betekintést nyújtani a belsőpontos módszerek világába. A lineáris optimalizálás feladatainak megoldására legelterjedtebb eljárás a szimplex módszer (1947), ám egyre ismertebbé és elfogadottabbá válnak a belsőpontos algoritmusok (1984) is. A két különböző módszercsalád összevetését találhatjuk meg Illés és Terlaky cikkében, melyből néhány fontosabb gondolatot most itt is megemlítenénk.

Talán a legszembetûnőbb különbség az algoritmusok geometriájában jelentkezik. Míg a szimplex algoritmus a polinom csúcsait látogatja végig, addig a belsőpontos algoritmusok a megengedett tartomány (relatív) belsejében haladó centrális utat követve konvergálnak a megoldáshoz. Mindkét módszer a gyakorlatban jól alkalmazható, ezt igazolja az is, hogy a főbb programcsomagok részét képezi mindkét algoritmus-család egy-egy implementációja. Ennek ellenére a szimplex módszer esetében léteznek olyan feladatok, melyekre exponenciális a futásideje --- a legelső exponenciális ellenpélda Klee és Minty nevéhez fûződik (1970). A belsőpontos algoritmusokkal polinom időben állítunk elő egy jól közelítő megoldást. Megfelelő pontosság esetén ebből a pontból egy erősen polinomiális eljárással nyerünk szigorúan komplementáris egzakt megoldást, sőt létezik olyan polinomiális algoritmus, mely ennek a pontnak az ismeretében optimális bázismegoldást nyújt. Ezzel szemben a szimplex algoritmussal kapott optimális bázismegoldásból szigorúan komplementáris megoldás előállítása degeneráció esetén közel olyan nehéz, mint az eredeti feladat.
Minden algoritmus esetén fontos kérdés az induló pont megadása. Ez a szimplex algoritmus esetén az első fázis feladat megoldásával állítható elő. A belsőpontos módszerek esetén két lehetőség áll rendelkezésünkre, vagy mint egy infizíbilis feladatot oldjuk meg a problémát --- ekkor belátható, hogy az algoritmus végére az eredeti feltételeinket kielégítő megoldást kapunk--- vagy pedig egy beágyazást alkalmazunk, ám ekkor megnő a feladat dimenziója.

Mint láthatjuk mindkét módszernek vannak előnyei és hátrányai is a másikkal szemben. A gyakorlati problémák esetében ezeknek megfelelően kell eldönteni, melyik eljárással oldjuk meg a problémát, például megmutatható, hogy a vágósíkos módszerek esetén a szimplex algoritmus, míg az érzékenységvizsgálat esetén a belsőpontos algoritmusok a hatékonyabbak.

A dolgozat következő fejezetében a szükséges elméletet ismertetjük. Majd a harmadik fejezetben megmutatjuk, hogy létezik polinomiális belsőpontos módszer (Dikin algoritmus), és polinom időben pontos megoldás is előállítható. A negyedik fejezetben a primál--duál feladatpárt visszavezetjük a ferdén szimmetrikus önduális feladatosztályra --- melyet a második fejezetben tárgyalunk --- a Goldman--Tucker modellen keresztül. Továbbá a lineáris optimalizálás néhány alapvető tételére adunk bizonyítást az ismertetett eredményekre támaszkodva. A dolgozat második felében konkrét, a gyakorlatban is használt algoritmusokat mutatunk be egyfajta fejlődési utat követve. Ezen kívül minden fejezet bevezetésének végén kitekintést adunk, hogy az adott fejezet eredmenyeinek milyen általánosításai születtek már a belsőpontos algoritmusokra értelmezhető legbővebb, $\cP_*$-mátrixokkal definiált lineáris komplementaritási feladatosztály esetén.

     
pdf  

Sensitivity analysis for production planning model of an oil company , M.Sc. Thesis, by Yu Da   [pdf

The optimization or mathematical programming is the branch of mathematics dealing with methods of optimization of some decision variables which are restricted by given constraints. Interest in optimization methods and their applications has become very widespread. They are used in almost all area of the industry. Still, the applications must not be isolated from theory, otherwise the solutions can be inaccurate, inexact or even turn aside from the truth. Therefore, it is always necessary for all the applied mathematicians to give mathematical arguments and analysis for each step of resolution process in order to approximate the real life problems in a correct way. In this thesis, a production planning model of an oil company and related topics, like solution methods, important properties of the problem etc.
are introduced. This is a typical example for applying optimization in the real life. In order to discuss the model in-depth, the specification of linear programming, linear programming pivot algorithms, degeneracy are studied in the first three sections. Afterwards, sensitivity analysis, parametric programming are presented. Computer programs have become essential tools by modelling and analyzing as in the case studied. In the last part of this thesis the documentation of our program are included, with which it is possible to analyze the model and the solutions. Our program is an LP modelling and analyzing tool for general purpose. The linear programming problem can be described by defining it’s constraints and variables. The program uses the mps file format, as the models were given in this format. With the program we can modify the model description, e.g. any value given in the model can be altered, the order of the variables can be changed, the objective function can be transformed to a constraint. With the program we can read the solutions of the model and check, whether the solution really satisfies the constraint conditions. Furthermore, if the solution is outside of the feasible solution set the right-hand side can be changed by a single click to make it feasible.

pdf ps

Matrix classes and linear complementarity problems [in Hungarian], M.Sc. Thesis, by Zsolt Csizmadia   [pdf]  [ps]

A dolgozat a lineáris komplementaritási feladatok (LCP) vizsgálatakor felmerülő főbb mátrixosztályok áttekintésére vállalkozik. Egyben áttekintést ad az LCP feladatok jelentősebb előfordulásairól. A dolgozat önálló eredményként új típusú criss-cross módszereket általánosít elégséges mátrixú LCP feladatokra. A legtöbb LCP megoldó algoritmus előre feltételez bizonyos tulajdonságokat a feladat mátrixáról.

Egy mátrix elégségessége nehezen ellenőrizhető tulajdonság (nem ismert rá polinomiális eljárás). Az algoritmus Zhang lineáris programozási, illetve Akkeles-Balogh-Illés LCP-QP feladatra adott criss-cross típusú algoritmusával rokon. Az algoritmus abban tér el az előzőektől, hogy számára nem szükséges a priori információ a mátrix tulajdonságáról. Az algoritmus leállási kritériumai: megoldja az LCP feladatot, megoldja az LCP feladat duálját, illetve kijelzi azt, hogy a feladat mátrixa nem elégséges és ezért ciklizálásra kerül(het)ne sor. Annak ellenére, hogy az algoritmus általánosabb feltételek mellett dolgozik, mint Akkelesék módszere, mégis sikerült a végességet egyszerûbben bizonyítani.

Az algoritmus végessége egyben új, konstruktív bizonyítást jelent az LCP Dualitás tételére.

     


Department of Operations Research, Eötvös Loránd University of Sciences
1117 Budapest, Pázmány Péter Sétány 1/c, Hungary
Contact: Adrienn Nagy - orr@cs.elte.hu