Samenvatting Lineaire Optimalisatie
Volledige samenvatting van het vak — van modelleren tot speltheorie. Bedoeld om in één keer het hele
vak te kunnen instuderen.
Inhoud
1. Wat is een LO-probleem? (terminologie & assumpties)
2. Modelleren
3. Niet-lineaire trucs lineair maken
4. Standaardvorm
5. Grafisch oplossen
6. Convexiteit & extreme punten
7. De simplexmethode
8. Begin – midden – einde van simplex (2-fasenmethode, degeneratie, cycling)
9. Dualiteit
10. Eigenschappen van dualiteit (zwakke/sterke dualiteit, complementary slackness)
11. Sensitiviteitsanalyse
12. LINDO-output lezen
13. Speltheorie
14. Examenaanpak & valkuilen
1. Wat is een LO-probleem?
Een lineair optimalisatieprobleem (LO) is een optimalisatiemodel met drie bouwstenen:
• Beslissingsvariabelen (decision variables): wat je kan kiezen (bv. productieaantallen).
• Doelfunctie (objective function): wat je minimaliseert of maximaliseert.
• Beperkingen (constraints): de grenzen waaraan een oplossing moet voldoen.
Je zoekt waarden voor de beslissingsvariabelen zodat de doelfunctie geoptimaliseerd wordt (min/max)
en aan alle beperkingen voldaan is.
Terminologie (ken deze woorden!)
In het model max 160𝑥𝑇 + 100𝑥𝑆 onder 2𝑥𝑇 + 2𝑥𝑆 ≤ 8, 2𝑥𝑇 + 𝑥𝑆 ≤ 6, 𝑥𝑇 , 𝑥𝑆 ≥ 0:
Term Betekenis Voorbeeld
beslissingsvariabele wat je kiest 𝑥𝑇 , 𝑥𝑆
doelfunctiecoëfficiënt getal vóór variabele in 160, 100
doelfunctie
technologische coëfficiënt getal vóór variabele in een 2, 1
beperking
rechterhand (right-hand side, het getal na ≤ / = / ≥ 8, 6
RHS)
niet-negativiteitsbeperking 𝑥𝑗 ≥ 0 𝑥𝑇 ≥ 0
onbeperkt in teken (oit) / variabele mag negatief zijn —
unrestricted in sign (uis)
1
, De drie LO-assumpties
Een model is pas een LO-model als het aan alle drie voldoet:
1. Zekerheid (certainty) — alle parameters (doelfunctiecoëfficiënten, RHS, technologische
coëfficiënten) zijn met zekerheid gekend. Het model is deterministisch. Niet voldaan bij
geschatte/onzekere parameters (toekomstige uitkomsten, kansverdelingen…).
2. Deelbaarheid (divisibility) — variabelen mogen elke fractionele waarde aannemen (continu,
dus 𝑥 = 2/3 mag). Als variabelen geheeltallig moeten zijn → integer programming (IP)
(veel moeilijker). Mix van beide → mixed integer programming (MIP). Afronden van een
fractionele oplossing is niet altijd correct.
3. Lineariteit (linearity) — de doelfunctie is lineair en alle beperkingen zijn lineaire
(on)gelijkheden (≤, =, ≥). Een functie 𝑓(𝑥1 , … , 𝑥𝑛 ) = 𝑐1 𝑥1 + ⋯ + 𝑐𝑛 𝑥𝑛 is lineair.
√
Niet-lineair zodra er voorkomt: 𝑥21 , sin 𝑥2 , 𝑥1 , een product 𝑥2 𝑥3 , of een strikte ongelijkheid (< of
>).
Modellen die niet aan de drie assumpties voldoen, kunnen niet opgelost worden met de
methoden uit dit vak.
Algemene vorm
𝑛
{max of min} 𝑧 = ∑ 𝑐𝑗 𝑥𝑗
𝑗=1
𝑛
s.t. ∑ 𝑎𝑖𝑗 𝑥𝑗 {≤, =, ≥} 𝑏𝑖 𝑖 = 1, … , 𝑚
𝑗=1
𝑥𝑗 ≥ 0 of 𝑥𝑗 oit 𝑗 = 1, … , 𝑛
Verwante families: stelsel lineaire vergelijkingen (lineair, enkel gelijkheden, geen doelfunctie), IP
(geheeltallig), niet-lineaire programmering (bv. 𝑥21 + 𝑥22 ≤ 1), Lagrange-functie (niet-lineair, enkel
gelijkheden).
2. Modelleren
Componenten van een model: - Parameters: inputs/data (prijzen, aanbod, vraag, beschikbare
uren). - Variabelen: wat je kiest (productie, aankoop, voorraad). - Beperkingen: limieten (hulp-
middelen, voorraadrelaties, vraag). - Doel: max winst / min kosten.
Stappenplan: 1. Hoe beschrijf je een mogelijke oplossing? → definieer beslissingsvariabelen. 2.
Waaraan moet een oplossing voldoen? → beperkingen. 3. Hoe vergelijk je oplossingen? → doelfunctie.
De cruciale stap is het correct definiëren van de beslissingsvariabelen. Bij het
personeelsplanningsprobleem mag je niet “aantal agenten dat werkt in periode 𝑖” nemen
(dubbeltellen, niet onafhankelijk), maar wél “aantal agenten dat start in periode 𝑖 met een
shift van die lengte”. Dan ligt automatisch vast wanneer iedereen werkt.
2
Volledige samenvatting van het vak — van modelleren tot speltheorie. Bedoeld om in één keer het hele
vak te kunnen instuderen.
Inhoud
1. Wat is een LO-probleem? (terminologie & assumpties)
2. Modelleren
3. Niet-lineaire trucs lineair maken
4. Standaardvorm
5. Grafisch oplossen
6. Convexiteit & extreme punten
7. De simplexmethode
8. Begin – midden – einde van simplex (2-fasenmethode, degeneratie, cycling)
9. Dualiteit
10. Eigenschappen van dualiteit (zwakke/sterke dualiteit, complementary slackness)
11. Sensitiviteitsanalyse
12. LINDO-output lezen
13. Speltheorie
14. Examenaanpak & valkuilen
1. Wat is een LO-probleem?
Een lineair optimalisatieprobleem (LO) is een optimalisatiemodel met drie bouwstenen:
• Beslissingsvariabelen (decision variables): wat je kan kiezen (bv. productieaantallen).
• Doelfunctie (objective function): wat je minimaliseert of maximaliseert.
• Beperkingen (constraints): de grenzen waaraan een oplossing moet voldoen.
Je zoekt waarden voor de beslissingsvariabelen zodat de doelfunctie geoptimaliseerd wordt (min/max)
en aan alle beperkingen voldaan is.
Terminologie (ken deze woorden!)
In het model max 160𝑥𝑇 + 100𝑥𝑆 onder 2𝑥𝑇 + 2𝑥𝑆 ≤ 8, 2𝑥𝑇 + 𝑥𝑆 ≤ 6, 𝑥𝑇 , 𝑥𝑆 ≥ 0:
Term Betekenis Voorbeeld
beslissingsvariabele wat je kiest 𝑥𝑇 , 𝑥𝑆
doelfunctiecoëfficiënt getal vóór variabele in 160, 100
doelfunctie
technologische coëfficiënt getal vóór variabele in een 2, 1
beperking
rechterhand (right-hand side, het getal na ≤ / = / ≥ 8, 6
RHS)
niet-negativiteitsbeperking 𝑥𝑗 ≥ 0 𝑥𝑇 ≥ 0
onbeperkt in teken (oit) / variabele mag negatief zijn —
unrestricted in sign (uis)
1
, De drie LO-assumpties
Een model is pas een LO-model als het aan alle drie voldoet:
1. Zekerheid (certainty) — alle parameters (doelfunctiecoëfficiënten, RHS, technologische
coëfficiënten) zijn met zekerheid gekend. Het model is deterministisch. Niet voldaan bij
geschatte/onzekere parameters (toekomstige uitkomsten, kansverdelingen…).
2. Deelbaarheid (divisibility) — variabelen mogen elke fractionele waarde aannemen (continu,
dus 𝑥 = 2/3 mag). Als variabelen geheeltallig moeten zijn → integer programming (IP)
(veel moeilijker). Mix van beide → mixed integer programming (MIP). Afronden van een
fractionele oplossing is niet altijd correct.
3. Lineariteit (linearity) — de doelfunctie is lineair en alle beperkingen zijn lineaire
(on)gelijkheden (≤, =, ≥). Een functie 𝑓(𝑥1 , … , 𝑥𝑛 ) = 𝑐1 𝑥1 + ⋯ + 𝑐𝑛 𝑥𝑛 is lineair.
√
Niet-lineair zodra er voorkomt: 𝑥21 , sin 𝑥2 , 𝑥1 , een product 𝑥2 𝑥3 , of een strikte ongelijkheid (< of
>).
Modellen die niet aan de drie assumpties voldoen, kunnen niet opgelost worden met de
methoden uit dit vak.
Algemene vorm
𝑛
{max of min} 𝑧 = ∑ 𝑐𝑗 𝑥𝑗
𝑗=1
𝑛
s.t. ∑ 𝑎𝑖𝑗 𝑥𝑗 {≤, =, ≥} 𝑏𝑖 𝑖 = 1, … , 𝑚
𝑗=1
𝑥𝑗 ≥ 0 of 𝑥𝑗 oit 𝑗 = 1, … , 𝑛
Verwante families: stelsel lineaire vergelijkingen (lineair, enkel gelijkheden, geen doelfunctie), IP
(geheeltallig), niet-lineaire programmering (bv. 𝑥21 + 𝑥22 ≤ 1), Lagrange-functie (niet-lineair, enkel
gelijkheden).
2. Modelleren
Componenten van een model: - Parameters: inputs/data (prijzen, aanbod, vraag, beschikbare
uren). - Variabelen: wat je kiest (productie, aankoop, voorraad). - Beperkingen: limieten (hulp-
middelen, voorraadrelaties, vraag). - Doel: max winst / min kosten.
Stappenplan: 1. Hoe beschrijf je een mogelijke oplossing? → definieer beslissingsvariabelen. 2.
Waaraan moet een oplossing voldoen? → beperkingen. 3. Hoe vergelijk je oplossingen? → doelfunctie.
De cruciale stap is het correct definiëren van de beslissingsvariabelen. Bij het
personeelsplanningsprobleem mag je niet “aantal agenten dat werkt in periode 𝑖” nemen
(dubbeltellen, niet onafhankelijk), maar wél “aantal agenten dat start in periode 𝑖 met een
shift van die lengte”. Dan ligt automatisch vast wanneer iedereen werkt.
2
