<div dir="ltr"><div style="font-size:12.8px;text-align:center"><font size="4"><b>Meghívó</b></font><br></div><font style="font-size:12.8px" size="4"><br></font><div><div style="text-align:center">Szeretettel várunk minden kedves érdeklődőt a BME<br><span>Optimalizálás</span> <span>Szeminárium</span>án,<br></div><br></div><br><div style="text-align:center">ahol <b style="font-family:arial,helvetica,sans-serif">június 16</b><span style="font-family:arial,helvetica,sans-serif">-án</span><b style="font-family:arial,helvetica,sans-serif"> 14.15</b><span style="font-family:arial,helvetica,sans-serif">-től a </span><b style="font-family:arial,helvetica,sans-serif">H306</b><span style="font-family:arial,helvetica,sans-serif">-os teremben<br><br></span></div><span style="font-family:arial,helvetica,sans-serif"><b>három</b> matematikus MSc-s hallgató számol be a szakdolgozatáról.<br><br></span><div style="text-align:left"><br></div><div style="text-align:left">Az előadások részletei:<br><br></div><div style="text-align:left"><span style="font-family:arial,helvetica,sans-serif"><font size="2"><b>Varga Anita:</b> LP-megoldó
bővítése kombinatorikus algoritmusokkal<br></font></span><div><br><b>Kivonat:</b></div><div><div>A dolgozat célja az volt, hogy létrehozzunk egy olyan modult az XPRESS optimalizáló</div><div>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.</div><div>A létrehozott modul teszteléséhez a kvadratikus hozzárendelési feladat közelítésére szolgáló</div><div>EDAP-algoritmus (Enhanced Dual Ascent Procedure - Javított duál növekedés módszere) két</div><div>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.</div><div>Összességében a létrehozott modul nagyon hatékonynak bizonyult az EDAP-algoritmus futási</div><div>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.<br><br></div></div>
</div><div style="text-align:left">
<br><br>
</div><div style="text-align:left"><font size="2"><span style="font-family:arial,helvetica,sans-serif"><b>Deák
Attila</b>: Belsőpontos
módszer geometriai programozási feladatra</span></font><font size="2"><span style="font-family:arial,helvetica,sans-serif"><br><br><b>Kivonat:</b><br>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. </span></font>
</div><font size="2"><span style="font-family:arial,helvetica,sans-serif">
</span></font><p style="margin-bottom:0in;line-height:100%" align="justify"><font size="2"><span style="font-family:arial,helvetica,sans-serif"><a name="m_4868014630628248897__GoBack"></a>
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.</span></font></p><font size="2"><span style="font-family:arial,helvetica,sans-serif">
</span></font><p style="margin-bottom:0in;line-height:100%" align="justify"><font size="2"><span style="font-family:arial,helvetica,sans-serif">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.</span></font></p><p style="margin-bottom:0in;line-height:100%" align="justify"><font size="2"><span style="font-family:arial,helvetica,sans-serif"><br></span></font></p><p style="margin-bottom:0in;line-height:100%" align="justify"><font size="2"><span style="font-family:arial,helvetica,sans-serif">és<br></span></font></p><p style="margin-bottom:0in;line-height:100%" align="justify"><font size="2"><span style="font-family:arial,helvetica,sans-serif"><b><br></b></span></font></p><p style="margin-bottom:0in;line-height:100%" align="justify"><font size="2"><span style="font-family:arial,helvetica,sans-serif"><b>Huszti Marcell: </b>Bilineáris programozás módszerei és alkalmazásai</span></font></p><p style="margin-bottom:0in;line-height:100%" align="justify"><span style="font-family:arial,helvetica,sans-serif"><font size="2"><b>Kivonat:</b></font></span><font size="2"><span style="font-family:arial,helvetica,sans-serif"> A diplomamunkámban bemutatom a bilineáris programozási feladat elhelyezke-<br>dését az optimalizálási feladatok körében. Láthatjuk, hogy a bilineáris programozás<br>legegyszerűbb esete, ha a változóinkhoz tartozó feltételhalmazok diszjunktak. Eb-<br>ben az esetben a vágósíkos algoritmus jól használható a megoldás megtalálására<br>és, ha létezik megoldása, akkor létezik olyan megoldása is, amely a megengedett<br>megoldásokat alkotó poliéderek extremális pontja. A bilineáris programozás ezen<br>fajtája ekvivalens többek között a kvadratikus programozási feladattal, amelynek a<br>megoldására ismert a minimálindexes criss-cross algoritmus, és továbbá ekvivalens<br>a konkáv minimalizálási feladattal.<br>A következő és ennél bonyolultabb esete a bilineáris programozási feladatnak,<br>ha a feltételhalmazok összefüggőek. Ebben az esetben a bilineáris programozási fel-<br>adat a bikonvex programozási feladat egy speciális esete, amelyre megállapítható,<br>hogyha van optimális megoldása, akkor van a megengedettségi halmaz határán lévő<br>optimális megoldása is. Viszont ha a feltételhalmazaink nem konvexek a bilineáris<br>programozási feladat NP-nehézzé válik. Erre a típusra érdekes példa, az olajiparban<br>is felmerülő, pooling probléma. A pooling probléma egy szállítási feladat (amely egy<br>LP feladat) továbbfejlesztése. A minőségi paraméterek azok, amelyek bevezetésével<br>a feladat NP-nehéz lesz, viszont mivel a gyakorlatban gyakran előkerülő példa, ezért<br>a megoldásának keresése központi téma, aminek eredményeképpen sok különböző<br>modellfelírása jött létre.<br>A numerikus eredmények azt mutatják, hogy a feladat NP-nehézsége miatt a<br>beépített nemlineáris megoldóprogramok nagy feladatok esetén alulmúlják a heu-<br>risztikus megközelítéseket. Ebből kifolyólag a jövőben új heurisztikus megközelítések<br>keresése és kombinálása meglévő algoritmusokkal az optimálishoz közeli eredmények<br>eléréséhez vezethet.<br></span></font></p><p style="margin-bottom:0in;line-height:100%" align="justify"><font size="2"><span style="font-family:arial,helvetica,sans-serif"><br></span></font></p><p style="margin-bottom:0in;line-height:100%" align="justify"><font size="2"><span style="font-family:arial,helvetica,sans-serif">Üdvözlettel,</span></font></p><font size="2"><span style="font-family:arial,helvetica,sans-serif">Majoros Csilla</span></font></div>