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, FletcherReeves, PARTAN Kvázi-Newton módszerek,  legmélyebb leszállás és Newton módszer kombinációja.

Legkisebb négyzetek módszere, GaussNewton és LevenbergMarquardt 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.  KuhnTucker 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 HamiltonJacobiBellman 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.