Operációkutatás vizsgakérdések
2024 Tavasz
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
Szakasszal, egyenessel való összekötés leírása Rn-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.
-
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.
-
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.
-
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 Rn-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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.