A tantárgy az alábbi témakörök ismeretére épít:
Lineáris algebra és matematikai analízis (Mat A1-A2 vagy azzal ekvivalens tárgyak)
A tantárgy szerepe a képzés céljának megvalósításában:
Szabadon választható tárgy
A tantárgy részletes tematikája magyarul és angolul:
Bonyolultságelméleti bevezető
Szállítási feladat
Hálózati feladat (Maximális folyam – minimális vágás; minimális folyam) Többtermékes folyam feladat (Megoldási módszerek, visszavezetés) Lineáris programozás alapjai
LP feladatok geometriája (hipersík, félsík, támaszsík, csúcs, poliéder, politop, kúp) Farkas lemma, dualitás
Szimplex algoritmus, belsőpontos algoritmus váza
Szemidefinit optimalizálás (Dualitás elmélet, algoritmus, alkalmazások (polinom optimalizálás, 0-1 optimalizálás)) Kvadratikus programozás (Dualitás elmélet, algoritmusok)
Egészértékű programozás (Feladatok: hátizsák feladat, halmazfedés, halmazfelbontás, Algoritmusok: B&B, vágósíkos, dinamikus programozás)
Globális optimalizálás, elhelyezési problémák
Követelmények szorgalmi időszakban:
Algoritmus programozása(esetleg modellezés és előadás tartása)
Követelmények vizsgaidőszakban:
Konzultációs lehetőségek:
Számonkérések előtt szervezett konzultációk, továbbá egyéni konzultációk fogadóórákon
Jegyzet, tankönyv, felhasználható irodalom:
Illés Tibor: Lineáris optimalizálás elmélete és módszerei; Gáspár-Temesi: Lineáris programozási gyakorlatok;
D.G. Luenberger, Y. Ye: Linear and Nonlinear Programming; E. de Klerk, K. Roos, T. Terlaky: Nemlineáris Optimalizálás;
E. de Klerk: Aspects of Semidefinite Programming; G.L. Nemhauser, L.A. Wolsey: Integer and Combinatorial Optimization
Nyomtatóbarát változat
