Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Optimalizálás és alkalmazásai

    A tantárgy angol neve: Optimalization and Its Applications

    Adatlap utolsó módosítása: 2010. szeptember 16.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar

    Villamosmérnöki Szak

    Doktoranduszképzés

    (kötelezően választható)

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VITMDV01   4/0/0/v 5  
    3. A tantárgyfelelős személy és tanszék Dr. Rétvári Gábor Ferenc, Távközlési és Médiainformatikai Tanszék
    4. A tantárgy előadója
    NévBeosztás
    Tanszék
    Dr. Rétvári Gábor
    tud. munkatárs
    TMIT
    Dr. Tapolcai János
    egyetemi adjunktusTMIT
    Dr. Cinkler Tibor
    egyetemi docens
    TMIT
    6. Előtanulmányi rend
    Ajánlott:
    A következő tárgyak korábbi hallgatása esetén ez a tantárgy nem vehető fel:
    VITMD097     Alkalmazott optimalizálás és játékelmélet
    7. A tantárgy célkitűzése

    A numerikus optimalizálási eljárások fontos szerepet töltenek be a műszaki feladatok megoldásában. A tárgy sok példán keresztül bemutatja a műszaki természetű -- kiemelten a villamosmérnöki tervezésben előforduló -- problémák megfogalmazását optimalizálási feladat formájában, majd a megoldási módszerek ismertetése után rámutat a tipikus modellezési hibákra is. Kiemelt hangsúlyt kap a lineáris programozás és az egészértékű programozás alapjainak elsajátítása, melyek segítségével vizsgáljuk az egyes optimalizálási feladatok sajátosságait. Bemutatjuk a nemlineáris, és a heurisztikus megoldó algoritmusokat is. A hallgatók megismerik a legelterjedtebb optimalizáló és modellező programcsomagokat, hogy a tanultakat a gyakorlatban kamatoztathassák.

    8. A tantárgy részletes tematikája
    • Bevezetés a numerikus optimalizálásba: alapfogalmak, feltételes és feltétel nélküli feladatok, célfüggvény(ek), osztályozás (lineáris, kvadratikus, nemlineáris, ...), az algoritmusok iteratív jellege. Modellezési technikák, a modellezés lépései, hibafüggvények. Konkrét műszaki problémák megfogalmazása optimalizálási feladatként (pl. hálózati útvonalválasztás, hálózattervezés, optimális szabályozás, készletoptimalizálás)
    • A lineáris programozás alapjai. A lineáris programok általános formája. Példák. Lineáris és nemlineáris optimalizálási problémák megfogalmazása lineáris program formájában. A lineáris programmal modellezhető problémák általános jellemzői, példák és alkalmazások
    • Lineáris programok megoldása: bevezetés a konvex analízisbe, poliéderek, lineáris programok grafikus megoldása, a szimplex tábla, bázismegoldások, a szimplex algoritmus, optimalitás, nemkorlátos megoldások, a degeneráció fogalma és kezelése, komplexitás. Példák megoldása a szimplex tábla segítségével
    • Lineáris programok duáljai és a duál szimplex: Farkas lemmája, a dualitás fogalma, a duális előállítása, a dualitás gyenge és erős tétele, a duál szimplex algoritmus. Példák megoldása a duál szimplex segítségével
    • A lineáris programozás klasszikus alkalmazásai: a szállítási probléma, az ütemezési probléma, hálózati folyamproblémák, folyamok egészértékűsége, többtermékes folyamok, duálisok, lineáris programok dekompozíciójának alapjai. A klasszikus alkalmazások, mint a híradástechnikai feladatok megoldásának modell esetei.
    • Lineáris programok megoldása számítógépes programcsomaggal (labor): irodai alkalmazások (OpenOffice.org, MS Excel), matematikai szoftverek (GNU Octave, MATLAB), matematikai modellező nyelvek (GNU MathProg, AMPL), explicit megoldó szoftverek (GLPK, SAS-OR).
    • Bevezetés az egészértékű lineáris programozásba: nevezetes kombinatorikus optimalizálási problémák megfogalmazása egészértékű lineáris program formájában, az egészértékű lineáris programok általános formája, komplexitás
    • Egészértékű lineáris programok megoldása: egészértékű lineáris programok visszavezetése lineáris programra, teljes unimodularitás, a Gomory-féle duál-frakcionális vágások módszere, korlátozás és szétválasztás (branch-and-bound), korlátozás és vágás (branch-and-cut), a Lagrange-i relaxáció, esettanulmányok
    • Egészértékű lineáris programok megoldása számítógépes programcsomaggal (labor): szöveges példák megfogalmazása és megoldása folytonos és egészértékű lineáris program formájában, gyakorlati korlátok
    • Bevezetés a nemlineáris programozásba: a nemlineáris programok általános alakja. Az optimalitás szükséges és elégséges feltételei. Alkalmazások
    • Nemlineáris programok megoldása: kvadratikus programok megoldása, feltételmentes optimalizálás, keresési és gradiens alapú algoritmusok (egy és többváltozós), nemlineáris programok visszavezetése feltételmentes optimalizálásra (megengedett irányok módszere, SUMT módszer)
    • Globális optimum keresése/közeítése: mohó módszer, helyi/szomszédossági keresés, dinamikus programozás
    • Általános optimalizáló metaheurisztikák: tabu-keresés, szimulált lehűtés (SA), genetikus/evolúciós algoritmus (GA), ILP és nemlineáris feladatok megoldása SA és GA módszerekkel
    • Nemlineáris programok és metaheurisztikák megoldása számítógépes programcsomaggal (labor): GAMS és LEMON bemutatása.
    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Előadás
    10. Követelmények a. A szorgalmi időszakban: 2 zárthelyi
    b. A vizsgaidőszakban: írásbeli és szóbeli vizsga
    c. Elővizsga: nincs

    A 2 zárthelyinek külön-külön min. elégségesnek kell lennie.
    11. Pótlási lehetőségek a szorgalmi időszak utolsó két hetének valamelyikében különeljárási díj fejében a zárthelyi pótolható abból a részből (részekből), amely nem sikerült. A zárthelyit (zárthelyiket) csak a szorgalmi időszakban lehet pótolni.
    12. Konzultációs lehetőségek Az órákon egyeztetett illetve kihirdetett időpontokban.
    13. Jegyzet, tankönyv, felhasználható irodalom
    • Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali, "Linear Programming and Network Flows" (2nd ed), Wiley-Interscience, 2004.
    • Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, "Network Flows: Theory, Algorithms, and Applications", Prentice Hall, 1993, 846 pages.
    • Luenberger D. G., Ye Y., "Linear and Nonlinear Programming (3nd ed.), New York: Springer 2008, 544 pages
    • Vizvári Béla, "Egészértékű programozás", Tankönyv, Budapest: Typotex 2006, 353 oldal
    • Laurence A. Wolsey, "Integer Programming", Wiley and Sons, 1998
    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra60
    Félévközi készülés órákra20
    Felkészülés zárthelyire20
    Házi feladat elkészítése-
    Kijelölt írásos tananyag elsajátítása-
    Vizsgafelkészülés50
    Összesen150
    15. A tantárgy tematikáját kidolgozta
    Név:
    Beosztás:Tanszék:
    Dr. Halász Edit
    egyetemi docensTMIT
    Dr. Cinkler Tibor
    egyetemi docensTMIT
    Dr. Tapolcai János
    egyetemi adjunktusTMIT
    Dr. Rétvári Gábortud. munkatárs
    TMIT