Detail předmětu

Výpočtové metody v logistických optimalizačních úlohách

FSI-SOU-A Ak. rok: 2027/2028 Letní semestr

Předmět se zabývá matematickými a výpočetními metodami pro řešení optimalizačních problémů se zaměřením na logistiku, plánování a řízení procesů. Studenti se seznámí s principy vybraných exaktních, deterministických a stochastických optimalizačních algoritmů, jejich implementací a možnostmi využití při řešení praktických úloh. Důraz je kladen na rozpoznání struktury optimalizačního problému, výběr vhodné metody a experimentální vyhodnocení kvality získaných řešení.

Úvodní část předmětu zahrnuje jednorozměrnou a vícerozměrnou spojitou optimalizaci, gradientní metody, metody Newtonova typu, přímé a stochastické metody a populační algoritmy. Následují metody optimalizace s omezeními, penalizační reformulace, metoda rozšířeného Lagrangiánu, metody vnitřního bodu, simplexová metoda a vybrané metody celočíselné optimalizace.

Další část se zaměřuje na heuristické a metaheuristické algoritmy vhodné zejména pro kombinatorické optimalizační problémy. Probírány jsou metody lokálního prohledávání, iterovaného lokálního prohledávání, GRASP, prohledávání s proměnným okolím, tabu prohledávání, simulovaného žíhání, evoluční algoritmy a optimalizace mravenčími koloniemi. Součástí předmětu jsou také vícekriteriální optimalizační algoritmy NSGA-II a MOEA/D a úvod do modulárních implementací a automatické konfigurace algoritmů.

Počítačová cvičení se zaměřují na implementaci a experimentální analýzu vybraných metod, práci s dostupnými optimalizačními knihovnami a jejich využití při řešení modelových logistických problémů, například plánování tras, rozvrhování, přiřazování a dalších rozhodovacích úloh. Studenti porovnávají kvalitu řešení, výpočetní náročnost a spolehlivost použitých postupů.

Jazyk výuky

angličtina

Počet kreditů

Garant předmětu

doc. Ing. Jakub Kůdela, Ph.D.

Zajišťuje ústav

Ústav automatizace a informatiky

Vstupní znalosti

Předpokládá se znalost základů matematické optimalizace, zejména formulace optimalizační úlohy, pojmů účelová funkce, rozhodovací proměnné a omezení a základních principů numerických optimalizačních metod.

Z matematických disciplín jsou požadovány základy lineární algebry, diferenciálního počtu funkcí jedné a více proměnných, pravděpodobnosti a matematické statistiky.

Student by měl ovládat základy programování, včetně práce s funkcemi, datovými strukturami, podmíněnými příkazy a cykly, a být schopen samostatně implementovat, spustit a testovat jednoduchý algoritmus. Předchozí znalost konkrétních logistických optimalizačních algoritmů není vyžadována.

Způsob zakončení předmětu a pravidla hodnocení studentů

Podmínky udělení zápočtu: aktivní účast ve cvičeních, zvládnutí celé látky, odevzdání semestrální práce.

Zkouška: Písemná zkouška zaměřená na úspěšnou implementaci probíraných metod s ústní rozpravou o výsledcích.

Účast je kontrolována pomocí aktivní účasti studentů na řešených problémech, zameškaná výuka je nahrazována samostatným řešením zadaných úloh.

Učební cíle

Po úspěšném absolvování předmětu student:

Formuluje a klasifikuje vybrané logistické optimalizační problémy, identifikuje jejich rozhodovací proměnné, účelové funkce a omezení a na základě struktury problému zdůvodní volbu vhodného optimalizačního postupu.
Aplikuje a porovná vybrané metody spojité optimalizace, včetně gradientních metod, metod Newtonova typu, přímých a stochastických metod, a posoudí jejich vhodnost pro úlohy s různými vlastnostmi účelové funkce a omezení.
Použije a vyhodnotí vybrané postupy optimalizace s omezeními a celočíselného programování, včetně penalizačních metod, metody rozšířeného Lagrangiánu, metod vnitřního bodu, simplexové metody a principů větvení a mezí.
Navrhne, implementuje a analyzuje vybrané heuristické a metaheuristické algoritmy založené na lokálním prohledávání a prohledávání okolí, zejména pro kombinatorické logistické úlohy, a posoudí vliv volby reprezentace řešení a okolí na jejich účinnost.
Implementuje nebo vhodně použije vybrané populační, evoluční a vícekriteriální optimalizační algoritmy, včetně metod inspirovaných kolektivním chováním, a porovná jejich výsledky z hlediska kvality řešení a výpočetní náročnosti.
Navrhne a provede reprodukovatelný výpočetní experiment s vybranými optimalizačními algoritmy, vyhodnotí výsledky pomocí vhodných ukazatelů, využije dostupné algoritmické frameworky a posoudí přínos automatické konfigurace parametrů.

Studijní opory

Studijní opory zahrnují materiály k přednáškám, zadání počítačových cvičení, ukázkové implementace optimalizačních algoritmů, testovací úlohy. Materiály jsou zpřístupňovány prostřednictvím univerzitního e-learningového prostředí.

Použití předmětu ve studijních plánech

Program N-LAN-A: Logistics Analytics, magisterský navazující, povinný

Typ (způsob) výuky

Přednáška

26 hod., nepovinná

Osnova

1. Úvod do optimalizačních algoritmů a optimalizace v 1D

2. Spádové metody, gradientní metody, metody Newtonova typu

3. Přímé a stochastické metody

4. Populační metody pro spojité úlohy

5. Penalizační reformulace, metoda Augmented Lagrangian

6. Metody vnitřního bodu, barierová metoda, dvojfázové metody

7. Simplexová metoda v maticovém tvaru, Celočíselná a kombinatorická optimalizace – metoda větví a mezí, Gomoryho řezy

8. Metody Local Search, Iterated Local Search, GRASP

9. Metody Variable Neigborhood Search, Tabu Search a Simulated Annealing

10. Evoluční algoritmy, genetické algoritmy

11. Hejnové algoritmy, metoda Ant Colony Optimization

12. Vícekriteriální metody, metody NSGA-II a MOEA/D

13. Dostupné softwarové implementace, modulární frameworky, automatický návrh algoritmů a moderní přístupy

Cvičení s počítačovou podporou

26 hod., povinná

Osnova

Implementace a analýza následujících metod:

1. 1D optimalizační metody

2. Spádové metody, gradientní metody, metody Newtonova typu

3. Přímé a stochastické metody

4. Populační metody pro spojité úlohy

5. Augmented Lagrangian a penalizační metody

6. Metody vnitřního bodu, barierová metoda, dvojfázové metody

7. Simplexová metoda v maticovém tvaru, metoda větví a mezí, Gomoryho řezy