Počet kreditů 6
Vyučováno v Letní
Rozsah výuky 3+2c
Garant předmětu
Přednášející
Cvičící

Cílem předmětu je seznámit studenty s problémy a algoritmy

kombinatorické optimalizace (často se nazývá diskrétní optimalizace,

významně se překrývá s pojmem operační výzkum). V návaznosti na

předměty z oblasti lineární algebry, algoritmizace, diskrétní

matematiky a základů optimalizace jsou ukázány techniky založené na

grafech, celočíselném lineárním programování, heuristikách,

aproximačních algoritmech a metodách prohledávání prostoru řešení.



Předmět je zaměřen na aplikace optimalizace ve skladech, pozemní a letecké dopravě, logistice, plánování lidských zdrojů, rozvrhování výrobních linek, směrování zpráv, rozvrhování v paralelních počítačích. \\Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A4M35KO

Optimalizace, Diskrétní matematika, Logika a grafy

  1. Uvedení základních pojmů z kombinatorické optimalizace, příklady aplikací.
  2. Celočíselné lineární programování - algoritmy.
  3. Formulace problémů pomocí celočíselného lineárního programování.
  4. Nejkratší cesty.
  5. Formulace problémů pomocí nejkratších cest.
  6. Toky a řezy v sítích - formulace problémů a algoritmy. Párování v bipartitních grafech. Test I.
  7. Multi-komoditní toky.
  8. Problém batohu, pseudo-polynomiální a aproximační algoritmy.
  9. Úloha obchodního cestujícího.
  10. Rozvrhování na jednom procesoru.
  11. Paralelní procesory. Test II.
  12. Rozvrhování projektu s časovými omezeními.
  13. Programování s omezujícími podmínkami.
  14. Rezerva

  1. Seznámení s předmětem a pravidly.
  2. Seznámení s experimentálním prostředím a knihovnou pro optimalizaci
  3. Celočíselné lineární programování
  4. Samostatná úloha I - zadání a kategorizace
  5. Modelovácí jazyky pro řešení problémů kombinatorické optimalizace
  6. Samostatná úloha II - rešerše literatury a prezentace řešení
  7. Aplikace toků a řezů v sítích
  8. Samostatná úloha III - konzultace
  9. Test III
  10. Rozvrhování
  11. Pokročilé metody pro řešení problémů kombinatorické optimalizace
  12. Samostatná úloha IV - odevzdání algoritmu a písemné zprávy
  13. Zápočet
  14. Rezerva

B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms.

Springer, third ed., 2006.



J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,

second ed., 2001.



J. Demel, Grafy a jejich aplikace. Academia, second ed., 2002.

TORSCHE http://rtime.felk.cvut.cz/scheduling-toolbox/

Rozvrh předmětu
Po
Út
St
Čt
PřednáškyCvičení