Detail předmětu
Optimalizační modely I
FSI-SOM-A Ak. rok: 2025/2026 Zimní semestr
Předmět je zaměřen na základní optimalizační modely a metody pro řešení logistických problémů. Výklad se opírá o základní zásady matematického programování prezentované v následujících krocích: 1) formulace a analýza problémů, 2) sestavování matematických modelu, 3) jejich klasifikace,
případná transformace a posouzení jejich teoretických vlastností, 4) výběr a úpravy řešících algoritmů, 5) jejich softwarová implementace 6) nalezení, analýza a interpretace optimálních řešení. Předmět zejména zahrnuje témata lineárního programování (konvexní a polyedrické množiny,
simplexová metoda, dualita) a nelineárního programování (konvexní funkce, podmínky optimality, vybrané algoritmy). Náplň předmětu byla autorem sestavena na základě jeho zkušeností s obdobnými kursy na zahraničních školách, kde působil.
Jazyk výuky
angličtina
Počet kreditů
6
Garant předmětu
Zajišťuje ústav
Vstupní znalosti
Základní poznatky diferenciálního a integrálního počtu, lineární algebry a programování.
Pravidla hodnocení a ukončení předmětu
Zápočet je udělen na základě aktivní účasti studenta na výuce předmětu a jeho významného podílu na zpracování skupinových domácích projjektů během semestru. Zkouška je založena na vypracování písemné práce zahrnujcí formulační, výpočtové a teoretické otázky. K písemné práci pak probíhá ústní rozprava se studentem. Úč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
Předmět se zaměřuje na seznámení studentů se základními poznatky z oblasti optimalizace – matematického programování. Důraz je kladen na uvedení podstatných informací o modelech a metodách řešení optimalizačních problémů. Jedná se zejména o uvedení do analýzy rozhodovacích problémů, tvorby základních (lineárních a nelineárních) matematických modelů, jejich formálních zápisů a rozborů jeho vlastností, vhodných
transformací modelů z pohledu jejich řešitelnosti, volby a modifikací algoritmů. Teoretický výklad uvedených poznatků je podložen ilustrujícími náázornými geometrickými a číselnými příklady s cíllem vést studenty k hlubokému a aplikačně užitečnému pochopení přednášené látky.
Předmět je určen pro studenty Logistics Analytics a je užitečný pro studenty aplikovaných věd a vybraných inženýrských oborů. Účastnící se studenti získají znalosti teoretických základů optimalizace (zejména lineárního a nelineárního programování), osvojí si obecné principy modelování a vybrané algoritmy řešení optimalizačních úloh a utvoří si základní představu o uplatnění optimalizačních modelů v typických aplikacích.
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. Tvorba optimalizačních modelů (LP, NLP příklady, klasifikace, pravidla a kroky)
2. Úvodní optimalizační pojmy a jejich využití (spojitost, kompaktnost, konvexnost množin a funkcí)
3. Hlavní algoritmické ideje (grafické řešení, optimalizační software – přehled)
4. Základní teoretické poznatky lineárních úloh (polyedrické množiny, standardní tvar úlohy LP a její vlastnosti, krajní body, krajní směry, věta o reprezentaci)
5. Klíčové ideje simplexové metody (podmínky optimality, geometrický a algebraický přístup, kompaktní popis)
6. Simplexová metoda (tabulkový tvar, maticový tvar, dvoufázová metoda, M metoda)
7. Pokročilá témata simplexové metody (degenerace, konvergence, zacyklení, paměťové a iterační nároky, redukované ceny)
8. Dualita v LP – syntaktická pravidla (kanonický a standardní tvar, duální simplexová metoda)
9. Dualita v LP sémantika (slabá věta o dualitě, silná věta o dualitě, věta o komplementaritě, stínové ceny)
10. Pokročilá témata LP (citlivost, meze, aktualizace, parametric ká analýza)
11. NLP – volné extrémy (kvadratické a speciální případy, konvexní a nekonvexní úlohy, podmínky optimality, analytické řešení, základní numerické přístup, reformulace)
12. NLP – vázané extrémy (kvadratické programování, formulace a speciální případy, podmínky optimality – KKT, poznámky o numerickém řešení)
13. NLP – speciální případy v logistice
Cvičení s počítačovou podporou
26 hod., povinná
Osnova
1. Tvorba optimalizačních modelů, typické logistické aplikace (LP, NLP příklady)
2. Využití optimalizačních pojmů na příkladech
3. Hlavní algoritmické ideje na příkladech, zejména grafické řešení, využití optimalizačního software na příkladech
4. Příklady využití základních teoretických poznatků lineárních úloh pro polyedrické množiny, převod na standardní tvar úlohy LP, výpočty krajních bodů a krajních směrů, využití věty o reprezentaci
5. Klíčové ideje simplexové metody na příkladech
6. Simplexová metoda pomocí tabulkového i maticového tvaru, příklady dvoufázové metody a M metody
7. Pokročilá témata simplexové metody na příkladech, příklady degenerace a zacyklení, redukované ceny
8. Dualita v LP – příklady na syntaktická pravidla a výpočty duální simplexovou metodou
9. Dualita v LP – příklady na využití slabé věty o dualitě, silné věty o dualitě, věty o komplementaritě, určení stínových cen
10. Pokročilá témata LP – vybrané příklady na citlivost, určení mezí a efektivní aktualizaci, parametrická analýza na příkladě
11. NLP – volné extrémy – výpočty příkladů, využití podmínek optimality, analytické a numerické výpočty, ukázky reformulace úloh
12. NLP – vázané extrémy – výpočty pro kvadratické programování, formulace NLP pro speciální případy, výpočty pro podmínky optimality – KKT, ukázky numerického řešení
13. NLP – příklady speciální úloh