BME ALKALMAZOTT MATEMATIKA MESTERSZAK (MSc)
Operációkutatás szakirány tárgyainak tárgyleírása
Jelölés: Az egyes tárgyak
leírásában megjelentetett e/g/l/t/k jelölés feloldása
e = előadások heti óraszáma,
g = gyakorlatok heti óraszáma,
l = laboratóriumi foglalkozások
heti óraszáma,
t = teljesítés módja = v(izsga) vagy f(élévközi jegy),
k = kreditszám.
Nemlineáris programozás
3/1/0/v/5
Tárgyfelelős: Mádi-Nagy Gergely
További oktatók Tóth Boglárka
I. Optimalitás feltételei: Elsőrendű szükséges feltételek
(feltétel nélküli optimalizálás). Másodrendű szükséges + elégséges feltételek
(feltétel nélküli optimalizálás). Konvex (és konkáv) függvények tulajdonságai,
minimalizálás és maximalizálás. Ponthalmaz leképezések, zártság, összetett
leképezések, globális konvergencia-tétel.
II. Vonal menti optimalizálás: Konvergencia-sebesség, Armijo szabály.
Fibonacci, aranymetszés, Newton módszer vonal menti optimalizálásra. Görbe
illesztéses algoritmusok, pontatlan vonal menti optimalizálás zártsága.
III. Feltétel nélküli optimalizálás: Legmélyebb leszállás algoritmusa, Kantorovich
egyenlőtlenség, konvergenciasebesség.
Newton módszer. Koordinátánkénti
minimalizálás, konvergencia és zártság, távolságtartó lépések. Konjugált irányok, kiterjeszkedő
alterek. Konjugált gradiens módszer,
optimalitása. A részleges konjugált gradiens módszer, konvergenciasebesség.
Nem-kvadratikus problémák, Fletcher–Reeves, PARTAN
Kvázi-Newton módszerek, legmélyebb
leszállás és Newton módszer kombinációja.
Legkisebb négyzetek módszere, Gauss–Newton és Levenberg–Marquardt algoritmus
IV. Feltételek melletti optimalizálás: Tangens sík, regularitás - feltételek
karakterizálása. Elsőrendű szükséges
feltételek. Másodrendű szükséges és elégséges feltételek. Primál módszerek,
megengedett irányok (Zoutendijk).
Aktív halmaz stratégia, munkahalmaz, Langrange szorzók
szerepe, érzékenység. Kuhn–Tucker
tétel.
Gradiensvetítés, lineáris feltételek esetén, nemlineáris
feltételek esetén. A redukált gradiens
módszer. Büntető és korlát függvények
módszerei. Lokális dualitás tétel. Duál és metszősík módszerek. Lineáris
komplementaritási feladat. A kvadratikus programozási feladat és a
komplementaritási feladat kapcsolata. Belsőpontos algoritmusok.
Irodalom:
D.G. Luenberger: Linear and Nonlinear Programming, second
edition, Addison Wesley, 1984.
M.S Bazaraa, H.D.Sherali, C.M.Shetty: Nonlinear Programming:
Theory and Algorithms, John Wiley and Sons, New York, 1993,
E.deKlerk, C.Roos, T.Terlaky: Nemlineáris optimalizálás,
Operációkutatás sorozat, No. 5., Aula kiadó
Kombinatorikus optimalizálás
3/1/0/v/5
Tárgyfelelős: Recski András
További oktatók Hujter Mihály:
Gráfelméleti algoritmuscsaládok (legrövidebb út, párosítás,
hálózati folyamok, a PERT-módszer) átismétlése, nevezetes NP-teljes feladatok a
gráfelméletben (pontszínezés, független pontok maximális száma, maximális
klikk-méret, Hamilton-kör és -út létezése, az utazó ügynök problémája,
irányított köröket lefogó maximális halmazok) és rokon területeken (az
egészértékű programozás alapfeladata, a többtermékes folyamprobléma). A
lineáris programozás dualitás tételének alkalmazásai, egészértékű programozás,
kombinatorikus optimalizálási feladatok, totális unimodularitás: maximális
összsúlyú teljes párosítás (optimal assignment), minimálköltségű folyamprobléma
egytermékes hálózatban. Matroidok definíciója, bázis, kör, rang, dualitás,
minorok. Grafikus és koordinátázható matroidok, Tutte és Seymour tételei.
Orákulumok, mohó algoritmus, k-partíció és 2-metszet algoritmus, a 3-metszet
probléma, polimatroidok. Polinomrendű algoritmusokkal megoldható nevezetes
műszaki problémák: a) a villamos hálózatok klasszikus elméletében
(ellenálláshálózatok egyértelmű megoldhatósága, gráfok kör- és vágásmátrixainak
tulajdonságai, általánosítás passzív és/vagy nonreciprok hálózatokra), b) a
nagybonyolultságú áramkörök tervezésében (egyetlen pontsor huzalozása a
Manhattan-modellben, csatornahuzalozás a különféle modellekben, az éldiszjunkt
modell alkalmazása) és c) a rúdszerkezetek merevségével kapcsolatos kérdésekben
(merevség, infinitezimális merevség, genetikus merevség, Laman tétele, Lovász
és Yemini algoritmusa, a síkbeli rúdszerkezetek minimális számú csuklóval való
lefogásának problémája, négyzetrácsok merevítésének kombinatorikus kérdései).
Irodalom:
Jordán Tibor, Recski András és Szeszlér Dávid: Kombinatorikus
optimalizálás, Typotex Kiadó, Budapest, 2004
Sztochasztikus programozás
3/1/0/v/5
Tárgyfelelős: Szántai Tamás
További oktatók Mádi-Nagy Gergely
Statisztikai
döntési elvek. Pétervári probléma, Bernoulli-elv és
az újságárus probléma, holland gátmagasítási probléma, ‘safety
first’ elv, Marschak
döntési elv, a Bayes-i döntési elv, Markowitz elv, játékelmélet, Neumann János tétele.
Konvexitási
tételek. A logkonkáv mértékek elmélete. Általános
konvexitási tételek. Valószínűségi eloszlásfüggvények konkávitási
és kvázi-konkávitási tételei.
Statikus
sztochasztikus programozási modellek. Valószínűség maximalizálás. Egyedi,
illetve együttes valószínűségi korlátokat tartalmazó sztochasztikus
programozási feladatok elmélete és megoldási módszerei. Feltételes várható
értéket tartalmazó modellek. Véletlen célfüggvényes modellek. Büntetéses
sztochasztikus programozás elmélete és speciális esetekre vonatkozó megoldási
módszerei: diszkrét eloszlás, egyenletes eloszlás esete.
Dinamikus
sztochasztikus programozási modellek. Kétlépcsős sztochasztikus programozási
feladat és matematikai tulajdonságai. Diszkrét valószínűségi vektorváltozóra
vonatkozó kétlépcsős sztochasztikus programozási feladat megoldása bázis dekompozíciós módszerrel. A Wets-féle , ‘L-shaped’ megoldási módszer. A sztochasztikus dekompozíció és a feltételes sztochasztikus dekompozíció módszere. Sztochasztikus kvázi-gradiens
módszerek. Többlépcsős sztochasztikus programozási feladatok. Bázis dekompozíció és ‘L-shaped’
megoldó módszer a többlépcsős sztochasztikus programozási feladatok esetében.
A
sztochasztikus programozás néhány alkalmazása. Elektromos energia véletlen
hatások melletti termelése és kapacitás bővítése. Erőművi
megbízhatósági elemzések. Tó vízkészlet szabályozása. Tározók optimális
irányítása. A PERT probléma. Pénzügyi modellek.
Irodalom:
A. Prékopa:
Stochasztic Programming, Kluwer Academic Publishers, Budapest, 1995
Operációkutatási programrendszerek 0/0/2/f/2
Tárgyfelelős: Szántai
Tamás
További oktatók Tóth Boglárka
A tantárgy célja kettős, egyrészt hogy az operációkutatás
egyszerűbb algoritmusai számítógépes kódjának az elkészítésével a hallgatók
számítógépes programozói gyakorlatra tegyenek szert, másrészt hogy jártasságot
szerezzenek a kész operációkutatási szoftverek használatában.
A lineáris programozási feladatok standard leírási módja, az
MPS adatformátum, illetve a legfontosabb algebrai modellezési nyelvek (GAMS,
AMPL, AIMMS) és az azokhoz kapcsolt lineáris, egészértékű, nemlineáris és
sztochasztikus programozási szoftverek (CPLEX, MINOS, SNOPT, LOQO, LGO)
ismertetése.
Irodalom:
I. Maros: Computational Techniques
of the Simplex Method, Kluwer Academic Publishers, 2003
J. D. Pintér: Global Optimization
in Action, Continuous and Lipschitz Optimization: Algorithms, Implementations
and Applications, Kluwer Academic Publishers, 1996
Irányítási rendszerek 2/0/0/v/3
Tárgyfelelős: Gyurkovics
Éva
További oktatók:
Irányítási rendszerek fogalma,
példák irányítási rendszerekre. Lineáris rendszerek tulajdonságai:
irányíthatóság, megfigyelhetőség, stabilizálhatóság. Kanonikus alakok, lineáris
rendszerek struktúrája. Állapotmegfigyelők. Realizáció. Optimális irányítási
feladat. Dinamikus programozás véges feladatra. Dinamikus programozás általános
rendszerre. A Hamilton–Jacobi–Bellman
egyenlet. Lineáris-kvadratikus feladat. A pályakövetés feladata. Végtelen
időintervallumon tekintett feladat.
Irodalom:
E. D. Sontag: Mathematical Control Theory, 2nd ed. (1998)
Gyurkovics Éva: Irányítási
rendszerek, http://www.math.bme.hu/~gye/OktAny.htm
Bevezetés a közgazdasági dinamikába 3/1/0/v/5
Tárgyfelelős: Simonovits
András
További
oktatók:
A
hagyományosan statikus közgazdaságtan az utóbbi évtizedekben egyre nagyobb
figyelmet fordít a dinamikus közgazdaságtani modellezésre. A fizikához és a
biológiához képest itt sokkal fontosabb a diszkrét idejű rendszerek elemzése. A
dinamikus optimalizálás nemcsak technika, hanem sokak számára az egyedül
lehetséges közgazdasági megközelítés. A téma további megkülönböztető
sajátossága, hogy a várakozásokon keresztül nemcsak a múlt, de a jövő(kép) is befolyásolja a jelent. A tantárgy a szükséges
matematikai eszközök mellett nagy súlyt helyez a legfontosabb közgazdasági
modellek ismertetésére: optimális növekedés, együttélő
korosztályok.
A
tárgy felépítése:
Lineáris
differenciaegyenletek: készletjelzéses szabályozás
Nemlineáris
differenciaegyenletek: stabilitás, ciklus és káosz
Differenciálegyenletek:
növekedési modell, árigazodási modell
Dinamikus
programozás: optimális halászat
Optimális
folyamatok: optimális növekedés és felhalmozás
Együttélő nemzedékek modelljei
Együttélő korosztályok modelljei
Irodalom:
Simonovits, A.: Matematikai módszerek a dinamikus
közgazdaságtanban, Közgazdasági és Jogi Könyvkiadó, Budapest, 1998
Játékelmélet 2/0/0/f/3
Tárgyfelelős: Simonovits
András
További
oktatók:
A
tárgy bevezetést nyújt
a játékelméletetbe, különösen annak
nem-kooperatív változatába.
A
játékelmélet olyan gazdasági, politikai, katonai stb. helyzeteket modellez,
ahol több szereplő optimalizálja a célfüggvényét, amely értéke a többi szereplő
döntésétől is függ. A játékelmélet napjainkban a közgazdaságtan alaptudományává
válik, amely segítséget nyújt a monopolhelyzetek modellezéséhez, az optimális
árverés rendszerének kidolgozásához és még sok más kérdés megválaszolásához.
Az
előadások szerkezete a következő:
Nem
kooperatív játékelmélet
Nash egyensúly
Tökéletes
egyensúly
Bayes-i egyensúly
Irodalom:
Tirole, J. (1988): The Theory of Industrial
Organization, Chapter 11, MIT Press, Cambridge, MA.
Ökonometria
0/0/2/f/2
Tárgyfelelős: Simonovits
András
További oktatók: Orlovits Zsanett
Kétváltozós kapcsolatok: lineáris regresszió, legkisebb
négyzetes (LS) becslés és statisztikai tulajdonságai, Gauss-Markov tétel,
predikció. Többváltozós lineáris regresszió korrelálatlan, azonos szórású hiba,
illetve általános hibafolyamat esetén, általános Gauss-Markov tétel,
előrejelzés, multi-kollinearitás.
Általánosított LS módszer, speciális esetek (autokorrelált
zaj, nem azonos szórású korrelálatlan zaj), segédváltozók (IV) módszere.
Idősorok elemzése: stacionaritás, autokorreláció, fehérzaj
folyamat, speciális modellek (lineáris szűrők, autoregresszív (AR) folyamat,
mozgóátlag (MA) folyamat, ARMA folyamatok). Paraméterbecslés (ML-becslés),
előrejelzés. Integrált és kointegrált folyamatok (ARIMA modellek), trend,
szezonalitás.
Spektrálreprezentáció, periodogram és becslése, spektrum
becslése.
Többváltozós modellek: VAR(1) folyamatok, n-dimenziós ARMA
folyamatok, stacionaritás, stabilitás, Lyapunov egyenlet.
Frakcionálisan integrált folyamatok, ARFIMA modellek, hosszú
emlékezetű folyamatok és becslésük.
Sztochasztikus volatilitás modellek: ARCH és GARCH
folyamatok, bilineáris folyamatok és jellemzőik, stacionaritás,
paraméterbecslés, állapottér reprezentáció.
Alkalmazások: pénzpiaci hozamok
idősorának vizsgálata, biológiai adatok elemzése.
Irodalom:
Tusnády G. - Ziermann M.: Idősorok
analízise, Műszaki, 1986
Ramu Ramanathan: Bevezetés az
ökonometriába, PANEM, Budapest, 2003
G.E.P Box and G.M. Jenkins: Time Series
Analysis, Forecasting and Control, Holden Day, 1970
Témalabor 1,2 0/0/4/f/4
+ 0/0/4/f/4
Tárgyfelelős: Lángné Lázi Márta
A tárgy keretében a hallgató külső témavezető által
meghirdetett, alkalmazás orientált sztochasztikus matematikát alkalmazó témán
dolgozik, a témavezető irányításával. Minden félév végén beszámolót készít a
hallgató az eredményeiről, melyet előadás formájában a társainak bemutat. A
tárgy során begyakorolandó tevékenységek: irodalmazás, modellezés,
számítógéppel segített feladatmegoldás, matematikai problémamegoldás.
Matematikai modellalkotás szeminárium 1,2 2/0/0/f/1 + 2/0/0/f/1
Tárgyfelelős: Szász Domokos
A
szeminárium célja rendszeres fórumot biztosítani alkalmazott matematikai eredmények,
modellek és problémák bemutatására, és ezzel elősegíteni
(i)
a Matematika Intézeten belül és szélesebb körben is, az alkalmazott matematikai
ismeretek és kultúra elterjesztését;
(ii) fejleszteni egyfelől a Matematika Intézet oktatói és diákjai,
másfelől más intézmények, intézetek (a BME több tanszékét, intézetét is
ideértve), cégek, vállalatok matematika iránt fogékony munkatársaival való
kapcsolattartást, együttműködést.
A
szemináriumra hétről hétre meghívunk egy-egy előadót, aki a munkája során
felmerülő matematikai problémáról beszél. Általában két
típusú előadó van: matematikus, aki alkalmazott matematikusként
dolgozik, illetve nem matematikus, de munkája során matematikai problémák
merülnek fel. A korábbi évek gyakorlatához hasonlóan széles palettát kívánunk
nyújtani a témákat illetően; előadókat hívunk meg a BME különböző tanszékeiről,
a SZTAKI-ból, bankokból, a távközlés területéről, és egyéb piaci cégtől
(bővebben lásd a szeminárium honlapján: www.math.bme.hu/~molnar/amsz).
A
II-III. éves hallgatóinknak előírjuk a matematikai
modellalkotás szeminárium látogatását, hogy ezzel is plasztikus képet nyerjenek
szakmájuk lehetséges alkalmazásairól. A szeminárium előadásai általában
érthetőek lesznek ezen hallgatóink számára, akik ekkor már túl vannak az igen
sokoldalú alapképzésen. Alkalmazott matematikai témáknál természetesen
különösen fontos a problémafelvetés motivációja, a modellalkotás bemutatása és
annak illusztrálása, a javasolt megoldás mennyire segít a felmerült
problémában. Az előadások után a hallagtóknak
lehetőségük van kérdéseikkel további ismereteket szerezni a bemutatott témáról,
illetve az előadó munkásságáról.
Az
előadások egy másik célja, hogy az érdeklődő hallgatók esetleg valamilyen
formában bekapcsolódhatnának a munkába, ezzel is elősegítve a hosszabbtávú
érvényesülésüket, hogy az egyetem elvégzése után könnyebben jussanak
álláslehetőséghez.