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