Operációkutatás vizsgakérdések

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.
   • 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.
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.
   • 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.
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.
   • 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.
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.
   • 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.
5. • 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.
   • 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.
6. • 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.
   • Dijkstra algoritmusa: címke update-elés. Az algoritmus helyességének indoklása.
7. • 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.
   • 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.
8. • 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.
   • 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.
9. • 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.
   • A minimális költségű feszítőfa probléma. Kruskal algoritmusa. A mohó "filozófia". A Kruskal-algoritmus matematikai elemzése.
10. • 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.
    • 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.
11. • 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).
    • Dijkstra algoritmusa: címke update-elés. Az algoritmus helyességének indoklása.
12. • 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.
    • 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.
13. • 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.
    • 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.
14. • 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.
    • Dijkstra algoritmusa: címke update-elés. Az algoritmus helyességének indoklása.
15. • 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.
    • 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.
16. • 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.
    • 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.
17. • 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.
    • 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.
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). Gyenge dualitás tétel és bizonyítása.
    • 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.
19. • 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.
    • A minimális költségű feszítőfa probléma. Kruskal algoritmusa. A mohó "filozófia". A Kruskal-algoritmus matematikai elemzése.
20. • 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.
    • 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.