Hoorcollege aantekeningen Management Science

college 1

Modelleren (H1)

Modelleren is het vereenvoudigd weergeven van de werkelijkheid.

Doel: situatie beter begrijpen/besturen.

Het is een creatief denkproces, niet goed/fout maar geschikt/ongeschikt.

7 stappen proces (zie slides/boek)

1. Probleem defineren. Belangrijkste vaardigheid is luisteren

2. Data verzamelen. Op basis van feiten

3. Model ontwikkelen. Welke aannames van de toekomst: ‘stel nou…’ vragen (Kun je later weer gebruiken).

4. Verifiëren. Nog steeds recht aan het probleem: heb je het begrepen? Je hebt dus al model + informatie maar nog geen oplossing

5. Optimaliseren. Oplossingen bedenken m.b.v. een model (Excel)

6. Communiceren. Ook aangeven hoe gevoelig het model is (welke variaties er zijn op algemene oplossing)

7. Uitvoering

Een model bestaat uit:

• Parameters (gegevens + aannames)

• Beslissingen (variabelen)

• Uitkomsten (consequenties)

• Structuur (samenhang)

Bij verificatie vraag je jezelf af: “is dit model juist?”

Bij validatie vraag je jezelf: “helpt dit model?”

Spreadsheet modellen (H2)

Spreadsheet modellen zijn rijen en kolommen met cellen waarin gegevens/relaties tussen andere cellen met gegevens staan.

Gegevens:

• Parameters: celwaarde ongewijzigd in het model

• Variabele: mag gewijzigd worden

Relaties: de cel bevat (de uitkomst van) een formule waarin naar andere cellen wordt verwezen.

Veel gemaakte fouten:

• Foute/verouderde gegevens

• Onjuiste bewerkingen op gegevens

• Absolute/relatieve verwijzingen

• Instelling handmatige herberekening

• Toevoegen/weghalen van rijen/kolommen

Voordelen van spreadsheets: zie slides

Data analyse (H2+H3)

Data analyse is vanuit date een model construeren

1. Patronen herkennen (verondersteld verband)

2. Hypothese testen/veronderstelling verifiëren (verondersteld verband)

3. Alternatieven vergelijken (en andere alternatieven vinden)

4. Voorlopige keuze: voorlopige theorie, er kan dus nog een betere komen.

Voorbeeld theorie: ‘belonen is beter dan straffen’, maar het patroon is andersom. Wat mis is met deze patroonherkenning is dat er onterecht invloed verondersteld wordt op de uitkomst, zoals bijvoorbeeld het straffen bij het gooien van een dobbelsteen.

Dus: altijd kritisch zijn op eigen veronderstelling en eigen denkfouten door kritiek adresseren.

Oplossing: dataset splitsen

• Deel voor vinden relaties

• Deel voor aantonen relaties

Vertrouw niet alleen op een grafiek maar bekijk ook de achterliggende data bij bijvoorbeeld het aantonen van een trend. Voor voorbeeld zie slide!

Reden tot snelle patroonherkenning: de mens wil graag patronen zien:

• Geeft gevoel van controle

• Wordt versterkt als eigen gedrag de verklaring is (“ik heb hard gewerkt dus verdien ik een bonus”)

• Cognitieve bias: niet meer van de eigen denkwijze afwijken

Trends aantonen: regressie (H3)

Met Excel kun je trends aantonen

Zie slide voor voorbeeld!

Houd het model zo simpel mogelijk

Geschikt of niet?

• Wat zegt de theorie

• Wat vertelt de R2 waarde?

• Wat zegt je gezonde verstand? 

College 2

Regressie

Scanner diagram: de data is verspreid over het vlak. Op de horizontale as staan de verklarende variabelen (zoals bijvoorbeeld de vraag) wat verklaart wat op de verticale as staat. Zie slide 4, voor een voorbeeld van een scanner diagram.

Zet alle punten in de grafiek. De volgorde (van bijvoorbeeld dagen) wordt dan weggelaten.

Ga op zoek naar een model dat een mogelijk verband tussen benzineprijs en verkochte hoeveelheid weergeeft (patroon). Je kunt bijvoorbeeld kiezen tussen een lineair model, kwadratisch model en een 3e graads polynoom. Zie slide 5 voor voorbeelden hiervan! 

Let op: als je kiest voor een model moet je niet voor de plek in de data kiezen maar voor het soort model!

Formules: 

• Lineair model: y=a+bx

• Kwadratisch model: y= a+bx+cx2

• 3e grads polynoom: y=a+bx+cx2+dx3

Als je op zoek gaat naar het soort model moet je je eerst richten op de theorie (bijvoorbeeld: als de prijs omlaag gaat gaan de verkopen omhoog).

Stelling wetenschappers: “Als het kan met een simpel model, doe het dan met een simpel model!” Hierdoor wordt je resultaat ook minder gevoelig voor fouten.

Lineaire modellen zijn typische regressiemodellen, maar naast lineair zijn er nog veel meer andere modellen. Je moet het wel kunnen uitleggen!

Stap 2: op zoek naar patronen

Regressie met Excel trendline

Trendline toevoegen aan Scatterdiagram:

1. Selecteer de grafiek

2. Kies in de Ribbon voor Chart Tools >> Layout

3. Klik op de kleine pijl onder Trendline

4. Kies onderaan voor “More trendline options”

5. Kies Trend/Regression Type: Linear en vink de onderste twee opties aan (Display Equation en Display R-squared

6. Druk nog niet op Close, maar pas eerst de kleur en dikte van de trendlijn aan.

Regressie met lineair model 

Een model kan vaak afwijken. Een model wijkt bijna altijd af van de waarden. Dit worden errors genoemd. X=0 is bijvoorbeeld bij prijs zeer onwaarschijnlijk maar wordt in het model wel aangegeven. Zie slide 8 voor voorbeeld model! 

Stap 3: Bepaal het model

• Lineair verband Y=ax+b

• A is verwachte y als x=0

• B is de richtingscoëfficiënt lijn

• We kennen ((x1,Y1);(x2,y2);…)

• Definieer ei=yi-(ax+bxi)

• Bepaal a en b zodanig dat bijvoorbeeld de APE (Abslute Percentage Error) minimaal is.

• Er is een trend als b significant afwijkt van 0: y verandert met x

‘zo goed mogelijk’ is een criterium dat je kiest.

Stap 4: Los het model op

Data > Data Analysis (eventueel nog bij Opties > Addins aanvinken) > regression > waarden invullen voor y en x > labels aanvinken, residuals aanvinken

Stap 5: Interpreteer het model

Hogere R-kwadraat betekent een betere fit, dus minder nodig om ook andere verklarende variabelen in het model op te nemen. De a-coefficient geeft het snijpunt met de y-as aan. De b-coefficient geeft de richting aan ten opzichte van de x-as. Als de P-waarde <0,05 dan is het significant, want hij wijkt dan voldoende af van 0 om te spreken van een trend.

Belangrijk: slide 12! Uitleg uit je hoofd leren en kunnen gebruiken!

Trends aantonen

• Met lineaire regressie bepaal je lijn y=ax+b

• Waarden voor a en b zodanig dat APE of RMSE minimaal (RMSE is meest gebruikte criterium)

• R geeft correlatie tussen lijn en waarnemingen

• Als b significant afwijkt van 0 nemen we een trend aan

• Controleer significantie niet op het oog, maar met P-waarde van de b-coëfficient

• Verificatie: juistheid lineair model bij gegeven data volgt uit hoge R2

• Validatie: terechte keuze lineair model volgt uit theorie

Toepassing regressie

Vragen:

Wat is de current growth rage?

Op hoeveel datapunten is dit gebaseerd? Probeer voor voorspellingen de dataset zo breed mogelijk te maken!

Als we een regressielijn berekenen, op hoeveel datapunten is die gebaseerd?

Helpt het om data uit (verre) verleden te gebruiken om te voorspellen?

Zie voorbeeld slide 19

• Hoe sterk is het verband tussen de variabelen?

• Is het verband significant?

Stap 1: Informatie bepalen + bepaal wat x en wat y is

Stap 2: Teken scatterdiagram (puntenwolk)

Volgens het voorbeeld staan er 3 punten in

Stap 3: Vind de correlatie (r) tussen X en Y (Multiple R, pagina 73)

R waarde ligt tussen -1 en +1. Als het 0 is, is er geen samenhang tussen X en Y. Is het negatief, dan wordt het verband steeds sterker maar negatief (tegengesteld).

Bij een r van -0,945:

Positief:

1. Bijna perfect verband in onze case studie data: r ver weg van 0

2. Lineair verband luidt: Y = 0-2,5 x

Negatief:

1. Stemt lineair model overeen met theorie?

2. Levert het model zinvolle uitkomsten?

3. Hebben we de trend al wel aangetoond? (door middel van p-waarde)

Zie slide 23

Als het verband (bijna) perfect leek maar toch niet aangetoond kan worden, wat doet een onderzoeker dan?

Niet doen:

• “Statistischeniet significant, maar wel klinisch relevant”

• “Statistisch niet sifnificant, maar wel substantieel”

• “Er is een duidelijke statistisch niet-significante trend te zien”

• “De trend is niet significant, maar negeren zou dom zijn”

Goede oplossingen:

1. Op zoek naar een beter model (niet-lineair) dat aansluit op theorie

2. Meer data zoeken

3. Andere verklarende variabelen zoeken

4. Extra verklarende variabelen zoeken

Door 1 extra datapunt toe te voegen kan een lijn al erg kantelen, je moet zo’n model creëren zodat hij bijna niet meer verandert wanneer je nog meer data toevoegt.

College 3

Data analyse

Voorspellen met modellen. Modellen die Y voorspellen gebaseerd op verklarende variabelen (x1,…,Xn). Je kunt er meer toevoegen. Op basis van observatie van X-en kun je misschien een voorspelling maken van variabelen die je wilt weten. Je gebruikt informatie om een voorspelling te maken, de kwaliteit van de voorspelling hangt af van de input.

Type 1: Theorie en Regressie

Je maakt gebruik van de theorie en deels van regressie. Regressie is altijd een oorzaak-gevolg relatie. Causale relatie: oorzaak/gevolg relatie, X is oorzaak van Y. Alle veranderingen in X verklaren dus de veranderingen in Y en als er niks in X verandert, verandert er ook niks in Y. X gaat een tijdsperiode t>0 vooraf aan Y (dus de oorzaak moet voor het gevolg plaatsvinden).

De verklaring (causale relatie) moet gedragen worden door de theorie (wetmatigheden). De verklaring hoeft niet perfect te zijn, ook andere oorzaken spelen namelijk mogelijk een rol. Je moet de hoofd en bijzaak onderscheiden. Een ‘goed’ medicijn hoeft namelijk ook niet bij iedereen te werken. Voorbeeld: Model van impact van snelheid voor de botsing en omvang van de schade.

Type 2: Correlatie

Dit is een samenhang tussen patronen en wordt gebruikt om een voorspelling van het gedrag van Y in de toekomst te maken. Het is samenhangend beide kanten op.

Type 3: Autocorrelatie

Autocorrelatie is een samenhang met zichzelf, variabele x heeft samenhang met variabele Y. Veranderingen in X gaan vaak samen met veranderingen in Y. Er is nog geen verklaring vanuit de theorie, en een eventuele relatie kan beide kanten op gaan. Een andere variabele kan namelijk de veroorzaker zijn. De voorspellende waarde is twijfelachtig.

De historische data (Yt-1,Yt-2…) voorspelt Yt De aanname is dan dat patronen uit het verleden zich opnieuw zullen voldoen (na-ijlen). Dit werkt goed bij beurskoersen en bij het weer. Sommige van die patronen kun je verklaren vanuit theorie. Meestal zie je dat de patronen zelf niet verklaard worden. Ander woord voor autocorrelatie model: tijdreeks analyse. Voorbeeld: watertemperatuur Atlantische oceaan over de jaren heen.

Veelgemaakte fouten bij het voorspellen van causale relaties :

• Er worden 2 dingen waargenomen, maar de echte verklaring ligt niet in de X maar ergens anders in. De achterliggende verklaring blijft dan onopgemerkt (samenhang is niet hetzelfde als causaliteit).

• Verwisselen van oorzaak en gevolg

• Verwarren van volgordelijkheid met causaliteit. Bij volgordelijkheid gebeurt iets na iets, waardoor het tijdverschil van waarneming en effect dan dus wel klopt.

Vaak hebben onderzoekers wel al een voorkeursuitkomst

Vraagvoorspelling: tijdreeks. Hier vul je een tijdseenheid in.

Tijdreeks: verloop van variabele over de tijd

Voorbeelden: vraag per product per week, prijs koffie op termijnmarkt per periode

Variabele Y krijgt dan de index t (tijd): Yt. Dus bij tijd gebruik je meestal geen i of j.

Vraagvoorspelling notatie

1. Stel t=4

2. Doe observaties: (Yt, Yt-1, Yt-2, Yt-3 ….)

3. Tussenberekeningen (bijvoorbeeld: gemiddelde)

4. Voorspelling voor de toekomst: Fe+1 = Lt

Voorspelkwaliteit

Zie slide 12 voor voorbeeld!

Stel nu dat de echte vraag in periode 5 gelijk is aan 15, en 10 voorspelt was.

Voorspelfout et = Yt-Ft : e5 (hokje 5) = 5

Bij de nieuwe voorspelling gebruik je ook de voorspelfout

Nieuwe informatie: F6 – L5 = 11

Stel dat de echte vraag in periode 6 toch gelijk is aan 8:

Voorspelfout et = Yt – Ft = 8-11=-3

Et wordt de inputdata voor de voorspelkwaliteit en is dus heel belangrijk!

Nauwkeurigheid voorspelling

Werkwijze:

• Bepaal enkele mogelijke waarden voor de parameter van je voorspelmode (bijv. span = 3, 4 of 5, alpha -0,1, 0,15 etc)

• Kies eventueel beginwaarde voorspelmodel

  • Bereken voorspellingen voor N perioden waarvoor al observaties beschikbaar zijn

  • Meet het verschil tussen observatie en voorspelling

  • Kies en bereken de maat voor de voorspelkwaliteit (criteria):

    • MAE Mean Absolute Error

    • RMSE Root Mean Squared Error

    • MAPE Mean Absolute Percentage Error

• Vergelijk de waarde voor de voorspelkwaliteit. Hoe lager het criterium, hoe beter de voorspelde kwaliteit!

Je moet je eigen aannames uiteindelijk altijd ter discussie stellen! Nog beter is om verder te proberen (de alfa bijvoorbeeld weer veranderen).

Formules: zie slide 14/pagina 103 boek!

N gaat om het aantal waarnemingen dat je in de laatste kolom gebruikt (in het voorbeeld dus in ‘error’)!

Voorspelmethoden

Hoe bepalen we de voorspelling Ft+1?

1. Moving average

2. Exponental smoothing

Moving Average

• Bepaal span: s recentste observaties

Yt, Yt-1, Yt-2,… worden gemiddeld en gebruikt als voorspelling

• De voorspelling voor t+1 maak je zodra de observatie van periode t (Yt) bekend is

• Tussenberekening en voorspelling: Zie slide 16

Zie slide 17 voor voorbeeld van voorspellen Moving Average

Bij extra waarnemingen verbetert de P waarde (significantie).

Zie pagina 105 boek voor bepalen span

• Als span 1 is, is de voorspelling gelijk aan de laatste observatie

• Als span oneindig is, is de voorspelling een constant gemiddelde

• Als de span groter wordt past de voorspelling zich minder aan ten gevolge van recente observatie. Ook die keuze maak je als onderzoeker.

Exponental smoothing

Hier wordt meer gewicht gegeven aan recente observaties, alle observaties uit het verleden tellen mee en er wordt dus geen data uitgesloten. De nieuwe voorspelling is een gewogen som van de nieuwste observatie en de vorige voorspelling. De voorspelling voor t+1 maak je zodra de realisatie van peirode t bekend is. Tussenberekening en voorspelling: zie slide 19. a is de wegingsfactor (smoothing factor).

Zie slide 20 voor voorbeeld voorspellen Exponential Smoothing

a bepalen:

0<a<1

Als a bijna 1 zit al het gewicht op de laatste observatie

Als a bijna 0 is, zit al het gewicht op het gemiddelde

Als a = 0,66: zit 99% van het gewicht op de laatste 5 observaties

Als a = 0,2: zit 67% van het gewicht op de laatste 5 observaties

Er wordt vaak gezegd dat je a zo laag mogelijk moet houden, maar de afweging wordt gemaakt met behulp van MAE, RMSE en MAPE.

Als er een trend is heeft Moving average en Exponential smoothing weinig zin. In cyclische modellen zit vaak geen voorspelbaarheid

Vergelijking tussen regressie en tijdsreeks voorspelling

• Regressie met als verklarende variabel t bepaalt of er een trend in de tijd is en neemt als constante het gemiddelde zonder trend

• Tijdsreeksanalyse zonder trend of seizoen voorspelt voor elke volgende periode dezelfde uitkomst. Er is immers geen trend of seizoenscorrectie van de voorspelling nodig.

Waarom wil je voorspellen?

• Wachten kan soms meer kosten dan anticiperen (klanten kunnen al overgestapt zijn)

• De exacte waarde mag onzeker zijn, maar de richting geeft te denken

• Automatiseren voorspellingen voor tienduizenden producten en de reactie daarop bespaart veel geld

• Laat de data spreken, maar betrek ook experts met zicht op veranderingen en hun effecten.

College 4

Wiskundig modelleren

Stappen in modelleren:

1. Probleem definitie

2. Dataverzameling. Bijvoorbeeld: wat zijn de bestellingen, welke producten, hoeveel medewerkers nodig etc.

3. Modelbouw. Bijvoorbeeld: hoe kun je de vraag maken tot iets concreets waarmee je kunt rekenen, abstract model met informatie

4. Oplossen van model. Antwoord op de vraag, wiskundige technieken gebruiken en bijv Excel

5. Gevoeligheidsanalyse, interpretatie resultaten. Hoe gevoelig is de uitkomst voor wat je er in hebt gestopt, wat als de voorspelling niet helemaal klopte?

6. Resultaten en advies

7. Implementatie resultaten

1 en 2 gebeuren door het bedrijf zelf. Je weet dan wat de input is.

Wees altijd kritisch als je gaat modelleren. Wanneer de input niet goed is, is de output ook niks waard, hoe goed het model ook is.

Bouwstenen van een model

• Parameters. Welke input gegevens zijn bekend en noodzakelijk om beslissingen te kunnen nemen? Voorbeeld: model bij winst maximaliseren, data gaat over verkoopprijs en kosten van het product. Je moet dan zelf eerst een bewerking toepassen.

• Variabelen. Beschrijving van de beslissingen die moeten worden genomen. Mogelijke waarden van een variabele: Positief of negatief (of mag allebei), niet-negatief of niet-positief, geheeltallig, niet-geheeltallig (bijvoorbeeld bij aantal medewerkers die fulltime werken), binair (als alleen 0 of 1 uit kunnen komen, vaak bij een vraag waar het antwoord ja of nee is)

De definitie van x en y is in een model is heel belangrijk, je moet duidelijk formuleren.

• Doelstelling. Instrument om alternatieve oplossingen te kunnen ranken. Wat wil je bereiken? Wiskundeige uitdrukking van je doel door variabelen en parameters te gebruiken. Minimaliseren of maximaliseren?

• Randvoorwaarden. Beperkingen in waarden van beslissingsvariabelen. Wiskundige relaties geven randvoorwaarden weer. Bijvoorbeeld: minimaal aan de vraag voldoen, maximaal aantal in te zetten medewerkers

Soorten modellen

• Lineair programmeren. Variabelen met continue waarden

• Integer programmeren. Variabelen met geheeltallige waarden

• Binair programmeren. Variabelen (bijvoorbeeld wel(1) of niet (0) openen van een nieuw magazijn)

Mogelijke eigenschappen oplossing

• Toelaatbaar versus niet-toelaatbaar: Een toelaatbare oplossing voldoet aan alle randvoorwaarden

• Optimaal versus niet-optimaal:De toelaatbare oplossing die de doelstellingsfunctie optimaliseert

Gevoeligheidsanalyse

Op welke manier verschillen de uitkomsten van het model als we de waarde van een bepaalde parameter of een randvoorwaarde veranderen? Belangrijk omdat manager bij investering (wel of niet nieuwe machine) wordt uitgerekend met bepaalde vraag, maar vraag kan afwijken. Dit bereken je vaak met een grafiek en met de doorlooptijd, waarbij de x-as de waarde is die verandert en de y-as de verandering in de output als resultaat van de verandering in je input. Voor voorbeeld zie slide 11. De vraag is hoe gevoelig de uitkomst is voor de originele waarden die je in het model hebt gestopt.

Casus: Distributie van kranten

Hiermee wordt het hele proces van de klant tot zijn bestelling bedoeld. Situatie: 2 distributeurs die de klanten naar het noorden vervoerden. Ze besloten samen te gaan werken om lege ritten tegen te gaan en hierdoor kosten te besparen. Bezorgers moesten hierdoor meer kranten bezorgen. Verandering: Nieuwe stroom van kranten, meer kranten en krantenwijken en een gelijk aantal bezorgers. Vraag van het bedrijf: Hoe de integratie van een nieuwe stroom in het bedrijfsproces opnemen

Beslissingen:

• Hoe ga je rijden

• In welke volgorde gaat de bezorger adressen bezoeken(Routeringsprobleem)

• Krantenwijken samenstellen

Zie slide 13 t/m 20

Wiskundig formuleren probleem

Stap 1: Definitie van variabelen

1a: Welke beslissingen worden genomen?

1b: Druk de beslissingen uit in bijvoorbeeld x1, x2, x3 en geef duidelijke uitleg bij de variabelen.

1c: Geef de range van elke variabele weer (geheeltallig, niet-geheeltallig, positief, negatief, 0-1)

Voorbeeld 1 (zie slide 23)

Stap 1:

Xa1 Chauffeur A vervoert container 1

Xa2 Chauffeur A vervoert container 2

Xb1 Chauffeur B vervoert container 1

Xb2 Chauffeur B vervoert container 2

1 = ja

0 = nee

Er zijn 4 variabelen nodig om dit beslissingsprobleem wiskundig te beschrijven

Stap 2: Antwoord c: Het maximaliseren van de winst

Max 27.000x1 + 18.000 x2 + 37.000 x3

Stap 3: Doelstelling, zie stap 1

Stap 4: Formuleer de randvoorwaarden

X1: project 1 is wel/niet afgerond

X2: Project 2 is wel/niet afgerond (binaire variabele)

Randvoorwaarde: Project 1 kan alleen worden afgerond als project 2 al is afgerond

Hoe kun je dit wiskundig uitdrukken?

X1 – X2 ≤ 0

Want als x1 = 1 dan X2 = 1

Als X2 = 0 dan is X1 = 0

Als X2 = 1 dan is X1 = 1 V X1 = 0

X1 ≤ X2

0,1X1 = 1X2

0X1 = 0X2

Correcte wiskundige formulering voor de beperking is:

X1 + X2 + X3 + X4 + X5 ≥ 3

Bij beperking: Als 2 wordt gekozen mag 5 niet worden gekozen

Formulering:

X1 = 1 dan X5 = 0

X1 = 0 dan X5 =0 V X5 = 1

Dus X1 + X5 < 1 (je mag 1 van de 2 kiezen)

Goede antwoord: X1 + X5 ≤ 1

Voorbeeld 2 (zie slide 24)

Stap 1: Formuleer variabelen en range

X1 = Hoeveelheid bonen haiti gebruikt in premium koffie

X2 = Hoeveelheid Colombia gebruikt in premium

X3 = Hoeveelheid bonen Peru gebruikt in premium

X1 + X2 + X3 = Hoeveel premium

X4 = Hoeveelheid Haiti gebruikt in deluxe koffie

X5 = Hoeveelheid Colombia gebruikt in deluxe koffie

X6 = Hoeveelheid Peru gebruikt in deluxe koffie

Netwerk = verbindingslijn tussen twee verschillende knooppunten

Product-Mix voorbeeld: 2 variabelen

Vraag: Hoeveel van elk grondstof gebruiken in de mix om de winst te maximaliseren?

Het bedrijf maakt whisky.

Stap 1: Randvoorwaarden: 500 l is maxi capaciteit, 4 euro/l rogge, 2 euro/l bourbon

X1 = hoeveelheid rogge in liters

X2 = hoeveelheid bourbon in L

X1, X2 ≥ 0 niet-geheeltallig geheeltallig

Mix whisky: X1 + X2

Stap 2: Geef parameters

1 liter whisky €12

1 liter rogge €4

1 liter bourbon €2

Winst = verkoopprijs – kosten

Stap 3: Geef doelstelling

Doelstelling is maximale winst

Kosten: 12 ( X1 + X2) - ( 4X1 +2X2)

Verkoopprijs – Kosten

12X1 + 12X2 – 4X1 -2X2

Doelstellingsfunctie: 8X1 + 10X2

Stap 4: Geef randvoorwaarden

Minstens 400 liter

Maximaal 500 liter

1. mix in liter ≥ 400

X1 + X2 ≥ 400

2.X1 + X2 ≤ 400

X1 + X2 ≤ 500

3. Niet meer dan 250 liter bourbon

X2 ≤ 250

4. Minstens 40% van de mix moet rogge bevatten

X1 ≥ 0,4(X1 + X2)

X1 – 0,4X1 – 0,4X2 > 0

0,6X1-0,4X2 ≥ 0

College 5

Lineair programmeren oplossen

Check de eigenschappen van een model

• Is het een lineair programmeringsmodel?

• Volgende eigenschappen spelen een rol, deze moet je controleren:

1. Is de doelstelling proportioneel: is de bijdrage van een variabele proportioneel met de waarde van de variabele (met elke stijging van de variabele zal dan met een factor de doelstelling groeien)

2. Additiviteit: alles is sommatie, geen vermenigvuldiging, delen e.d. van variabelen. Als er x of : staat is het niet lineair, + en – is goed

3. Deelbaarheid: variabelen kunnen elke waarde hebben (dus ook niet-geheeltallige waarden)

4. Zekerheid: zijn alle parameters bekend en constant

Als X en Y variabelen zijn en a en b parameters zijn:

• Bij X + Y/B ≤ 0 is het wel lineair, want b is een parameter en dus een getal. Je kunt alles x b doen en dan worden het gewoon getallen: bx_4 <- 0

• X + b/y ≤ 0 is niet lineair

• Bij Abx + BY ≤ 0 is het wel lineair, want 2 variabelen worden niet met elkaar vermenigvuldigd

• Bij Axy + aY ≤ 0 is het niet lineair, want er worden 2 variabelen met elkaar vermenigvuldigd

Oplossen van een LP model

Voor een lineair programmerings (LP) model met 2 variabelen wordt de grafische methode gebruikt (met de hand, op een blaadje). Als er meerdere variabelen zijn gebruiken we de Simplex methode. Hiermee wordt er een optimaal antwoord gevonden. Deze methode kun je bijvoorbeeld in Excel met een spreadsheet model gebruiken.

Een LP kan meerdere optimale oplossingen hebben. Dit geldt ook als de hoek van de doelstelling gelijk is aan de hoek van de constraints. Er kunnen dus meerdere combinaties zijn van variabelen die leiden tot hetzelfde optimale antwoord. Ook kan het mogelijk zijn dat een LP-probleem geen oplossing heeft. Dit komt omdat er dan geen oplossing is binnen de toelaatbare oplossingen.

(= een oplossing die voldoet aan de randvoorwaarde, maar is niet direct de ultieme oplossing)

Zie slide 8 voor algemene weergave van een model

Vector-en matrixnotatie

Deze formulering kun je gebruiken om het in Excel te zetten, en daardoor antwoord te krijgen op je vraag. De matrixnotatie is een hulpmiddel voor de simplex methode. Zie slide 9 t/m 11 voor voorbeeld. 

Stappen bij het grafisch oplossen:

1. Teken een lijn per constraint

2. Bepaal voor elke lijn aan welke kant het toelaatbare gebied met oplossingen ligt

3. Geef alle hoekpunten (alleen hoekpunten geven de toelaatbare oplossing)

4. Controleer de waarde van de doelstellingsfunctie voor elk hoekpunt

5. Selecteer een van de hoekpunten met de beste waarde (hangt af van het soort doelstellingsfunctie, minimaliseren of maximaliseren)

Zie slide 13 en 14 voor voorbeeld

Simplex methode

Deze kan worden gebruikt om een LP model optimaal op te lossen. Het is gebaseerd op een klassieke wiskundige theorie uit de 19e eeuw. Het heeft twee belangrijke eigenschappen: oplossingen moeten niet-negatief zijn en een optimale oplossing moet worden gekozen uit een oneindige verzamenling van toelaatbare oplossingen. Slack variabelen worden geïntroduceerd om modellen op te lossen. Er zijn veel solvers op de markt om dit op te lossen. Dit doe je op basis van het spreadsheet model, bijvoorbeeld met Excel.

Maak gebruik van de input van stappen 1-4 bij het opstellen van het model. Dit moet op basis van het matrix structuur. Bij gebruik van Excel heb je een solver nodig.

Vergelijkbare structuur:

• Cellen met input (parameters)

• Veranderende cellen (variabelen)

• Cel doel (doelstellingsfunctie)

• Randvoorwaarden

• Niet-negatieve waarden (range)

Zie slide 17 en 18 voor voorbeeld

Bindende randvoorwaarde: maximale productie en arbeid (randvoorwaarden maximaal gebruiken). De ruimte tussen niet-bindende randvoorwaarden noemen we Slack.

Gevoeligheidsanalyse

Zie slide 19 en 20 voor voorbeeld van veranderingen in doelstellingsfuctie

Veranderingen in randvoorwaarden

Schaduwprijs: Deze prijs geeft de verandering weer in de optimale waarde van de doelstellingsfunctie als de rechterkant van een randvoorwaarde met een eenheid verandert. Bijvoorbeeld: Hoeveel wil je uitgeven om 1 uur meer aan arbeid te hebben en nog steeds winst te maken?

Als arbeidsuren nog beschikbaar zijn is het een niet-bindende randvoorwaarde, met als schaduwprijs 0. Deze vind je dus alleen bij bindende randvoorwaarden.

Netwerken

Veel optimalisatieproblemen hebben een onderliggende netwerkstructuur. Er zijn vaak goede oplossingstechnieken beschikbaar. De structuur helpt bij het oplossen via een spreadsheet tool. Veel grote en complexe problemen uit het bedrijfsleven laten zich vertalen naar een netwerkprobleem:

• Het plannen van routes en vertrek- en aankomsten van vliegtuigen

• Toewijzing van medewerkers aan taken

• Het vinden van de kortste route langs klanten om goederen af te leveren

• Het bepalen welke fabriek levert aan welke klant en in welke hoeveelheden

Soorten netwerken:

• Ongerichte graaf G=(V,E) bestaat uit twee delen, waarbij de afstand tussen knooppunten gelijk is. Je hebt te maken met een verzameling knooppunten, set V en takken tussen de knooppunten, set E (in Engels: edge). Representatie vindt plaats door middel van punten (knooppunten) en lijnen (takken).

• Gericht netwerk: Als er wel verschil zit tussen de knooppunten gebruiken we een gericht netwerk. De verbindingen tussen knooppunten krijgen nu een richting mee (set A; in Engels: arcs). De gerichte graaf heeft knooppunten (set V) en pijlen (set A). Een pijl geeft de verbinding aan van de start naar het eindpunt.

Kosten en capaciteit:

Voor takken en pijl kunnen kosten (bij gebruik van bepaalde route) of capaciteiten (maximaal aantal keer dat bepaalde verbinding gebruikt kan worden) gelden. Weergave vindt naast een pijl of tak plaats.

Zie slide 30 en 31 voor voorbeeld netwerk tekenen

Handelsreizigersprobleem: de handelsreiziger zoekt een route met minimale afstand om zijn klanten elk precies 1 keer te bezoeken. Het betreft hier een netwerk met eenrichtingsverkeer (dus afstanden kunnen verschillen)

Geef een gericht netwerk SLIDE

Verschillende typen netwerkmodellen

Voor alle type modellen moet je straks kunnen:

• Het geven van een probleembeschrijving

• Het tekenen van het bijbehorende netwerk

• Het opstellen van een lineair programmeringsprobleem (LP)

• Het benoemen van eigenschappen van het probleem

• Het oplossen met spreadsheetmodellen

Transportprobleem

Bij een transportprobleem vraag je jezelf af hoe je tot een oplossing komt als vraag en aanbod niet gelijk zijn.

1. Probleembeschrijving:

Een bedrijf verzendt producten van productie- of opslaglocaties (origins) naar klantlocaties (destinations). Verzendingen vinden alleen plaats tussen een opslaglocatie naar een klantlocatie.

Bekend: vraag op elke locatie, capaciteiten en de kosten om 1 eenheid van locatie naar klant te versturen (deze variabelen MOET je weten om het op te kunnen lossen)

Een transportprobleem bevat vaak een grote hoeveelheid randvoorwaarden en variabelen (omdat je veel locaties hebt en een groot netwerk).

2. Netwerk tekenen

3. LP-formulering: variabelen en doel

• Parameters invullen (=bekende waarden)

• Randvoorwaarden opstellen

Zie slide 35 t/m 40 voor voorbeeld

Eigenschappen van een transportprobleem zijn dat het alleen toelaatbare oplossingen als de totale vraag gelijk is aan de totale capaciteit. Kosten zijn direct proportioneel met het aantal eenheden dat wordt verzonden. Variabelen zijn door eigenschappen van de structuur van het probleem per definitie geheeltallig in oplossing. Het is oplosbaar met simplex methode voor LP (en daardoor met Excel).

College 6

Toewijzingsprobleem (Assignment probleem)

Probleembeschrijving

Er zijn twee sets: machines en producten of bijvoorbeeld medewerkers en taken. Op de een een-op-een basis worden elementen van de ene set aan elementen van de andere set toegewezen. Prototype: het toewijzen van taken aan machines zodanig dat de totale tijd om alle taken te doen minimaal is. Er zijn speciale types transportproblemen:

• Machines: leveranciers

• Taken: klanten

• Tijdsduur product op bepaalde machine: verzendkosten

• Aantal taken op een machine: capaciteit

• Aantal keer dat een taak op een machine moet (meestal 1): vraag

• Arc met capaciteit 0 of 1 (machine doet de taak wel/niet)

Een bipartiete graph is een ongerichte graaf G = (V, E) waarbij V kan worden opgedeeld in 2 sets (V1 en V2. Verbindingen gaan altijd van links naar rechts of rechts naar links, andere combinaties zijn niet mogelijk. Voor voorbeeld zie slide 1 t/m 10 

Eigenschappen van een toewijzingsprobleem:

• Het aantal taken en het aantal medewerkers is gelijk (n)

• Als dit niet zo is, is er een dummy nodig (opbrengst is dan 0)

• Als aan alle eigenschappen wordt voldaan, dan is het probleem zeer efficiënt optimaal op te lossen

• Elke variabele in oplossing is geheeltallig door de eigenschappen van het probleem (daardoor kan de randvoorwaarde binaire variabelen worden weggelaten in formulering)

• Het probleem is oplosbaar met de simplex methode (en dus met Excel), ook al zijn het hele getallen.

Kortste pad probleem (shortest path problem)

Het doel van dit probleem is het vinden van een korste pad tussen twee knooppunten in een netwerk. Voorbeelden van toepassingen zijn een grafische context (kiezen van het kortste pad tussen plaats A naar B) of het vinden van het optimale rooster voor het vervangen van machines. Dit kan in gerichte en ongerichte netwerken. Voor voorbeeld zie slide 14 t/m 19

Je moet altijd 1 keer vaker vertrekken dan dat je aankomt, anders ben je namelijk niet vertrokken. Dus bij de randvoorwaarden moet je ook altijd ‘– het terugkomen’ invullen. Als je begint met 3 moet je positief eindigen, als je eindigde met 3 moet je negatief eindigen.

Bij transshipment knooppunten moeten de in- en uitgaande stroom in balans zijn.

Eigenschappen van een kortste pad probleem:

Variabelen zijn door de eigenschappen van de structuur van het probleem per definitie geheeltallig in oplossing. Het is oplosbaar met de simplex methode voor LP (en daardoor met Excel).

IP modellen

Geheeltallige LP modellen worden ook wel integer lineair programming (in Engels; afgekort met IP) genoemd. IP modellen zij lastiger op te lossen dan LP modellen. Netwerkproblemen zijn een uitzondering zoals we hebben gezien. Door de structuur van het probleem kunnen we deze oplossen als LP probleem. Er zijn 3 vragen die je kunt stellen:

• Waarom is het complexer?

• Waarom kunnen we de LP oplossing niet altijd direct gebruiken?

• Hoe doen we dit dan wel?

Waarom is het IP model complex?

Bij het oplossen van LP modellen is er keuze uit een oneindige verzameling van toelaatbare oplossingen. De Simplex methode zoekt efficiënt in de hoekpunten. IP modellen hebben een eindig aantal toelaatbare oplossignen, maar dit aantal kan astronomisch groot zijn. Een eigenschap is de exponentiële groei in het aantal variabelen. Voorbeeld: neem een probleem met n binaire variabelen. Het aantal oplossingen is 2n. Met extra variabelen verdubbelt het aantal oplossingen. Voor IP zijn er nog meer mogelijke oplossingen variabele. Volledige enumeratie ( = elke mogelijke oplossing bekijken) wordt dan onmogelijk.

LP oplossing:

Stap 1: Los het probleem op als LP model (dit noemen we LP relaxatie van het IP model). Als voor de optimale oplossing geldt dat de waarden van alle variabelen geheeltallig zijn ben je nu klaar.

De verkregen oplossing kan niet toelaatbaar zijn en de verkregen oplossing kan ook niet optimaal zijn. Voor voorbeeld zie slide 25 en 26.

Branch-and-bound:

De verzameling van toelaatbare oplossingen wordt onderverdeeld in deelverzamelingen door het maken van een boom. In elke boom worden takken met (interval van) waarden branching variabelen toegevoegd. Voor elke deelverzameling hebben we een grens (bound) nodig om te bepalen hoe goed de oplossing is. Dit wordt verkregen door het oplossen van bijvoorbeeld een LP relaxatie probleem. Voor elke deelverzameling wordt besloten of er mee doorgegaan wordt of niet

• Als de integer oplossing de beste waarde van de doelstelling heeft die onder bound ligt, dan moet je het opslaan en ben je klaar met het deelprobleem (incumbent oplossing)

• Voor maximaal: ondergrens en voor minimaal: bovengrens

• Als de integer oplossing hogere waarde heeft dan bound ben je klaar

• Als er geen toelaatbare oplossing is ben je klaar

Voor voorbeeld zie slide 28 en 29

Incumbent: er is een oplossing gevonden, deze hoeft niet optimaal te zijn

Voorbeeld van een probleem: locatieprobleem

Algemeen locatie-keuze model:

• Set van klanten

• Set van bedrijven die klanten kunnen voorzien van producten

• Afstanden, tijden en kosten worden gemeten in een bepaalde eenheid

Hoofdvragen zijn:

• Hoeveel bedrijven open je

• Wat zijn de locaties van de bedrijven

• Welke klanten worden bedient vanuit welk bedrijf of welke bedrijven

Doelstellingsfunctie: minimaliseren van kosten

De input van dit probleem zijn de typen materialen, locatie van de leveranciers, locatie van de klanten, het vervoermiddel en kosten van transport, afhandelen en opslag.

Factoren die invloed hebben op de keuze:

• Beschikbaarheid van grondstoffen

• Kosten van arbeid en beschikbaarheid van arbeid

• Nabijheid van klanten en leveranciers

• Regelgeving

• Kosten van de locatie

• Gas, elektra, water

• Infrastructuur

Voor voorbeeld zie slide 34

College 7

Eigenschappen van een lineair programmeringsprobleem:

• Proportioneel

• Additiviteit

• Deelbaarheid

• Zekerheid

Als deze eigenschappen niet aanwezig zijn spreken we over een niet-lineair programmerings probleem

Niet-lineair model:

• In doelstelling en/of randvoorwaarden

• Als niet aan een of meerdere eigenschappen op vorige slide wordt voldaan

• Meerdere vormen afhankelijk van karakteristieken van functies f en g

SLIDE

Het kan ook dat de randvoorwaarden niet deze eigenschappen hebben, en het daardoor een niet-lineaire programmeringsprobleem is. Voor voorbeeld zie slide

In de praktijk heb je vaak een niet-lineaire doelstellingsfunctie.

Voorbeelden:

1. Prijselasticiteit: de hoeveelheid die kan worden verkocht heeft een omgekeerde relatie met de prijs die wordt gevraagd (bijvoorbeeld het effect van doelstelling van winst)

2. Marginale kosten: de productiekosten dalen als geproduceerde aantallen toenemen (bijvoorbeeld in randvoorwaarde budget of in doelstelling van kosten)

Bij een niet-lineaire functie kun je nog steeds de winst gewoon formuleren! Voor voorbeeld zie slide

Optimaliseren van een functie

Het optimaliseren van een functie met 1 variabele bereken je met behulp van differentiëren. Het is een zoekproces naar optimale waarde x = x*. De variabele x is differentieerbaar in het interval [a,b]. x is het stationair punt: f’(x)=0

De maxima noemen we locale maxima. Vervolgens zoek je het optimale maximum, ofwel het hoogste maximum. Het stationair punt kan een locaal minimum of een locaal maximum zijn.

Differentiëren van een functie

C = constant getal

X = variabele

F(x) F’(x)

F(x) = c F’(x) = 0

F(x) = xb F’(x) = bxb-1

F(x)=cx F’(x) = cxln(c)

Voor voorbeelden zie slide

Differentiëren van samengestelde functies

= g(x)-1

Optie 1: Kettingregel: dh = f’(g(x)) * g’(x)dx

Optie 2: Quotiëntregel: dh =

Optimalisatie: vervolg zoekproces

Als je een minimum zoekt gebruik je alleen de locale minima

Als je maximum zoekt gebruik je alleen de locale maxima

Je hebt meer informatie over elk van deze punten, of ze convex of concaaf zijn. Je hebt hiervoor een tweede afgeleide F”(x) nodig.

Als f’(x) = 0 en f”(x) >0 dan is x een lokaal minimum

Als f’(x) = 0 en f”(x) <0 dan is x een lokaal maximum

Een functie is convex als de bijbehorende helling van de tweede afgeleide niet-negatief is. De lijn tussen elke twee punten ligt boven de curve (voor voorbeeld zie slide). Er is geen tekenbare lijn die onder de curve ligt.

Een functie is concaaf als de tweede afgeleide niet-positief is. De lijn tussen elke twee punten ligt dan onder de curve.

Convex of concaaf zijn eigenschappen van een functie. Deze eigenschap helpt om het zoekproces naar een optimum te beperken. Een lineaire functie is zowel convex als concaaf. Y = ax+b heeft een constante helling. De solver van Excel gebruikt deze eigenschappen en vindt gegarandeerd een globaal maximum (minimum) als deze bestaat

Bij maximaliseren: de doelstellingsfunctie (of log ervan) is concaaf EN de randvoorwaarden zijn lineair

Bij minimaliseren: de doelstellingsfunctie (of log ervan) is convex EN de randvoorwaarden zijn lineair

Als de aannames niet gelden of niet kunnen worden getoetst moet je zelf gegevens uitproberen:

1. Probeer verschillende startwaarden voor ‘veranderende cellen’

2. Run voor elk van deze startwaarden

3. Kies de beste oplossing die wordt gevonden

Dit is een manier om uit een lokaal optimum te breken. Als elke keer hetzelfde optimale antwoord wordt gevonden kun je er redelijk zeker van zijn dat het juiste antwoord is gevonden.

Optimaliseren in de praktijk gebracht

Soorten voorraad:

• Grondstoffen

• Work-in-progress (halffabrikaten)

• Onderdelen voor onderhoud/repareren/componenten

• Eindproducten

Er zijn heel veel verschillende types voorraadmodellen. Welk model je kiest hangt af van de eigenschappen van het probleem. Hiervoor moet je jezelf afvragen wanneer je de voorraad weer moet aanvullen en hoeveel je dan moet bestellen. Tekorten worden op deze manier voorkomen. Bestellen in grote hoeveelheden is meestal voordeliger, maar een grotere voorraad heeft meer kosten. De vraag is dus of dit uit kan.

Bij een onafhankelijke vraag kan EEQ gebruikt worden, SLIDE

Soorten kosten:

• Kosten voor het houden van voorraad: Bijvoorbeeld onverkoopbaarheid, verzekeringen, rente, magazijn en personeel

• Bestelkosten: Bijvoorbeeld kosten van formulieren, orderverwerking, transport en betalingen

• Setup kosten: Kosten om een machine klaar te maken voor het klaarmaken van een bestelling

EOQ model (Economic Order Quantity)

Om te besluiten of je dit kunt toepassen moet je een aantal dingen testen:

• Er moet een bekende en constante vraag zijn

• Er moet een bekende en constante levertijd zijn

• De levering moet gelijk en volledig komen

• Er moet geen korting gegeven worden bij een bepaalde hoeveelheid

• Er moeten alleen bestelkosten en kosten voor het houden van voorraad zijn

• Aannemen dat je nooit uit voorraad bent

Als iets van dit bovenstaande niet geldt is het nuttig om verder te kijken dan het EOQ model.

Het doel van dit model is het bepalen van de bestelgrootte om totale kosten te minimaliseren. De totale kosten bestaan uit de bestelkosten en de kosten van het houden van de voorraad (totale kosten = bestelkosten + kosten houden voorraad).

Variabelen en parameters in het model:

Q = bestelgrootte (variabele)

D = vraag per tijdsperiode (parameter)

S = kosten voor plaatsen van 1 bestelling (parameter)

H = kosten voor het houden van voorraad per eenheid per tijdsperiode (parameter)

Er zijn eigenlijk 2 keuzes: vaak of weinig bestellen. Bij een hoge bestelhoeveelheid wordt er minder vaak besteld. Bij een lage bestelhoeveelheid moet er vaker besteld worden. De vraag is de afweging tussen bestelkosten en voorraadkosten.

Bestelkosten zijn afhankelijk van het aantal bestellingen per tijdsperiode en van de kosten per bestelling.

Aantal bestellingen per tijdsperiode: De vraag D is voor een bepaalde periode. Als we Q producten per keer bestellen hebben we D/Q bestellingen per periode. De kosten per bestelling zijn S, dus de bestelkosten per periode zijn

De kosten van het houden van voorraad zijn afhankelijk van de kosten van het houden van voorraad van 1 product per tijdsperiode en van de gemiddelde voorraad.

De kosten van voorraad van 1 product per tijdsperiode is H.

Gemiddelde voorraad: Elke bestelling ebstaat uit Q producten, de maximale voorraad is dus gelijk aan Q. De minimale vooraad is 1, dus de gemiddelde vooraad is Q/2

Voor voorbeeld EOQ model grafisch zie slide

Het voorbeeld is een convex model.

Functie van de totale kosten per jaar: TC =

Voor het vinden van de beste bestelhoeveelheid zoeken we die Q waarbij TC minimaal is.

TC = (DS) Q-1 +

TC ‘= -1 (DS)Q-2+ = 0

TC’= = H/2

Q2 = =

Q*(optimaal) =

Voor ander voorbeeld EOQ zie slide

EOQ: recorder point

Lead time: tijdsduur tussen plaatsen bestelling en ontvangst

Reorder point (ROP): voorraadniveau waarop een nieuwe bestelling moet worden geplaatst om tijdig elevering te garanderen.

ROP = d * L

d = vraag per dag