Optimalizace v inteligentních systémech

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 algoritmy řešícími problémy kombinatorické optimalizace. V návaznosti na předmět algoritmizace jsou ukázány základní 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 optimalizačních technik v inteligentních systémech pro využití skladů, pozemní přepravu, leteckou přepravu, logistiku, plánování lidských zdrojů, rozvrhování strojů ve výrobě, směrování zpráv v sítích, rozvrhování úloh v paralelních počítačích.

Požadavky:

Lineární algebra

Agoritmizace

Osnova přednášek:

Přednášky

1.Příklady aplikací a uvedení základních pojmů z kombinatorické optimalizace

2.Formulace problémů a časová náročnost algoritmů

3.Komunikační a dopravní problémy založené na hledání nejkratší cesty a stromu

4.Toky v sítích

5.Lineární programování

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

7.Příklady řešení kombinatorických problémů metodou větví a mezí

8.Heuristiky a metody umělé inteligence

9.Plánování trajektorie metodou dynamického programování

10.Úloha obchodního cestujícího

11.Využití kapacit a problém batohu

12.Aplikace úloh rozvrhování na jednom procesoru

13.Rozvrhování na paralelní procesory

14.Rozvrhování v dílně

Cvičení

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

2.Minimální kostra grafu a shluková analýza

3.Dopravní úloha na hledání nejkratší cesty

4.Aplikace toků v sítích

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

6.Rozvrhování a Metoda větví a mezí

7.Aproximační algoritmy a SAT problém

8.Test

9.Konzultace individuální práce - zadání

10.Konzultace individuální práce - návrh algoritmu

11.Konzultace individuální práce - implementace algoritmu

12.Konzultace individuální práce - experimenty

13.Odevzdání individuální práce

14.Zápočet

Osnova cvičení:

V přednáškách je cílem seznámit studenty se základními stavebními kameny kombinatorické optimalizace.

Ve cvičeních se studenti seznámí s experimentálním prostředím a optimalizační knihovnou, aby si mohli na úlohách optimalizace skladu, rozvrhování na paralelní procesory, optimalizace výrobního postupu a dalších procvičit látku probíranou na přednáškách. S využitím takto nabytých znalostí budou ve druhé části semestru studenti pracovat na samostatné úloze.

Cíle studia:

Studijní materiály:

Main textbook

[1] B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms. Springer, third ed., 2006.

Some parts of:

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

[3] J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer, second ed., 2001.

Poznámka:

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ů:

• Inteligentní systémy (povinný předmět)