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

Grafo della rete stradale

Rete stradale

Grafo della rete stradale

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

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.

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 (x₁ = 0, x² = 3; x₁ = 1, x₂ = 2; x₁ = 2, x₂ = 1; x₁ = 3, x₂ = 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 g₁(x₁) + g₂(x₂). 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 x₁ = 1, x₂ = 2.

Grafo delle soluzioni del problema di allocazione con 2 attività

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