Alkalmazott optimalizálás és játékelmélet

Bevezetés
Optimalizálás, folytonos, diszkrét és dinamikus feladatok
Játékelmélet, nem-kooperatív, kooperatív és dinamikus játékok

OPTIMALIZÁLÁS
Bevezetés az optimalizálásba
Célfüggvény, feltételes és kötetlen optimalizálás, megengedett megoldások
Az optimalizálási problémák (nemlineáris, kvadratikus, lineáris; valós értékű, diszkrétváltozós és egész értékű; kötött, kötetlen; statikus, dinamikus) és algoritmusok osztályozása (egy- és sokváltozós, kereső- és gradiensalapú eljárások, általános heurisztikák)
Lokális és globális optimum, a konvexitás szerepe, konvex programozás
Modellezési technikák, a modellezés lépései, hibafüggvények. Konkrét műszaki problémák megfogalmazása optimalizálási feladatként. Megoldószoftverek.

A lineáris programozás
A lineáris programozás alapjai, a lineáris programok általános alakja, a modellezhető problémák általános jellemzői, példák és alkalmazások
Lineáris programok megoldása, grafikus megoldás, bázismegoldások, a szimplex algoritmus, optimalitás, nemkorlátos megoldások, a degeneráció fogalma és kezelése, komplexitás, a szimplex tábla, példák megoldása a szimplex tábla segítségével
Lineáris programok duáljai és a duál szimplex, Farkas lemmája, a dualitás fogalma, a duális előállítása, a dualitás gyenge és erős tétele, a duál szimplex algoritmus
A lineáris programozás klasszikus alkalmazásai, a szállítási probléma, az ütemezési probléma, hálózati folyamproblémák, folyamok egészértékűsége, többtermékes folyamok, duálisok
Lineáris programok megoldása számítógépes programcsomaggal

Nemlineáris programozás
Feltételmentes nemlineáris optimalizálás: kötetlen szélsőérték-keresés, a gradiens módszer, másodrendű gradiens módszerek, a Newton módszer
Feltételek szerinti nemlineáris programozás: a nemlineáris programok általános alakja, az optimalitás szükséges és elégséges feltételei
Nemlineáris programok megoldásának visszavezetése kötetlen optimalizálásra: az iránykeresés módszere. Visszavezetés lineáris programok megoldására: szukcesszív lineáris programozás

Diszkrét (kombinatorikus) optimalizálás
Lokális és globális optimum.
Statikus és Dinamikus optimalizálás (dinamikus programozás)
Többcélú optimalizálás
Helyi (lokális) keresés
Mohó, iteratív és „véletlen” módszerek
Állapottér, szomszédosság, célfüggvény
Állapottér szűkítése, korlátok kezelése
Heurisztikák
Egészértékű és bináris lineáris programozás
Bonyolultság. Kapcsolat a folytonos és diszkrét optimalizálás között. Kapcsolat a bináris és egészértékű optimalizálás között
Kevert egészértékű LP (MILP)
ILP megoldó módszerek: Branch and bound, Cutting plain, Branch and cut, Lagrangian relaxation, Column Generation
Példák: útvonalválasztás, töbtermékes hálózati folyamok, osztatlan folyamok, diszjunkt osztatlan folyamok

Általánosan alkalmazható optimalizáló heurisztikák
Simulated Annealing: energia függvény, szomszédosság, kezdő hőmérséklet, hűtési szabályok, kiinduló pont
Threshold Accepting: a küszöbérték megválasztása
Tabu Search: Tabu lista típusai
Genetic (Evolutionary) Algorithms: különböző reprezentációk, GA operátorok, kereszteződések, mutációk
Go With the Winner: fa mélysége és optimalizálás kapcsolata
STAGE: becslésekkel gyorsított optimalizálás
Példák: TSP (utazóügynök feladat), Hátizsák probléma és ládapakolás, Simulated Allocation (szimulált foglalás)

JÁTÉKELMÉLET

Bevezetés
Mi a játékelmélet
Racionális választás elmélete

Nash egyensúly: Elmélet és illusztráció
Stratégiai játékok
Nash-egyensúly fogalom
A legjobb válasz fogalma és domináns stratégiák
Szimmetrikus játékok és szimmetrikus egyensúlyok
Algoritmusok a tiszta stratégiai Nash-egyensúlyok keresésére

Kevert stratégiai játékok 
Stratégiai játékok kevert bővítése
Von Neumann - Morgenstein kifizetési függvények
Kevert stratégiai Nash-egyensúly
Nash tétele a kevert stratégiai Nash egyensúly létezéséről
Algoritmusok a kevert stratégiai egyensúlyok keresésére

Dinamikus játékok: elmélet és illusztráció
Alapfogalmak
Aljáték-tökéletes egyensúly
Hátráló indukció algoritmus
Ismételt játékok
Nash tétele (Nash folk theorem)
Stackelberg-féle játékok és Stackelberg-egyensúly kiszámítása
Végtelen dinamikus játékok

Kooperatív játékok
Általános fogalmak
Shapley-értékek vizsgálata
A mag (The Core) fogalma
Sztochasztikus játékok

Műszaki alkalmazások, esettanulmányok
Hálózatmenedzsment (erőforrás-foglalás, torlódásvezérlés, „peering”-megállapodások, ütemezés)
Útvonalválasztás (QoS routing, optimális útvonalválasztás-vezérlés)
Torlódásvezérlés (TCP paraméter-beállítások)

KITEKINTÉS
Az optimalizálás és játékelmélet alkalmazási területeinek áttekintése és rendszerezése
Nyilvánosan elérhető optimalizálási programok, valamint optimalizálással foglalkozó toolbox-ok áttekintése.