Operációkutatás tematika

2022 Tavasz

1. Lineáris függvények, klasszikus és vektorírásmóddal. Egyenlet- és egyenlőtlenségrendszerek mátrix alakja. Mátrix szorzás interpretációi. Megoldáshalmaz fogalma. Adjon példát két 2-változós egyenlőtlenség megoldáshalmazára és összegük megoldáshalmazára.
2. Egyenlet- és egyenlőtlenségrendszerek logikája. Logikai következtetések (egyenletrendszerek és egyenlőtlenségek hasonlósága és különbözősége). Levezetés fogalma. Univerzalitás jelentése és ennek bizonyítása.
3. Egyenlőtlenségrendszerek megoldása n=1 változó esetén. Hogy írható le a megoldhatóság logikai nyelven? n változós esetben egy változó Fourier-Motzkin-eliminációja. A kiinduló és konstruált egyenlőtlenségrendszer kapcsolata.
4. Farkas-lemma első alternativa formájának kimondása. Farkas-lemma második alternativa formájának kimondása. Miért nem teljesülhet mindkét alternatíva egyszerre? Egyik formát igazolja.
5. A levezethetőség és logikai következmény fogalma kineáris egyenlet- egy egyenlőtlenségerendszerekre. Mi a nyilvánvaló kapcsolat a két fogalom között? Indokolja az állítását Farkas lemma logikai formájának kimondása. Igazolja ezt.
6. Lineáris egyenlet (homogén, nem homogén) és lineáris egyenlőtlenség megoldáshalmaza. Hipersík és féltér leírása n-dimenzióban.
7. Szakasszal, egyenessel való összekötés leírása Rⁿ-ben. Lineáris egyenletrendszer megoldáshalmaza, lineáris kombináció, affin kombináció, lineáris altér, affin altér fogalma.
8. Homogén egyenlőtlenségrendszer megoldáshalmaza, kúp kombináció, poliedrikus kúp fogalma. Végesen generált kúp fogalma. Minkowski és Weyl poliedrikus kúpokra vonatkozó tételének kimondása.
9. Projekció. Fourier---Motzkin-elimináció geometriai jelentése. Végesen generált kúp fogalma. Farkas-lemma geometriai alakja: Szeparációs tétel. Poliéderek "kúposítása". A kúp és a kiinduló poliéder kapcsolata.
10. Egyenlőtlenségrendszer megoldáshalmaza: poliéder fogalma. Konvex kombináció fogalma, végesen generált konvex halmazok: politóp. Politópok alaptételének kimondása. Ponthalmazok Minkowski-összege Rⁿ-ben. Minkowski és Weyl tételének kimondása (a benne szereplő fogalmak leírásával).
11. Az optimalizálás alapfeladata, alapfogalmai: optimális érték, optimális hely, közelítő, approximációs megoldások. Optimalizálási feladatok átfogalmazásai. Egyenlőtlenségek kiküszöbölése előjel feltételekkel, lineáris egyenletek kiküszöbölése. Min/max csere.
12. Az optimalizálás alapfeladata, alapfogalmai: optimális érték, optimális hely, közelítő, approximációs megoldások. A lineáris programozása alapfeladata. Normálformák, poliedrikus forma, előjeles poliedrikus forma, szimplexforma és a köztük való transzformációk. Feltételek a szimplex alakra.
13. Feltételek a szimplex alakra. A teljes rangúság és az egységmátrix jelenlétének feltevése, ennek garantálása. A szótár alak. A b vektor előjel feltétele és ennek fontossága. Hogyan olvasható ki a szótárból, hogy optimális megoldásunk van? Indoklás. Hogyan olvasható ki a szótárból, hogy célfüggvényünk felülről nem korlátos? Indoklás.
14. A szótár alak. Hogyan olvasható ki a szótárból, hogy optimális megoldásunk van? Indoklás. Hogyan olvasható ki a szótárból, hogy célfüggvényünk felülről nem korlátos? Indoklás. A pivot fogalma. Pivot szabályok, Ciklizálás fogalma.
15. A szótár alak. Hogyan olvasható ki a szótárból, hogy optimális megoldásunk van? Indoklás. Hogyan olvasható ki a szótárból, hogy célfüggvényünk felülről nem korlátos? Indoklás. Két fázisú szimplex módszer fázisai, a lehetséges leállások az egyes fázisokban. Hogyan található meg egy kiinduló bázismegoldás, ha a lehetséges megoldások halmaza nem üres.
16. Egy LP feladat feltételeiből felső becslés levezetése a célfüggvény értékére. LP feladatok dualizálása (poliedrikus forma, előjeles poliedrikus forma és szoimplex forma). Gyenge dualitás tétel és bizonyítása.
17. Egy LP feladat feltételeiből felső becslés levezetése a célfüggvény értékére. LP feladatok dualizálása (poliedrikus forma, előjeles poliedrikus forma és szoimplex forma). Erős dualitás tétel és bizonyítása.
18. Egy LP feladat feltételeiből felső becslés levezetése a célfüggvény értékére. LP feladatok dualizálása (poliedrikus forma, előjeles poliedrikus forma és szoimplex forma). Primál és duális leheséges megoldások párja azonos célfüggvény értékkel. Laza és nem-laza feltételek. Komplementáris lazasági feltétel.
19. A minimális költségű feszítőfa probléma. Kruskal algoritmusa. A mohó "filozófia". A Kruskal-algoritmus matematikai elemzése.
20. Gráfok, irányított gráfok. Séták és utak, gráfelméleti távolság, súlyozott távolság. Legrövidebb út problémája. Súlyozatlan eset: Szélességi keresés. Szélességi kereső fa.
21. Legrövidebb út problémájának algebraizálása. Irányított gráf pont-él illeszkedési mátrixa. IP alapfeladat. LP relaxáció. Mátrixok TU tulajdonsága. Irányított gráf pont-él illeszkedési mátrixa és a TU tulajdonság kapcsolata, illetve ennek következménye.
22. Dijkstra algoritmusa: címke update-elés. Az algoritmus helyességének indoklása.
23. Párosítások. Párosítási probléma: súlyozatlan, súlyozott eset. Súlyozatlan eset: Mohó algoritmus. Lefogó ponthalmazok és kapcsolatuk a párosításokkal. A mohó algoritmus outputjának méretére vonatkozó tétel.
24. Párosítások. Párosítási probléma: súlyozatlan, súlyozott eset. Súlyozatlan eset: Javító utak, javító utas algoritmus. Javító út keresése: címkézés és dupla ághajtásos növelése. Lefogó ponthalmazok és kapcsolatuk a párosításokkal. A mohó címkebővítéses algoritmus páros gráfokban működik.
25. Páros gráfok, hozzárendelési probléma. Egerváry-számozások és kapcsolatuk az optimális súlyú párosításokkal. Éles élek. A magyar módszer leírása.