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

Név:	Beosztás:	Tanszék, Int.:
Dr. Tapolcai János PhD	egy. adjunktus	TMIT
Dr. Rétvári Gábor Ferenc PhD	tud. s.munkatárs	TMIT

Alapvető matematikai ismeretek.

Hálózattervezés, hálózati forgalom optimalizálása, termelési stratégia optimalizálása, repülő- és vonattársaságok menetrend optimalizálása: olyan, a mérnöki gyakorlatban gyakran előforduló problémák, amikor a feladat valamilyen jósági kritérium szerinti legjobb megoldás megtalálása úgy, hogy a lehetséges megoldások halmazát valamely műszaki megkötésből származó kényszerfeltételek határozzák meg. Jelen tárgy célja bemutatni, hogyan lehet ezeket a műszaki optimalizálási problémákat matematikai program formájában egyszerűen megfogalmazni és megoldani. Rengeteg példán keresztül ismertetjük a legelterjedtebb modellezési technikákat, áttekintjük a megoldó módszerek működését és a megoldó szoftverek használatát, valamint bevezetjük a hallgatókat a hatékony optimalizálási algoritmusok tervezésébe is. A tárgy során elsajátított tudás nemcsak a műszaki problémák megoldásában nyújt hasznos gyakorlati támaszt a leendő mérnökök számára, de az optimalizálás témakörén keresztül betekintést ad olyan területekre is, mint a gazdaságtan, a logisztika vagy a menedzsmenttudományok.

Bevezetés a mérnöki optimalizálásba: egyszerű problémák megfogalmazása matematikai program formájában, matematikai programok grafikus megoldása, összetett optimalizálási problémák megfogalmazása matematikai programként: termelési stratégia optimalizálása, telepítési, készletgazdálkodási, ütemezési problémák.

A lineáris programozás: bevezetés a konvex analízisbe, a lineáris programozás alapfeladata és formái, a szimplex algoritmus, optimalitási és megoldhatósági kritérium, a szimplex tábla, degeneráció, a kétfázisú szimplex algoritmus, lineáris programok duálja, duál optimalitási kritériumok, Farkas lemmája, komplementaritás, a lineáris programozás dualitásának gyenge és erős tételei, a duál szimplex algoritmus, a szimplex algoritmus komplexitása, polinom-idejű módszerek, érzékenységi vizsgálat, parametrikus analízis.

Egészértékű programozás: az egészértékű lineáris programozás alapfeladata, komplexitás, nevezetes NP-teljes problémák felírása egészértékű lineáris programként, lineáris programra visszavezethető egészértékű programok, totális unimodularitás és detektálása, egészértékű programok egzakt megoldása (dinamikus programozás, korlátozás és szétválasztás, vágás-típusú módszerek, korlátozás és vágás módszere), közelítő módszerek (Lagrange-relaxáció, szubgradiens módszer, dekompozíció)

Optimalizálási algoritmusok tervezése: a dualitás felhasználása polinom idejű algoritmusok tervezésére, párosítások, minimális költségű feszítőfa, Steiner fák, utazóügynök probléma.

Nemlineáris programozás: kvadratikus programozás, szemidefinit programozás, sztochasztikus programozás.

Szoftver eszközök matematikai programok megoldásához: implicit lineáris megoldó szoftverek (Octave-MATLAB, Mathematica, Excel, OO Calc), explicit lineáris program megoldó szoftverek (GLPK, lp_solve, CPLEX, LEMON), egyszerű lineáris program megoldó fejlesztése.

előadás és gyakorlat jellegű előadás

A félév során 2 zárthelyi dolgozatot kell írniuk a hallgatóknak. Mindkét zárthelyit legalább elégségesre kell megírni, különben az elégtelen zárthelyit pótolni kell. A zárthelyi illetve pót-zárthelyi eredményes, ha a maximális pontszám legalább 50%-t elérte a hallgató. A félévközi jegy megállapításának módja: a két dolgozat számtani közepe felfele kerekítéssel.

A pótlási időszakban lehetőség van egy eredménytelen zárthelyi dolgozat újbóli pótlására, különeljárási díj megfizetése mellett.

Az órákon egyeztetett illetve kihirdetett időpontokban.

Vizvári Béla, „Egészértékű programozás”, typotex 2006

Név:	Beosztás:	Tanszék, Int.:
Dr. Tapolcai János PhD	egy. adjunktus	TMIT
Dr. Rétvári Gábor Ferenc PhD	tud. s.munkatárs	TMIT