Modelli e Algoritmi per la Logistica
Lezione – 3
Il Processo Decisionale
ANTONIO SASSANO
Università di Roma“La Sapienza”
Dipartimento di Informatica e Sistemistica
Roma, 25-11-01
Introduzione alla Logistica
• Introduzione alla Logistica
Lezione 1
• La Catena Logistica (“Supply Chain”)
• Rilevanza della Logistica
• Classificazione dei Sistemi Logistici
• Modello Decisionale Logistico
• Aree di Intervento della Logistica
Lezione 2
• Principali aree di intervento
• Problemi Logistici: Esempi
• Il Processo Decisionale
Lezione 3
• Definizione del modello matematico (PL, PL01,…)
• Generazione delle Soluzioni (Euristiche e Metodi Esatti)
• Valutazione delle Soluzioni (Simulazione e “Benchmarking”)
Problema di Decisione – Soluzioni
S = insieme delle possibili alternative in un problema di decisione
ESEMPI:
Scelta del modo di trasporto:
S ={Nave + Treno, Camion, Aereo+Treno}
Scelta del periodo di produzione:
S ={Gennaio, Febbraio+Marzo, Marzo+Aprile, Luglio+Agosto}
Scelta del cammino di costo minimo da s a t:
S ={Cammini da s a t}
Problema di Decisione – Funzione Obiettivo
S = insieme delle possibili alternative in un problema di decisione
f (x) : S
R = funzione obiettivo
ESEMPIO
Scelta del modo di trasporto:
S ={Nave + Treno, Camion, Aereo+Treno}
f(Nave+Treno) =150.000
f(Camion)
=121.000
f(Aereo+Treno)=180.000
Problema di Decisione – Modello di Ottimizzazione
Problema di Decisione:
min { f (x) : x S}
< TROVA LA SOLUZIONE DI COSTO MINIMO >
Soluzione ottima x*: f (x*) < f (x) per ogni xS
f (x*) = min { f (x) : x S}
x* = argmin { f (x) : x S}
ESEMPIO: Scelta del modo di trasporto:
S ={Nave + Treno, Camion, Aereo+Treno}
f(Nave+Treno) =150.000
f(Camion)
=121.000
f(Aereo+Treno)=180.000
f(x*)=121.000;
x*=Camion
Ottimizzazione Combinatoria
Problema di Decisione:
min { f (x) : x S}
CON |S| < ∞
L’insieme delle soluzioni ammissibili ha cardinalità finita
L’ottimo x* esiste sempre e puo’ essere individuato
con una enumerazione completa di S
• Tempi di calcolo inaccettabili
• Necessita’ di algoritmi sofisticati (esatti e approssimati)
Basati su
– Certificati di qualita’
– Metodologie generali di soluzione
Soluzioni e “Certificati”
xS soluzione ammissibile
f( x ) = z valore della soluzione
f(x*)= z* valore ottimo
Lower bound LB < z* = “certificato di qualità” per x :
Riduzione del “gap” :
z
z*
LB
1. Miglioramento del “lower bound”
“gap”
2. Miglioramento (riduzione) di
z
Tecniche di ricerca nell’insieme delle soluzioni
Tecniche euristiche (euriskein=trovare)
- Algoritmo Avido (“Greedy”)
- Ricerca Locale (“Local Search”)
- Algoritmi Genetici
“Lower Bounds”
Metodi per il calcolo dei “Lower Bounds”:
• Rilassamento Lineare
• Rilassamento Lagrangiano
• Programmazione Semi-Definita
• Metodi combinatorici e “ad hoc”
• Formulazione Lineare
• Teoria della Dualità
Esempio: Problema di Decisione
DATI
• Due progetti A e B
• Vantaggi cA e cB associati
• Risorse necessarie dA e dB
• Vincolo di “budget” : dA + dB < D
DETERMINARE
Quali progetti realizzare per massimizzare il
vantaggio rispettando il vincolo di “budget”
Se dA =5, dB =7 e D=10
Soluzioni ammissibili: S={{A},{B}, }
Utilizzando i vettori di incidenza
max cA xA + cB xB
 1   0   0  
xS =  ,  ,   
  0  1   0  
Problemi di OC con funzione obiettivo lineare
• Insieme base G={1,2,…,n} (eventi elementari)
(es. progetto i attivato, nodo i scelto, connessione i stabilita)
• Costi (Vantaggi) elementari {ci associati agli elementi di G}
• Soluzione Ammissibile = Opportuno sottoinsieme F1 G
(es. sottoinsieme di progetti attivati che soddisfano il “budget”)
• Costo di una soluzione F1 = somma dei costi elementari
degli elementi di F1
c(F1 )=  ci
iF1
c1 1
• Insieme delle soluzioni ammissibili
S ={F1, F2, …,Fm}
Problema:
min {c(F): FS}
c2
F2
F1
3
2
cn n
F3
Problemi di PL01
• Insieme baseG={1,2,…,n} (eventi elementari)
• Soluzione ammissibile F={1,2,3,9}S
1 F
• Se rappresentiamo F con il suo vettore 1
 
di incidenza xF abbiamo:
1
xF= 0
0 
 
0 
0 
 
0 
1
 
E quindi:
S = {vettori di incidenza degli insiemi FS}
1
9
5
3
4
2
6
7
8
S
• PL01= Problemi di OC con funzione obiettivo lineare f(x)=cTx
min {c(F): FS}
=
min {cTx: xS  {0,1}n }
Approccio Modellistico
Definizione del Modello Matematico:
• Individuazione delle soluzioni ammissibili
• Codifica (= Creazione di S )
• Definizione della funzione obiettivo
Soluzione del problema:
• Definizione dei “lower bounds”
• Definizione dei meccanismi di enumerazione
• Realizzazione e test degli algoritmi
• Integrazione di strumenti standard
Verifica della Soluzione:
Verifica delle Soluzioni
Simulazione
- Verifica della soluzione in un ambiente ancora artificiale ma più realistico
- Rilassamento delle ipotesi modellistiche più restrittive
- Calcolo dettagliato di tutte le grandezze coinvolte
- Rappresentazione statistica e dinamica della “realtà”
“Benchmarking”
- Confronto input-output della soluzione con altre soluzioni “simili”
dominanza
“virtuale”
Metodologia DEA
“Data Envelopment Analysis”
Possibile
miglioramento
Frontiera efficiente
Finanziamento
(“input”)
dominanza
Risultato
(“output”)