Stochastisch programmeren

Stochastisch programmeren (Engels: stochastic programming) — een deelgebied van wiskundig programmeren dat modellen en methoden ontwikkelt voor het oplossen van optimalisatieproblemen onder onzekerheid, waarbij sommige parameters van het model niet exact bekend zijn, maar worden weergegeven als stochastische grootheden met bekende of geschatte kansverdelingen.

In tegenstelling tot deterministische problemen, waarbij alle gegevens als gegeven constanten worden beschouwd, beoogt stochastisch programmeren een oplossing (of beslissingsbeleid) te vinden die optimaal is in een zekere statistische zin. Meestal betekent dit het minimaliseren of maximaliseren van de verwachtingswaarde van de doelfunctie. Het kernidee is een beslissingsbeleid te vinden dat «gemiddeld» het beste is over alle mogelijke realisaties van de stochastische parameters, wat bijzonder relevant is voor problemen waarbij beslissingen herhaaldelijk worden genomen onder vergelijkbare omstandigheden (bijvoorbeeld bij voorraadbeheer of energiesystemen).

Wiskundige probleemstelling

In algemene vorm kan een stochastisch programmeringsprobleem worden geformuleerd als: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ waar:

• $x$ — de vector van beslissingsvariabelen (beslissingen) die bepaald moeten worden.
• $X$ — de verzameling van toegestane oplossingen voor $x$, bepaald door deterministische beperkingen.
• $\xi$ — een stochastische vector die de onzekere parameters van het probleem vertegenwoordigt (bijvoorbeeld vraag, prijzen, weersomstandigheden).
• $f(x,\xi )$ — de doelfunctie, waarvan de waarde afhangt van zowel de genomen beslissing $x$ als de realisatie van de stochastische vector $\xi$.
• $𝔼[\cdot ]$ — de verwachtingswaarde-operator, berekend over de kansverdeling van de vector $\xi$.

Een fundamenteel principe dat ten grondslag ligt aan meerfasige stochastische modellen is het niet-anticipatieprincipe (Engels: non-anticipativity principle). Dit stelt dat beslissingen die in enige fase worden genomen, alleen mogen afhangen van informatie die op dat moment beschikbaar is, en niet «in de toekomst mogen kijken».

Tweefasig probleem met compensatie

Het meest voorkomende model is het tweefasig stochastisch programmeringsprobleem met compensatie (Engels: two-stage stochastic program with recourse). Het beslissingsproces is verdeeld in twee fasen:

1. Eerste fase: Er wordt een «hier en nu»-beslissing (here-and-now) genomen — de vector $x$ wordt bepaald. Deze beslissing moet worden genomen voordat de concrete realisatie van de stochastische vector $\xi$ bekend is.
2. Tweede fase: Nadat de stochastische gebeurtenis heeft plaatsgevonden, wordt een corrigerende of compenserende beslissing (recourse decision) genomen — de vector $y(\xi )$, gericht op het minimaliseren van negatieve gevolgen of het benutten van gunstige kansen die voortkomen uit de combinatie van de eerste-fasebeslissing $x$ en de uitkomst $\xi$.

Wiskundig wordt het tweefasige stochastische lineaire programmeringsprobleem als volgt geformuleerd: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ met eerste-fasebeperkingen: $Ax=b,x\ge 0$. Hier is $Q(x,\xi )$ de compensatiefunctie (recourse function), die de optimale waarde van het tweede-faseprobleem vertegenwoordigt: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ waar $\xi$ — een stochastische vector die de parameters $q(\xi ),T(\xi )$ en $h(\xi )$ omvat; en $c,A,b$ en $W$ — deterministische parameters zijn.

Belangrijke eigenschappen en stellingen

• Convexiteit: Een van de fundamentele resultaten van de theorie is dat voor het tweefasige stochastische lineaire programmeringsprobleem de verwachte compensatiefunctie $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ een convexe functie is. Deze eigenschap is van groot belang, omdat zij garandeert dat het algehele eerste-faseprobleem een convex programmeringsprobleem is, waarvoor efficiënte oplossingsmethoden bestaan en het globale optimum samenvalt met het lokale optimum.
• Deterministisch equivalent: Als de stochastische vector $\xi$ een eindig aantal mogelijke realisaties (scenario's) ${\xi }_1,\dots ,{\xi }_K$ heeft met kansen $p_1,\dots ,p_K$, dan kan het stochastische programmeringsprobleem worden hergeformuleerd als één groot deterministisch optimalisatieprobleem. In dit geval wordt de verwachtingswaarde vervangen door een gewogen som over alle scenario's. De omvang van dit probleem groeit echter lineair met het aantal scenario's, wat leidt tot de «vloek van de dimensionaliteit» en een dergelijke aanpak rekenkundig onoplosbaar maakt voor een groot aantal scenario's.

Vergelijking met robuuste optimalisatie

Stochastisch programmeren is een van de verschillende benaderingen voor optimalisatie onder onzekerheid. Het belangrijkste verschil met robuuste optimalisatie ligt in de manier waarop onzekerheid wordt gemodelleerd en in het optimaliteitscriterium.

Vergelijking van benaderingen voor optimalisatie onder onzekerheid

Criterium	Stochastische optimalisatie	Robuuste optimalisatie
Weergave van onzekerheid	Parameters zijn stochastische grootheden met een bekende kansverdeling	Parameters behoren tot een gegeven onzekerheidsverzameling; een verdeling is niet vereist
Optimaliteitscriterium	Optimalisatie van de verwachtingswaarde van de doelfunctie	Optimalisatie in het slechtste scenario (minimax)
Aard van de oplossing	Beleid dat «gemiddeld» optimaal is; kan ontoelaatbaar zijn voor zeldzame scenario's	Oplossing die gegarandeerd toelaatbaar is voor alle realisaties; kan conservatief zijn

Voorbeelden

• Het krantenverkoopprobleem (Engels: newsvendor problem): Een klassiek voorraadbeheerprobleem waarbij een verkoper moet beslissen hoeveel eenheden van een product hij inkoopt zonder de exacte toekomstige vraag te kennen. De oplossing balanceert tussen het risico van verlies door overschotten en het risico van gederfde winst door tekorten.
• Het boerenprobleem: Een boer beslist hoeveel hectare grond hij aan verschillende gewassen wil toewijzen op een totale oppervlakte, zonder de toekomstige weersomstandigheden te kennen, die de opbrengst beïnvloeden. Nadat het weer bekend is geworden, kan de boer corrigerende maatregelen nemen (bijvoorbeeld overschotten verkopen of ontbrekende oogst bijkopen op de markt).

Zie ook

• Wiskundig programmeren
• Operations research
• Robuuste optimalisatie
• Dynamisch programmeren
• Regelsysteemtheorie

Noten

</references>