Stokastisk programmering

Stokastisk programmering (eng. stochastic programming) — en gren av matematisk programmering som utvecklar modeller och metoder för att lösa optimeringsproblem under osäkerhet, när vissa parametrar i modellen inte är exakt kända utan representeras som slumpvariabler med kända eller uppskattade sannolikhetsfördelningar.

Till skillnad från deterministiska problem, där alla data betraktas som givna konstanter, syftar stokastisk programmering till att finna en lösning (eller en beslutsregel) som är optimal i någon statistisk mening. Oftast innebär detta minimering eller maximering av väntevärdet av målfunktionen. Grundidén är att hitta en beslutsregel som är bäst "i genomsnitt" över alla möjliga utfall av de slumpmässiga parametrarna, vilket är särskilt relevant för problem där beslut fattas upprepade gånger under liknande förhållanden (till exempel inom lagerhantering eller energisystem).

Matematisk problemformulering

I allmän form kan ett stokastiskt programmeringsproblem formuleras som: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ där:

• $x$ — vektor av beslutsvariablar (lösningar) som ska bestämmas.
• $X$ — mängden av tillåtna lösningar för $x$, definierad av deterministiska bivillkor.
• $\xi$ — slumpmässig vektor som representerar osäkra parametrar i problemet (till exempel efterfrågan, priser, väderförhållanden).
• $f(x,\xi )$ — målfunktionen, vars värde beror både på det fattade beslutet $x$ och på utfallet av den slumpmässiga vektorn $\xi$.
• $𝔼[\cdot ]$ — väntevärdesoperatorn, beräknad med avseende på sannolikhetsfördelningen för vektorn $\xi$.

Ett centralt princip som ligger till grund för flerstegsstokastiska modeller är icke-anticipativitetsprincipen (eng. non-anticipativity principle). Den innebär att beslut som fattas i vilket steg som helst endast får bero på information som är tillgänglig vid det tillfället och inte kan "se in i framtiden".

Tvåstegsproblem med kompensation

Den vanligaste modellen är tvåstegsproblem med kompensation (eng. two-stage stochastic program with recourse). Beslutsprocessen delas upp i två steg:

1. Första steget: Ett "här och nu"-beslut (here-and-now) fattas — vektorn $x$ bestäms. Detta beslut måste fattas innan det konkreta utfallet av den slumpmässiga vektorn $\xi$ är känt.
2. Andra steget: När det slumpmässiga händelseförloppet har inträffat fattas ett korrigerande eller kompenserande beslut (recourse decision) — vektorn $y(\xi )$, som syftar till att minimera negativa konsekvenser eller utnyttja gynnsamma möjligheter som uppstår till följd av kombinationen av första stegets beslut $x$ och utfallet $\xi$.

Matematiskt formuleras tvåstegs stokastisk linjär programmering på följande sätt: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ med bivillkor för första steget: $Ax=b,x\ge 0$. Här är $Q(x,\xi )$ — kompensationsfunktionen (recourse function), som representerar det optimala värdet av andra stegets problem: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ där $\xi$ — en slumpmässig vektor som inkluderar parametrarna $q(\xi ),T(\xi )$ och $h(\xi )$; medan $c,A,b$ och $W$ — deterministiska parametrar.

Viktiga egenskaper och satser

• Konvexitet: Ett av teorins grundläggande resultat är att den förväntade kompensationsfunktionen $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ för ett tvåstegs stokastiskt linjärt programmeringsproblem är en konvex funktion. Denna egenskap är av stor betydelse eftersom den garanterar att det övergripande problemet för första steget är ett konvext programmeringsproblem, för vilket det finns effektiva lösningsmetoder och det globala optimumet sammanfaller med det lokala.
• Deterministisk ekvivalent: Om den slumpmässiga vektorn $\xi$ har ett ändligt antal möjliga utfall (scenarier) ${\xi }_1,\dots ,{\xi }_K$ med sannolikheter $p_1,\dots ,p_K$, kan det stokastiska programmeringsproblemet omformuleras som ett enda stort deterministiskt optimeringsproblem. I detta fall ersätts väntevärdet av en viktad summa över alla scenarier. Storleken på detta problem växer dock linjärt med antalet scenarier, vilket leder till "dimensionalitetens förbannelse" och gör detta tillvägagångssätt beräkningsmässigt olösbart för ett stort antal scenarier.

Jämförelse med robust optimering

Stokastisk programmering är ett av flera tillvägagångssätt för optimering under osäkerhet. Dess viktigaste skillnad från robust optimering ligger i sättet att modellera osäkerhet och i optimalitetskriteriet.

Jämförelse av tillvägagångssätt för optimering under osäkerhet

Kriterium	Stokastisk optimering	Robust optimering
Representation av osäkerhet	Parametrar är slumpvariabler med känd sannolikhetsfördelning	Parametrar tillhör en given osäkerhetsmängd; fördelning krävs inte
Optimalitetskriterium	Optimering av väntevärdet av målfunktionen	Optimering i värsta fallet (minimax)
Lösningens karaktär	En regel som är optimal "i genomsnitt" kan vara otillåten för sällsynta scenarier	En lösning som garanterat är tillåten för alla utfall; kan vara konservativ

Exempel

• Tidningssäljarproblemet (eng. newsvendor problem): Ett klassiskt lagerhanteringsproblem där en säljare måste besluta hur mycket av en vara som ska köpas in utan att känna till den exakta framtida efterfrågan. Lösningen balanserar risken för förluster till följd av överskott mot risken för utebliven vinst till följd av brist.
• Bondeproblemet: En bonde beslutar hur många tunnland mark som ska avsättas för olika grödor på en total areal, utan att känna till det framtida vädret som påverkar skörden. När vädret är känt kan bonden vidta korrigerande åtgärder (till exempel sälja överskott eller köpa in otillräcklig skörd på marknaden).

Se även

• Matematisk programmering
• Operationsanalys
• Robust optimering
• Dynamisk programmering
• Reglerteknik

Noter

</references>