BMETE93MM01

Nyomtatóbarát változatNyomtatóbarát változat
Tantárgy azonosító adatok
A tárgy címe: 
Lineáris programozás
A tárgy angol címe: 
Linear Programming
A tárgy rövid címe: 
LinProgramozás
3
1
0
v
Kredit: 
5
A tantárgy felelős tanszéke: 
Differenciálegyenletek Tanszék
A tantárgy felelős oktatója: 
Dr. Illés Tibor
A tantárgy felelős oktatójának beosztása: 
egyetemi docens
Akkreditációs adatok
Akkreditációra benyújtás időpontja: 
2017.01.15.
Akkreditációs bizottság döntési időpontja: 
2017.01.31.
Tematika
A tantárgy az alábbi témakörök ismeretére épít: 
analízis, lineáris algebra, operációkutatás alapjai
A tantárgy szerepe a képzés céljának megvalósításában: 
TTK Matematikus és Alkalmazott matematikus MSc képzések törzstárgya
A tantárgy részletes tematikája magyarul és angolul: 

Lineáris egyenletrendszerek megoldhatóságának kérdése és megoldása. Gauss-Jordán eliminációs módszer. Lineáris egyenlőtlenségrendszerek megoldhatósága. Alternatíva tételek, Farkas lemma és variánsai. Lineáris egyenlőtlenségrendszerek megoldása pivot algoritmusokkal. Konvex poliéderek. Minkowski-tétel, Farkas-tétel, Weyl-tétel, Motzkin felbontási tétele.
A lineáris programozás feladata, példák lineáris programozási feladatra, grafikus szemléltetés. A lineáris programozási feladat megengedett megoldásának, bázis megoldásának fogalma, a szimplex módszer alap algoritmusa. A ciklizálás és annak kizárási lehetőségei: lexikografikus szimplex módszer, Bland-szabály alkalmazása. Induló megengedett bázis keresése, a kétfázisú szimplex módszer. Az explicit bázisinverz és a módosított szimplex módszer. A lineáris programozás dualitás elmélete. Kiegészítő eltérések tételei. A duál szimplex módszer. Speciális lineáris programozási, illetve arra visszavezethető feladatok. Egyedi felső korlát technika. Érzékenységvizsgálat. A Dantzig–Wolfe dekompozíciós eljárás.
Lineáris programozás belsőpontos módszereire épített elmélete. Önduális feladat, szinthalmazok, centrális út létezése és egyértelműsége. Newton-irányok kiszámítása. Analitikus centrum, Sonnevend-tétele. Dikin-ellipszoid, affin skálázású belsőpontos módszer és polinomialitása. Goldmann–Tucker-modell, Goldmann–Tucker-tétel. Pontos megoldás előállítása erősen polinomiális kerekítési eljárással.
Hacsián ellipszoid módszere. Karmarkar potenciálfüggvényes belsőpontos algoritmusa. Speciális belsőpontos algoritmusok.

Követelmények szorgalmi időszakban: 
zárthelyi dolgozat eredménye beleszámít a vizsgaeredménybe
Követelmények vizsgaidőszakban: 
írásbeli és szóbeli vizsga
Pótlási lehetőségek: 
a zárthelyi dolgozat a szorgalmi időszakban egyszer pótolható
Konzultációs lehetőségek: 
a tárgy oktatójának heti rendszerességgel meghirdetett fogadóóráján
Jegyzet, tankönyv, felhasználható irodalom: 
Illés T., Lineáris optimalizálás elmélete és pivot algoritmusai, 2013.
Illés T., Lineáris optimalizálás elmélete és belsőpontos algoritmusai, 2014.
A. Schrijver, Theory of Linear and Integer Programming, John Wiley, New York, 1986.
A tárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
Kontakt óra: 
56
Félévközi felkészülés órákra: 
28
Felkészülés zárthelyire: 
14
Zárthelyik megírása: 
2
Házi feladat elkészítése: 
0
Kijelölt írásos tananyag elsajátítása (beszámoló): 
0
Egyéb elfoglaltság: 
0
Vizsgafelkészülés: 
50
Összesen: 
150
Ellenőrző adat: 
150
A tárgy tematikáját kidolgozta
Név: 
Dr. Illés Tibor
Beosztás: 
egyetemi docens
Munkahely (tanszék, kutatóintézet, stb.): 
Differenciálegyenletek Tanszék
A tanszékvezető neve: 
Dr. Illés Tibor