I sistemi di supporto alle decisioni sono uno strumento indispensabile per la gestione di molti sistemi reali complessi. Tra questi assumono particolare ri- lievo i problemi di ottimizzazione su reti, quali quelle logistiche, generalmente assai complessi.
Un ulteriore aspetto da tenere in considerazione è relativo alla effettiva conoscenza dei parametri che caratterizzano il sistema: ci può essere infatti incertezza relativa all’effettivo valore assunto da alcuni di tali parametri a causa di accadimenti imprevisti, che possono alterare lo stato corrente del sistema, oppure per l’impossibilità di conoscere gli stati corrente e futuri.
A causa della complessità computazionale di molti problemi di ottimizza- zione e della limitata capacità risolutiva di molti sistemi di supporto, tuttavia, l’incertezza è stata a lungo trascurata o affrontata mediante il cosiddetto pro-
blema del valore atteso, in cui si assume che i parametri incerti del sistema si realizzino mediante il relativo valore atteso, nella speranza che il solutore fornisca una soluzione ragionevolmente buona nel caso medio.
Con l’incremento della potenza di calcolo, a seguito del progresso tecnologi- co, la comunità scientifica ha iniziato a includere esplicitamente l’incertezza nei modelli matematici, affrontandola per via algoritmica.
Le principali metodologie utilizzate (Pascali e Scutellà, 2009) –frutto di un attento bilanciamento tra il livello di robustezza (ovvero l’insieme degli scenari per i quali la soluzione determinata risulta ammissibile anche in segui- to al verificarsi di eventi incerti) e il costo computazionale di elaborazione– sono:
• la programmazione stocastica, in cui ad ogni parametro incerto (o ad ogni evento imprevisto) –anzichè un valore definito– viene associata un’opportuna distribuzione di probabilità;
• l’ottimizzazione robusta, con il fine ultimo di determinare una soluzio- ne ottima, tenendo in considerazione il verificarsi di un numero ben specificato di variazioni dei parametri incerti.
Relativamente al problema di Home Care, l’incertezza relativa ai para- metri del problema può riguardare, ad esempio, i tempi di viaggio. Tale incertezza può essere trattata definendo un insieme S di scenari possibili: si potrebbero considerare due scenari –mattino e pomeriggio–, che descrivono i tempi di percorrenza di ciascun arco della rete nelle ore mattutine (scenario mattino) e nelle ore pomeridiane – in cui si suppone la presenza di maggior traffico lungo l’infrastruttura (scenario pomeriggio).
In alternativa, impiegando la cosiddetta rappresentazione mediante inter- valli, è possibile assumere che il tempo di viaggio lungo ciascun arco – tij, ∀(i, j) ∈ A– appartenga ad un intervallo dato [t−ij, t
+ ij], ove t − ij e t + ij sono
rispettivamente il lower bound e l’upper bound per il valore assunto da tij.
Ancora, l’incertezza può essere rappresentata mediante poliedri: il vettore dei parametri incerti, α, può dunque variare all’interno di uno spazio definito da un poliedro della forma Q = {α : H · α ≤ g}, ove H è una matrice di vincoli e g il corrispondente vettore di termini noti.
Più formalmente, si denoti un generico problema di ottimizzazione con la notazione:
min{c(x) : x ∈ F } (2.1)
con F regione ammissibile del problema, su cui va minimizzata la funzione obiettivo c(x). Il problema 2.1 è definito problema nominale, mentre il pro- blema di ottimizzazione che determina soluzioni robuste viene indicato come la controparte robusta di 2.1.
Tale controparte robusta può essere definita in diversi modi, considerando per semplicità il caso in cui un solo parametro, sempre denotato mediante il simbolo α, sia affetto da incertezza, quali:
• Incertezza in senso assoluto, a livello di funzione obiettivo o a livello di regione ammissibile:
1. nel primo caso, dato S l’insieme dei possibili scenari del parame- tro incerto α, sia cs(x) il valore della funzione obiettivo per la soluzione x ∈ F , nel caso si realizzi lo scenario s ∈ S. Una solu- zione robusta può essere determinata con il criterio min − max, risolvendo il problema:
min{max{cs(x) : s ∈ S} : x ∈ F } (2.2) o, equivalentemente, introducendo una variabile ausiliaria m:
min{m : cs(x) ≤ m, s ∈ S, x ∈ F }. (2.3) 2. qualora il parametro α entri in gioco nella definizione della regio- ne ammissibile, la soluzione x∗ ∈ F∗ si determina risolvendo il
problema:
min{c(x) : x ∈ F∗} (2.4)
ove F∗ è l’insieme di tutte le soluzioni ammissibili per tutti gli scenari (F∗ = ∩s∈SF (s), con F (s) l’insieme delle soluzioni ammis-
sibili per lo scenario s).
• Incertezza in senso assoluto con parametro di controllo:
sia Γ un parametro intero non negativo, detto parametro di control- lo, utilizzato per segnalare che soltanto alcuni scenari sono meritevoli di attenzione. Infatti, si prendono in considerazione soltanto gli sce- nari in cui al più Γ componenti del parametro incerto α si discostano dal rispettivo valore nominale. Più formalmente, definito S(Γ) ⊆ S come il sottoinsieme di scenari individuati dal parametro di controllo Γ, la controparte robusta del problema è determinabile risolvendo il problema:
min{max{cs(x) : s ∈ S(Γ)} : x ∈ F }. (2.5) All’aumentare di Γ si registra un incremento del livello di robustezza; al contrario, con Γ = 0, si ignora ogni forma di incertezza attribuita al parametro, assumendo conseguentemente che ciascuna componente di α si verifichi secondo il proprio valore nominale.
• Incertezza in senso relativo: qualora si ritenga che gli approcci pre- cedenti siano eccessivamente conservativi, il criterio di robustezza in senso relativo definisce il problema robusto come:
min{max{(cs(x) − c∗(s) : s ∈ S} : x ∈ F } (2.6) ovvero, il massimo scostamento del costo di x rispetto al valore ottimo nello scenario considerato deve essere il minore possibile, al variare del parametro incerto α. c∗(s) denota il costo della soluzione ottima (di cui si assume l’esistenza) corrispondente allo scenario s.
Un importante contributo nell’ambito dello studio sulla robustezza, che discende dalle teorie proposte sin dai primi anni ’70, è offerto da Bertsimas e Sim (2004). Tali autori hanno infatti proposto l’approccio di ottimizzazione robusta con parametro di controllo, che sarà utilizzato anche in questo lavoro di tesi.