Budapesti Műszaki és Gazdaságtudományi Egyetem
Természettudományi Kar		 Tantárgy Adatlap
Tantárgy kód BMETE93MM01
Tantárgy azonosító adatok
1. A tárgy címe Lineáris programozás
2. A tárgy angol címe Linear Programming
3. Heti óraszámok (ea + gy + lab) és a félévvégi követelmény típusa 3 + 1 + 0 v Kredit 5
4. Ajánlott/kötelező előtanulmányi rend
vagy Tantárgy kód 1 Rövid cím 1 Tantárgy kód 2 Rövid cím 2 Tantárgy kód 3 Rövid cím 3
4.1
4.2
4.3
5. Kizáró tantárgyak
6. A tantárgy felelős tanszéke Differenciálegyenletek Tanszék
7. A tantárgy felelős oktatója Dr. Illés Tibor beosztása egyetemi docens
Akkreditációs adatok
8. 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
9. A tantárgy az alábbi témakörök ismeretére épít
analízis, lineáris algebra, operációkutatás alapjai
10. A tantárgy szerepe a képzés céljának megvalósításában (szak, kötelező, kötelezően választható, szabadon választható)
TTK Matematikus és Alkalmazott matematikus MSc képzések törzstárgya
11. A tárgy részletes tematikája
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.
12. Követelmények, az osztályzat (aláírás) kialakításának módja
szorgalmi
időszakban		 zárthelyi dolgozat eredménye beleszámít a vizsgaeredménybe vizsga-
időszakban		 írásbeli és szóbeli vizsga
13. Pótlási lehetőségek
a zárthelyi dolgozat a szorgalmi időszakban egyszer pótolható
14. Konzultációs lehetőségek
a tárgy oktatójának heti rendszerességgel meghirdetett fogadóóráján
15. 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.
16. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
16.1 Kontakt óra
56
16.2 Félévközi felkészülés órákra
28
16.3 Felkészülés zárthelyire
14
16.4 Zárthelyik megírása
2
16.5 Házi feladat elkészítése
0
16.6 Kijelölt írásos tananyag elsajátítása (beszámoló)
0
16.7 Egyéb elfoglaltság
0
16.8 Vizsgafelkészülés
50
16.9 Összesen
150
17. Ellenőrző adat Kredit * 30
150
A tárgy tematikáját kidolgozta
18. Név beosztás Munkahely (tanszék, kutatóintézet, stb.)
Dr. Illés Tibor
egyetemi docens
Differenciálegyenletek Tanszék
A tanszékvezető
19. Neve aláírása
Dr. Illés Tibor