Szeptember - 2018
H K S C P S V
  01 02
03 04 05 06 07 08 09
10 11 12 13 14 15 16
17 18 19 20 21 22
24 25 26 27 28 29 30

Tantárgy adatlap

Operációkutatási (optimalizálási) modellek

Tantárgy adatlap letöltése: Letöltés

A tantárgy kódja: 4OP13NAK14M
A tantárgy megnevezése (magyarul): Operációkutatási (optimalizálási) modellek
A tantárgy neve (angolul): Operations Research (Optimization) Models
A tanóra száma (Előadás + szeminárium + gyakorlat + egyéb): 2+2 v
Kreditérték: 5
A tantárgy meghirdetésének gyakorisága: tavaszi félév
Az oktatás nyelve: magyar
Előtanulmányi kötelezettségek: Operációkutatás
A tantárgy típusa: Választható szaktárgy
Tantárgyfelelős tanszék: Operációkutatás és Aktuáriustudományok Tanszék
A tantárgyfelelős neve: Biró Péter

A tantárgy szakmai tartalma: A tárgy kombinatorikus optimalizálással foglalkozik.
Gréfelméleti alapozás után foglalkozunk a Ford Fulkerson algoritmus kombinatorikai következményeivel.
További fontosabb témakörök:Párosítások és súlyozott párosítások optimalizálása páros gráfban.
Párosítások és súlyozott párosítások optimalizálása nempáros gráfban.
Poliéderek és politópok.
Matroidok.
Teljesen unimoduláris mátrixok.

Évközi tanulmányi követelmények: Részvétel a félév során három alkalommal meghirdetett pályázatokon.
Mindegyik pályázaton a legjobb(ak) 10 pontot kaphat(nak).

Vizsgakövetelmény: Szóbeli vizsga, ahol elméleti tétel és feladatmegoldás is szerepel.

Az értékelés módszere: A vizsgét pontozzuk.
A vizsgapontszámhoz hozzáadódik a pályázatokon esetleg szerzett pontszám.

40 pontttól elégséges, 85-től jeles.

Tananyag leírása: 1. hét: Konvex halmazok, konvex burok. A szeparációs tétel. Poliedrikus halmaz, poliéder, politóp. Extremális pontok jellemzése. Minden poliéder az extremális pontjainak konvex burka. Duplán sztochasztikus mátrixok.

2. hét: 0-körüli politóp, politóp konjugáltja. 0-körüli politóp a konjugáltjának a konjugáltja. Minden politóp poliéder. Maximális folyam, minimális vágás. Folyam értéke, vágás kapacitása. Gyenge és erős dualitás tétel. Javítás út illetve lánc mentén. A Ford-Fulkerson algoritmus.

3. hét: A Ford-Fulkerson algoritmus végigkövetése példán. Gráfelméleti alapok. Irányított és irányítatlan gráfok. Pont-pont mátrix, él-pont mátrix. Fokszám. Fa és kör. Részgráf és feszített részgráf. Összefüggőség. Fa ekvivalens definíciói. Páros gráfok jellemzése. A mod 2 test. Bn vektortér. Körök, illetve lineáris összefüggőség kapcsolata az él-pont mátrixban.

4. hét: Euler gráfok. Szükséges és elégséges feltétel. k-szoros pont- illetve él-összefüggőség. Menger tételei irányított és irányítatlan gráfokban.

5. hét: Maximális számú független él, minimális számú lefogó pont páros gráfokban. Kőnig-Egerváry tétel. (n,n) pontú k-reguláris páros gráf élhalmaza k db diszjunkt teljes párosítás uniója. Maximális számú független él páros gráfokban. Mendelssohn-Dulmage tétel.

6. hét: Maximális súlyozott párosítás páros gráfban. Teljes párosítás politóp és párosítás politóp páros gráfban.


7. hét: A hozzárendelési feladat Minimális összsúlyú teéljes párosítás páros gráfban primál-duál algoritmussal.

8. hét: Maximális számú független él nempáros gráfokban. Blossom és kontrakció. Edmonds algoritmus.

9. hét: Minimális kapacitású páratlan ponthalmaz-fedés. Az Edmonds politópok nempáros gráfban.


10. hét: Minimális összsúlyú teljes párosítás nempáros gráfban primál-duál algoritmussal.

11. hét: Maximális összsúlyú párosítások. A kínai postás probléma.

12. hét: Matroid axiómák. Mátrix matroid, gráf matroid, matching matroid, partíció matroid.

13. hét: Bázis, rang, kör. A mohó algoritmus. A matroid politóp.

14. hét: Teljesen unimoduláris mátrixok. Hoffman Kruskal tétel. Irányítatlan gráfok él-pont mátrixai. Irányított gráfok él-pont mátrixai.

Órarendi beosztás: NEPTUN szerint

Kompetencia leírása: 

Félévközi ellenőrzések: 

A hallgató egyéni munkával megoldandó feladatai: 

Szak neve: Gazdaságmatematikai elemző mesterszak

Irodalomjegyzék:
Kötelező irodalom:

  • Fiala Tibor: Kombinatorikus optimalizálás, AULA, 2010 (tervezett)

Ajánlott irodalom:

  • 1.Eugene Lawler: Kombinatorikus optimalizálás: hálózatok és matroidok, Műszaki Könyvkiadó, Budapest, 1982.
  • 2.Eugene Lawler: Combinatorial Optimization, Networks and Matroids,Dover Publications, INC. Mineola, New York, 1976.
  • 3. Alexander Schrijver: A course on Combinatorial Optimization, CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands, 2009.
  • http://homepages.cwi.nl/~lex/files/dict.pdf
Ajánlott irodalmak:
Eugene Lawler: Kombinatorikus optimalizálás: hálózatok és matroidok, Műszaki Könyvkiadó, Budapest, 1982.
Megtalálható a Központi Könyvtárban
Eugene Lawler: Combinatorial Optimization, Networks and Matroids,Dover Publications, INC. Mineola, New York, 1976.
Alexander Schrijver: A course on Combinatorial Optimization, CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands, 2009.
Kötelező irodalmak:
Fiala Tibor: Kombinatorikus optimalizálás, AULA, 2010 (tervezett)
Megtalálható a Központi Könyvtárban

 
A tantárgy oktatói:

Utolsó módosítás:

Kurzusok

Kurzus kódTipusFélévOktatói


A "Tantárgyfelelős tanszék", a tantárgyfelelős neve a tantárgy oktatói és a kurzusinformációk automatikusan frissülnek a tanulmányi rendszerünk alapján.