A centrális út módszere
Dátum
Authors
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
DOI
Absztrakt
A lineáris programozási feladatok a feltételes szélsőérték problémák igen speciális osztályát képezik. Ezek egyik sajátossága, hogy a megoldást szolgáltató szimplex módszer könnyen programozható és hatékony algoritmust biztosít. Azonban léteznek a szimplex módszer mellett egyéb algoritmusok is. A szimplex módszernél a határpontokon van a hangsúly, ezzel szemben az úgynevezett belsőpontos módszerek az optimumot a feltételi halmaz belső pontjain keresztül érik el. Az egyik legfontosabb belsőpontos módszer matematikai háttere az úgynevezett barrier-probléma, melynek alapgondolata, hogy az eredeti lineáris programozási feladat célfüggvényét egy logaritmikusan perturbált egyparaméteres célfüggvénycsaládra cseréljük. Az optimumok a paraméter függvényében egy görbét határoznak meg a feltételi halmazban, ez a görbe a centrális út. Jelen szakdolgozat legfontosabb célkitűzése a barrier-probléma elméleti hátterének tárgyalása a konvex analízis módszereivel. Fő eredményünkben azt igazoljuk, hogy a centrális út optimumhoz érkezik, amennyiben a primál–duál feladatpár feltételi halmazai korlátosak és belsejük nem üres. A szimplex módszer mellett a centrális út módszere is igen hatékony, a gyakorlatban jól alkalmazható eljárást biztosít.