Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

A tantárgy a lineáris és egészértékű programozás elméletének alapjaival kívánja megismertetni a hallgatókat. A fő célkitűzése az, hogy a hallgatók megismerjék ennek az elméletnek az alkalmazási területeit és lássák annak a határait is. A tárgyat sikerrel teljesítő hallgatók képesek lesznek megítélni, hogy egy, a gyakorlati életben felmerülő algoritmikus feladatot egyrészt lehetséges-e, másrészt érdemes-e a lineáris és egészértékű programozás módszerével megközelíteni.

 1) A lineáris programozás alapfeladata, annak változatai, a megoldhatóság és a korlátosság fogalma. Kétváltozós feladatok megoldása grafikus módszerrel. A gyakorlati életből származó feladatok modellezése lineáris programozási feladatként. A lineáris programozás algoritmikus bonyolultsága, lineáris programozási feladatok megoldása számítógéppel.

2) Az egészértékű programozás feladata, annak algoritmikus bonyolultsága. A gyakorlati életből származó feladatok modellezése egészértékű programozási feladatként, bináris döntési változók használata. Egészértékű programozási feladatok megoldása számítógéppel. Hálózati folyamproblémák (maximális folyam, minimális költségű folyam és többtermékes folyam) definíciója, azok modellezése és megoldása a lineáris és egészértékű programozás segítségével.

3) A lineáris programozás alapfeladata mátrixos alakban. Szükséges és elégséges feltételek lineáris egyenletrendszerek nemnegatív változókkal való, illetve lineáris egyenlőtlenségrendszerek megoldhatóságára: a Farkas-lemma. A lineáris programozás alapfeladata mátrixos alakban. Szükséges és elégséges feltételek a lineáris program célfüggvényének korlátosságára. A lineáris programozás dualitástétele.

4) Korlátozás és szétválasztás (Branch and Bound) módszer egészértékű programok megoldására. Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazások: egészértékű hálózati folyamproblémák, páros gráfok párosítási feladatai.

 A tárgy a levelező képzés része, kontaktórák nincsenek. A tárgy honlapján elérhetők lesznek a felkészüléshez szükséges anyagok. Emellett havonta egy konzultációt tartunk, amelyen az elmélet megértését segítő példák és feladatok kerülnek bemutatásra.

A szorgalmi időszakban:

A tárgyból egy beadandó házi feladat lesz. A félévvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) a feltétele a házi feladat beadása.

A vizsgaidőszakban:

A tárgyból a vizsgaidőszakban írásbeli vizsgát tartunk.

Elővizsga: nem lehetséges.

Amennyiben a beadott házi feladat megoldása hibás, akkor a javított megoldás a pótlási hét végéig újra beadható.

A sikertelen vizsga javítása a TVSz-nek megfelelően zajlik.  

 A szorgalmi időszakban havonta egy konzultációt tartunk.

Jordán Tibor, Recski András, Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, 2004.