Kombinatorická optimalizace

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra řídicí techniky

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í.

Požadavky:

Stránky předmětu: http://support.dce.felk.cvut.cz/e-kurzy/course/view.php?id=45

Osnova přednášek:

1. Uvedení základních pojmů z kombinatorické optimalizace, příklady aplikací

a ověření znalostí z prerekvizit formou testu

2. Celočíselné lineární programování - algoritmy

3. Formulace problémů pomocí celočíselného lineárního programování

4. Heuristiky, test

5. Nejkratší cesty

6. Toky v sítích a řezy

7. Multi-komoditní toky

8. Metoda dynamického programování, test

9. Problém batohu a pseudo-polynomiální algoritmy

10. Úloha obchodního cestujícího a aproximační algoritmy

11. Rozvrhování na jednom procesoru

12. Paralelní procesory

13. Rozvrhování projektu s časovými omezeními

14. Programování s omezujícími podmínkami

Osnova cvičení:

1. Seznámení s experimentálním prostředím a knihovnou pro optimalizaci

2. Celočíselné lineární programování

3. Aplikace celočíselného lineárního programování

4. Zadání samostaných úloh

5. Metoda větví a mezí

6. Nejkratší cesty

7. Aplikace toků a řezů v sítích

8. Prezentace průběžných výsledků samostatných úloh

9. Rozvrhování na jednom procesoru - Earliest deadline first

10. Aproximační algoritmy - List scheduling

11. Rezerva

12. Test

13. Odevzdávání samostatné úlohy

14. Zápočet

Cíle studia:

Studijní materiály:

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.

Poznámka:

Rozsah výuky v kombinované formě studia: 21p+6c

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: