[Mat08] BME Optimalizálás Szeminárium

[Csilla Majoros]

*Meghívó*

Szeretettel várunk minden kedves érdeklődőt a BME
Optimalizálás Szemináriumán,


ahol *június 16*-án* 14.15*-től a *H306*-os teremben

két matematikus MSc-s hallgató számol be a szakdolgozatáról.


Az előadások részletei:

*Varga Anita:* LP-megoldó bővítése kombinatorikus algoritmusokkal

*Kivonat:*
A dolgozat célja az volt, hogy létrehozzunk egy olyan modult az XPRESS
optimalizáló
szoftverhez, amely képes hatékonyabban kezelni az olyan problémákat,
amelyek valamilyen gráfelméleti feladatként is megfogalmazhatóak lennének,
felhasználva a LEMON C++ könyvtárat.
A létrehozott modul teszteléséhez a kvadratikus hozzárendelési feladat
közelítésére szolgáló
EDAP-algoritmus (Enhanced Dual Ascent Procedure - Javított duál növekedés
módszere) két
változatát használtuk. Az algoritmus során számos lineáris hozzárendelési
feladatot kell megoldanunk, ezeket az egyik változatban lineáris
programozási feladatként oldattuk meg az XPRESS-szel, a másikban pedig
hálózati folyam feladatként, alkalmazva az új mmgraph modult.
Összességében a létrehozott modul nagyon hatékonynak bizonyult az
EDAP-algoritmus futási
idejének csökkentésében, minden tesztfeladatra lényegesen rövidebb idő
alatt tudtuk előállítani az alsó korlátokat. Egyes esetekben az
iterációnkénti futási idő akár ötvenedére csökkent.


és

*Deák Attila*: Belsőpontos módszer geometriai programozási feladatra

*Kivonat:*
A 2015/16-os tavaszi félévében készített diplomamunkám során egy speciális
nemlineáris programozási témakörrel, a geometriai programozással
foglalkoztam. Ennek a témakörnek a megjelenése 1958-ra tehető, mikor W.B.
White, S.M. Johnson és G.B. Dantzig cikkükben a kémiai egyensúlyi feladatot
vizsgálták matematikai módszerekkel. Munkámban kitértem rá, hogy
tulajdonképpen az ekkor felírt matematikai programozási feladat a későbbi
geometriai programozási feladat duális feladata volt. Az ezt követő években
a kutatók a geometriai egyenlőtlenséget használták különböző optimalizálási
feladatokra. 1966-ban az addigi közel 10 éves tapasztalatokat és
eredményeket R.J. Duffin, E.L. Peterson és C. Zener egy átfogó műben
egységesítette. Nagyobb áttörésnek azonban az 1973-ban megjelent Klafszky
Emil kandidátusi értékezése számított, ahol Klafszky egy új megközelítést
használt a geometriai programozás felépítéséhez.

A diplomamunkám során a fent említett geometriai programozási feladatpár
megoldására használható belsőpontos algoritmussal is foglalkoztam. Az első
belsőpontos algoritmus Karmarkar nevéhez köthető, aki lineáris programozási
feladatot oldott meg polinomiális időben. Később többen vizsgálták, hogy ez
az algoritmus hogyan vihető át a logaritmikus barrier algoritmusokhoz,
melyek eredményeseknek bizonyultak az általános nemlineáris programozási
feladatok megoldásainál. Ezután Nesterov és Nemirowskii általános konvex
programozási feladatok belsőpontos módszereit vizsgálták, emellett
megmutatták, hogy bizonyos simasági feltételek teljesülése esetén az egyes
konvex programozási feladatokat megoldja a logaritmikus barrier algoritmus.
Áttörésnek számított 1991-ben K.O. Kortanek, X. Xu, Y. Ye primál-duál
lineáris feltételeket használó konvex programozási algoritmusa.

Az előadásomban a szükséges, rövid történeti bevezető után kitérek az imént
említett Klafszky-féle feladatpárra,dualitás tételekre és az bevezetőben
említett kémiai egyensúlyi feladatra, megmutatva, hogy valóban a geometriai
programozási duális feladata. Ehhez szükségem van a monom és pozinóm
függvények fogalmára és a pozinóm programozási feladatpárra. Megmutatom,
hogy milyen kapcsolat van ezen programozási feladat és a Klafszky-féle
geometriai programozási feladatok között. Végül kitérek a Kortanek, Xu és
Ye által bevezetett belsőpontos algoritmusra, kitérve a lépésszámra,
önkorlátozó tulajdonságra és ezen algoritmus továbbgondolására.


Üdvözlettel,

Majoros Csilla
--------- következő rész ---------
Egy csatolt HTML állomány át lett konvertálva...
URL: <http://lists.math.bme.hu/pipermail/mat08/attachments/20160615/aaca83f7/attachment-0001.html>