Netwerkmodel (operationeel onderzoek)

Netwerkmodellen (in operations research; Engels Network models) — dit is een klasse van wiskundige modellen die een probleem voorstellen in de vorm van een graaf (netwerk), waarbij knopen (vertices) objecten of toestanden aanduiden en kanten (bogen) de verbindingen of processen daartussen. In de context van optimalisatie wordt onder een netwerk vaak een gerichte graaf verstaan, die in de operationele analyse rechtstreeks een 'netwerk' wordt genoemd; de knopen van zo'n netwerk heten knooppunten en de kanten heten bogen.

Netwerkmodellen zijn een krachtig instrument voor de analyse en optimalisatie van complexe systemen op gebieden als logistiek, telecommunicatie, projectmanagement en financiën. Hun kracht ligt in het hoge abstractieniveau: een knooppunt kan een stad, een computerrouter of een projectfase voorstellen, en een boog kan een weg, een communicatiekanaal of een technologische operatie zijn.

Definitie en terminologie

De basis voor netwerkmodellen wordt gevormd door de grafentheorie. De kernbegrippen zijn:

• Stromingsnetwerk (Engels flow network): een gerichte graaf waarbij elke kant een capaciteit (capacity) en een stroom (flow) heeft. In de graaf worden twee bijzondere knopen onderscheiden: de bron (source), waaruit de stroom ontspringt, en de put (sink), waarin de stroom toestroomt.
• Wet van behoud van stroom: Voor elk knooppunt dat geen bron of put is, moet de totale instromende stroom gelijk zijn aan de totale uitstromende stroom. Deze voorwaarde is een discreet analogon van de fysische behoudswetten.
• Netwerkplanning: Een model dat een project voorstelt als een geheel van onderling samenhangende bewerkingen (bogen) en gebeurtenissen (knooppunten). Dergelijke netwerken zijn gerichte acyclische grafen, wat de volgorde van de uit te voeren werkzaamheden weerspiegelt.

Sleuteleigenschappen en stellingen

Netwerkmodellen bezitten een aantal bijzondere eigenschappen waardoor zeer efficiënte algoritmen kunnen worden toegepast voor het oplossen ervan.

• Geheeltalligheid van oplossingen: Veel netwerkoptimalisatieproblemen (zoals het maximale-stroomprobleem of het kortste-padprobleem) hebben de eigenschap van volledige unimodulariteit van de beperkingsmatrix. Daardoor geldt dat als de parameters van het probleem (capaciteiten, lengten) geheeltallig zijn, de optimale oplossing gevonden met methoden van lineair programmeren eveneens geheeltallig zal zijn, zonder dat aanvullende beperkingen nodig zijn.
• Maximale-stroom-minimale-snede-stelling: Het centrale resultaat van de stroomtheorie. De stelling stelt dat de maximale stroomwaarde van de bron naar de put gelijk is aan de minimale capaciteit van alle sneden die de bron en de put scheiden. Deze stelling stelt een optimaliteitscriterium voor de stroom vast en vormt de basis van vele algoritmen.
• Optimaliteitsprincipe voor kortste paden: Als een pad van punt A naar punt C het kortste pad is, dan is elk deeltraject ervan (bijvoorbeeld van een tussenliggend punt B naar C) eveneens het kortste pad tussen de overeenkomstige knooppunten. Deze eigenschap, die ten grondslag ligt aan dynamisch programmeren, garandeert de correctheid van algoritmen zoals het algoritme van Dijkstra.
• Eigenschappen van de minimale opspannende boom (MOB):
• Snede-eigenschap: Voor elke snede van de graaf behoort de kant met het minimale gewicht die de snede kruist tot ten minste één MOB.
• Cykel-eigenschap: In elke cykel van de graaf behoort de kant met het maximale gewicht tot geen enkele MOB.

Op deze eigenschappen is de correctheid van de 'gulzige' algoritmen van Prim en Kruskal gebaseerd.

Belangrijkste taken van netwerkoptimalisatie

• Kortste-padprobleem: Vind het pad met de minimale totale lengte (gewicht) tussen twee gegeven knooppunten. Opgelost met het algoritme van Dijkstra (voor niet-negatieve gewichten) of het algoritme van Bellman-Ford (voor willekeurige gewichten).
• Maximale-stroomprobleem: Bepaal de maximaal mogelijke stroom van de bron naar de put bij gegeven capaciteiten van de bogen. De klassieke oplossingsmethode is het algoritme van Ford-Fulkerson.
• Minimale opspannende boom: Vind de deelgraaf die alle knooppunten van het netwerk verbindt en de minimale totale kostensom van de kanten heeft.
• Methode van het kritieke pad (CPM): Bepaal in netwerkplanningsmodellen de langste reeks van werkzaamheden die de minimaal mogelijke doorlooptijd van het gehele project vastlegt. Werkzaamheden op dit pad hebben een vrije tijdsmarge van nul.

Voorbeelden

• Kortste pad: Het zoeken van de optimale route door een navigatiesysteem tussen twee punten op een stadskaart, waarbij steden knooppunten zijn en wegen bogen met gewichten gelijk aan de afstand of reistijd.
• Maximale stroom: Het bepalen van de maximale doorvoercapaciteit van een pijpleidingnetwerk, waarbij pompstations knooppunten zijn en leidingen bogen met een beperkte capaciteit.
• Minimale opspannende boom: Het ontwerpen van een communicatienetwerk (bijvoorbeeld het aanleggen van glasvezelkabel) om meerdere steden met elkaar te verbinden met een minimale totale kabellengte.
• Kritiek pad: Bij een project voor de bouw van een huis, waarbij werkzaamheden (fundering leggen, muren optrekken, dak plaatsen) een vastgestelde doorlooptijd en technologische afhankelijkheden hebben, bepaalt het kritieke pad de minimale termijn voor voltooiing van de bouw. Elke vertraging van een werkzaamheid op dit pad leidt tot vertraging van het gehele project.

Zie ook

• Operations research
• Grafentheorie
• Transportprobleem
• Methode van het kritieke pad
• PERT