Lineair programmeren
Lineair programmeringsprobleem: lineaire doelfunctie met lineaire beperkingen,
programmeren staat voor plannen.
Vorm LP-probleem beperkingen met ≤ teken, constante rechts en variabelen links.
Beslissingsvariabelen zijn elementen uit verzameling reële getallen en doelfunctie als lineaire
vergelijking en ongelijkheden geschreven.
Grafisch de beperkingen worden getekend als lijnen, grensrechte (lijnen zijn = teken).
Oplosruimte is verzameling van punten die door beperkingen zijn toegelaten.
Isowinstlijn: doelfunctielijn waarbij beslissingsvariabelen zelfde winst opleveren
Simplex methode: bij meer dat 3 beslissingsvariabelen kan je niet meer grafisch weergeven.
Begin in een van hoekpunten toegestane gebied, daar wordt waarde doelfunctie
bepaald. Dan kijken welk aangrenzend hoekpunt gunstigste waarde heeft
Altijd optimum optimum altijd hoekpunt oplosruimte, hoekpunt beter dan alle
verbonden hoekpunten dan is dit optimale oplossing, er zijn maar eindig aantal
hoekpunten
Voor grote problemen en veel variabelen niet meer grafisch, maar algebraïsch.
Ongelijkheden schrijven als vergelijkingen door middel van spelingsvariabelen (deze
moeten altijd positief zijn)
Simplex tableau
Pivot kolom eenheidskolom van een bepaalde variabele
Meest beperkende waarde = pivot
Eenheidskolom krijgen door andere beperkingen op te tellen en af te trekken
Onderste rij moet waardes bevatten hoger dan 0, dan ben je klaar
1. Als onderste rij (c) ≥ 0, stop
2. Kies variabele met meest negatieve waarde voor c, bijbehorende kolom i is
pivotkolom
3. Bereken ratio tussen rechterlid/waarde voor alle waardes van A ≥ 0, selecteer rij
waarvoor ratio het kleinste is, dit is pivot
4. Veeg matrix zodat pivotkolom eenheidskolom wordt
Problemen bij oplossen
Meerdere optimale oplossingen
Onoplosbaar probleem
Onbegrensd probleem
Bij lineair programmeren geen onzekerheid over gegevens, maar in werkelijkheid wel
gevoeligheidsanalyse (kleine aanpassingen van parameters en relaxatie beperkingen)
, Schaduwprijs: waarde die doelfunctie zou stijgen of dalen wanneer van een van de
beperkingen de waarde verhoogd of verlaagd wordt.
Problemen van grafen zijn ook optimalisatieproblemen, maar zijn beslissingsvariabelen niet
continu waardoor je geen simplex methode kan toepassen.
Maximale stroom probleem takken zijn maximale stromen, geen stroom negatief,
in/uit gelijk en Max = S (instroom put)
Toewijzingsprobleem toewijzing is binaire variabele (toegewezen of niet), som xij,
elke knoop maximaal aan een andere knoop, Integer LP (ILP) of Mixed integer LP
(MILP)
Kortste pad probleem minimale som van lengte pad, in en uit gelijk aantal takken
Minimaal opspannende boom minimale som lengte pad, bij n knopen: n-1 takken
en geen circuits (voor elke deelverzameling niet meer dan alle knopen)
Kleuringsprobleem minimaal aantal kleuren, elke knoop 1 kleur, naburige knopen
niet zelfde kleur
Handelreizigersprobleem minimaliseren lengte takken, 1 tak gaat knoop in en uit,
voor deelverzameling minder of gelijk aantal knopen
Beslissen onder onzekerheid
Onzekerheid: ontbreken van kennis of informatie met betrekking tot gevolgen van handelen
Scenario: verschillende mogelijke toekomsten waarin handelen andere gevolgen heeft
Volledige onzekerheid geen enkele info over waarschijnlijkheid scenario’s
Beslissen onder volledige onzekerheid
Maximincriterium (Wald) kies alternatief waarvan de laagste waardering het
hoogst is
Minste-spijt criterium (Savage) kies alternatief waarvan verschil in waardering ten
opzichte van meest gunstigste alternatief in dat scenario
Optimisme-pessimisme criterium (Hurwicz) hoogste en laagste waardering
bepalen van elk scenario, kies alternatief waarvoor aWmax + (1-a)Wmin hoogste is
Onverschilligheidscriterium van Laplace kies alternatief waarvoor som van
waarderingen het hoogste is (delen door aantal scenario’s)
Geïnformeerde onzekerheid of risico wel info beschikbaar over de waarschijnlijkheid van
scenario’s, geijkte besliscriterium is dan hoogste verwachte nut
Sequentiële beslissingen: als beslisser meer dan 1 beslissing na elkaar moet nemen
hulpmiddel gebeurtenis beslisboom
Gebeurtenis-beslisboom (GBB): graaf met boomstructuur, knopen zijn beslissingen,
uitgaande takken zijn alternatieve handelswijzen of alternatieve gebeurtenissen.
Pad van wortel tot blad een mogelijke toekomst
Waardering van beslisser bij elk blad
Voor hoogste nut, maar ook beslissen onder onzekerheid
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 MvanB. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €5,49. Je zit daarna nergens aan vast.
