-***- Alkalmazott optimalizálás és játékelmélet (VITMD097)  -***-
       =================================================================



  Folytonos változójú lineáris és nemlineáris programok megoldása. Elméleti
  háttér, modellezés, megoldó algoritmusok és klasszikus alkalmazások.


* Tematika

** 1. előadás

    Bevezetés a lineáris programozásba.  A modellezés lépései, terminológia,
    modellfeltevések.  A lineáris programok általános formája.  Mátrixalak.
    Maximalizálás és minimalizálás, áttérés a kettő közt.  A
    kényszerfeltételek formái, áttérés.  Példák: termelésoptimalizálás,
    szállítási probléma, folyamprobléma, többtermékes folyamok,
    portfólióoptimalizálás.  Lineáris algebrai alapfogalmak, lineáris
    egyenletrendszerek, bázisok.

    Az előadás fóliái


** 2. előadás

    Lineáris programok megoldása.  A konvex analízis alapjai, konvex
    kombináció, konvex halmazok, konvex és konkáv függvények, lokális és
    globális optimum, konvex függvények minimalizálása konvex
    tartományon. Hipersíkok, félterek, extrém pontok, konvex poliéderek,
    Minkowski-Weyl tétele, az optimális megoldások és az extrém pontok
    összefüggései. Lineáris programok grafikus megoldása, a megengedett
    tartomány (korlátos, nem korlátos, üres), optimális megoldások (egyedi,
    alternatív, nem korlátos).

    Az előadás fóliái


** 3. előadás

    A szimplex algoritmus.  Bázisok, bázismegoldások, megengedett
    bázismegoldások, degenerált bázismegoldás. A szimplex algoritmus alapjai,
    indítás megengedett bázismegoldásról, áttérés a nembázis változók terére,
    új változó felvétele a bázisba, változó kiléptetése a bázisból,
    végződtetés, optimalitás.

    Az előadás fóliái


** 4. előadás

    A szimplex tábla és alkalmazása.  A szimplex algoritmus végződtetése,
    egyedi és alternatív optimális megoldások, nem korlátos megoldások.  A
    degeneráció fogalma.  Komplexitás (elméleti és gyakorlati).  A szimplex
    tábla.  Példák megoldása a szimplex tábla segítségével

    Az előadás fóliái


** 5. előadás

    A lineáris programozás dualitáselmélete. Lineáris programozás optimális
    megoldásainak jellemzése, a Karush-Kuhn-Tucker (KKT) feltételek, példák.
    Lineáris programok duáljai, a duális lineáris program tulajdonságai, a
    dualitás gyenge és erős tétele. A duál feladat közvetlen megoldása a
    primál szimplex algoritmus segítségével. Farkas lemmája

    Az előadás fóliái


** 6. előadás

    A duál szimplex algoritmus.  Primál optimális (duál megengedett) és
    primál megengedett (duál optimális) bázisok.  A duál közvetlen megoldása
    a duál szimplex algoritmussal, változó kiléptetése a bázisból, új változó
    felvétele a bázisba, a duál szimplex tábla.  A lineáris programozás
    klasszikus alkalmazásai, példák megoldása a primál szimplex és a duál
    szimplex segítségével

    Az előadás fóliái


** 7. előadás

    A szimplex indítása, kezdeti bázis keresése, a mesterséges változók
    módszere, példák. Lineáris programok megoldásának analízise.
    Érzékenységvizsgálat: a célfüggvény megváltoztatása. Paraméteranalízis:
    a RHS perturbációja.

    Az előadás fóliái


** 8. előadás

    A lineáris programozás klasszikus alkalmazásai. Termelésoptimalizálás.
    Hozzárendelési probléma: folytonos eset.  Arbitrázsárazás.

    Az előadás fóliái
       

** 9. előadás

    Nemlineáris programok általános alakja, feltételes és feltételmentes
    programok, konvex programok, lokális is globális minimumok kapcsolata
    nemkonvex tartomány és/vagy nemkonvex célfüggvény mellett.  Optimalitási
    feltételek, a differenciálhatóság szerepe, a javítóirányok és megengedett
    javítóirányok fogalma, konvex programok optimalitása és a megengedett
    javítóirányok kapcsolata.  Egyszerű nemlineáris programok megoldása, a
    megengedett irányok módszere, megengedett javítóirány keresése, a
    lépésköz megválasztása, egyenes menti keresés

    Az előadás fóliái


** 10. előadás

    Feltételmentes optimalizálás: egyenes menti keresés, a keresési tartomány
    fogalma, konvex függvények szélsőértékeinek tulajdonságai,
    nemdifferenciálható függvények minimumának megadása dichotóm kereséssel,
    differenciálható függvények minimumának megadása bináris kereséssel.
    Többdimenziós feltételmentes minimumkeresés, a legmeredekebb irányok
    módszere.  Nemlineáris programok általános megoldása, belső és külső
    büntetőfüggvények alkalmazása, a büntetőfüggvények leggyakoribb
    megválasztása, a két módszer összehasonlítása

    Az előadás fóliái


* Szóbeli vizsga: tételsor


* Gyakorlófeladatok

    A szimplex táblák használatának elsajátításához rendelkezésre áll egy
    rövid segédlet, illetve pár egyszerű GNU Octave/MATLAB szkript. A
    szkriptek standard alakban adott maximalizálási problémákat oldanak meg
    egy megadott kezdeti bázisról, és a szimplex algoritmus minden
    iterációjában kiírják a kapott szimplex táblákat.

    Letöltések:

    - Segédlet a GNU Octave/MATLAB szoftverek használatához

    - GNU Octave/MATLAB primál szimplex algoritmus

    - GNU Octave/MATLAB duál szimplex algoritmus

    - Gyakorlófeladatok
    
    
* Ajánlott irodalom

    Mokhtar S. Bazaraa, John J. Jarvis, and Hanif D. Sherali. "Linear
      Programming and Network Flows", John Wiley and Sons, New York, 2nd
      edition, 1990.

    Mokhtar S. Bazaraa, Hanif D. Sherali, C. M. Shetty. "Nonlinear
      Programming: Theory and Algorithms", 3rd ed., Wiley Interscience, 2006.

    D. G. Luenberger, Yinyu Ye.  "Linear and Nonlinear Programming", 3rd
      Edition, Springer. 2008.



Back