Tárgy neve: Operációkutatás ea. (BSc)

Tanszék: Halmazelmélet és Matematikai Logika Tanszék

Tematika:
Lineáris egyenletrendszerek és egyenlőtlenségrendszerek alapjai. Mátrix jelölés, logikai levezetések, logikai következmények. Lineáris egyenlőtlenségrendszerek megoldhatósága. Fourier-Motzkin elimináció. Farkas-lemma: alternatíva formák, logikai formák. Alkalmazás. Lineáris egyenlőtlenségrendszerek megoldáshalmaza. Hipersíkok, félterek, lineáris alterek, kúpok. (Konvex) Poliedrikus kúpok és végesen generált kúpok. Weyl-Minkowski-tétel. (Konvex) Poliéderek, politópok. Végesen generált politópok és korlátos poliéderek. Lineáris programozás (LP) alapjai. Bázismegoldások, pivotok, ezek geometria háttere. Pivot szabályok. Szimplex módszer (egyszerű elindulás feltételezésével, két fázisú szimplex módszer). LP dualizálás, dualitás tétel. Legolcsóbb feszítőfa probléma, Kruskal-algoritmus. Legrövidebb út probléma, súlyozatlan esete, súlyozott eset. Dijkstra-algoritmus. Hozzárendelési probléma. Egerváry számozás. Magyar módszer. A kombinatorikus algoritmusok és LP kapcsolata. Totálisan unimoduláris mátrixok.

Előadás kódja: MBNA13E, óraszám: 2, kredit: 6