Sistemi di Supporto alle
Decisioni I
Scelte di consumo
Chiara Mocenni
Corso di laurea L1 in Ingegneria Gestionale e L2 in
Ingegneria Informatica
III ciclo
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Caso statico
• Consideriamo il caso di un consumatore che
deve allocare delle risorse economiche per
ottenere un certa quantita’ di un bene c, in un
unico periodo ed in funzione di due stati di
natura, uno favorevole f (P(f)= π) ed uno
sfavorevole n (P(n)= 1-π) . Siano inoltre cf e
cn le scelte di consumo nei due stati di natura
(gli argomenti della sua funzione utilita’).
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Utilita’ attesa
• L’utilita’ attesa del consumo nei due stati e’
U (c f , cn )   u (c f )  (1   )u (cn )
Soggetta al vincolo
p f c f  p n cn  y
dove y rappresenta l’entita’ delle sue risorse.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Il problema decisionale
max U (c f , cn )  max  u (c f )  (1   )u (cn )
c f ,cn
c f , cn

s.v. p f c f  pn cn  y
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Caso dinamico
• Estendiamo ora la scelta di consumo al caso
in cui le decisioni comportino una allocazione
delle risorse non solo tra gli stati ma anche
nel tempo. Supponiamo che vi siano solo due
periodi, il presente (periodo 1) ed il futuro
(periodo 2). Siano c1 il consumo nel periodo 1
e c1f e c2f i consumi nel periodo 2
corrispondenti ai due stati di naura f ed n.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
 max u (c1 )   v(c2 f )  (1   )v(c2 n )
c1 ,c2 f ,c2 n

s.v. p1c1  p2 f c2 f  p2 n c2 n  y
Questo problema e’ riconducibile al problema
statico di allocazione di risorse tra i tre beni c1,
c2f e c2n visto in precedenza.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Il caso generale
• Le decisioni vengono prese in periodi discreti
• L’esito di ciascuna decisione non è completamente
predicibile ma può essere osservato prima che venga
presa la successiva
• L’obiettivo è dunque quello di minimizzare un costo o
di massimizzare una utilita’, cioe’ ottimizzare una
espressione che rappresenta l’esito desiderabile
• Le decisioni non possono essere analizzate
singolarmente dal momento che la singola decisione
deve bilanciare il basso costo desiderato attuale e gli
alti costi inevitabili futuri
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• L’idea di base nella programmazione
dinamica è quella di selezionare volta per
volta la soluzione che minimizza la somma
del prezzo al tempo attuale con il miglior
costo che può essere atteso nei tempi
successivi.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Le caratteristiche che compongono il problema sono:
• un sistema dinamico a tempo discreto del tipo
xk+1 = fk(xk, uk, wk)
• variabili aleatorie wk indipendenti che dipendono da
xk e uk;
• dei vincoli di controllo, ad esempio imponendo che uk
assuma valori positivi o nulli;
• una funzione di costo additivo del tipo:
N 1


E  g N xN +  g k xk ,uk , wk 
k =0


Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
dove gk, k = 0, ..., N sono funzioni;
• delle leggi di ottimizzazione necessarie per la
scelta di uk per ogni k ed ogni possibile valore
di xk;
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• k è l’indice del tempo discreto;
• xk è lo stato del sistema e riassume le informazioni
passate che sono rilevanti per l’ottimizzazione
futura;
• uk è la variabile di controllo o di decisione da
selezionare al tempo k conoscendo lo stato xk;
• wk è una variable aleatoria;
• N è l’orizzonte temporale o il numero di volte in cui
viene presa la decisione.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• La soluzione del problema consiste in una
successione di funzioni, chiamate leggi di controllo o
politiche
  0 , 1 ,...,  N 1
Dove k mappa gli stati xk nelle decisioni:
uk  k xk 
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Formalmente
• Dato uno stato iniziale x0, il problema e’ quello di
individuare una legge di controllo ammissibile che
minimizza il funzionale di costo:
N 1


J  x0   E  g N xN    g k xk ,  k xk , wk 
wk
k 0

k 0 ,...,N 1 
• con il vincolo che xk+1 = fk(xk, uk, wk), k=0,1,...,N-1;
• le funzioni gk sono note.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• Per un dato stato iniziale x0, una legge di controllo
ottima (una successione ottima di decisioni) * e’
quella che minimizza il costo corrispondente
J  *  x0   min J   x0 
 
• dove  e’ l’insieme di tutte le leggi di controllo.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• Il costo ottimo corrispondente allo stato
iniziale x0 viene indicato con J*(x0).
• Cioe’ J* e’ un funzionale che associa ad ogni
stato iniziale x0 il costo ottimo J*(x0) e viene
pertanto chiamato funzionale di costo ottimo.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Esempio
• Si considera il problema di fare l’ordine di un certo quantitativo
di oggetti all’inizio di ciascun degli N periodi così da soddisfare
una domanda di mercato di tipo stocastico. Siano:
– xk lo stock della merce disponibile in magazzino all’inizio del kesimo periodo;
– uk lo stock ordinato ed immediatamente venduto all’inizio del
periodo k-esimo;
– wk la richiesta di mercato durante il k-esimo periodo con una certa
distribuzione di probabilità associata ed assumiamo che w0, w1, …,
wN-1 siano indipendenti e che la domanda in eccesso sia evasa non
appena ci sia sufficiente spazio in magazzino.
• Lo stock evolve secondo la seguente equazione tempo discreto:
• xk+1 = xk + uk - wk
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• Il costo della merce ad ogni periodo k è dato dalla somma di
due contributi:
• il costo dell’acquisto cuk, dove c è il costo per unità ordinata;
• un costo H(xk+1) che rappresenta la penalità per gli stock xk+1 > 0
alla fine del periodo (costo della merce in giacenza per eccesso
di materiale in magazzino) o per xk+1 < 0 (costo per domanda
non soddisfatta).
• Dall’equazione dell’evoluzione del sistema, possiamo scrivere il
costo per periodo k come:
cuk + H(xk + uk – wk)
• e il valore atteso totale del costo su N periodi è dato da:
 N 1

E  cuk + H xk + uk – wk 
 k =0

Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• L’obiettivo è quello di minimizzare il costo mediante
un’appropriata scelta di u0, …, uN-1 soggetto al
vincolo uk ≥ 0, per k = 0, …, N-1, senza attendere di
vedere il livelli di domanda. Ovviamente sarebbe
meglio poter posporre l’ordinazione di uk fino al
tempo k, quando il livello corrente xk sarà noto.
Possiamo allora raccogliere l’informazione su tutte le
decisioni ottime in ogni periodo e prendere poi la
decisione nel momento in cui sara’ osservabile lo
stato del sistema. Questo significa che non siamo
interessati a scegliere i valori ottimi per l’ordine ma
piuttosto nel trovare una regola ottima per la scelta
dell’ordine uk in ciascun periodo k per ogni possibile
valore dello stock xk.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• Matematicamente il problema è quello di
trovare una sequenza di funzioni μk, k = 0, …,
N-1, che mappano lo stock xk nell’ordine uk
così da minimizzare il costo totale atteso. Il
significato di μk per ogni k e per ogni possibile
valore di xk è il seguente:
• μk(xk) = quantità di merce che deve essere
ordinata al tempo k se lo stock è xk
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• La programmazione dinamica si basa sul principio di
ottimalità:
• sia π* = {μ0*, μ1*, ..., μN-1*} una legge di controllo
ottima per il problema di base. Si consideri il sotto
problema in cui siamo allo stato xi al periodo i e
vogliamo minimizzare il costo per andare dal tempo i
al tempo N ed assumiamo che quando usiamo π*,
questa si presenti con probabilità positiva. Allora, la
legge di controllo troncata {μi*, μi+1*, ..., μN-1*} è a sua
volta ottima per il sotto-problema.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• Considerando il problema dell’inventario,
analizziamo l’algoritmo per la determinazione
dell’ordine dell’inventario ottimo partendo
dall’ultimo periodo e procedendo a ritroso nel
tempo (backward induction).
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• Tempo N-1: si assume che all’inizio del periodo N-1
lo stock disponibile sia xN-1. In tale periodo, chi fa
l’inventario dovrebbe ordinare, senza preoccuparsi di
quello che e’ avvenuto nel passato, un quantitativo
uN-1* = μN-1*(xN-1) che minimizza la somma del costo
dell’ordine, della giacenza e della domanda non
soddisfatta per l’ultimo periodo di tempo. Questo
costo è uguale a E{cuN-1 + H(xN-1 + uN-1 – wN-1)}
calcolato su wN-1. Denotiamo JN-1(xN-1) il minimo
calcolato per uN-1 ≥ 0 di questa quantità.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• Tempo N-2: si assume che lo stock all’inizio del periodo N-2 sia
xN-2 e che il valore da ordinare sia uN-2 = μN-2*(xN-2) tale da
minimizzare non solo il costo atteso del periodo N-2 ma
piuttosto:
(il valore del costo atteso del periodo N-2) + (il valore del costo
atteso del periodo N-1, avendo a disposizione di una politica
ottima per il periodo N-1).
~
E{cuN-2 + H(xN-2 + uN-2 – wN-2)} + E{JN-1(xN-1)}
calcolato su wN-2 e sapendo che xN-1 = xN-2 + uN-2 – wN-2, il
termine E{JN-1(xN-1)} diventa E{JN-1(xN-2 + uN-2 – wN-2)}.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Dunque, il costo ottimo per gli ultimi due periodi,
sapendo di trovarsi nello stato xN-2, è dato da:
J N-2 (x N -2 ) 
min
u N-2  0
Ecu N -2  H(x N-2  u N-2 - w N -2 )  J N -1 (x N-2  u N-2 – w N-2 )
w N 2
in cui il minimo è calcolato per ogni stock xN-2.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
• Tempo k: lo stock è xk e deve essere ordinato uk tale da
minimizzare la quantità:
(il valore del costo atteso del periodo k) + (il valore del costo atteso
del periodo k+1, …, N-1, avendo a disposizione di una politica
ottima per tutti questi periodi)
J k (x k ) 
min
uk  0
~
Ecu k  H(x k  u k - w k )  J k 1 (x k  u k – w k )
wk
• Le funzioni Jk(xk) denotano il valore ottimo del costo atteso per i
rimanenti periodi quando si parte dal periodo k con valore
iniziale xk e sono calcolate in modo ricorsivo indietro nel tempo,
partendo dal periodo N-1 fino al periodo 0. Il valore J0(x0) è il
valore ottimo del costo atteso per il processo quando l’inventario
iniziale è proprio x0. Durante il calcolo della politica ottima di
inventario, i valori {μ0*(x0), μ1*(x1), ..., μN-1*(xN-1)} sono ottenuti
minimizzando Jk(xk) per ogni possibile valore di k e di xk.
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Soluzione del problema
dell’inventario
• Consideriamo il problema dell’inventario in
cui sia gli stock da ordinare che la domanda
sono varibili intere positive. Assumiamo
inoltre che vi sia una capacita’ massima di
immagazzinamento e che la domanda in
eccesso venga persa. Dunque lo stock
assume la forma
Xk+1=max(0, xk + uk – wk)
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Dati del problema
•
•
•
•
capacita’ massima di stock immagazzinato (xk+uk) = 2,
orizzonte temporale N = 3 periodi
costo per una unita’ di prodotto c = 1,
funzione di costo per periodo:
H(xk+uk–wk)=max(0, xk+uk–wk) + 3 max(0,wk–xk–uk),
• costo nello stato finale = 0,
• lo stato iniziale x0 e’ noto,
• la domanda wk ha sempre la stessa probabilita’ in ogni
periodo:
p(wk=0)=0.1, p(wk=1)=0.7, p(wk=2)=0.2
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Risultati
Stage 0 (k = 0)
Stage 1 (k = 1)
Quantità di
merce da
ordinare
Cost-to-go
Stage 2 (k = 2)
Stock in
magazzino
Cost-to-go
Quantità di
merce da
ordinare
Cost-to-go
0
4.9
1
3.3
1
1.7
1
1
3.9
0
2.3
0
0.7
0
2
3.35
0
1.82
0
0.9
0
Chiara Mocenni - Sistemi di Supporto alle Decisioni I – aa. 2007-2008
Quantità di
merce da
ordinare