Síťové toky v logistice (FSI-SNF-A)

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. 

Předpokládají se znalosti základních pojmů lineární optimalizace a teorie grafů (návaznost na předmět SGA-A Grafy a algoritmy).  

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). Bude probrán konkrétní případ distribuce prostředků zelené mikromobility na místa jejich vypůjčení, jejich relokace a servis, což vede na úlohu multikriteriální celočíselné optimalizace na Time-Space síti. Bude navržen specifický výpočetní algoritmus a diskutována jeho složitost.  

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.

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.

9.-10. Matematická formulace problému multikriteriální celočíselné optimalizace na Time-Space síti.

11.-13. Návrh výpočetního algoritmu, implementace a složitost.

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.

9.-10. Formulace problému multikriteriální celočíselné optimalizace v modelovacím prostředí.

11.-13. Návrh a implementace algoritmů řešení (přepis na single-objective, Pareto frontier)

Bazaraa, M.S. et al. Linear Programming and Network Flows, 4th edition, Wiley, 2010.