Basismodellen: overzicht
Deel 1: Inleiding en modelleren
Algemene setup van een LP-probleem:
Probleemstelling: doelfunctie + beslissingsvariabelen definiëren
Grenzen: beperkingen van indien geen beperkingen is de doelfunctiewaarde ∞!
● Capaciteit nooit een strikte ongelijkheid (< of >) gebruiken!
● Geld redundante beperking = beperking niet nodig!
● Tijd
● Vraag
● …
Vragen: Hoeveel produceren van elk product? Maximale of minimale doelfunctiewaarde? Hoeveel betalen voor extra
capaciteit? Effect van verlies van tijd, capaciteit, … ? Hoeveel winst minstens maken op elk product?
Oplossing: met lineaire programmering, grafisch of algoritmisch (lindo)
Assumpties van een LP-probleem:
● Lineariteit: lineaire functie van de beslissingsvariabelen is ≥, = 𝑜𝑓 ≤ constante
● Deelbaarheid: beslissingsvariabelen kunnen fractioneel zijn
● Zekerheidsassumpties
Investeringsprobleem met NAW:
B = bedrag op tijdstip 0
B (1 + r) = bedrag op tijdstip 1
𝑇 𝑐𝑡
𝐵
NAW = 𝑡 → NAW in functie van cashflows = ∑ 𝑡
(1 + 𝑟) 𝑡 = 1 (1 + 𝑟)
Cashflows = 𝑐𝑡
Enkele tips:
● Indien de gegeven kosten per product kommagetallen zijn, vermenigvuldig deze met 10/100/… zodat ze gehele
getallen worden in de doelfunctie. Dit is makkelijker om mee te rekenen!
● Wanneer je als uitkomst kommagetallen uitkomt (deelbaarheid assumptie) en deze afrond, dan maak vind je
slechts een ‘heuristiek’.
● Vergeet de samenhang tussen de variabelen niet bij het definiëren van de grenzen, alles wat uit gaat moet eerst
in komen!
Deel 2: LP-problemen oplossen
Notatie matrix en vectoren: met vector = geordende lijst van getallen/scalars (scalar = 1 getal hierin)
A= ( 𝑎11 ... 𝑎1𝑛
𝑎𝑚1 ... 𝑎𝑚𝑛 ) → m x n matrix
Rijvector: m = 1
Kolomvector: n = 1 indien er ‘vector’ wordt geschreven verwijzen we automatisch naar een kolomvector!
1
, 0 vector: vector met alle componenten gelijk aan 0 vectoren aangeduid door een kleine vetgedrukte letter ⇔ scalar
zal cursief (niet vet) worden weergegeven
𝑛
Transpose matrix: A’ = ∑ 𝑥𝑖𝑦𝑖 formule = inwendig/scalair product
𝑖=1
2 2
Lengte van de vector: ||(𝑥1, 𝑥2, ... 𝑥𝑛)|| = 𝑥1 + ... + 𝑥𝑛
Scalair/inwendig product: x’y of y’x = ||𝑥|| . ||𝑦|| . 𝑐𝑜𝑠 θ met θ de hoek tussen vector x en vector y en
→ positief voor 0° ≤ θ ≤ 90°, negatief voor 90° ≤ θ ≤ 180°, 0 voor θ = 90°
Grafisch oplossen van LP-probleem:
Doelfunctie en beperkingen zijn gegeven.
STAP 1: bepaal de oplossingsruimte op je grafiek, teken alle beperkingen
STAP 2: uit de doelfunctie haal je de normaalvector, BV: max 3x1 + 4x2 → normaalvector (3,4)
STAP 3: definieer voor normaalvector een niveaucurve: π(𝑧) = {(𝑥1, 𝑥2) | 𝑧)} en vul een ‘willekeurig’ getal (Y) in π(𝑌)
STAP 4: teken deze niveaucurve op de grafiek, hij zou loodrecht moeten staan op de normaalvector
→ Indien je maximaliseert zal je zoveel mogelijk naar boven willen gaan op de normaalvector, indien je minimaliseert wil
je zoveel mogelijk naar onder gaan op de normaalvector.
Dimensies van een LP-probleem:
n=2 n=3 Algemene n
Soort tekening Rechte Vlak (grens) Hypervlak
Oplossingsruimte Halfvlak veelhoek, Halfruimte veelhoek Halfruimte veelhoek,
polyhedron polyhedron
Optimum Hoekpunt Hoekpunt ???
𝑛
Convexe verzameling: S ⊂ 𝑅 is convex indien voor alle twee punten in 2, het lijnstuk dat de twee punten verbindt
volledig in S ligt (vierkant, cirkel, vijfhoek zijn convex → donut is niet convex).
→ ∀𝑥, 𝑦 ∈ 𝑆, ∀λ ∈ [0, 1]: λ𝑥 + (1 − λ)𝑦 ∈ 𝑆
Extreem punt: 𝑥 ∈ 𝑆 is een extreem punt indien S een convexe verzameling is. Indien S een veelvlak is, dan zijn de
extreme punten de hoekpunten. We kunnen x als een hoekpunt beschouwen indien er geen 2 andere punten (y,z) zijn die
ook in de verzameling liggen, verschillend zijn van x, en zodanig dat x toch op het lijnstuk ligt tussen y en z.
→ ∄ 𝑦, 𝑧 ∈ 𝑆, λ ∈ [0, 1]: 𝑦 ≠ 𝑧 , 𝑧 ≠ 𝑥 𝑒𝑛 𝑥 = λ𝑦 + (1 − λ) 𝑧
Enkele stellingen:
● Het toegelaten gebied van een LP-probleem is een convexe verzameling
● Voor elk LP-probleem dat een eindige optimale oplossingen heeft, bestaat er ook een extreem punt van het
toegelaten gebied dat optimaal is
● Het toegelaten gebied van een LP-probleem bevat slechts een eindig aantal extreme punten
Extra: in klassieke optimalisatie zoeken we de ‘vrije’ extrema, er zijn dan geen beperkingen/randvoorwaarden.
2
Deel 1: Inleiding en modelleren
Algemene setup van een LP-probleem:
Probleemstelling: doelfunctie + beslissingsvariabelen definiëren
Grenzen: beperkingen van indien geen beperkingen is de doelfunctiewaarde ∞!
● Capaciteit nooit een strikte ongelijkheid (< of >) gebruiken!
● Geld redundante beperking = beperking niet nodig!
● Tijd
● Vraag
● …
Vragen: Hoeveel produceren van elk product? Maximale of minimale doelfunctiewaarde? Hoeveel betalen voor extra
capaciteit? Effect van verlies van tijd, capaciteit, … ? Hoeveel winst minstens maken op elk product?
Oplossing: met lineaire programmering, grafisch of algoritmisch (lindo)
Assumpties van een LP-probleem:
● Lineariteit: lineaire functie van de beslissingsvariabelen is ≥, = 𝑜𝑓 ≤ constante
● Deelbaarheid: beslissingsvariabelen kunnen fractioneel zijn
● Zekerheidsassumpties
Investeringsprobleem met NAW:
B = bedrag op tijdstip 0
B (1 + r) = bedrag op tijdstip 1
𝑇 𝑐𝑡
𝐵
NAW = 𝑡 → NAW in functie van cashflows = ∑ 𝑡
(1 + 𝑟) 𝑡 = 1 (1 + 𝑟)
Cashflows = 𝑐𝑡
Enkele tips:
● Indien de gegeven kosten per product kommagetallen zijn, vermenigvuldig deze met 10/100/… zodat ze gehele
getallen worden in de doelfunctie. Dit is makkelijker om mee te rekenen!
● Wanneer je als uitkomst kommagetallen uitkomt (deelbaarheid assumptie) en deze afrond, dan maak vind je
slechts een ‘heuristiek’.
● Vergeet de samenhang tussen de variabelen niet bij het definiëren van de grenzen, alles wat uit gaat moet eerst
in komen!
Deel 2: LP-problemen oplossen
Notatie matrix en vectoren: met vector = geordende lijst van getallen/scalars (scalar = 1 getal hierin)
A= ( 𝑎11 ... 𝑎1𝑛
𝑎𝑚1 ... 𝑎𝑚𝑛 ) → m x n matrix
Rijvector: m = 1
Kolomvector: n = 1 indien er ‘vector’ wordt geschreven verwijzen we automatisch naar een kolomvector!
1
, 0 vector: vector met alle componenten gelijk aan 0 vectoren aangeduid door een kleine vetgedrukte letter ⇔ scalar
zal cursief (niet vet) worden weergegeven
𝑛
Transpose matrix: A’ = ∑ 𝑥𝑖𝑦𝑖 formule = inwendig/scalair product
𝑖=1
2 2
Lengte van de vector: ||(𝑥1, 𝑥2, ... 𝑥𝑛)|| = 𝑥1 + ... + 𝑥𝑛
Scalair/inwendig product: x’y of y’x = ||𝑥|| . ||𝑦|| . 𝑐𝑜𝑠 θ met θ de hoek tussen vector x en vector y en
→ positief voor 0° ≤ θ ≤ 90°, negatief voor 90° ≤ θ ≤ 180°, 0 voor θ = 90°
Grafisch oplossen van LP-probleem:
Doelfunctie en beperkingen zijn gegeven.
STAP 1: bepaal de oplossingsruimte op je grafiek, teken alle beperkingen
STAP 2: uit de doelfunctie haal je de normaalvector, BV: max 3x1 + 4x2 → normaalvector (3,4)
STAP 3: definieer voor normaalvector een niveaucurve: π(𝑧) = {(𝑥1, 𝑥2) | 𝑧)} en vul een ‘willekeurig’ getal (Y) in π(𝑌)
STAP 4: teken deze niveaucurve op de grafiek, hij zou loodrecht moeten staan op de normaalvector
→ Indien je maximaliseert zal je zoveel mogelijk naar boven willen gaan op de normaalvector, indien je minimaliseert wil
je zoveel mogelijk naar onder gaan op de normaalvector.
Dimensies van een LP-probleem:
n=2 n=3 Algemene n
Soort tekening Rechte Vlak (grens) Hypervlak
Oplossingsruimte Halfvlak veelhoek, Halfruimte veelhoek Halfruimte veelhoek,
polyhedron polyhedron
Optimum Hoekpunt Hoekpunt ???
𝑛
Convexe verzameling: S ⊂ 𝑅 is convex indien voor alle twee punten in 2, het lijnstuk dat de twee punten verbindt
volledig in S ligt (vierkant, cirkel, vijfhoek zijn convex → donut is niet convex).
→ ∀𝑥, 𝑦 ∈ 𝑆, ∀λ ∈ [0, 1]: λ𝑥 + (1 − λ)𝑦 ∈ 𝑆
Extreem punt: 𝑥 ∈ 𝑆 is een extreem punt indien S een convexe verzameling is. Indien S een veelvlak is, dan zijn de
extreme punten de hoekpunten. We kunnen x als een hoekpunt beschouwen indien er geen 2 andere punten (y,z) zijn die
ook in de verzameling liggen, verschillend zijn van x, en zodanig dat x toch op het lijnstuk ligt tussen y en z.
→ ∄ 𝑦, 𝑧 ∈ 𝑆, λ ∈ [0, 1]: 𝑦 ≠ 𝑧 , 𝑧 ≠ 𝑥 𝑒𝑛 𝑥 = λ𝑦 + (1 − λ) 𝑧
Enkele stellingen:
● Het toegelaten gebied van een LP-probleem is een convexe verzameling
● Voor elk LP-probleem dat een eindige optimale oplossingen heeft, bestaat er ook een extreem punt van het
toegelaten gebied dat optimaal is
● Het toegelaten gebied van een LP-probleem bevat slechts een eindig aantal extreme punten
Extra: in klassieke optimalisatie zoeken we de ‘vrije’ extrema, er zijn dan geen beperkingen/randvoorwaarden.
2
