Samenvatting
samenvatting operationeel onderzoek TEW
- Instelling
- Katholieke Universiteit Leuven (KU Leuven)
samenvatting volledige cursus + oefeningen + lesnota's + alle begrippen uitgelegd + uitgebreide inhoudstafel
[Meer zien]Voorbeeld 9 van de 34 pagina's
Voorbeeld 9 van de 34 pagina's
In winkelwagenVoorbeeld van de inhoud
SAMENVATTING: Operationeel OnderzoekInhoudstafel
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
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, Bancontact of creditcard 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 mariedebode. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €15,49. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 52510 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen