OPERATIONEEL ONDERZOEK
Samenvatting
KU Leuven – Vak D0H28 – Prof. dr. Roel Leus
Geheeltallige Programmering | Netwerken | Dynamisch Programmeren | Complexiteit | Wachtlijnen
,H1 – Inleiding & Herhaling LP
Wat is Operationeel Onderzoek?
Operationeel onderzoek (OR) = het gebruik van wiskundige technieken voor optimalisatie en
analyse van 'operaties'. Operaties = het gebruik van hulpmiddelen (kapitaal, materialen,
technologie, menselijke kennis) bij de productie en distributie van goederen en diensten.
Categorieën van problemen
Deterministisch Stochastisch
• Gegevens zijn exact bekend • Onzekerheid aanwezig →
• Doelstelling: optimale oplossing kansvariabelen
vinden • Doelstelling: verwachte opbrengst
• Methoden: LP, IP, DP, maximaliseren
netwerkmodellen • Methode: wachtlijnen, stochastische
DP
Herhaling: Lineair Programmeren (LP)
Een LP-probleem bestaat uit:
• Een lineaire doelfunctie: {max of min} z = Σ cⱼxⱼ
• m lineaire beperkingen: Σ aᵢⱼxⱼ ≤ / = / ≥ bᵢ voor i = 1,...,m
• Tekenbeperkingen: xᵢ ≥ 0, xᵢ ≤ 0, of onbeperkt in teken
Assumpties LP:
• Proportionaliteit: bijdrage variabele proportioneel met zijn waarde
• Additiviteit: doelfunctie en beperkingen zijn sommen van individuele bijdragen
• Deelbaarheid: beslissingsvariabelen mogen fractioneel zijn
• Zekerheid: alle parameters zijn exact bekend
Voorbeeldproblemen
• Dieetprobleem: min kost van maaltijd onderhevig aan minimale nutriëntenbeperkingen
• Werkrooster: min # werknemers bij vereiste dagelijkse bezetting (variabelen = # starters per
dag)
• Investeringsprobleem: max NAW van portefeuille, rekening houdend met beschikbaar
kapitaal
Simplex-algoritme (herhaling)
Empirisch efficiënt maar exponentieel in worst-case. LP heeft ook polynomiale methoden:
• Ellipsoïde-methode (Khachian, 1979): polynomiaal maar traag in de praktijk
• Inwendige puntmethode (Karmarkar, 1984): polynomiaal en soms sneller dan simplex
Dualiteit (herhaling)
, Duale variabelen = schaduwprijzen: wat is de marginale waarde van een extra eenheid van
beperking i?
Complementaire slakheid: als xⱼ > 0 dan de duale beperking is binding; als slak > 0 dan de
duale var = 0.
Samenvatting
KU Leuven – Vak D0H28 – Prof. dr. Roel Leus
Geheeltallige Programmering | Netwerken | Dynamisch Programmeren | Complexiteit | Wachtlijnen
,H1 – Inleiding & Herhaling LP
Wat is Operationeel Onderzoek?
Operationeel onderzoek (OR) = het gebruik van wiskundige technieken voor optimalisatie en
analyse van 'operaties'. Operaties = het gebruik van hulpmiddelen (kapitaal, materialen,
technologie, menselijke kennis) bij de productie en distributie van goederen en diensten.
Categorieën van problemen
Deterministisch Stochastisch
• Gegevens zijn exact bekend • Onzekerheid aanwezig →
• Doelstelling: optimale oplossing kansvariabelen
vinden • Doelstelling: verwachte opbrengst
• Methoden: LP, IP, DP, maximaliseren
netwerkmodellen • Methode: wachtlijnen, stochastische
DP
Herhaling: Lineair Programmeren (LP)
Een LP-probleem bestaat uit:
• Een lineaire doelfunctie: {max of min} z = Σ cⱼxⱼ
• m lineaire beperkingen: Σ aᵢⱼxⱼ ≤ / = / ≥ bᵢ voor i = 1,...,m
• Tekenbeperkingen: xᵢ ≥ 0, xᵢ ≤ 0, of onbeperkt in teken
Assumpties LP:
• Proportionaliteit: bijdrage variabele proportioneel met zijn waarde
• Additiviteit: doelfunctie en beperkingen zijn sommen van individuele bijdragen
• Deelbaarheid: beslissingsvariabelen mogen fractioneel zijn
• Zekerheid: alle parameters zijn exact bekend
Voorbeeldproblemen
• Dieetprobleem: min kost van maaltijd onderhevig aan minimale nutriëntenbeperkingen
• Werkrooster: min # werknemers bij vereiste dagelijkse bezetting (variabelen = # starters per
dag)
• Investeringsprobleem: max NAW van portefeuille, rekening houdend met beschikbaar
kapitaal
Simplex-algoritme (herhaling)
Empirisch efficiënt maar exponentieel in worst-case. LP heeft ook polynomiale methoden:
• Ellipsoïde-methode (Khachian, 1979): polynomiaal maar traag in de praktijk
• Inwendige puntmethode (Karmarkar, 1984): polynomiaal en soms sneller dan simplex
Dualiteit (herhaling)
, Duale variabelen = schaduwprijzen: wat is de marginale waarde van een extra eenheid van
beperking i?
Complementaire slakheid: als xⱼ > 0 dan de duale beperking is binding; als slak > 0 dan de
duale var = 0.
