Operations Research 1 (OR1) – Week 3 – Netwerkoptimalisatie – samenvatting en toetsvoorbereiding

Studiedossier OR1 week 3
Netwerkoptimalisatie: Algoritmen, Modellen en Toepassingen

Inhoud
1. Fundamenten van de Netwerktheorie ......................................................................... 2
Kernbegrippen en Definities ............................................................................................ 2
Netwerkclassificatie en Structuur ............................................................................... 2
Stroomparameters ............................................................................................................ 2
2. Kortstepadenproblematiek (Shortest Path)............................................................. 3
Dijkstra’s Algoritme .......................................................................................................... 3
Stappenplan: ..................................................................................................................... 3
Bellman-Ford Algoritme ................................................................................................... 3
Vergelijkende Analyse ....................................................................................................... 4
3. Minimum Spanning Tree (MST) ........................................................................................ 4
4. Maximale Stroom (Max Flow) .......................................................................................... 4
Augmenting Path Algoritme & Residual Networks ................................................... 5
Max-Flow Min-Cut Theorem.............................................................................................. 5
5. Minimum Cost Flow & Network Simplex ....................................................................... 5
Wiskundige Formulering .................................................................................................... 5
Network Simplex Methode ................................................................................................ 5
Special Cases Matrix ......................................................................................................... 5
6. Projectmanagement: CPM en Crashing ....................................................................... 6
Project Netwerken en Kritiek Pad.................................................................................. 6
Time-Cost Trade-Offs (Crashing) .................................................................................. 6
LP-Formulering voor Crashing ........................................................................................ 6
7. Toetsvoorbereiding: Overzicht & Kernbegrippen ...................................................... 6
Formule-overzicht .............................................................................................................. 6
Beslissingsmatrix: Algoritmekeuze ............................................................................... 6
Veelgemaakte Fouten ........................................................................................................ 7




In de Operations Research (OR) vormen netwerkmodellen een fundamentele
methodiek voor strategische besluitvorming. Door complexe systemen te
abstraheren tot een structuur van knopen en takken, creëren we een

1

, krachtig visueel en conceptueel hulpmiddel. Deze abstractie is niet louter
illustratief; de student dient te begrijpen dat elk lineair
programmeringsprobleem (LP) met een specifiek coëfficiëntpatroon van +1 en
-1 in elke kolom gemodelleerd kan worden als een netwerk. Dit dossier
behandelt de transitie van statische netwerkdefinities naar dynamische
optimalisatievraagstukken in logistiek, transport en projectmanagement.

1. Fundamenten van de Netwerktheorie
Een eenduidige wiskundige notatie is cruciaal voor het begrijpen van de
algoritmen die volgen. Een netwerk wordt gedefinieerd als een verzameling
knopen (nodes) en takken (arcs) die paren knopen verbinden.

Kernbegrippen en Definities
Begrip Didactische Definitie

Knopen (Nodes/Vertices) Punten in het netwerk (steden, kruispunten,
faciliteiten).

Takken Verbindingen tussen twee knopen, genoteerd
(Arcs/Links/Edges) als arc 𝑖 → 𝑗.

Richting Een 'directed arc' staat stroom in één richting
(Directed/Undirected) toe; een 'link' (undirected) in beide.

Pad (Path) Een opeenvolging van verschillende takken die
twee knopen verbindt.

Cyclus (Cycle) Een pad dat begint en eindigt bij dezelfde knoop.

Netwerkclassificatie en Structuur
Netwerken worden geclassificeerd op basis van de aard van hun takken. Een
'directed network' bevat uitsluitend gerichte takken, terwijl een 'mixed
network' beide types bevat. Een cruciaal concept voor de Network Simplex
methode is de spanning tree: een samenhangend netwerk voor alle n knopen
dat geen cycli bevat en precies n-1 takken telt.

Stroomparameters
Binnen netwerkmodellen wordt de 'flow' (𝑥𝑖𝑗 ) gekenmerkt door de volgende
parameters:

• Arc Capacity (𝑢𝑖𝑗 ): De bovengrens voor de stroom over tak 𝑖 → 𝑗.

• Supply Node (Bron): Een knoop i waar de netto stroom 𝑏𝑖 > 0 is.

• Demand Node (Sink): Een knoop i waar de netto stroom 𝑏𝑖 < 0 is.

• Transshipment Node: Een knoop i waar 𝑏𝑖 = 0 (behoud van stroom).




2