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
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 MvanB. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.88. You're not tied to anything after your purchase.