Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Anotace:
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:
A4M35KO
Osnovy přednášek:
| 1. | | Uvedení základních pojmů z kombinatorických algoritmů, příklady aplikací. |
| 2. | | Složitost kombinatorických problémů. |
| 3. | | Celočíselné lineární programování - algoritmy. |
| 4. | | Formulace problémů pomocí celočíselného lineárního programování. |
| 5. | | Nejkratší cesty. |
| 6. | | Formulace problémů pomocí nejkratších cest. |
| 7. | | Toky a řezy v sítích - formulace problémů a algoritmy. |
| 8. | | Párování v bipartitních grafech. |
| 9. | | Problém batohu, pseudo-polynomiální a aproximační algoritmy. |
| 10. | | Úloha obchodního cestujícího. |
| 11. | | Rozvrhování na jednom procesoru. |
| 12. | | Paralelní procesory. |
| 13. | | Programování s omezujícími podmínkami. |
| 14. | | Rezerva |
Osnovy cvičení:
| 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. | | Úloha obchodního cestujícího |
| 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 - vyhodnocení a písemná zpráva |
| 13. | | Zápočet |
| 14. | | Rezerva |
Literatura:
| B. | | H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms. |
Springer, sixth ed., 2018.
http://dx.doi.org/10.1007/978-3-662-56039-6
| J. | | Blazevicz, Scheduling Computer and Manufacturing Processes. Springer, |
second ed., 2001.
| J. | | Demel, Grafy a jejich aplikace. Academia, second ed., 2015. |
https://kix.fsv.cvut.cz/~demel/grafy/gr.pdf
Požadavky:
Optimalizace, Diskrétní matematika, Logika a grafy
Poznámka:
| Rozsah výuky v kombinované formě studia: 21p+6c |
Předmět je zahrnut do těchto studijních plánů:
| Stránka vytvořena 31.3.2023 17:50:04, semestry: Z/2024-5, Z,L/2022-3, Z/2023-4, připomínky k informační náplni zasílejte správci studijních plánů |
Návrh a realizace: I. Halaška (K336), J. Novák (K336) |