Lineaire Optimalisering
uitleg vanaf nul
Voor de bachelor Econometrie en Operationele Research, Tilburg University
Vakcode: 35B108-B-6
Gebaseerd op: Bertsimas & Tsitsiklis (1997), Introduction to Linear Optimization · hfdst. 1–4, §10.1, §11.1–11.2
Gemaakt door Levi, Master of Science
Lees dit eerst
• Voor wie? Voor jou als “simplex” en “duaal” nog vage woorden zijn. Dit document laat
zien welk probleem je oplost (de beste keuze onder lineaire beperkingen), welke methodes
er zijn en hoe ze samenhangen. Doel: het grote plaatje en een voldoende.
• Taal. Uitleg in het Nederlands. Boek en tentamen zijn Engelstalig, dus vaktermen staan
vetgedrukt in het Engels. Achterin staat een woordenlijst.
• Volgorde. Lees van voor naar achter. §3 (standaardvorm en basisoplossingen) is het fun-
dament: simplex, Phase I, dualiteit en Gomory-sneden werken allemaal met 𝐵, 𝐵−1 en
gereduceerde kosten.
• Eerlijk. De onderwerpen volgen de tentamens Linear Optimization (35B108) van 2017–
2019 en de bijbehorende hoofdstukken van Bertsimas en Tsitsiklis (1997). Gevoeligheids-
analyse (hfdst. 5) en netwerken (hfdst. 7) kwamen in die tentamens niet voor en zijn
weggelaten. Check de studiehandleiding. Dit is een eigen uitleg naast het boek, niet in
plaats ervan. Maak de oude tentamens.
Inhoud
1. Het grote plaatje 6. Dualiteit
2. Modelleren (ook met gehele en binaire variabelen) 7. Complementaire slackness en waar/onwaar
3. Standaardvorm, hoekpunten en basisoplossingen 8. Branch-and-bound
4. De simplexmethode 9. Gomory-sneden
5. Een startoplossing vinden: Phase I 10. Strategie voor een voldoende
1
, Lineaire Optimalisering – uitleg vanaf nul Tilburg EOR, 35B108-B-6 · Levi, Master of Science
1 Het grote plaatje: waar gaat dit vak over?
Een bedrijf wil zoveel mogelijk winst, maar heeft beperkte uren, grondstoffen en geld. Als winst
en beperkingen allemaal lineair zijn, heb je een linear optimization problem (LOP). Het hele
vak draait om:
Wat is de beste keuze x
als doel en beperkingen lineair zijn?
Denk aan een veelhoekige kamer (het toegestane gebied) en een schuine vloer (de doelfunctie). Een
knikker rolt altijd naar een hoek van de kamer. Daarom hoef je alleen hoekpunten te bekijken, en
de simplexmethode loopt van hoek naar hoek, steeds bergafwaarts.
Modelleren Geometrie
van tekst naar hoekpunten
LOP (§2) = BFS (§3)
Simplex
Sneden min c𝑇 x
gereduceerde
Gomory (§9) s.t. 𝐴x = b, x ≥ 0 kosten (§4, §5)
Geheeltallig Dualiteit
branch-and- ondergrens, prij-
bound (§8) zen (§6, §7)
De tabel die je nooit mag vergeten: zo maak je het duale probleem van een minimalisatieprobleem
(Bertsimas & Tsitsiklis, 1997, §4.2). uit je hoofd leren zeer tentamengevoelig
Primaal: minimaliseer c𝑇 x Duaal: maximaliseer p𝑇 b
beperking 𝑖: a𝑇𝑖 x ≥ 𝑏𝑖 variabele 𝑝𝑖 ≥ 0
beperking 𝑖: a𝑇𝑖 x ≤ 𝑏𝑖 variabele 𝑝𝑖 ≤ 0
beperking 𝑖: a𝑇𝑖 x = 𝑏𝑖 variabele 𝑝𝑖 vrij
variabele 𝑥𝑗 ≥ 0 beperking 𝑗: p𝑇 𝐴𝑗 ≤ 𝑐𝑗
variabele 𝑥𝑗 ≤ 0 beperking 𝑗: p𝑇 𝐴𝑗 ≥ 𝑐𝑗
variabele 𝑥𝑗 vrij beperking 𝑗: p𝑇 𝐴𝑗 = 𝑐𝑗
Ezelsbruggetje: bij een min-primaal zijn “natuurlijke” beperkingen ≥ en die horen bij “natuurlijke”
duale variabelen ≥ 0. Bij een max-primaal lees je de tabel van rechts naar links.
2
uitleg vanaf nul
Voor de bachelor Econometrie en Operationele Research, Tilburg University
Vakcode: 35B108-B-6
Gebaseerd op: Bertsimas & Tsitsiklis (1997), Introduction to Linear Optimization · hfdst. 1–4, §10.1, §11.1–11.2
Gemaakt door Levi, Master of Science
Lees dit eerst
• Voor wie? Voor jou als “simplex” en “duaal” nog vage woorden zijn. Dit document laat
zien welk probleem je oplost (de beste keuze onder lineaire beperkingen), welke methodes
er zijn en hoe ze samenhangen. Doel: het grote plaatje en een voldoende.
• Taal. Uitleg in het Nederlands. Boek en tentamen zijn Engelstalig, dus vaktermen staan
vetgedrukt in het Engels. Achterin staat een woordenlijst.
• Volgorde. Lees van voor naar achter. §3 (standaardvorm en basisoplossingen) is het fun-
dament: simplex, Phase I, dualiteit en Gomory-sneden werken allemaal met 𝐵, 𝐵−1 en
gereduceerde kosten.
• Eerlijk. De onderwerpen volgen de tentamens Linear Optimization (35B108) van 2017–
2019 en de bijbehorende hoofdstukken van Bertsimas en Tsitsiklis (1997). Gevoeligheids-
analyse (hfdst. 5) en netwerken (hfdst. 7) kwamen in die tentamens niet voor en zijn
weggelaten. Check de studiehandleiding. Dit is een eigen uitleg naast het boek, niet in
plaats ervan. Maak de oude tentamens.
Inhoud
1. Het grote plaatje 6. Dualiteit
2. Modelleren (ook met gehele en binaire variabelen) 7. Complementaire slackness en waar/onwaar
3. Standaardvorm, hoekpunten en basisoplossingen 8. Branch-and-bound
4. De simplexmethode 9. Gomory-sneden
5. Een startoplossing vinden: Phase I 10. Strategie voor een voldoende
1
, Lineaire Optimalisering – uitleg vanaf nul Tilburg EOR, 35B108-B-6 · Levi, Master of Science
1 Het grote plaatje: waar gaat dit vak over?
Een bedrijf wil zoveel mogelijk winst, maar heeft beperkte uren, grondstoffen en geld. Als winst
en beperkingen allemaal lineair zijn, heb je een linear optimization problem (LOP). Het hele
vak draait om:
Wat is de beste keuze x
als doel en beperkingen lineair zijn?
Denk aan een veelhoekige kamer (het toegestane gebied) en een schuine vloer (de doelfunctie). Een
knikker rolt altijd naar een hoek van de kamer. Daarom hoef je alleen hoekpunten te bekijken, en
de simplexmethode loopt van hoek naar hoek, steeds bergafwaarts.
Modelleren Geometrie
van tekst naar hoekpunten
LOP (§2) = BFS (§3)
Simplex
Sneden min c𝑇 x
gereduceerde
Gomory (§9) s.t. 𝐴x = b, x ≥ 0 kosten (§4, §5)
Geheeltallig Dualiteit
branch-and- ondergrens, prij-
bound (§8) zen (§6, §7)
De tabel die je nooit mag vergeten: zo maak je het duale probleem van een minimalisatieprobleem
(Bertsimas & Tsitsiklis, 1997, §4.2). uit je hoofd leren zeer tentamengevoelig
Primaal: minimaliseer c𝑇 x Duaal: maximaliseer p𝑇 b
beperking 𝑖: a𝑇𝑖 x ≥ 𝑏𝑖 variabele 𝑝𝑖 ≥ 0
beperking 𝑖: a𝑇𝑖 x ≤ 𝑏𝑖 variabele 𝑝𝑖 ≤ 0
beperking 𝑖: a𝑇𝑖 x = 𝑏𝑖 variabele 𝑝𝑖 vrij
variabele 𝑥𝑗 ≥ 0 beperking 𝑗: p𝑇 𝐴𝑗 ≤ 𝑐𝑗
variabele 𝑥𝑗 ≤ 0 beperking 𝑗: p𝑇 𝐴𝑗 ≥ 𝑐𝑗
variabele 𝑥𝑗 vrij beperking 𝑗: p𝑇 𝐴𝑗 = 𝑐𝑗
Ezelsbruggetje: bij een min-primaal zijn “natuurlijke” beperkingen ≥ en die horen bij “natuurlijke”
duale variabelen ≥ 0. Bij een max-primaal lees je de tabel van rechts naar links.
2
