Moodle FEL ČVUT
Kombinatorická optimalizace
Tento předmět se nenachází v Moodle. Na jeho domovskou stránku se můžete dostat pomocí tlačítka "Stránka kurzu (mimo Moodle)" vpravo (pokud existuje).
Kombinatorická optimalizace AD4M35KO
| Kredity | 6 |
| Semestry | letní |
| Zakončení | zápočet a zkouška |
| Jazyk výuky | čeština |
| Rozsah výuky | 21KP+6KC |
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: http://www.fel.cvut.cz/anketa/aktualni/courses/A4M35KO
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
Cíle studia
Žádná data.
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
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
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/
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
Za správnost dat zodpovídá:
Studijní Informační Systém (KOS)