Optimalizálási eljárások ea. (MSc)

Tanszék: Halmazelmélet és Matematikai Logika Tanszék

Tematika:
Optimalizálási problémák matematikai formalizálása, példák. Lagrangue dualizáció, példák. Gyenge dualitás tétel. Erős dualitás. Karusk-Kuhn-Tucker tétel. A lineáris programozás geometriája. Egész értékűségi feltételek: totálisan unimoduláris mátrixok, TDI egyenlőtlenség-rendszerek. LP módszer a konbinatorikában: gráfok párosítási politópja. Edmonds tétele, Cunningham-Marsh-tétel. Független ponthalmazok gráfokban, perfekt gráfok és kapcsolatuk az LP módszerrel. Szemidefinit programozás, az alapfeladat. Dualitás. Kombinatorikus alkalmazások: SCP relaxációk, approximációs algoritmusok nehéz problémákra. Ellipszoidok geometriája, az ellipszoid módszer. Barrier függvények, belső pontos módszerek. Heurisztikák, branch and bound módszerek.

Előfeltétel: nincs.

Helyettesítő tárgyak: nincsenek.

Előadás:
Kurzuskód: MMNK52E Kredit: 6 Óraszám: 2 hetente