Programmazione stocastica

La programmazione stocastica (in inglese stochastic programming) è una branca della programmazione matematica che sviluppa modelli e metodi per la risoluzione di problemi di ottimizzazione in condizioni di incertezza, quando alcuni parametri del modello non sono noti con precisione, ma sono rappresentati come variabili casuali con distribuzioni di probabilità note o stimate.

A differenza dei problemi deterministici, in cui tutti i dati sono considerati costanti note, la programmazione stocastica si propone di trovare una soluzione (o una politica decisionale) che sia ottimale in un certo senso statistico. Nella maggior parte dei casi ciò significa minimizzare o massimizzare il valore atteso della funzione obiettivo. L'idea chiave è quella di individuare una politica decisionale che risulti la migliore «in media» su tutte le possibili realizzazioni dei parametri casuali; questo è particolarmente rilevante per i problemi in cui le decisioni vengono prese ripetutamente in condizioni analoghe (ad esempio, nella gestione delle scorte o dei sistemi energetici).

Formulazione matematica del problema

In forma generale, il problema di programmazione stocastica può essere formulato come: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ dove:

• $x$ — il vettore delle variabili decisionali (decisioni) che devono essere determinate.
• $X$ — l'insieme delle soluzioni ammissibili per $x$, definito da vincoli deterministici.
• $\xi$ — il vettore casuale che rappresenta i parametri incerti del problema (ad esempio, domanda, prezzi, condizioni meteorologiche).
• $f(x,\xi )$ — la funzione obiettivo, il cui valore dipende sia dalla decisione adottata $x$ sia dalla realizzazione del vettore casuale $\xi$.
• $𝔼[\cdot ]$ — l'operatore del valore atteso, calcolato rispetto alla distribuzione di probabilità del vettore $\xi$.

Il principio fondamentale alla base dei modelli stocastici multi-stadio è il principio di non anticipatività (in inglese non-anticipativity principle). Esso afferma che le decisioni prese in qualsiasi stadio possono dipendere solo dalle informazioni disponibili fino a quel momento e non possono «guardare al futuro».

Problema a due stadi con ricorso

Il modello più diffuso è il problema stocastico a due stadi con ricorso (in inglese two-stage stochastic program with recourse). Il processo decisionale è suddiviso in due stadi:

1. Primo stadio: Viene presa una decisione «qui e ora (here-and-now) — viene determinato il vettore $x$. Questa decisione deve essere presa prima che sia nota la specifica realizzazione del vettore casuale $\xi$.
2. Secondo stadio: Dopo che l'evento casuale si è verificato, viene presa una decisione correttiva o di ricorso (recourse decision) — il vettore $y(\xi )$, finalizzata a minimizzare le conseguenze negative o a sfruttare le opportunità favorevoli emerse dalla combinazione della decisione del primo stadio $x$ e dell'esito $\xi$.

Matematicamente, il problema stocastico a due stadi di programmazione lineare è formulato come segue: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ con i vincoli del primo stadio: $Ax=b,x\ge 0$. Qui $Q(x,\xi )$ è la funzione di ricorso (recourse function), che rappresenta il valore ottimale del problema del secondo stadio: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ dove $\xi$ è il vettore casuale che comprende i parametri $q(\xi ),T(\xi )$ e $h(\xi )$; mentre $c,A,b$ e $W$ sono parametri deterministici.

Proprietà chiave e teoremi

• Convessità: Uno dei risultati fondamentali della teoria è che, per il problema stocastico a due stadi di programmazione lineare, la funzione di ricorso attesa $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ è una funzione convessa. Questa proprietà è di grande importanza, poiché garantisce che il problema complessivo del primo stadio sia un problema di programmazione convessa, per il quale esistono metodi di soluzione efficienti e l'ottimo globale coincide con quello locale.
• Equivalente deterministico: Se il vettore casuale $\xi$ ha un numero finito di possibili realizzazioni (scenari) ${\xi }_1,\dots ,{\xi }_K$ con probabilità $p_1,\dots ,p_K$, il problema di programmazione stocastica può essere riformulato come un unico grande problema di ottimizzazione deterministica. In questo caso il valore atteso viene sostituito da una somma pesata su tutti gli scenari. Tuttavia, la dimensione di tale problema cresce linearmente con il numero di scenari, il che porta alla «maledizione della dimensionalità» e rende questo approccio computazionalmente intrattabile per un numero elevato di scenari.

Confronto con l'ottimizzazione robusta

La programmazione stocastica è uno dei diversi approcci all'ottimizzazione in condizioni di incertezza. La sua differenza chiave rispetto all'ottimizzazione robusta risiede nel modo di modellare l'incertezza e nel criterio di ottimalità.

Confronto degli approcci all'ottimizzazione in condizioni di incertezza

Criterio	Ottimizzazione stocastica	Ottimizzazione robusta
Rappresentazione dell'incertezza	I parametri sono variabili casuali con una distribuzione di probabilità nota	I parametri appartengono a un insieme di incertezza definito; la distribuzione non è richiesta
Criterio di ottimalità	Ottimizzazione del valore atteso della funzione obiettivo	Ottimizzazione nello scenario peggiore (minimax)
Natura della soluzione	Politica ottimale «in media», che può risultare inammissibile per scenari rari	Soluzione garantita ammissibile per tutte le realizzazioni; può essere conservativa

Esempi

• Problema del giornalaio (in inglese newsvendor problem): Classico problema di gestione delle scorte, in cui un venditore deve decidere quanta merce acquistare senza conoscere la domanda futura esatta. La soluzione bilancia il rischio di perdite da eccedenze con il rischio di mancato guadagno dovuto alla carenza.
• Problema del contadino: Un agricoltore deve decidere quanti ettari di terreno destinare a colture diverse su una superficie totale, senza conoscere le condizioni meteorologiche future, che influenzano i raccolti. Una volta note le condizioni meteorologiche, l'agricoltore può intraprendere azioni correttive (ad esempio, vendere le eccedenze o acquistare sul mercato il raccolto mancante).

Vedi anche

• Programmazione matematica
• Ricerca operativa
• Ottimizzazione robusta
• Programmazione dinamica
• Teoria del controllo

Note

</references>