100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
samenvatting operationeel onderzoek TEW $16.60
Add to cart

Summary

samenvatting operationeel onderzoek TEW

 81 views  1 purchase
  • Course
  • Institution

samenvatting volledige cursus + oefeningen + lesnota's + alle begrippen uitgelegd + uitgebreide inhoudstafel

Preview 9 out of 34  pages

  • November 22, 2022
  • 34
  • 2021/2022
  • Summary
avatar-seller
SAMENVATTING: Operationeel Onderzoek


Inhoudstafel


1.Lineaire programmering (H3-4-5)
Inleiding op een LP-probleem
Bepalen van de optimale oplossing grafisch (H3)
Maximaliseringsprobleem met 2 variabelen

Minimaliseringsprobleem met 2 variabelen

Speciale gevallen

Alternatieve optimale oplossingen (oneindig)

Onmogelijk LP-probleem

Onbegrensd LP-probleem

Voorbeelden met meerdere beslissingsvariabelen

Dieetprobleem

Mengprobleem

Productieproces modelleren

Voorraadmodel



Bepalen van de optimale oplossing procedureel (H4)
Standaardformatie

Simplex algoritme inleiding

Matrixnotatie

Basis en niet-basisvariabelen (BV & NBV)

Haalbare / toelaatbare basisoplossingen (BFS)

Simplex algoritme

Voor maximaliseringsprobleem

standaardformatie

Rij 0 versie

Canonieke vorm 0,1,2,…


1

, Simplex tableau

Ratio test (ingaande en uitgaande NBV/BV)

Pivot rij

Voor minimaliseringsproblemen -> min. omzetten in max.

M-techniek (penaliseringsmethode) (-> voor >/=)

Goal programming (afweging maken bij ledige verzameling)

Pre-emptive goal programming



Bepalen van de optimale oplossing software (Lindo, Excel Solvare) (H5)
Gevoeligheidsanalyse

Grafisch

Doelfunctiecoëffiënt wijzigen

RHS beperking wijzigen

Schaduwprijs inleiding

Computer

Interpretatie computer-output

Schaduwprijzen (shadowprices/dualprices)

Dualiteit

Van primaal normaal max. probleem naar duaal normaal min. probleem

Van primaal normaal min. Probleem naar duaal normaal max. probleem



2.Niet lineaire programmering = NLP (H11)
Inleidende concepten
Lokaal extremum

Convexe en concave functies
Definities

Eigenschappen

De hessiaan
N x n-matrix

Principale minor



2

, NLP met 1 beslissingsvariabele
Lokale extremum

Bepaal optimale oplossing

NLP met meerdere beslissingsvariabelen
Lagrangefunctie -> voor ‘= ‘
Optimum NLP

Maximum NLP

Minimum NLP

Gevoeligheidsanalyse

Voorbeelden

Cobb-Douglas

Bij meerdere beperkingen

Kühn-Tucker voorwaarden -> voor ‘</=’
Maximum

Minimum

Interpretatie

Kwadratische programmering
Voorbeeld: portfolio-selectie



3.Veel voorkomende typeproblemen (H7-8-9)
Transportproblemen (H7)
Evenwichtige LP problemen

Onevenwichtige LP problemen

Voorraadproblemen

Toewijzingsproblemen (H7)
Hongaarse methode

Transitoproblemen (H7)




3

,Netwerkmodellen (H8)
Elementaire begrippen

Kortste-pad-problemen

Maximale-stroom-problemen

Kritieke-pad-methode

Projectnetwerk / projectdiagram

Early event time

Late event time

Total float

Kritiek pad

Free float  niet te kennen

Projectcrashing

Minimaal-opspannende-boom-problemen

Geheeltallige programmering (GP) (H9)
LP relaxatie
Enumeratie
GP problemen van 0-1 variabelen
Knapzakproblemen

Vaste kosten

Magazijnvestigingsproblemen

Partitieproblemen

Overdekkingsproblemen

Branch & bound methode
Puur GP

Gemengd GP

0-1 GP




4

,1. Lineaire Programmering
Inleiding op een LP-probleem
Beslissingsvariabelen: de onbekende beslissingen die moeten gemaakt worden (bvb. Aantal van x1?)

Doelfunctie: deze willen we zo groot (maximaliseringsprobleem) of zo klein
(minimaliseringsprobleem) mogelijk krijgen

Lineair: moet een som of aftrekking zijn (-> geen vermenigvuldiging van de variabelen) EN moet </=
of = of >/= zijn -> niet < of >  lineaire functie

LP-probleem: optimeren onder voorwaarden, gebonden optimeringsprobleem waarbij alle functies
lineair zijn en waarbij elke beslissingsveranderlijke al dan niet met een tekenbeperking geassocieerd
is (-> niet negatief of onbeperkt in teken). ; doelfunctie met beperkingen

Oplossen LP-probleem:

1) bepaal de beslissingsveranderlijken

2) formuleer de doelstelling (winst = opbrengst – kost) en beperkingen

S.t. : onder voorwaarde dat

Tekenbeperking: wijst op geen negatieve output mogelijk

Basisveronderstellingen betreffende beslissingsvariabelen: deze voorwaarden moeten voldaan zijn
opdat LP een realistische voorstelling biedt van het beslissingsprobleem.

Proportionaliteit: bijdrage doelfunctie is proportioneel aan de waarde van de
beslissingsvariabele; als de productie met x stijgt, zal de output met x stijgen -> elk product
vraagt 4 min tijd onafhankelijk van het aantal producten  elk product levert dus constante
winst op

Additiviteit: onafhankelijkheid van beslissingsvariabele x1 en x2, je kunt optellen

Divisibiliteit: deelbaarheid; x1 en x2 kunnen eender welke fractionele waarde aannemen
(halve kan) maar vaak niet realistisch (0=NEE en 1=JA -> wat indien 0,5??)
dus geheeltalligheid vereisen -> voorwaarde van Giopetto

Zekerheid: alle coëfficiënten zijn gekend met zekerheid; doel is zeker, verkoop is zeker (->
wel moeilijk)

Geheeltallig = integer programmeringsprobleem

Haalbaarheidsverzameling: verzameling van alle punten die voldoen aan de LP- en tekenbeperkingen

Optimale oplossing: beste haalbare punt (max -> hoogste doelfunctiewaarde, min -> laagste
doelfunctiewaarde)

NU: bepalen van de optimale oplossing grafisch, procedureel en software




5

,Bepalen van de optimale oplossing grafisch
Maximaliseringsprobleem met 2 variabelen
-> Haalbaar: onder de rechte (of op)

Lijnen die alle punten omvatten met een zelfde doelfunctiewaarde; bij max-probleem = isowinstlijn :
bij min-probleem = isokostenlijn -> zoek dus punt in haalbaarheidsverzameling met hoogste/laagste
isowinstlijn/isokostenlijn.

Bindende beperking: LHS en RHS van de beperking zijn gelijk bij de optimale oplossing -> geen
overschot/tekort -> alles produceren

Niet-bindende beperking: LHS en RHS van de beperking zijn niet gelijk bij de optimale oplossing

Convexe verzameling: verzameling is convex als een lijnsegment dat éénder welk puntenpaar in de
verzameling verbindt (= convexe combinatie) ook volledig in deze verzameling ligt  de
haalbaarheidsverzameling van een LP probleem is steeds een convexe verzameling (met eindig aantal
extreme punten)

Extreem punt of hoekpunt: kan niet tussen een convexe combinatie liggen -> steeds een hoekpunt
 optimale oplossing is steeds een extreem punt

-> Optimale oplossing op snijpunt van rechten van 2 bindende beperkingen



Minimaliseringsprobleem met 2 variabelen
-> haalbaar: boven de rechte (of op) -> haalbaarheidsverzameling onbegrensd ( niet gelijk aan een
onbegrensd LP probleem)

Doelfunctiewaarde: kost x1 . aantal x1 + kost x2 . aantal x2

Afvragen of de impliciete basisveronderstellingen realistisch zijn? -> telkens probleem



Speciale gevallen
Alternatieve/multipele optimale oplossingen (oneindig)

Indien de isolijn verschoven wordt zal deze terecht komen op een lijnstuk van de
haalbaarheidsverzameling -> oneindig veel optimale punten met meerdere extreme punten (2) die
optimaal zijn (-> alle convexe combinaties van deze extreme punten zijn dus ook optimaal) -> al deze
combo’s zijn in principe even goed -> verdere discriminatie (omwille van bvb. Eenvoud)



Onmogelijk LP-probleem
Indien de haalbaarheidsverzameling leeg is (= onmogelijk om te voldoen aan alle beperkingen) -> valt niet op te
lossen, geen optimum




6

,Onbegrensd LP-probleem

Haalbare punten die corresponderen met een oneindig hoge/lage waarde voor de doelfunctie ->
doelfunctie onbegrensd -> optimum onbepaald -> de isolijnen kunnen oneindig verschoven worden
en nog steeds binnen de haalbaarheidsverzameling blijven  oplossingswaarde = oneindig

 Dus 4 mogelijkheden van optimale oplossing  UNIEK (max. en min.), ONEINDIG, ONBEGRENSD,
ONMOGELIJK



Voorbeelden met meerdere beslissingsvariabelen
Dieetprobleem

Dagelijkse behoefte tegen minimale kost

-> meerdere beslissingsvariabelen dus oplossen via simplex methode



Mengprobleem

Optimale winst bepalen in termen van de geproduceerde producten die omgezet worden in een
nieuw product. Input -> output

Maximaliseren -> opbrengst – kost



Productieproces modelleren

Output als finaal goed: kan rechtstreeks verkocht worden -> het eindproduct

Output als intermediair goed: wordt gebruikt als input voor een ander product

Optimale hoeveelheid bepalen; afwegen hoeveel intermediaire goederen

Maximaliseren: opbrengst – kost (intermediaire kost en materiele kost)



Voorraadmodel

Dynamisch beslissingsprobleem -> t heeft invloed op t+1

-> veel variabelen -> per tijd en per product -> ook de voorraden per tijd en product

Eindvoorraad periode = Beginvoorraad (= eindvoorraad van vorige periode) + geproduceerd –
gebruikt (= de vraag)




7

,Bepalen van de optimale oplossing procedureel (H4)
Standaardformatie
Standaardformatie = Ongelijkheidsbeperkingen worden omgezet in gelijkheidsbeperkingen dmv:

- slackvariabelen (tekort) -> bij “<” -> + S -> “S” capteert het verschil tussen links en rechts

- excess variabelen (overschot) -> bij “>” -> - e

-> S1 -> 1 stemt overeen met de eerste beperking van een LP-probleem



Simplex algoritme inleiding
Matrixnotatie

Meer onbekenden/variabelen (=n) dan vergelijkingen/beperkingen (=m) -> matrixnotatie: Ax = b

Voorwaarde: n >/= m

- M = n -> exact 1 oplossing

- M < n -> minstens ‘n-m’ NBV

- M > n -> strijdige beperkingen

Wij gaan er in onze context dus altijd van uit dat 𝑚 ≤ 𝑛. Vermits we in standaardvorm al m
beperkingen hebben, hebben we er nog maar (𝑛 − 𝑚) bijkomende nodig om tot een uniek punt te
komen.



Basis en niet-basisvariabelen (BV & NBV)

Basisoplossing: oplossing van dit stelsel wanneer juist ‘n-m’ variabelen op nul gesteld worden

Basisvariabelen (BV): de ‘n-m’ variabelen die niet nul zijn

Niet-basisvariabelenv (NBV): de ‘n-m’ variabelen die nul zijn

-> niet elk systeem van n variabelen en m vergelijkingen heeft een basisoplossing

Een basisoplossing voor 𝑨𝒙 = 𝒃 kunnen we vinden door (𝒏 − 𝒎) variabelen (nietbasisvariabelen of
NBV) te kiezen en deze gelijk te stellen aan 0. Daarna zoeken we de waarde van de resterende 𝒏 − (𝒏
− 𝒎) = 𝒎 variabelen (basisvariabelen of BV) die voldoen aan 𝑨𝒙 = 𝒃. Elke basisoplossing voor 𝑨𝒙 = 𝒃
die we zo vinden is een toelaatbare basisoplossing (TBO) als alle variabelen groter dan of gelijk aan 0
zijn.



Haalbare / toelaatbare basisoplossingen (BFS)

Haalbare / toelaatbare basisoplossingen = ‘basic feasible solution’ = BFS: is een basisoplossing
waarbij alle variabelen niet-negatief zijn -> wanneer 1 variabele negatief is in de basisoplossing dan is
deze oplossing niet haalbaar



8

, -> een extreem punt van de haalbaarheidsverzameling van een LP, is steeds een haalbare
basisoplossing (BFS) -> dus alle variabelen in een extreem punt zijn positief

Elk LP met een optimale oplossing heeft een optimale BFS -> het volstaat om te kijken naar de
eindige verzameling van BFS (=> of extreme punten) voor het stelsel Ax=b om het optimum van het
LP probleem op te lossen

Aanliggende BFS: 2 BFS zijn aanliggend als ze een zelfde factor hebben die verschillend is van nul
(NBV) en een BV en NBV omgewisseld zijn -> ze hebben grafisch éénzelfde lijnsegment

In principe, kunnen we alle toelaatbare basisoplossingen van een LP opstellen en dan de toelaatbare
basisoplossing kiezen met de grootste z-waarde om de optimale toelaatbare basisoplossing te
vinden. Probleem: Zelfs kleine LP’s hebben een groot aantal toelaatbare basisoplossingen!
Oplossing: In plaats van alles te enumereren (‘brute-forcen’) gaan we verstandig te werk met het
simplex-algoritme.



Simplex algoritme
Simplex algoritme = een eindige en efficiënte procedure om snel tot optimale oplossing te komen
(bij meerdere beslissingsvariabelen) -> begint met een toelaatbare basisoplossing en probeert dan
aan de hand van aanliggende BFS betere oplossingen te vinden

-> indien de beperkingen </= zijn dan gebruiken we het simplex algoritme, indien er minstens 1
keer ‘>/=’ of ‘=’ staat dan gebruiken we de Big M methode of de Two-Phase Simplex methode

Voor maximaliseringsprobleem
1. Zet doelfunctie om in Rij 0 versie en LP om in standaardformaat (-> naar gelijkheid met +S en -e)

2. Vind een BFS voor het LP -> converteer LP naar canonieke vorm en simplextableau + Als de
rechterkant van het LP in canonieke vorm overal niet negatief is, dan kunnen we een toelaatbare
basisoplossing zo aflezen

3. Bepaal of deze optimaal is  Toelaatbare basisoplossing is optimaal als er in rij 0 geen niet-
basisvariabelen zijn met negatieve coëfficiënten. In zo’n geval kunnen we ‘z’ niet meer verhogen
door één van die NBV-variabelen in de basis te brengen

4. Zoniet, vind dan een aanliggende BFS met hogere doelfunctiewaarde (-> BV en NBV omwisselen
om beter te vinden)  Pivoteren totdat we een optimale toelaatbare basisoplossing hebben
gevonden -> welke wisselen bepalen we adhv de ratio test

5. Een nieuw simplex tableau door elementaire rijoperaties (ERO’s):

-> ingaande BV krijgt waarde 1 in de pivot rij en waarde 0 in de andere rijen

-> de pivot rij delen door de coëfficiënt van de ingaande BV in de pivotrij

-> de ingaande BV vervangen door de nieuwe pivot rij  in ELKE rij

Rij 0 versie

Oorspronkelijke versie: z = c1x1 + c2x2 +….

Rij 0 versie: 0 = z – c1x1 – c2x2 - ….

9

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

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

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

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 mariedebode. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for $16.60. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

52510 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling
$16.60  1x  sold
  • (0)
Add to cart
Added