Síťový model (operační výzkum)

From Systems analysis Wiki
Jump to navigation Jump to search

Síťové modely (v operačním výzkumu; angl. Network models) — jsou třídou matematických modelů, které reprezentují úlohu ve formě grafu (sítě), kde vrcholy (uzly) označují objekty nebo stavy a hrany (oblouky) — vazby nebo procesy mezi nimi[1]. V kontextu optimalizace se sítí často rozumí orientovaný graf, který je v operační analýze přímo nazýván „sítí"; vrcholy takové sítě se nazývají uzly a hrany — oblouky[2].

Síťové modely jsou mocným nástrojem pro analýzu a optimalizaci složitých systémů v oblastech, jako jsou logistika, telekomunikace, řízení projektů a finance. Jejich síla spočívá ve vysoké míře abstrakce: uzel může představovat město, počítačový směrovač nebo fázi projektu, a oblouk — silnici, komunikační kanál nebo technologickou operaci.

Definice a terminologie

Základem síťových modelů je teorie grafů. Klíčovými pojmy jsou:

  • Toková síť (angl. flow network): orientovaný graf, ve kterém má každá hrana kapacitu (capacity) a tok (flow). V grafu jsou vyčleněny dva zvláštní vrcholy: zdroj (source), ze kterého tok vychází, a spotřebič (sink), do kterého vstupuje[1].
  • Zákon zachování toku: Pro každý vrchol, který není zdrojem ani spotřebičem, musí být celkový vstupující tok roven celkovému vystupujícímu toku. Tato podmínka je diskrétní analogií fyzikálních zákonů zachování[3].
  • Síťové plánování: Model reprezentující projekt jako soubor vzájemně propojených operací (oblouků) a událostí (uzlů). Takové sítě jsou orientované acyklické grafy, což odráží pořadí provádění prací[4].

Klíčové vlastnosti a věty

Síťové modely mají řadu zvláštních vlastností, které umožňují používat pro jejich řešení vysoce efektivní algoritmy.

  • Celočíselnost řešení: Mnohé úlohy síťové optimalizace (například o maximálním toku nebo nejkratší cestě) mají vlastnost úplné unimodularity matice omezení. Díky tomu, pokud jsou parametry úlohy (kapacity, délky) celočíselné, bude i optimální řešení nalezené metodami lineárního programování celočíselné, aniž by bylo nutné zavádět další omezení[5][6].
  • Věta o maximálním toku a minimálním řezu: Ústřední výsledek teorie toků. Tvrdí, že maximální hodnota toku ze zdroje do spotřebiče se rovná minimální kapacitě ze všech řezů oddělujících zdroj a spotřebič. Tato věta stanovuje kritérium optimality pro tok a je základem mnoha algoritmů[6][7].
  • Princip optimality pro nejkratší cesty: Pokud je cesta z bodu A do bodu C nejkratší, pak každý její úsek (například od mezilehlého bodu B do C) je rovněž nejkratší cestou mezi příslušnými vrcholy. Tato vlastnost, která stojí v základu dynamického programování, zajišťuje správnost algoritmů jako je Dijkstrův algoritmus[8].
  • Vlastnosti minimální kostry grafu (MKG):
  • Vlastnost řezu: Pro každý řez grafu patří hrana s minimální vahou procházející řezem alespoň do jedné MKG.
  • Vlastnost cyklu: V každém cyklu grafu nepatří hrana s maximální vahou do žádné MKG.

Na těchto vlastnostech je založena správnost „hladových" algoritmů Prima a Kruskala[9].

Základní úlohy síťové optimalizace

  • Úloha nejkratší cesty: Nalézt cestu minimální celkové délky (váhy) mezi dvěma zadanými uzly. Řeší se Dijkstrovým algoritmem (pro nezáporné váhy) nebo Bellman-Fordovým algoritmem (pro libovolné váhy)[8].
  • Úloha maximálního toku: Určit maximálně možný tok ze zdroje do spotřebiče při zadaných kapacitách oblouků. Klasická metoda řešení — Ford-Fulkersonův algoritmus[6].
  • Úloha minimální kostry grafu: Nalézt podgraf, který spojuje všechny vrcholy sítě a má minimální celkové náklady na hrany.
  • Metoda kritické cesty (CPM): V síťových modelech plánování určit nejdelší posloupnost prací, která stanovuje minimálně možnou dobu realizace celého projektu. Práce na této cestě mají nulovou časovou rezervu[10].

Příklady

  • Nejkratší cesta: Hledání optimální trasy navigačním systémem mezi dvěma body na mapě města, kde města jsou uzly a silnice jsou oblouky s váhami rovnými délce nebo době jízdy.
  • Maximální tok: Určení maximální propustnosti sítě potrubí, kde čerpací stanice jsou uzly a potrubí jsou oblouky s omezenou kapacitou.
  • Minimální kostra grafu: Návrh komunikační sítě (například pokládka optického kabelu) pro spojení několika měst s minimální celkovou délkou kabelu.
  • Kritická cesta: V projektu stavby domu, kde práce (zakládání, zdění stěn, montáž střechy) mají zadanou délku trvání a technologické závislosti, určuje kritická cesta minimální dobu dokončení stavby. Jakékoli zpoždění práce na této cestě povede ke zpoždění celého projektu[10].

Viz také

  • Operační výzkum
  • Teorie grafů
  • Dopravní úloha
  • Metoda kritické cesty
  • PERT

Poznámky

  1. ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
  2. ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [2]
  3. ↑ "Транспортная сеть". Википедия. [3]
  4. ↑ "Сетевое планирование". Википедия. [4]
  5. ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
  6. ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [6]
  7. ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
  8. ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [8]
  9. ↑ "Минимальное остовное дерево". Википедия.
  10. ↑ 10.0 10.1 "Метод критического пути". Википедия. [9]
Retrieved from "https://systems-analysis.info/int/index.php?title=Síťový_model_(operační_výzkum)&oldid=7804"