Voor het vak: operationeel onderzoek, basismodellen in de tweede bachelor van TEW. Dit document vat alle leerstof samen in korte samenvattingen. Er worden verschillende voorbeeldoefeningen gegeven en uitgewerkt. Ook geschreven notities van de lessen zit er vanachter bij. Hierin worden alle voorbeel...
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.
𝑛
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper lunazita. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €8,79. Je zit daarna nergens aan vast.
