Detail předmětu

Síťové toky v logistice

FSI-SNF-AAk. rok: 2024/2025

Předmět je zaměřen na základní síťové modely a metody pro řešení logistických úloh. Výklad navazuje na lineární optimalizační modely a prohlubuje a konkretizuje pochopení následujících obecných principů matematické optimalizace: porozumění síťovému problému, sestavení síťového modelu a zohlednění případné celočíselnosti proměnných,  nalezení, analýza a interpretace optimálního řešení. Předmět zahrnuje zejména problematiku toků v sítích  (typické úlohy, formulace LP modelů, grafové formulace, speciální algoritmy řešení úloh). Součástí výkladu je rovněž seznámení se související problematikou celočíselného programování (formulace úloh, celočíselné toky, návrhy sítí, indikátorové proměnné, vybrané algoritmy a jejich softwarové implementace). Kurs byl sestaven na základě zkušeností autora s obdobnými kursy na zahraničních školách.

Jazyk výuky

angličtina

Počet kreditů

5

Garant předmětu

RNDr. Pavel Popela, Ph.D.

Zajišťuje ústav

Ústav matematiky (ÚM)

Vstupní znalosti

Předpokládají se znalosti základních poznatků lineární optimalizace.

Pravidla hodnocení a ukončení předmětu

Zkouška je písemná a zahrnuje formulační, výpočtové a teoretické otázky. K písemné práci probíhá ústní rozprava.


Úč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

Důraz je kladen na získání hlubokých znalostí modelů a metod řešení síťových optimalizačních úloh s důrazem na logistické aplikace. Cíle jsou zaměřeny na analýzy problémů, tvorbu
matematických modelů včetně jejich zápisů, nalezení  vhodných přepisů, výběr, úpravu a implementaci algoritmů. Uvedené modely a metody jsou podloženy výkladem vybraných teoretických poznatků.


Předmět je určen pro studenty logistiky a může být užitečný také pro studenty aplikovaných věd a inženýrství. Studenti získají hlubší znalosti problematiky toků v sítích a celočíselné optimalizace ve vztahu k logistickým úlohám. Dále získají představu o uplatnění síťových optimalizačních modelů v typických aplikacích.

Základní literatura

Bazaraa, M.S. et al. Linear Programming and Network Flows, 4th edition, Wiley, 2010. (EN)
Garcia-Diaz A. and Phillips, D.T. Fundamentals of Network Analysis and Flow Optimization, Virtualbook Publishing, 2022. (EN)
Ghiani, G. et al. Introduction to Logistics Systems Management, 3rd edition, Wiley, 2022. (EN)
Williamson, D.P. Network Flow Algorithms, Cambridge University Press, 2019. (EN)
Wolsey, L. Integer Programming, 2nd Edition, Wiley, 2020. (EN)

Doporučená literatura

Ghiani, G. et al. Introduction to Logistics Systems Management, 3rd edition, Wiley, 2022. (EN)
Nemhauser, G.L. and Wolsey, L.A. Integer and Combinatorial Optimization, 1st Edition, Wiley, 1988.  (EN)
Bazaraa, M.S. et al. Linear Programming and Network Flows, 4th edition, Wiley, 2010. (EN)
Sofer, A. et al. Linear and Nonlinear Optimization (Chapter 8 Network Problems), 2nd Edition, Society for Industrial and Applied Mathematics, 2009. (EN)
Williams, H.P. Model Building in Mathematical Programming, 5th edition, Wiley, 2013. (EN)

Zařazení předmětu ve studijních plánech

  • Program N-LAN-A magisterský navazující 1 ročník, letní semestr, povinný

  • Program C-AKR-P celoživotní vzdělávání v akr. stud. programu

    specializace CLS , 1 ročník, letní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

RNDr. Pavel Popela, Ph.D.

Osnova

1. Motivační problémy a základy modelování síťových úloh.

2. Dopravní úlohy, jejich LP modelování a jejich (softwarové) řešení.  

3. LP modely úloh o minimálním toku v síti a jejich (softwarové) řešení.  

4. Speciální úlohy o minimálním toku sítí (LP modely pro hledání nejkratší cesty a pro přiřazovací problém). Problém maximálního toku sítí. 

5. Úskalí řešení síťových úloh simplexovou metodu a jejich řešení. 

6.-7. Efektivní metody řešení vybraných síťových úloh.

8. Celočíselnost řešení v síťových úlohách. 

8. Modelování změn struktury sítí pomocí binárních proměnných. 

9. Základy celočíselné optimalizace. 

10. Metoda větví a mezí a její softwarové implementace.

11.  Indikátorvé proměnné a jejich aplikace.

12.-13. Vybrané logistické aplikace z oblastí alokace, distribuce a rozvrhování. 

 

Cvičení

26 hod., povinná

Vyučující / Lektor

RNDr. Pavel Popela, Ph.D.

Osnova

1. Příklady logistických úloh a jejich modelování síťovými úlohami.

2. Příklady dopravních úloh, jejich LP modelování a jejich (softwarové) řešení v modelovacím jazyce.

3. Příklady LP modelů úloh o minimálním toku v síti a jejich (softwarové) řešení v modelovacím jazyce.

4. Příklady speciálních úloh o minimálním toku sítí (LP modely pro hledání nejkratší cesty a pro přiřazovací problém). Příklad pro maximální tok sítí.

5. Příklady problémů řešení síťových úloh simplexovou metodu a jejich řešení.

6.-7. Efektivní metody řešení vybraných síťových úloh a příklady jejich použití.

8. Příklady celočíselnosti řešení v síťových úlohách.

8. Příklady modelování změn struktury sítí pomocí binárních proměnných.

9. Základy celočíselné optimalizace na příkladech.

10. Příklady pro metodu větví a mezí a jejich softwarové implementace. 

11. Indikátorové proměnné a jejich aplikace v logistických příkladech.

12.-13. Vybrané logistické aplikace z oblastí alokace, distribuce a rozvrhování - příklady.