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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller lunazita. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $9.41. You're not tied to anything after your purchase.
