---
title: "Nätverksmodeller (operationsanalys)"
source: "https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)"
wiki: "systems-analysis.info/int"
article: "Nätverksmodeller_(operationsanalys)"
language: "sv"
categories:
  - "Category:Operations research"
  - "Category:Swedish"
revision_id: 4961
wiki_created_at: 2026-09-06T23:42:35Z
wiki_modified_at: 2026-09-06T23:42:35Z
downloaded_at: 2026-09-07T23:06:05Z
---

# Nätverksmodeller (operationsanalys)

**Nätverksmodeller** (inom operations research; eng. *Network models*) — är en klass av matematiska modeller som representerar ett problem i form av en graf (ett nätverk), där hörn (noder) betecknar objekt eller tillstånd, och kanter (bågar) betecknar samband eller processer mellan dem<sup>[\[1\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-en-wiki-flow-network-1)</sup>. I optimiseringssammanhang avses med ett nätverk ofta en riktad graf, som inom operationsanalys direkt kallas för "nätverk"; hörnen i ett sådant nätverk kallas noder och kanterna kallas bågar<sup>[\[2\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-belgut-lec-2)</sup>.

Nätverksmodeller är ett kraftfullt verktyg för analys och optimering av komplexa system inom områden som logistik, telekommunikation, projektledning och finans. Deras styrka ligger i den höga abstraktionsnivån: en nod kan representera en stad, en datornätrouter eller ett projektsteg, medan en båge kan representera en väg, en kommunikationskanal eller en teknologisk operation.

## Definition och terminologi

Grunden för nätverksmodeller utgörs av grafteori. De viktigaste begreppen är:

- **Flödesnätverk** (eng. *flow network*): en riktad graf där varje kant har en **kapacitet** (*capacity*) och ett **flöde** (*flow*). I grafen urskiljs två särskilda hörn: **källa** (*source*), från vilken flödet utgår, och **sänka** (*sink*), till vilken det flödar in<sup>[\[1\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-en-wiki-flow-network-1)</sup>.
- **Flödesbevarandelagen**: För varje hörn som inte är källa eller sänka måste det totala inflödet vara lika med det totala utflödet. Detta villkor är en diskret analog till fysikaliska bevarandelagar<sup>[\[3\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-ru-wiki-transport-net-3)</sup>.
- **Nätverksplanering**: En modell som representerar ett projekt som en uppsättning av sammankopplade operationer (bågar) och händelser (noder). Sådana nätverk är riktade acykliska grafer, vilket speglar ordningsföljden för arbetets utförande<sup>[\[4\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-ru-wiki-cpm-pert-4)</sup>.

## Centrala egenskaper och teorem

Nätverksmodeller har ett antal särskilda egenskaper som möjliggör användning av mycket effektiva algoritmer för att lösa dem.

- **Heltalighet hos lösningar**: Många problem inom nätverksoptimering (till exempel maximalt flöde eller kortaste väg) har egenskapen total unimodularitet hos bivillkorsmatrisen. Tack vare detta, om problemets parametrar (kapaciteter, längder) är heltal, kommer den optimala lösningen som hittas med linjärprogrammeringsmetoder också att vara heltalig utan att ytterligare bivillkor behöver införas<sup>[\[5\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-mit-amp-ch8-5)[\[6\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-ru-wiki-max-flow-6)</sup>.
- **Teoremet om maximalt flöde och minimalt snitt**: Ett centralt resultat inom flödesteori. Det anger att det maximala flödesvärdet från källa till sänka är lika med den minimala kapaciteten bland alla snitt som separerar källan från sänkan. Detta teorem fastställer optimalitetskriteriet för flödet och ligger till grund för många algoritmer<sup>[\[6\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-ru-wiki-max-flow-6)[\[7\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-goldberg-tarjan-1990-7)</sup>.
- **Optimalitetsprincipen för kortaste vägar**: Om vägen från punkt A till punkt C är den kortaste, är varje delsträcka av den (till exempel från en mellanliggande punkt B till C) också den kortaste vägen mellan motsvarande hörn. Denna egenskap, som ligger till grund för dynamisk programmering, motiverar korrektheten hos algoritmer som Dijkstras algoritm<sup>[\[8\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-ru-wiki-shortest-path-8)</sup>.
- **Egenskaper hos minimalt uppspännande träd (MST)**:
- **Snittegenskapen**: För varje snitt i grafen tillhör kanten med minsta vikt som korsar snittet minst ett MST.
- **Cykelegenskapen**: I varje cykel i grafen tillhör kanten med störst vikt inget MST.

På dessa egenskaper grundas korrektheten hos de "giriga" algoritmerna av Prim och Kruskal<sup>[\[9\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-ru-wiki-mst-9)</sup>.

## Huvudproblem inom nätverksoptimering

- **Kortaste väg-problemet**: Hitta en väg med minimal total längd (vikt) mellan två givna noder. Löses med Dijkstras algoritm (för icke-negativa vikter) eller Bellman–Fords algoritm (för godtyckliga vikter)<sup>[\[8\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-ru-wiki-shortest-path-8)</sup>.
- **Maximalt flöde-problemet**: Bestäm det maximalt möjliga flödet från källa till sänka givet bågarnas kapaciteter. Den klassiska lösningsmetoden är Ford–Fulkersons algoritm<sup>[\[6\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-ru-wiki-max-flow-6)</sup>.
- **Minimalt uppspännande träd-problemet**: Hitta en delgraf som förbinder alla noder i nätverket och har minimal total kantvikt.
- **Kritisk väg-metoden (CPM)**: I nätverksplaneringsmodeller, bestäm den längsta sekvensen av arbeten som fastställer den minimalt möjliga tid för hela projektets genomförande. Arbeten på denna väg har noll tidsmarginal<sup>[\[10\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-ru-wiki-cpm-10)</sup>.

## Exempel

- **Kortaste vägen**: Ett navigationssystem söker den optimala rutten mellan två punkter på en stadskarta, där städerna är noder och vägarna är bågar med vikter som motsvarar sträcka eller restid.
- **Maximalt flöde**: Bestämning av den maximala kapaciteten i ett rörnätverk, där pumpstationer är noder och rören är bågar med begränsad kapacitet.
- **Minimalt uppspännande träd**: Projektering av ett kommunikationsnätverk (till exempel dragning av optisk fiberkabel) för att förbinda flera städer med minimal total kabellängd.
- **Kritisk väg**: I ett husbyggnadsprojekt, där arbeten (grundläggning, uppförande av väggar, takmontering) har given varaktighet och teknologiska beroenden, bestämmer den kritiska vägen den minimala tid för byggnadens färdigställande. Varje försening av ett arbete på denna väg leder till försening av hela projektet<sup>[\[10\]](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_note-ru-wiki-cpm-10)</sup>.

## Se även

- Operations research
- Grafteori
- Transportproblemet
- Kritisk väg-metoden
- PERT

## Noter

1.  <span id="cite_note-en-wiki-flow-network-1">↑ <sup>[1.0](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_ref-en-wiki-flow-network_1-0)</sup> <sup>[1.1](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#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/N%C3%A4tverksmodeller_(operationsanalys)#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/N%C3%A4tverksmodeller_(operationsanalys)#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/N%C3%A4tverksmodeller_(operationsanalys)#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/N%C3%A4tverksmodeller_(operationsanalys)#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/N%C3%A4tverksmodeller_(operationsanalys)#cite_ref-ru-wiki-max-flow_6-0)</sup> <sup>[6.1](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_ref-ru-wiki-max-flow_6-1)</sup> <sup>[6.2](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#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/N%C3%A4tverksmodeller_(operationsanalys)#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/N%C3%A4tverksmodeller_(operationsanalys)#cite_ref-ru-wiki-shortest-path_8-0)</sup> <sup>[8.1](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#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/N%C3%A4tverksmodeller_(operationsanalys)#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/N%C3%A4tverksmodeller_(operationsanalys)#cite_ref-ru-wiki-cpm_10-0)</sup> <sup>[10.1](https://systems-analysis.info/int/N%C3%A4tverksmodeller_(operationsanalys)#cite_ref-ru-wiki-cpm_10-1)</sup> "Метод критического пути". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Метод_критического_пути" class="external autonumber" rel="nofollow">[9]</a></span>