Samenvatting Besliskunde dictaten

Besliskunde TB135C
Samenvatting dictaten

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