Lineáris programozás

1. Konvex poliéderek, konvex kúpok. Alternatíva tételek. Megengedettségi feladatok tulajdonságai és megoldása: criss-cross algoritmus, MBU-szimplex módszer. Végesen generált kúpok és polárisuk: Weyl-, Minkowski- és Farkas-tétel.
2. Lineáris programozás dualitás elmélete és pivot algoritmusai.
3. Polinomiális algoritmus a lineáris programozási feladat megoldására: teljes Newton-lépéses, logaritmikus büntetőfüggvényes algoritmus. Primál-duál lineáris programozási feladatpár. Belsőpont megoldás, optimalitási kritériumok, centrális út, Newton-rendszer, megengedett lépéshosz, centralitás-mértéke, dualitás rés és csökkenésének a mértéke, Ling lemmái, konvergencia tétel.
4. Ferdén szimmetrikus, önduális lineáris programozási feladat. Optimalitási kritériumok, Newton-lépés, szinthalmazok, centrális út létezése és egyértelműsége. Szigorúan komplementáris megoldás, Goldmann-Tucker tétel. Analitikus centrum. Sonnevend-tétel.
5. Dikin affin skálázású algoritmusa. Iránykereső segédfeladat, megengedett lépéshossz, centralitás-mértéke, dualitás rés és csökkenésének a mértéke, konvergencia tétel. (B, N) partíció előállítása, nagy és kis változók.
6. Beágyazás, Goldmann-Tucker modell. Induló, belsőpont konstruálása. Optimális megoldáshalmaz felírása ε-optimális belsőpontos megoldás segítségével. Erősen polinomiális kerekítési eljárás.