[Mat08] BME Optimalizálás Szeminárium - Helyesbítés

[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

*három* 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.



*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.


és


*Huszti Marcell: *Bilineáris programozás módszerei és alkalmazásai

*Kivonat:* A diplomamunkámban bemutatom a bilineáris programozási feladat
elhelyezke-
dését az optimalizálási feladatok körében. Láthatjuk, hogy a bilineáris
programozás
legegyszerűbb esete, ha a változóinkhoz tartozó feltételhalmazok
diszjunktak. Eb-
ben az esetben a vágósíkos algoritmus jól használható a megoldás
megtalálására
és, ha létezik megoldása, akkor létezik olyan megoldása is, amely a
megengedett
megoldásokat alkotó poliéderek extremális pontja. A bilineáris programozás
ezen
fajtája ekvivalens többek között a kvadratikus programozási feladattal,
amelynek a
megoldására ismert a minimálindexes criss-cross algoritmus, és továbbá
ekvivalens
a konkáv minimalizálási feladattal.
A következő és ennél bonyolultabb esete a bilineáris programozási
feladatnak,
ha a feltételhalmazok összefüggőek. Ebben az esetben a bilineáris
programozási fel-
adat a bikonvex programozási feladat egy speciális esete, amelyre
megállapítható,
hogyha van optimális megoldása, akkor van a megengedettségi halmaz határán
lévő
optimális megoldása is. Viszont ha a feltételhalmazaink nem konvexek a
bilineáris
programozási feladat NP-nehézzé válik. Erre a típusra érdekes példa, az
olajiparban
is felmerülő, pooling probléma. A pooling probléma egy szállítási feladat
(amely egy
LP feladat) továbbfejlesztése. A minőségi paraméterek azok, amelyek
bevezetésével
a feladat NP-nehéz lesz, viszont mivel a gyakorlatban gyakran előkerülő
példa, ezért
a megoldásának keresése központi téma, aminek eredményeképpen sok különböző
modellfelírása jött létre.
A numerikus eredmények azt mutatják, hogy a feladat NP-nehézsége miatt a
beépített nemlineáris megoldóprogramok nagy feladatok esetén alulmúlják a
heu-
risztikus megközelítéseket. Ebből kifolyólag a jövőben új heurisztikus
megközelítések
keresése és kombinálása meglévő algoritmusokkal az optimálishoz közeli
eredmények
eléréséhez vezethet.


Ü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/f8ed2e33/attachment-0001.html>