Youlaurea.it
Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Antonio Sforza » 14.Programmazione dinamica


Schema della lezione

In questa lezione si presentano gli elementi fondamentali della programmazione dinamica, introdotta da Bellman negli anni ‘50 per la soluzione dei problemi decisionali multistadio. Si presenta l’approccio risolutivo della programmazione dinamica per il problema del minimo percorso e per il problema dell’allocazione di una risorsa su più attività.

Stati e stadi di un processo decisionale multistadio

Negli anni ‘50 fu formulata la teoria matematica dei processi decisionali multistadio, cioè dei processi nei quali si riescono ad individuare degli stadi di evoluzione di tipo temporale, spaziale o logico. Questi processi erano presenti in un notevole numero di problemi applicativi in ambito industriale e territoriale e per descrivere l’argomento fu coniata l’espressione Programmazione Dinamica. Il termine “dinamico” indica che ci si rivolge a quei processi nei quali il tempo gioca un ruolo fondamentale, per le caratteristiche intrinseche del problema o per le ipotesi che è possibile formulare sui suoi elementi. Processi di questo tipo si presentano in molti campi di applicazione, nel controllo delle scorte, nella turnazione del personale, nella gestione dei servizi di un aeroporto, nella definizione delle politiche di investimento. In questi problemi il sistema oggetto di studio passa da uno stadio all’altro attraverso trasformazioni derivanti da decisioni prese in corrispondenza di ciascuno stadio. In ognuno di questi stadi è possibile definire lo stato del sistema, cioè le condizioni del sistema stesso, definito dai valori assunti dalle variabili del problema. Ad esempio, il livello delle scorte in un certo stadio del processo decisionale fornisce lo stato del sistema-magazzino in quello stadio. La funzione obiettivo assume in ogni stadio un valore che è funzione delle variabili. La programmazione dinamica scompone il problema nei k stadi in esso individuabili ed analizza ciascuno di essi, separatamente e in successione. Le kxn variabili individuate nel problema non saranno valutate contemporaneamente, ma k alla volta in n stadi successivi.

Il problema del minimo percorso in programmazione dinamica

Il problema del minimo percorso su una rete a livelli evidenzia i caratteri essenziali dei problemi che è possibile risolvere in Programmazione Dinamica. Si consideri il problema del collegamento interzonale rappresentato in figura. In ognuna delle 5 zone sono localizzate alcune città, collegate in successione da un certo numero di strade, a ciascuna delle quali viene associata un costo, sia esso una distanza o un tempo. Non ci sono strade colleganti zone non consecutive e si supponga inoltre di non prendere in considerazione le strade che congiungono città appartenenti alla stessa zona. Il problema consiste nel determinare il minimo percorso dalla zona origine alla zona destinazione. Il sistema può essere schematizzato con un grafo a livelli (la Teoria dei Grafi sarà introdotta in una lezione successiva) in cui a ciascuna città corrisponde un vertice, a ciascuna zona corrisponde un livello, e alle strade corrispondono gli archi di collegamento tra i vertici. I vertici sono numerati in maniera tale da indicarne il livello di appartenenza e la posizione nel livello stesso (il vertice ij è il j-esimo vertice del livello i). È necessario determinare il minimo percorso tra il vertice origine ed il vertice destinazione del grafo a livelli.

Rete stradale

Rete stradale

Rete stradale

Grafo della rete stradale

Grafo della rete stradale


Rete stradale

Grafo della rete stradale

Grafo della rete stradale

Decomposizione del problema in stadi

Decomposizione del problema in stadi


Soluzione dinamica del problema

Si valutano inizialmente le distanze tra il livello 0 e il I livello, associando a ciascun vertice del I livello la distanza minima da percorrere per giungere in esso. È risolta, in questo modo, la prima fase del processo decisionale. Sfruttando il calcolo effettuato per la prima fase si calcolano le distanze relative al passaggio dal I al II livello, associando a ciascun vertice di quest’ultimo la distanza minima da percorrere per giungere in esso dall’origine. Nel vertice 21 per esempio si può giungere dai vertici 11 e 12 per i quali già si conoscono le distanze dal livello 0. In 21 dunque si arriverà con il cammino O-11-21 di lunghezza 2+1 oppure con il cammino O-12-21 di lunghezza 3+2. Tra questi si sceglie il primo, più breve, registrando il valore 3 in corrispondenza del vertice 21. Un * sull’arco 11-21 ricorda che in 21 si giunge in maniera ottima dal vertice 11. In modo simile, sfruttando i valori associati agli stati del II livello, si può passare al III livello, determinando per ogni suo vertice la distanza minima a partire dal vertice origine. Utilizzando questi dati si può giungere infine al vertice destinazione, associando ad esso il valore del minimo percorso O-D che risulta pari a 6.

A questo punto, procedendo a ritroso dal vertice destinazione al vertice origine, sfruttando le indicazioni “memorizzate” sul grafo con *, si possono individuare gli archi costituenti il cammino minimo: 33-D, 22-33, 11-22, O-11. Essi compongono il cammino O-11-22-33-D, di lunghezza pari a 6 (2+2+1+1).

Soluzione dinamica del problema

Soluzione dinamica del problema

Soluzione dinamica del problema

Minimo percorso O -D

Minimo percorso O -D


Principio di Bellman

La validità della procedura di ottimizzazione dinamica è assicurata dal “principio di ottimalità” di Bellman (1957):

Una politica ottima ha la proprietà che, in un certo stato del sistema, essa è indipendente dal modo con il quale lo stato è stato generato, cioè le decisioni rimanenti devono costituire una politica ottima rispetto allo stato risultante dalle decisioni precedenti“.

Sulla base di questo principio è possibile frazionare il problema in stadi e risolvere gli stadi in sequenza, utilizzando i valori dinamicamente determinati della funzione obiettivo, indipendentemente dalle decisioni che ad essi hanno portato. Ciò consente di ottimizzare uno stadio per volta, riducendo il problema iniziale ad una sequenza di sottoproblemi di dimensioni minori e quindi di soluzione più agevole.

Problema di allocazione con 2 attività e 3 unità di risorsa

\text{Max  }z_1=6x_1+3x_2

\text{Max  }z_2=g_1(x_1)+g_2(x_2)

s.a.

x_1+x_2=3

x_1,x_2\geq 0

Il dominio di ammissibilità è costituito dal segmento AD.

Il punto di ottimo con la funzione obiettivo lineare z_1 è il punto D.

Il punto di ottimo con funzione obiettivo non lineare z_2 è il punto E.


Problema di allocazione con 2 attività e 3 unità di risorsa

È possibile discretizzare le variabili x1 e x2 e le relative funzioni di profitto. In tabella sono riportati i valori assunti da g1(x1) e g2(x2) con i valori discreti di x1 e x2 (vedi tabella in alto).

Il dominio di ammissibilità del problema di allocazione con variabili discrete si riduce ai punti A, B, C e D (vedi grafico in basso).


Grafo delle soluzioni del problema di allocazione con 2 attività

È possibile costruire il grafo delle soluzioni del problema di allocazione. I livelli corrispondono alle attività. Gli archi del primo livello corrispondono alle 4 possibili allocazioni di risorsa alla prima attività. Gli archi del secondo livello corrispondono alle 4 possibili allocazioni di risorsa alla seconda attività, tenendo conto delle allocazioni fatte nel primo livello. I percorsi tra o e d rappresentano le soluzioni del problema (x1 = 0, x2 = 3; x1 = 1, x2 = 2; x1 = 2, x2 = 1; x1 = 3, x2 = 0). Le soluzioni del problema espresse dal grafo così costruito corrispondono ai punti A, B, C, D in figura. Ad ogni percorso è associato un valore di profitto g1(x1) + g2(x2). La soluzione ottima corrisponde quindi al percorso di profitto massimo. A ciascuno stato di ciascun livello è possibile associare il valore massimo di utilità ottenibile per realizzare quello stato. Il percorso massimo, di valore 5, corrisponde alla soluzione x1 = 1, x2 = 2.

Grafo delle soluzioni del problema di allocazione con 2 attività


Problema di allocazione con 3 attività

Valori discreti delle 3 funzioni di utilità g1(x1), g2(x2), g3(x3) (vedi tabella in alto).

Il grafo delle soluzioni del problema di allocazione con 3 attività presenta 3 livelli. Nel primo livello gli archi corrispondono alle 4 possibili allocazioni di risorsa alla prima attività. Nel secondo livello da ciascun vertice partono tanti archi quante sono le allocazioni possibili a partire da quel vertice (vedi grafico in basso).


Tabella dei risultati dell’algoritmo di Programmazione Dinamica per il problema di allocazione con 3 attività


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion