Programmazione stocastica: procedure di approssimazione

4 
 
I. Ottimizzazione stocastica a vincoli probabilistici 
 
I.1    Introduzione e formulazione del problema 
 
L’ottimizzazione stocastica tratta di problemi di ottimizzazione in 
condizioni di incertezza in situazioni specifiche: si tratta di ottimizzare –  
minimizzare o massimizzare – una funzione subordinatamente ad un sistema 
di vincoli e questi, ma possibilmente anche la funzione obiettivo, dipendono 
da vettori aleatori di cui è nota la misura di probabilità.  
 
Questa situazione è formalmente espressa nella forma: 
“opt”  f (x,ω) 
subordinatamente a (s.a) 
                          f
i 
(x,ω)   0         i = 1,2,…,r; 
 
la variabile di decisione è x che varia in uno spazio assegnato E , qui e nel 
seguito lo spazio euclideo di dimensione finita; l’incertezza è racchiusa in 
questa rappresentazione nel parametro ω che varia in uno spazio di probabilità 
assegnato (Ω,a,μ), dove Ω è l’insieme dei valori possibili ω, a è la σ -algebra 
degli eventi mentre μ è la misura di probabilità su a. 
 
In questa fase preliminare l’espressione “opt” indica il fatto che non è 
ancora specificato in che senso debba intendersi il problema di ottimizzazione 
da risolvere. 
 
Modelli di ottimizzazione stocastica sono molto frequenti in problemi di 
decisione in condizione di incertezza in cui l'incertezza è rappresentata da 
variabili aleatorie di cui è noto la distribuzione di probabilità.
5 
 
Si può affermare che tali problemi sono “generalizzazioni” di problemi di 
ottimizzazione matematica deterministici.  
 
Vi sono diversi modelli di ottimizzazione stocastica che dipendono dalle 
circostanze concrete in cui un problema si pone e dall’attitudine del decisore 
rispetto al rischio. 
 
In questo lavoro trattiamo di modelli di ottimizzazione stocastica a vincoli 
probabilistici. In questa impostazione le decisioni ammissibili sono le 
decisioni x che soddisfano i vincoli con un livello α di probabilità.                  
Il livello α è fissato a priori e riflette l’atteggiamento del decisore verso il 
rischio.  
 
Al riguardo si intuisce facilmente che un livello α=1 riflette un 
atteggiamento totalmente avverso al rischio da parte del decisore il quale 
restringe il suo campo di scelta solo alle decisioni che soddisfano 
sostanzialmente tutti i vincoli qualunque cosa accada; per contro un livello 
α=0 riflette un atteggiamento totalmente indifferente al rischio ossia le 
decisioni ammissibili sono quelle che soddisfano i vincoli “almeno una volta” 
per cosi dire, cioè per almeno un ω.  
 
In generale per α fissato,        indichiamo con  X(α) l’insieme delle 
decisioni ammissibili: 
     X(α) = { xϵ E :           : f
i 
(x,ω)   0; i = 1,2,…,r}    } 
Se la funzione obiettivo, come sarà sempre in questo lavoro, non ha 
componenti aleatorie, il problema di ottimizzazione stocastica a vincoli 
probabilistici assume la forma di un problema deterministico: 
   min   
 
f(x) 
s.a      x   X(α) .
6 
 
Il punto cruciale è la natura matematica dell’insieme X(α) che rende 
difficile la soluzione del problema anche in casi “apparentemente” semplici. 
La difficoltà è tutta nell’esprimere analiticamente l’insieme X(α).  
 
Anche nel caso in cui i vincoli del problema originario sono lineari in x, 
l’insieme X(α) presenta una complessità tale che, salvo casi particolari, il 
problema può essere affrontato solo con procedure di approssimazione.  
Un' eccellente presentazione del problema è presentata in [10]. 
 
La complessità dell’insieme X(α) deriva dal fatto che in generale X(α) non 
si può direttamente collegare alle funzioni di ripartizione dei vettori aleatori 
che intervengono nel problema. In realtà, come si vedrà nel seguito, X(α) è 
direttamente collegato alle funzioni di probabilità degli insiemi aleatori che 
intervengono nel problema originario.  
 
Lo studio degli insiemi aleatori associati ai problemi di ottimizzazione 
stocastica è la chiave di volta per penetrare la struttura probabilistica del 
problema. Da questa analisi deriva innanzitutto la possibilità di rappresentare 
esplicitamente l’insieme X(α); quindi la possibilità di individuare insiemi 
aleatori ai quali si associano insiemi di decisioni ammissibili facili da trattare, 
ed infine la possibilità di trovare procedure di approssimazione convergenti 
per risolvere il problema originario. 
 
Rispetto al problema di ottimizzazione stocastica 
                                    “min”
   
f(x)                                 (I.1.1) 
                        s.a     f
i 
(x,ω)   0         i = 1,2,…,r; 
cui ci riferiamo come problema originario, la formulazione a vincoli 
probabilistici è espressa nella forma: 
                                              min    f(x)                                  (I.1.2) 
    s.a   x   X(α) = { xϵ  
 
 :      : f
i 
(x,ω)   0; i = 1,2,…,r}    }
7 
 
I problemi di tipo (I.1.2) si risolvono facilmente se le variabili aleatorie 
presenti in essi sono elementari ossia assumono al più un numero finito di 
valori; d’altra parte ogni variabile/vettore aleatoria/o può essere sempre 
riguardato/a come limite quasi certo di una successione di variabili aleatorie 
elementari. 
 
Queste osservazioni sostengono con forza l’approccio di approssimazione 
in cui le variabili aleatorie coinvolte nel problema originario sono rimpiazzate 
da variabili aleatorie elementari; quindi deve essere studiata la convergenza 
dei risultati. 
 
Nel paragrafo che segue formalizziamo i concetti base per il prosieguo:  
insiemi aleatori (multifunzioni) e funzioni critiche di probabilità ad essi 
associati.
8 
 
I.2  Insiemi aleatori e funzioni critiche di probabilità 
 
Nel problema di ottimizzazione stocastica originario (I.1.1) 
  “min”
   
f(x) 
                        s.a     f
i 
(x,ω)   0         i = 1,2,…,r; 
la presenza di vincoli con componente aleatoria dà luogo ad un insieme 
aleatorio: 
ω           Г(ω) = { xϵ  
 
: f
i 
(x,ω)   0 ; i = 1,2,…,r } 
 
Nelle applicazioni correnti, per ogni         l’insieme Г(ω) è in generale 
un sottoinsieme chiuso dello spazio euclideo   
 
. 
L’applicazione ω          Г(ω) di   nello spazio dei sottoinsiemi chiusi di  
 
 è 
una multiapplicazione misurabile se per ogni sottoinsieme chiuso F  di  
 
 si 
ha: 
Г 
-1
(F) = {      : Г(ω)   F   }     a 
 
Lo studio delle multiapplicazioni (dette anche multifunzioni) misurabili ha 
ricevuto notevole attenzione dalla fine degli anni ’60. Un riferimento di base 
resta comunque [5].  
In questa tesi faremo riferimento solo alle nozioni di base delle multifunzioni 
misurabili a valori chiusi, strettamente necessarie per la trattazione del 
problema. 
 
Dalla definizione di misurabilità della multifunzione Г( ) si intuisce 
facilmente che la misura di probabilità µ, definita sulla classe degli eventi a  
di  , si trasferisce ad una misura di probabilità per Г, nel senso che ad ogni 
sottoinsieme chiuso F  di   
 
 è associata la probabilità che Г( )   F sia non 
vuoto: 
    F           P(F) =            : Г(ω)   F   }
9 
 
In realtà è possibile mostrare che la corrispondenza 
K           D(K) =           : Г(ω)   K   }) 
definita sullo spazio di tutti i sottoinsiemi K compatti di   
 
 è una funzione 
che ha proprietà che possono essere riguardate come naturale estensione delle 
proprietà di una funzione di ripartizione di vettori aleatori; per questo motivo 
ci si riferisce ad essa di solito come funzione di distribuzione della 
multifunzione Г( ) . 
 
Al di là della portata teorica della funzione D e degli aspetti tecnici non 
elementari del suo studio è importante innanzi tutto sottolineare che la 
funzione K     D(K) racchiude tutta la struttura probabilistica della 
multifunzione misurabile Г( ), ovvero dell’insieme aleatorio ω         Г(ω) che 
governa il problema di ottimizzazione stocastica . 
 
Il punto cruciale rispetto ai problemi di ottimizzazione stocastica a vincoli 
probabilistici è il collegamento diretto dell’insieme X(α) delle decisioni 
ammissibili con la funzione D, o meglio con una sua restrizione.  
E’immediato constatare che :  
X(α) = { x :       : f
i 
(x,ω)   0; i = 1,2,…,r}     } 
                        = { x :       : Г(ω)   {x}    })    } 
                        = { x :   ({x})    } 
 
Ne deriva dunque che l’insieme delle decisioni ammissibili di un problema 
di ottimizzazione stocastica a vincoli probabilistici è rappresentato attraverso  
la funzione di distribuzione dell’insieme aleatorio del problema. 
 
Questo da un lato spiega l’intrinseca difficoltà nel t rattare questo tipo di 
problema: si tratta di lavorare con uno strumento nuovo e poco esplorato.
10 
 
 Dall’altro lato però chiarisce in modo inequivocabile che la determinazione di 
X(α) chiama in causa tutta la struttura probabilistica dell’insieme aleatorio      
e non semplicemente la funzione di ripartizione del vettore aleatorio che 
determina l’insieme aleatorio. 
 
E’ comodo e soprattutto comporta semplificazioni di notazione considerare 
la restrizione di D su  
 
 così definita per ogni x    
 
: 
      t(x) =   ({x}) =            : Г(ω)   {x}    } ) . 
 
Resta definita in questo modo la funzione  x       t(x)  su  
 
  cui ci 
riferiremo come funzione critica di probabilità di Г( ).  
Resta chiarito, con grande semplificazione anche concettuale, che l’insieme 
X(α) delle decisioni ammissibili del problema di ottimizzazione stocastica a 
vincoli probabilistici è l’insieme di livello α di t: 
X(α) = { x    
 
:   x)    } 
 
Ne segue che le proprietà di X(α) possono essere derivate dalle proprietà di 
t. In particolare due proprietà di  t  si rilevano cruciali per X(α) . 
 
Proposizione I.2.1.  – La funzione critica di probabilità  x          t(x) associata 
alla multifunzione Г( ) è semi-continua superiormente. Ne segue che l’insieme 
di livello X(α) è chiuso.  
 
Dimostrazione – Ricordiamo innanzitutto che per ogni       , l’insieme Г(ω) 
è un sottoinsieme chiuso di  
 
  Per dimostrare che x          t(x) è semicontinua 
superiormente in ogni x , occorre dimostrare che per ogni x e ogni successione 
x
n
            x si ha : 
limsup  t(x
n 
)     t(x) 
Siano dunque x e x
n
          x  dati.