---
title: "Hálózati modellek (operációkutatás)"
source: "https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)"
wiki: "systems-analysis.info/int"
article: "Hálózati_modellek_(operációkutatás)"
language: "hu"
categories:
  - "Category:Hungarian"
  - "Category:Operations research"
revision_id: 3134
wiki_created_at: 2026-09-06T23:16:13Z
wiki_modified_at: 2026-09-06T23:16:13Z
downloaded_at: 2026-09-07T22:55:24Z
---

# 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<sup>[\[1\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-en-wiki-flow-network-1)</sup>. 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<sup>[\[2\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-belgut-lec-2)</sup>.

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<sup>[\[1\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-en-wiki-flow-network-1)</sup>.
- **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<sup>[\[3\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-ru-wiki-transport-net-3)</sup>.
- **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<sup>[\[4\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-ru-wiki-cpm-pert-4)</sup>.

## 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<sup>[\[5\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-mit-amp-ch8-5)[\[6\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-ru-wiki-max-flow-6)</sup>.
- **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<sup>[\[6\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-ru-wiki-max-flow-6)[\[7\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-goldberg-tarjan-1990-7)</sup>.
- **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<sup>[\[8\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-ru-wiki-shortest-path-8)</sup>.
- **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<sup>[\[9\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-ru-wiki-mst-9)</sup>.

## 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)<sup>[\[8\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-ru-wiki-shortest-path-8)</sup>.
- **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<sup>[\[6\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-ru-wiki-max-flow-6)</sup>.
- **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<sup>[\[10\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-ru-wiki-cpm-10)</sup>.

## 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<sup>[\[10\]](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_note-ru-wiki-cpm-10)</sup>.

## Lásd még

- Operációkutatás
- Gráfelmélet
- Szállítási feladat
- Kritikus út módszere
- PERT

## Megjegyzések

1.  <span id="cite_note-en-wiki-flow-network-1">↑ <sup>[1.0](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-en-wiki-flow-network_1-0)</sup> <sup>[1.1](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-en-wiki-flow-network_1-1)</sup> "Flow network". *Wikipedia*. <a href="https://en.wikipedia.org/wiki/Flow_network" class="external autonumber" rel="nofollow">[1]</a></span>
2.  <span id="cite_note-belgut-lec-2">[↑](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-belgut-lec_2-0) "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. <a href="https://elib.gsu.by/bitstream/123456789/4781/13/Тема10_Сетевые%20модели_net_lec.pdf" class="external autonumber" rel="nofollow">[2]</a></span>
3.  <span id="cite_note-ru-wiki-transport-net-3">[↑](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-ru-wiki-transport-net_3-0) "Транспортная сеть". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Транспортная_сеть" class="external autonumber" rel="nofollow">[3]</a></span>
4.  <span id="cite_note-ru-wiki-cpm-pert-4">[↑](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-ru-wiki-cpm-pert_4-0) "Сетевое планирование". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Сетевое_планирование" class="external autonumber" rel="nofollow">[4]</a></span>
5.  <span id="cite_note-mit-amp-ch8-5">[↑](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-mit-amp-ch8_5-0) Bradley S. P., Hax A. C., Magnanti T. L. (1977). *Applied Mathematical Programming*. Addison-Wesley. Ch.8: Network Models. <a href="https://web.mit.edu/15.053/www/AMP-Chapter-08.pdf" class="external autonumber" rel="nofollow">[5]</a></span>
6.  <span id="cite_note-ru-wiki-max-flow-6">↑ <sup>[6.0](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-ru-wiki-max-flow_6-0)</sup> <sup>[6.1](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-ru-wiki-max-flow_6-1)</sup> <sup>[6.2](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-ru-wiki-max-flow_6-2)</sup> "Задача о максимальном потоке". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Задача_о_максимальном_потоке" class="external autonumber" rel="nofollow">[6]</a></span>
7.  <span id="cite_note-goldberg-tarjan-1990-7">[↑](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-goldberg-tarjan-1990_7-0) Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: *Paths, Flows, and VLSI-Layout*. Springer. <a href="https://www.cs.cornell.edu/~eva/Network.Flow.Algorithms.pdf" class="external autonumber" rel="nofollow">[7]</a></span>
8.  <span id="cite_note-ru-wiki-shortest-path-8">↑ <sup>[8.0](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-ru-wiki-shortest-path_8-0)</sup> <sup>[8.1](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-ru-wiki-shortest-path_8-1)</sup> "Задача о кратчайшем пути". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Задача_о_кратчайшем_пути" class="external autonumber" rel="nofollow">[8]</a></span>
9.  <span id="cite_note-ru-wiki-mst-9">[↑](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-ru-wiki-mst_9-0) "Минимальное остовное дерево". *Википедия*.</span>
10. <span id="cite_note-ru-wiki-cpm-10">↑ <sup>[10.0](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-ru-wiki-cpm_10-0)</sup> <sup>[10.1](https://systems-analysis.info/int/H%C3%A1l%C3%B3zati_modellek_(oper%C3%A1ci%C3%B3kutat%C3%A1s)#cite_ref-ru-wiki-cpm_10-1)</sup> "Метод критического пути". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Метод_критического_пути" class="external autonumber" rel="nofollow">[9]</a></span>