Hálózati modellek (operációkutatás)
Hálózati modellek (az operációkutatásban; ang. Network models) — a matematikai modellek egy osztálya, amelyek a feladatot gráf (hálózat) formájában ábrázolják, ahol a csúcsok (csomópontok) objektumokat vagy állapotokat jelölnek, az élek (ívek) pedig az ezek közötti kapcsolatokat vagy folyamatokat[1]. Az optimalizálás kontextusában a hálózaton gyakran irányított gráfot értenek, amelyet az operációanalízisben közvetlenül „hálózatnak" neveznek; az ilyen hálózat csúcsait csomópontoknak, éleit pedig íveknek hívják[2].
A hálózati modellek hatékony eszközök összetett rendszerek elemzéséhez és optimalizálásához olyan területeken, mint a logisztika, a telekommunikáció, a projektmenedzsment és a pénzügy. Erejük a magas szintű absztrakcióban rejlik: egy csomópont képviselhet várost, számítógépes útválasztót vagy projektfázist, egy ív pedig utat, kommunikációs csatornát vagy technológiai műveletet.
Meghatározás és terminológia
A hálózati modellek alapját a gráfelmélet képezi. A kulcsfogalmak a következők:
- Folyamhálózat (ang. flow network): irányított gráf, amelyben minden élnek van kapacitása (capacity) és folyama (flow). A gráfban két különleges csúcsot jelölnek ki: a forrást (source), amelyből a folyam ered, és a nyelőt (sink), amelybe a folyam beérkezik[1].
- A folyam megmaradásának törvénye: Minden olyan csúcsra, amely nem forrás vagy nyelő, a teljes bejövő folyamnak egyenlőnek kell lennie a teljes kimenő folyammal. Ez a feltétel a fizikai megmaradási törvények diszkrét analógja[3].
- Hálózati tervezés: Olyan modell, amely egy projektet egymással összefüggő műveletek (ívek) és események (csomópontok) összességeként ábrázol. Az ilyen hálózatok irányított aciklikus gráfok, ami tükrözi a munkák elvégzési sorrendjét[4].
Főbb tulajdonságok és tételek
A hálózati modellek számos különleges tulajdonsággal rendelkeznek, amelyek lehetővé teszik rendkívül hatékony algoritmusok alkalmazását a megoldásukhoz.
- A megoldások egészértékűsége: Számos hálózati optimalizálási feladat (például a maximális folyam vagy a legrövidebb út feladata) rendelkezik a feltételmátrix teljes unimodularitásának tulajdonságával. Ennek köszönhetően, ha a feladat paraméterei (kapacitások, hosszak) egészértékűek, akkor a lineáris programozási módszerekkel talált optimális megoldás is egészértékű lesz, anélkül hogy további korlátozásokat kellene bevezetni[5][6].
- A maximális folyam és a minimális vágat tétele: A folyamelmélet központi eredménye. Kimondja, hogy a forrástól a nyelőig terjedő folyam maximális értéke egyenlő a forrást és a nyelőt elválasztó összes vágat közül a minimális kapacitással. Ez a tétel meghatározza a folyam optimalitási kritériumát, és számos algoritmus alapját képezi[6][7].
- Az optimalitás elve a legrövidebb utakra: Ha az A pontból C pontba vezető út a legrövidebb, akkor annak bármely szakasza (például a B közbenső ponttól C-ig) szintén a legrövidebb út a megfelelő csúcsok között. Ez a dinamikus programozás alapját képező tulajdonság indokolja az olyan algoritmusok, mint a Dijkstra-algoritmus helyességét[8].
- A minimális feszítőfa (MFF) tulajdonságai:
- A vágat tulajdonsága: A gráf bármely vágatára az azt keresztező minimális súlyú él legalább egy MFF-hez tartozik.
- A kör tulajdonsága: A gráf bármely körében a maximális súlyú él egyetlen MFF-hez sem tartozik.
Ezeken a tulajdonságokon alapul a Prim- és a Kruskal-féle „mohó" algoritmusok helyessége[9].
A hálózati optimalizálás főbb feladatai
- Legrövidebb út feladata: Két adott csomópont között a minimális összhosszúságú (súlyú) út megtalálása. Megoldható a Dijkstra-algoritmussal (nemnegatív súlyok esetén) vagy a Bellman–Ford-algoritmussal (tetszőleges súlyok esetén)[8].
- Maximális folyam feladata: Az ívek adott kapacitásai mellett a forrástól a nyelőig terjedő maximálisan lehetséges folyam meghatározása. A klasszikus megoldási módszer a Ford–Fulkerson-algoritmus[6].
- Minimális feszítőfa feladata: Olyan részgráf megtalálása, amely összeköti a hálózat összes csúcsát, és minimális összes élköltséggel rendelkezik.
- Kritikus út módszere (CPM): A tervezési hálózati modellekben a munkák leghosszabb sorrendének meghatározása, amely megadja az egész projekt elvégzésének minimálisan lehetséges idejét. Az ezen az úton lévő munkáknak nulla időtartalékuk van[10].
Példák
- Legrövidebb út: Egy navigációs rendszer optimális útvonalat keres a várostérkép két pontja között, ahol a városok a csomópontok, az utak pedig az ívek, amelyek súlya az út hosszával vagy az utazási idővel egyenlő.
- Maximális folyam: Egy csővezetékhálózat maximális áteresztőképességének meghatározása, ahol a szivattyúállomások a csomópontok, a csövek pedig korlátozott kapacitású ívek.
- Minimális feszítőfa: Kommunikációs hálózat tervezése (például optikai kábel fektetése) több város összekötéséhez a minimális összkábelhosszal.
- Kritikus út: Egy házépítési projektben, ahol a munkáknak (alapozás, falak emelése, tetőszerkezet szerelése) adott időtartamuk és technológiai függőségeik vannak, a kritikus út meghatározza az építés minimális befejezési határidejét. Az ezen az úton lévő bármely munka késése az egész projekt késéséhez vezet[10].
Lásd még
- Operációkutatás
- Gráfelmélet
- Szállítási feladat
- Kritikus út módszere
- PERT
Megjegyzések
- ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
- ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [2]
- ↑ "Транспортная сеть". Википедия. [3]
- ↑ "Сетевое планирование". Википедия. [4]
- ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
- ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [6]
- ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
- ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [8]
- ↑ "Минимальное остовное дерево". Википедия.
- ↑ 10.0 10.1 "Метод критического пути". Википедия. [9]