Optimalizálás az infokommunikációs gyakorlatban

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.