Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Webová stránka:
https://moodle.dce.fel.cvut.cz/course/view.php?id=21
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é 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 |
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. | | 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 |
Literatura:
| 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/
Požadavky:
Optimalizace, Diskrétní matematika, Logika a grafy
Poznámka:
Předmět je zahrnut do těchto studijních plánů:
| Plán |
Obor |
Role |
Dop. semestr |
| Stránka vytvořena 14.3.2025 15:50:53, semestry: Z/2025-6, L/2024-5, L/2025-6, Z/2024-5, 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) |