Dipartimento di Economia e Management
Corso di Laurea Magistrale in Banca, Finanza aziendale e Mercati
finanziari
Tesi di laurea
Analisi di un modello stocastico a due stadi: un trend risolutivo
per problemi di ottimo con caratteristiche aleatorie
CANDIDATO RELATORE
Miriana Colaianni
Prof. Riccardo Cambini
2
Indice
Introduzione ... 4
Capitolo I L’analisi delle decisioni in condizioni incerte e i relativi metodi di supporto ... 6
1.1 Decision making e incertezza: il caso della lotteria ... 6
1.1.1 Scenari di incertezza e di rischio nell’analisi decisionale ... 14
1.2 Programmazione matematica e ricerca dell’ottimo ... 16
1.2.1 Modelli quantitativi per il supporto alle decisioni ... 20
1.3 Fondamenti di programmazione lineare e non lineare ... 24
1.4 Programmazione deterministica ... 26
1.5 Programmazione stocastica ... 27
1.5.1 Un problema di pianificazione: the farmer’s problem ... 31
1.5.2 Programmazione stocastica a due stadi con ricorso ... 36
1.5.3 Trasformazione del modello a due stadi con ricorso nell’equivalente modello deterministico ... 37
1.5.4 Generazione di scenari ... 39
1.6 Logica e sistemi di ottimizzazione fuzzy ... 42
Capitolo II La logica fuzzy applicata al two-stage model: un nuovo trend di risoluzione per processi decisionali aleatori ... 52
2.1 Programmazione a due stadi: un esempio di modello versatile ... 52
3
2.3 Nel vivo dell’analisi: un nuovo modello a due stadi con contratti options e
futures ... 63
2.3.1 Il valore atteso del contratto di fornitura ... 64
2.3.2 Analisi e semplificazione del valore atteso del modello: da two-stage model a single stage model ... 66
2.3.3 Trasformazione del modello stocastico nel suo equivalente deterministico ... 69
2.4 Applicazione reale del modello: il caso del mercato cinse ... 76
Capitolo III Conclusioni ... 83
3.1 Influenza dei diversi tipi di distribuzione sulle decisioni economiche ... 83
3.2 Confronto con il modello di ottimizzazione stocastico ... 85
3.3 Distribuzione di possibilità, profitti medi e ordini: un nuovo piano strategico per il decisore ... 87
3.4 Distribuzioni di possibilità, profitti medi e ordini: un nuovo piano strategico per il decisore ... 88
3.5 Principali conclusioni del modello ... 90
Bibliografia ... 95
4
Introduzione
Lo scopo della programmazione stocastica è quello di individuare decisioni ottimali in problemi che coinvolgono dati incerti. Negli ultimi anni, la produzione scientifica in questo campo è stata davvero intensa, tanto da aver reso possibile uno sviluppo multidisciplinare affiancato da una potenza di calcolo sempre maggiore. Partendo dal modello proposto da Li, Liu e Chen (2018), si sono analizzati due importanti strumenti utili nei processi di ottimizzazione stocastica, ovvero il modello a due stadi e la logica fuzzy.
Prima di entrare nel cuore dell’indagine, il lavoro ha seguito una ben definita impostazione logica per fornire concetti di base validi per la comprensione del modello presentato. Il Capitolo I inquadra il processo decisionale in condizioni rischiose o incerte. Molto spesso, la scelta di intraprendere un’azione tra più alternative o opzioni da parte di un individuo, ha un’evoluzione complessa e poco prevedibile; non a caso Ippocrate scriveva che “se la decisione è necessaria, l’errore è probabile”. L’iter decisionale che si presenta ad un agente che non conosce i risvolti futuri delle proprie scelte, viene descritto tramite il tipico esempio della lotteria. Un altro aspetto che caratterizza il processo di decision making è il problema della ricerca dell’ottimo, ossia della soluzione che garantisce al decisore il miglior soddisfacimento delle sue esigenze. L’ottimizzazione può avere diversi livelli di complessità: più il problema da risolvere è ostico e difficoltoso, più saranno complessi i metodi quantitativi utilizzati per ricercare il punto di ottimo. Data la vastità dei problemi che il decisore è chiamato a risolvere, svariati saranno i modelli che potrà usare; il caso oggetto di studio spazia da modelli lineari e non lineari, a modelli deterministici e stocastici, alla logica fuzzy, con particolare attenzione ai modelli a due stadi con ricorso, di cui saranno spiegati i principi teorici e le modalità di implementazione. Con questi modelli, viene fornito un supporto razionale alle decisioni complesse e l’incertezza viene affrontata in modo esplicito.
5
Il Capitolo II si concentra sull’analisi del case study “Modeling a two-stage
supply contract problem in a hybrid uncertain enviroment”: un rivenditore di gas
naturale nel mercato cinese è incaricato di acquistare la giusta quantità di sostanza gassosa da rivendere ai suoi clienti nel periodo invernale. Il punto critico di tutta l’analisi è che la funzione di domanda non è nota. Il venditore dovrà, dunque, prendere le sue decisioni non conoscendo questo dato fondamentale. L’ausilio fornito dal modello a due stadi ci permette di scomporre il problema in due fasi: nella prima fase, la società incaricata di distribuire il gas sottoscriverà dei contratti derivati per cautelarsi dal rischio derivante dalla funzione di domanda non nota, nella seconda fase i derivati sottoscritti verranno effettivamente esercitati, dopo aver conosciuto il dato incognito. In questo modo, il rivenditore potrà massimizzare i suoi profitti. Per determinare l’ammontare di questi ultimi appunto, sarà illustrato un processo che consente la semplificazione del modello a due stadi con ricorso in un equivalente e più agevole modello deterministico, attraverso l’applicazione di un modello dall’impostazione fuzzy. Attraverso la formulazione di quattro ipotesi differenti, si dimostra come l’aggiunta della componente “sfocata” al modello stocastico a due stadi consenta di raggiungere dei risultati altamente attendibili, coerenti e fedeli alla realtà. Il Capitolo III andrà a raccogliere le conclusioni dell’analisi, confermando sia la flessibilità dei sistemi a logica “sfumata”, sia l’originalità e l’innovazione del nuovo modello stocastico-fuzzy in grado di superare il convenzionale modello aleatorio in circostanze rette da incertezza.
6
CAPITOLO I
L’analisi delle decisioni in condizioni incerte e i relativi metodi di
supporto
L’obiettivo del presente Capitolo è quello di introdurre il lettore al problema dell’analisi decisionale sotto condizioni incerte, richiamando le principali nozioni che fanno da sfondo alla tematica. Per prima cosa, si chiarirà il concetto di decisione aleatoria, attraverso il classico esempio della lotteria. In seguito, verrà proposto il problema dell’ottimizzazione di questa difficile categoria di scelte, campo di indagine in cui la Ricerca Operativa ha registrato numerosi progressi. Interessanti e utili per il prosieguo della trattazione, saranno gli approfondimenti a proposito della programmazione lineare, non lineare, deterministica e stocastica, con un’attenzione particolare per il modello a due stadi e la logica fuzzy.
1.1 Decision making e incertezza: il caso della lotteria
Il processo decisionale, che spesso si caratterizza come arduo e complesso, è stato fulcro di numerosi studi appartenenti a diverse discipline. Ciò che ha, da sempre, attirato l’interesse di studiosi ed esperti, è stata la natura incerta e poco sicura che specifiche tipologie di scelte sembrano aver connaturate dentro di sé. Il rischio, ma in particolar modo l’incertezza, sono elementi che inquadrano qualsiasi problema di scelta o di decisione. È chiaro che un soggetto chiamato a scegliere tra più proposte, offerte o possibilità, dichiara di preferirne una, ritenendola la migliore, la più adatta o la più conveniente, secondo criteri oggettivi o meramente soggettivi.
7
Quando vi è un’informazione perfetta, e quindi una perfetta conoscenza del futuro, il decisore è in grado di compiere delle valutazioni in maniera del tutto consapevole. Essendo noti a priori gli effetti di quella determinata scelta, non esiste incertezza. Molto più spesso, l’agente non conosce ex ante gli effetti della sua decisione, poiché essa è influenzata da una serie di fattori esterni che lui stesso non è in grado di governare. Più il futuro di una decisione è incerto, più alto sarà il rischio associato ad essa. Ad esempio, la scelta di investire una determinata quantità di capitale in azioni è una scelta operata in condizioni di incertezza, perché l’investitore non conoscerà mai a priori l’andamento del mercato finanziario. L’accurato processo di decisione deve tener conto, pertanto, dell’esistenza di un determinato livello di incertezza in grado di condizionare o influenzare le scelte, rendendo il risultato finale dell’evento del tutto aleatorio: per questo prendere una decisione in condizioni non certe si dimostra un processo alquanto complesso, incentrato sulla realizzazione di previsioni attendibili circa quello che potrà accadere in futuro.
Un classico esempio che consente di analizzare le decisioni dei soggetti in condizioni incerte è quello della lotteria. Supponiamo che un soggetto debba scegliere tra una serie di lotterie con caratteristiche diverse, come ad esempio, i premi messi in palio. L’insieme di scelta del decisore quindi, è rappresentato dalle lotterie disponibili e l’informazione consiste nella conoscenza degli elementi distintivi di ciascuna lotteria. I possibili risultati associati al gioco sono rappresentati sotto forma di variabili casuali. Una variabile casuale, detta anche variabile aleatoria o stocastica, è una variabile che può assumere valori diversi e ciascuno di essi si può verificare con una certa probabilità. Ad esempio, il lancio di una moneta è una variabile casuale che può assumere il valore “testa” o il valore “croce”, entrambi con probabilità .L’insieme dei possibili risultati associati ad una lotteria è dato dal vettore , dove sta ad indicare i possibili risultati associati ad una qualsiasi lotteria appartenente all’insieme di scelta del decisore. Il soggetto conosce, inoltre, le probabilità con cui ogni risultato può realizzarsi in concreto, ovvero il vettore Data la lotteria , essa può essere formalizzata come:
8
dove è un generico risultato possibile a cui viene associata la probabilità di accadimento , con e . In sostanza, la lotteria riassume l’insieme dei risultati e delle probabilità secondo cui essi si realizzano. Il problema di scelta del decisore si articola nel determinare quale lotteria soddisfa nel modo migliore le sue preferenze. Un metodo mirato ad assistere il soggetto nella sua decisione, affinché quest’ultimo raggiunga la massima soddisfazione senza affidare al caso gli esiti della sua scelta, è il calcolo del valore atteso , cioè la somma dei possibili valori di una variabile casuale ciascuno moltiplicato per la probabilità di essere assunto. In altre parole, si procede al calcolo della media ponderata dei possibili risultati:
Sempre in riferimento alle lotterie, se il valore atteso costituisce un valido metodo per ordinare i giochi in base all’aspettativa di vincita, è ovvio che il decisore concentrerà la sua attenzione su quelli con un’aspettativa di vincita più alta.
Nelle scelte del decisore non conta solamente il valore atteso, ossia la media ponderata delle vincite in base alle rispettive probabilità; si deve tener conto anche di come è fatta la funzione di utilità del decisore. Nel processo di decision making, un ruolo fondamentale è giocato dal fattore rischio, o meglio dall’atteggiamento che ogni soggetto adotta nei confronti del rischio. Alcune persone infatti, potrebbero essere molto caute e preferire un rischio limitato, altre invece potrebbero amare l’azzardo. Di fronte a prospettive indeterminate quindi, i soggetti potrebbero manifestare una maggiore o minore propensione al rischio. Quando, di fronte a numerose alternative, un agente prende consapevolmente la propria decisione, questo procedimento non tiene conto solamente delle ‘quantità’ di beni o denaro, ad esempio, di cui poi l’individuo potrà godere in futuro. Ciò che rileva è il grado di benessere o di soddisfazione che egli ottiene da ciò di cui dispone. Entra in gioco il concetto di utilità attesa , cioè quella particolare teoria che assegna valori numerici di soddisfazione alle diverse possibili conseguenze delle scelte effettuate, conseguenze che poi vengono pesate con le probabilità di accadimento, come stimato dall’agente. Formalmente si ha:
9
dove è la funzione che associa un dato livello di utilità al generico ammontare di denaro ottenuto con certezza. La teoria dell’utilità attesa, elaborata nel 1944 da von Neumann-Morgenstern, poggia su determinati assiomi che costituiscono il filo logico che va a determinare ogni processo decisionale:
Comparabilità, i decisori sono in grado di confrontare e ordinare le alternative secondo un proprio ordine di preferenza,
Transitività, se un agente preferisce ad e a , allora preferirà a ,
Indipendenza forte, nel confronto fra due alternative i decisori si concentrano sui risultati che non sono comuni,
Misurabilità, per ogni alternativa è possibile stabilire un solo risultato equivalente certo compreso fra i risultati estremi,
Ordinabilità, a parità di risultato i soggetti preferiscono l’alternativa con maggiore probabilità.
Tale teoria rappresenta il modello più largamente applicato in economia per spiegare le preferenze di individui razionali1 in contesti dominati dall’incertezza. Nel caso di una lotteria, i diversi risultati possibili sono premi o, più in generale, somme di denaro. Tramite la funzione di utilità attesa, alla variabile indipendente, rappresentante le somme monetarie che potrebbero essere vinte, corrisponde un certo livello di soddisfazione. Il grado di soddisfazione è, dunque, la variabile dipendente. È chiaro che la relazione tra variabile indipendente e variabile dipendente è una relazione crescente: al crescere della somma monetaria cresce l’utilità del decisore ottenuta dalla vincita. Definita la funzione di utilità attesa, l’analisi si arricchisce di due nuovi elementi: l’equivalente certo e il premio per il rischio. L’equivalente certo di una lotteria è quel risultato che, se ottenuto con certezza, offre al decisore un’utilità pari all’utilità attesa di , ovvero . In altre parole, non è altro che l’ammontare sicuro che l’individuo considera equivalente al guadagno in condizioni aleatorie. Il premio per il rischio invece, è la somma massima che un decisore sarebbe disposto a pagare per non partecipare alla lotteria rischiosa e ottenere con certezza il valore medio della stessa. È la differenza tra il valore atteso del gioco e l’equivalente certo che un
1
10
individuo sarebbe disposto ad accettare pur di non sopportare l’aleatorietà della lotteria, .
La trattazione ora, passa ad esaminare le diversità del processo di scelta in base al grado di tolleranza al rischio mostrato dai decisori.
Un agente avverso al rischio, di fronte a due lotterie che hanno uguale valore atteso in termini di vincita, sceglie sempre quella caratterizzata da minore rischio. Immaginiamo come esempio di riferimento la seguente lotteria , con il risultato finale superiore al risultato finale ossia .Viene indicato con il valore atteso della lotteria per cui .
Figura 1.1: Avversione al rischio. Fonte: Fiaschi, Meccheri (2014).
Sull’asse delle ordinate, e rappresentano l’utilità del decisore qualora disponesse con certezza dei premi e della lotteria. , che sarebbe l’equivalente di rappresenta l’utilità del soggetto nel caso in cui quest’ultimo ottenesse una somma monetaria certa pari esattamente al valore atteso della lotteria , Sull’asse delle ascisse, dove viene rappresentato il valore atteso delle somme monetarie vinte, sarà compreso tra e , essendo la media ponderata di queste due variabili estreme. Per calcolare l’utilità attesa , ossia la media ponderata delle utilità dei risultati di azioni scelte dall’agente stesso, utilizzando come pesi le
11
probabilità del verificarsi delle singole azioni, si procede nel seguente modo: i livelli di utilità e , contrassegnati rispettivamente dalle lettere a e c, vengono uniti da un segmento. Su questo segmento, il punto d, tracciato sull’asse delle ascisse in corrispondenza dell’utilità del decisore nel caso in cui egli riceva una somma di denaro certa pari al valore atteso della lotteria, indicata con b, rappresenta l’utilità attesa che un individuo avverso al rischio attribuisce alla lotteria Come si evince dal grafico, l’utilità attesa della lotteria è inferiore a . L’utilità attesa che un soggetto avverso al rischio ottiene partecipando ad una lotteria con valore atteso è più bassa dell’utilità derivante dal poter usufruire con certezza di una somma di denaro pari al valore atteso della lotteria stessa, rappresentata dal punto b. Essendo il decisore avverso al rischio, il suo grado di soddisfazione aumenta quanto più certa è la somma di denaro di cui potrà godere in futuro; perciò è normale che per un individuo non propenso al rischio l’utilizzo di una quantità certa di denaro garantirà un livello di soddisfacimento maggiore rispetto alla partecipazione ad una lotteria che ha come risultato la stessa somma di denaro, ma che comunque comporta il dover sopportare un certo livello di aleatorietà. Il risultato è la creazione di una funzione del decisore concava. Sull’asse delle ascisse l’equivalente certo , ossia la somma certa che garantisce un livello di utilità sull’asse delle ordinate per cui , è inferiore al valore atteso della lotteria , Per questo motivo il premio per il rischio , ovvero , è positivo: il decisore avverso al rischio è disposto ad ‘assicurarsi’ pur di ottenere con certezza il valore medio della lotteria e pur di non partecipare all’evento aleatorio.
Consideriamo ora la stessa lotteria del caso precedente, questa volta con un soggetto neutrale al rischio. La funzione se per il soggetto avverso al rischio si configurava come concava, in questo caso è lineare: ciò significa che per il soggetto neutrale al rischio è indifferente ricevere una somma certa o prendere parte al gioco il cui risultato atteso è ; quindi l’equivalente certo della lotteria sarà esattamente uguale al suo valore atteso, . Il premio per il rischio sarà nullo. Come si evince dalla rappresentazione grafica del punto b, per un decisore neutrale rispetto al rischio l’utilità derivante dal ricevere una somma monetaria certa è
12
esattamente uguale all’utilità che fornisce la partecipazione ad una lotteria questo agente sarà indifferente tra ricevere un montante certo di denaro o partecipare ad una lotteria il cui valore atteso è pari al valore della somma di denaro che potrebbe ricevere con certezza, per cui .
L’ultimo caso da considerare è quello di un agente amante del rischio. In questa ipotesi la funzione sarà convessa; l’esatto contrario del caso di avversione al rischio dove la funzione si configura come concava.
Figura 1.2: Neutralità al rischio. Fonte: Fiaschi, Meccheri (2014).
La propensione al rischio di certi soggetti, li spinge a giocare con l’obiettivo di vincere una somma elevata piuttosto che accontentarsi di una somma certa dall’ammontare intermedio, né troppo basso, né troppo alto. Ovviamente, in circostanze molto rischiose, la possibilità di ottenere una vincita molto alta è controbilanciata dalla simmetrica possibilità di ricevere una vincita molto bassa o di incorrere addirittura in una perdita.
Un decisore che si definisce propenso al rischio, da un risultato certo ottiene un’utilità inferiore rispetto all’utilità attesa derivante da una lotteria con lo stesso valore atteso del risultato certo, . Come dimostrato dalla posizione del punto b, il decisore amante del rischio non ha alcun interesse, in termini di utilità, ad incassare una quantità certa di denaro: l’utilità del risultato certo non gli
13
garantisce il livello di soddisfazione che può raggiungere partecipando ad una lotteria rischiosa.
L’utilità attesa del gioco avente lo stesso valore atteso della cifra monetaria certa, è di gran lunga superiore all’utilità attesa derivante da quest’ultima. Qui l’equivalente certo, pari all’utilità attesa della lotteria, è maggiore del valore atteso del gioco aleatorio .
Inoltre il premio per il rischio risulta negativo: il decisore, propenso a commettere l’azzardo, non vorrà pagare alcuna somma per eliminare il rischio associato
Figura 1.3: Propensione al rischio. Fonte: Fiaschi, Meccheri (2014).
alla lotteria ; anzi è come se stesse chiedendo di essere pagato per privarsi dell’aleatorietà insita nel gioco.
A questo punto, l’analisi delle decisioni sotto incertezza ha definito gli elementi essenziali del problema: l’insieme delle varie scelte a disposizione del decisore, le eterogenee conseguenze delle decisioni intraprese secondo il set informativo che dispone l’agente e l’utilità attesa di ogni scelta, costituiscono l’apparato imprescindibile su cui si struttura il processo di decision making in condizioni incerte.
14
1.1.1 Scenari di incertezza e di rischio nell’analisi decisionale
Il processo decisionale è un insieme di atti consci e irrevocabili di allocazione delle risorse, finalizzato al raggiungimento di determinati obiettivi. Ricercare e formalizzare la soluzione dei problemi decisionali ha dato un forte impulso allo sviluppo di modelli efficaci per aiutare gli agenti a compiere scelte in situazioni dall’elevata complessità e aleatorietà. Questi modelli di supporto hanno l’obiettivo di evitare, o almeno minimizzare, il compimento di gravi errori di valutazione, tramite il confronto di situazioni e risultati ottenuti dai vari modelli.
L’analisi decisionale in condizioni di incertezza si compone dei seguenti elementi:
, l’insieme delle scelte o delle alternative possibili,
, l’insieme degli stati di natura, ossia le realizzazioni o gli scenari in cui un evento futuro si trova ad impattare, che non dipendono né dalle azioni né dalla volontà dei decisori. Per questi motivi, gli stati di natura delle possibili alternative non sono del tutto noti a priori,
, le probabilità riferite al verificarsi dei vari stati di natura,
, il guadagno, o la perdita, stimato in relazione alla combinazione scelta-stato di natura
Stabilite le variabili interessate nel processo di decision making, quest’ultimo può essere scomposto in quattro fasi:
1. Individuazione delle scelte o delle alternative possibili che si presentano al decisore,
2. Individuazione degli stati di natura, ossia degli scenari, o degli eventi futuri, che possono condizionare i risultati delle singole decisioni,
3. Stima del guadagno o della perdita riportata. Ad ogni combinazione decisione-stato di natura viene associata una stima del guadagno, o della perdita, ad essa riferita Questa espressione non è altro che la misura del valore della scelta in seguito al verificarsi dello stato di natura
15
4. Valutazione e confronto dei risultati delle diverse alternative. In quest’ultima fase risulterà fondamentale mettere in pratica il principio di dominanza secondo cui “l’alternativa è dominata se esiste un’alternativa , con q ≠ p, tale che
con disuguaglianza stretta almeno in corrispondenza di
uno stato di natura. Una alternativa si dirà ammissibile se non è dominata da nessun’altra alternativa”.2
In sostanza, tale principio afferma la possibilità di escludere dalla valutazione le alternative con implicazioni peggiori rispetto ad una qualsiasi altra alternativa.
Esistono diversi possibili scenari in cui il decisore è chiamato ad operare le proprie scelte aleatorie; tuttavia ne verranno analizzati principalmente due dal momento che questi sono gli stati di natura, o realizzazioni, che hanno interessato il modello di programmazione proposto nei capitoli successivi.
Il primo scenario decisionale analizzato si incentra sull’incertezza, ossia quando, nelle analisi delle decisioni, gli agenti non conoscono le probabilità degli stati di natura futuri e le valutazioni circa le diverse alternative possibili vengono effettuate non avendo a disposizione alcun tipo di informazione e non tenendo in considerazione parametri di natura probabilistica.
Nell’analisi decisionale in condizioni di rischio invece, gli agenti conoscono, o
meglio stimano, le probabilità di accadimento degli stati di natura futuri Le probabilità vengono determinate sulla base di valutazioni
soggettive oppure su esperienze simili registrate in passato; questo processo viene detto probabilità a priori, ossia la misura soggettiva sulla verosimiglianza che un certo evento ha di verificarsi. Spesso però, accade che le stime iniziali vengano modificate e, conseguentemente migliorate, ottenendo le cosiddette probabilità a posteriori, misure del livello di verosimiglianza relativo al verificarsi di un certo evento. Gli stati di natura sono esaustivi e mutualmente esclusivi, quindi le probabilità degli stati di natura futuri soddisfano le seguenti relazioni:
16
1.2 Programmazione matematica e ricerca dell’ottimo
La lista delle situazioni in cui gli agenti devono prendere delle decisioni è davvero estesa. Appurato che ogni soggetto segue dei precisi criteri per compiere la scelta da lui considerata migliore, il processo decisionale potrebbe essere definito come un vero e proprio problema di ottimizzazione. Quest’ultimo non è altro che un problema di programmazione matematica in cui alcuni vincoli sono espressi mediante funzioni. Il problema relativo alla scelta dell’alternativa migliore tra quelle disponibili, si compone di tre elementi:
Variabili decisionali, cioè le variabili tramite cui determinare il valore ottimo,
Funzione obiettivo, o funzione target, una specifica funzione che mette in relazione le variabili decisionali con altre variabili il cui valore debba essere massimizzato o minimizzato,
Insieme ammissibile, ovvero le alternative disponibili per il decisore tra cui questo dovrà effettuare la scelta. Tali alternative dovranno rispettare una serie di restrizioni, i cosiddetti vincoli, che vanno a delineare lo spazio delle soluzioni ammesse.
Quindi, in ogni problema decisionale, ci sarà un set di alternative che verrà attentamente valutato da ciascun agente in base a determinati parametri. Questi poi, stilano una sorta di classifica delle alternative, formalizzata matematicamente con la seguente funzione a valori reali, detta anche funzione obiettivo , dove una alternativa caratterizzata da un valore più elevato è ovviamente preferita ad una con un valore più basso. L’obiettivo del decisore sarà quello di scegliere, dal gruppo di alternative , quella in grado di massimizzare o minimizzare il valore della funzione obiettivo , in modo che si venga a costituire il vettore delle variabili di decisione . Conviene osservare che un problema di massimo può sempre essere ricondotto ad un problema di minimo cambiando il segno della funzione obiettivo. I punti di massimo di , con , coincidono con i punti di minimo di , con . Da ciò risulta che con .
17
L’ottimizzazione può essere generalmente riassunta come segue: massimizzare
tale che
A seconda delle proprietà della funzione e del choice set si otterranno diverse tipologie di ottimizzazione: ottimizzazione lineare, ottimizzazione non lineare, ottimizzazione vincolata, ottimizzazione non vincolata.
Qualsiasi scelta ideale che renda il valore massimo della funzione obiettivo è nota come punto di ottimo di all’interno del choice set . Il punto di ottimo altro non è che il punto in cui la funzione cambia il suo andamento e si ottiene calcolando la derivata della funzione stessa. La derivata di una funzione nel punto c è il limite (se esso esiste):
Figura 1.4: Funzioni aventi rispettivamente il punto di massimo e il punto di minimo in c. Fonte: Aliprantis, Chakrabarti (2000).
Se la funzione è derivabile proprio nel punto c, allora essa si dice differenziabile. La derivata rappresenta il momento in cui cambia il suo trend, nel punto c, relativamente ai cambiamenti di . In questo caso il punto c è detto punto critico della funzione se la sua derivata assume valore zero in c.
Per capire in concreto in cosa consiste il problema dell’ottimizzazione, verrà illustrato un esempio pratico.
Un soggetto ha a disposizione un budget di 12 Euro con cui desidera acquistare mele e arance. Le mele e le arance hanno un costo rispettivo di 1 Euro e 2 Euro al chilo.
18
Vincolato dalla somma di partenza di cui dispone, il soggetto in esame vorrebbe sia comprare la quantità massima di prodotti, sia acquistare quella determinata combinazione che gli consenta di ottenere la massima soddisfazione.
A questo punto, entra in gioco la funzione di utilità del soggetto, dove le due variabili rappresentano la quantità di mele e arance che può comprare il consumatore. Dai dati forniti riguardo il costo dei due prodotti, la linea di budget sarà ed è fondamentale nella soluzione del problema di ottimizzazione. Infatti si ottiene:
Per ricercare il punto di ottimo occorre soddisfare la cosiddetta condizione del primo ordine, ossia calcolare la funzione derivata della funzione obiettivo.
Dopo aver calcolato la quantità di arance da acquistare, è intuibile come la quantità ideale di mele sarà La combinazione è il punto di ottimo in grado di massimizzare la funzione di utilità , rispettando il set di scelta tra mele e arance.
Figura 1.5: Soluzione di ottimo.
Fonte: Aliprantis, Chakrabarti (2000).
Nella vita di tutti i giorni, l’idea di ottimizzare è molto più diffusa di quanto ci si possa aspettare ed è insita non solo nel comportamento umano, ma anche nel sistema naturale. Viene illustrato ora uno degli innumerevoli e più antichi problemi di ottimizzazione risalente ad un’epoca molto lontana: come raccontato nell’Eneide, Didone, per la fondazione di Cartagine, chiese a re Iarba un pezzo di terra per costruire la sua nuova città. Il re, in tutta risposta, le consegnò una pelle di toro, dicendo alla regina che poteva colonizzare tanto terreno quanto poteva contenerne il pezzo di pelle. Didone
19
astutamente, tagliò la pelle in tante striscioline e ne fabbricò una corda con cui delimitò una vasta zona su cui edificare la cittadina. Sebbene si tratti solamente di una leggenda, si capisce come il raggiungimento del risultato più vantaggioso possibile guida l’uomo e tutto ciò che lo circonda. L’intento di ogni agente razionale è quello di cercare di ottenere il miglior risultato con il minimo sforzo, impiegando il meno tempo possibile e sfruttando in modo ottimale le risorse che esso ha a disposizione. Quando pensiamo al miglior percorso da fare per recarci a lavoro, oppure quando andiamo a fare la spesa minimizzando il tempo impiegato e non superando la somma di denaro che possiamo agevolmente spendere, questi sono tutti esempi di problemi di ricerca dell’ottimo legati alla vita quotidiana, che per la loro effettiva semplicità, non hanno bisogno di strumenti matematici per essere risolti.
Altri sistemi reali, per la loro complessità, richiedono appropriate tecniche per essere progettati e coordinati efficacemente. Perciò, è indispensabile l’adozione di modelli di calcolo per risolvere problemi di ottimizzazione e per assicurare l’affidabilità delle operazioni in corso. Ad esempio, modelli matematici chiamati modelli di settorizzazione, sono molto utilizzati per la pianificazione dello spazio aereo. Analizzare la distribuzione delle rotte, con i rispettivi punti di conflitto, e studiare il carico di lavoro sopportato, aiuta a massimizzare la sicurezza delle operazioni di volo. Nella pianificazione e nel monitoraggio dei servizi di distribuzione merci, l’impiego di tali modelli consente una razionalizzazione dei costi di trasporto con un forte impatto positivo, in termini di risparmio, sia sul processo produttivo che sul processo di commercializzazione. Anche le reti di trasporto e le reti di comunicazione necessitano di sistemi di supporto alle decisioni imperniati su modelli matematici, la cui risoluzione è affidata a software informatici. Questi modelli assistono tutte le fasi del ciclo di vita del sistema, dalle operazioni più semplici a quelle più critiche, per far in modo che vengano prese le decisioni più convenienti. La complessità del fenomeno decisionale sta nel fatto che alcune scelte devono essere prese sotto condizioni incerte: può essere sconosciuto lo stato attuale del sistema, non si riescono a focalizzare con precisione gli eventuali imprevisti che potrebbero insorgere oppure non si riescono ad effettuare delle stime realistiche sull’andamento futuro del sistema stesso. Comunque, anche nel caso in cui si disponesse di una perfetta informazione e in assenza di imprevisti, risolvere
20
determinate problematiche potrebbe essere davvero critico, data la loro elevata difficoltà computazionale e la loro elevata dimensione.
Se molti aspetti dei problemi legati alla vita reale sono dominati dal fattore incertezza, ciò è particolarmente tangibile riguardo il funzionamento delle reti, come evidenziato poc’anzi. Il quotidiano utilizzo della rete elettrica, della rete idrica, della rete di trasporto e di quella delle telecomunicazioni è importante per capire il motivo principale per cui questi sistemi devono garantire il loro completo svolgimento, senza alcun tipo di interruzione o malfunzionamento. Le reti elettriche sono soggette a continue variazioni della produzione e della domanda del dispatching energetico e, eventualmente, anche a fenomeni catastrofici, quali la rottura di mezzi di trasmissione o la rottura degli impianti. Le reti di trasporto, frequentemente, sono esposte a ritardi a causa di imprevisti di varia natura (condizioni meteorologiche, scioperi, congestioni, guasti, errori umani). Le reti di telecomunicazione e le reti idriche non sono immuni da variazioni e danneggiamenti, molto difficili da predire con accuratezza. Da questa panoramica, si evince come i problemi di ottimizzazione, oltre ad essere legati a fattori dall’elevata incertezza, siano anche situazioni estremamente complesse da analizzare e risolvere. Nella pratica, l’incertezza viene affrontata con le cosiddette azioni di recupero, azioni in grado di modificare e correggere la soluzione precedentemente pianificata, in modo tale che essa rimanga sempre ammissibile. Nell’ambito delle reti, queste azioni devono essere eseguite in pochissimo tempo e sono estremamente dispendiose.
Se inizialmente l’incertezza veniva affrontata solo mediante azioni di recupero, col passare del tempo, è nata l’esigenza di poter disporre di mezzi più adatti e calibrati a superare ostacoli di questo genere.
1.2.1 Modelli quantitativi per il supporto alle decisioni
Se, da un lato, il futuro non può esser previsto perfettamente e con sicurezza, dall’altro, strumenti quali la statistica e la distribuzione di probabilità riescono a ben gestire l’incertezza e la casualità degli eventi. Per controllare la componente incerta dei processi di decision making più articolati e complessi, sono stati messi a punto
21
molteplici strumenti di supporto, diversi tra loro. La loro diversità dipende dal fatto che nella pianificazione delle attività decisionali, è necessario operare le scelte migliori per raggiungere un determinato obiettivo, rispettando i vincoli imposti dall'esterno, che non sono sotto il controllo dei decisori. Una volta che il processo decisionale è stato razionalmente studiato e analizzato, la sua complessità fa sì che venga richiesta l’implementazione e lo sviluppo di modelli matematici e informatici strutturati ad hoc per la situazione decisionale in esame, con lo scopo di prevederne i risultati e migliorarne le prestazioni. L’ottimizzazione avviene proprio grazie l’utilizzo di questi comprovati processi matematici e scientifici.
I metodi quantitativi dell’analisi decisionale utilizzati per risolvere ed ottimizzare questi modelli, sono in continua evoluzione. I momenti cruciali di questo processo matematico-decisionale sono principalmente due: la scelta e l’elaborazione del modello matematico da applicare al problema e la progettazione dell’algoritmo risolutivo, come verrà mostrato successivamente. L’algoritmo di ottimizzazione è un generatore di nuovi scenari, che dovranno poi essere verificati, sulla base degli scenari già testati in precedenza. In più, hanno un grosso ed importante impatto, specialmente sull’organizzazione e sulla gestione delle realtà aziendali: essi fanno sì che le ostiche
challenges che le organizzazioni sono chiamate ad affrontare giornalmente, vengano
trasformate in vere e proprie opportunità grazie alla conversione dei dati in informazioni, e delle informazioni in ‘intuizioni’ in grado di annullare imprevisti e consentire di risparmiare risorse economiche. I loro ambiti di applicazione sono davvero disparati: spaziano dalla selezione degli investimenti e dalle scelte di portafoglio, alla gestione ottima delle scorte; dalla produzione industriale e dalle telecomunicazioni, al dimensionamento di impianti; fino ad arrivare alla manutenzione di beni, all’instradamento dei veicoli e addirittura, alla conduzione di studi sulla struttura del DNA. Dunque, si può giustamente affermare che gli strumenti tecnici a sostegno del processo decisionale offrono un contributo interdisciplinare, applicabile in svariati contesti, anche molto distanti tra di loro; proprio da questo principio cardine, tali metodi derivano la ragione della loro attuale vitalità.
Qualunque sia la sua natura, un problema di ottimizzazione è suddiviso in una serie di passaggi obbligati:
22 Individuazione e analisi del problema da risolvere e raccolta di tutte le variabili
coinvolte,
Costruzione del modello matematico che racchiude le caratteristiche salienti del problema reale in termini numerici. Quest’ultimo, con tutte le sue variabili, viene trasformato in una funzione obiettivo, che verrà poi assoggettata a dei vincoli definendo il cosiddetto insieme ammissibile,
Analisi del modello matematico e ricerca della soluzione ottimale, ossia la soluzione in grado di massimizzare (o minimizzare) la funzione obiettivo,
Verifica e applicazione della soluzione.
Le fasi di cui sopra non devono essere eseguite pedissequamente in sequenza, anzi. Molto spesso sono da prevedere dei feedback, per cui i risultati di una fase prevedono un aggiornamento e una modifica delle fasi precedenti. Affrontare e risolvere un problema seguendo i criteri appena esposti può essere un percorso alquanto arduo: non è detto che il modello sia sufficiente e sempre adeguato a descrivere il funzionamento reale di un sistema, o che sia sempre possibile individuare la soluzione ottima. I modelli infatti, di qualunque tipo essi siano, sono un’astrazione della realtà e potrebbero non riprodurre tutti i dettagli necessari ad affrontare la questione: la soluzione finale è la soluzione del modello stesso, ossia di come è stato costruito, studiato e rappresentato il vero caso reale. È bene dunque, prestare grande attenzione alla fondatezza del modello, che sarà sempre una descrizione limitata del fenomeno osservato. Più il modello rappresenta con ragionevolezza i vari aspetti concreti inerenti la soluzione matematica, più esso sarà valido.
Come si può facilmente intuire, se il panorama degli strumenti quantitativi è assai vasto, altrettanto lo è la gamma di modelli che possono essere creati per dirimere le problematiche di scelta sotto condizioni incerte e aleatorie. Esistono diverse tecniche di cui ci si può servire allo scopo di risolvere un problema di ottimizzazione, ognuna delle quali è caratterizzata da determinate proprietà. Innanzitutto, bisogna fare una distinzione a proposito del tipo di decisione oggetto dell’analisi:
Se si è a conoscenza della situazione e dei dati di partenza (prezzi dei prodotti, consumi, domanda, offerta, valore e durata degli impianti) e si possono conoscere a priori le possibili implicazioni delle scelte intraprese, si sta
23
indagando un problema di decisioni in condizioni di certezza e ci si serve di un processo chiamato programmazione deterministica. Questo tipo di programmazione tratta problemi legati ad un solo decisore che ha un unico obiettivo da raggiungere,
Se, al contrario, non si è a conoscenza della situazione e dei dati di partenza e si possono solo prevedere gli eventuali risultati futuri in termini di probabilità, la ricerca dell’ottimo del problema utilizza la programmazione stocastica3
. Questo tipo di programmazione tiene conto della variabilità dei dati in input, fornendo risultati in termini di probabilità, al contrario della più semplice programmazione deterministica, che fornisce risultati senza dare nessuna misura della distribuzione probabilistica di quel risultato stesso.
È bene precisare che il fenomeno ottimizzatorio non è un processo one-shot, in cui viene scelto in maniera immediata un singolo metodo risolutivo applicabile per l’intero problema. È buona norma servirsi di più tecniche, anche se questo può risultare dispendioso; perciò l’impostazione di un processo di ottimizzazione non è sempre immediata e facilmente intuibile. Per esempio, in un determinato modello si può applicare un metodo di ottimizzazione stocastico; una volta trovata la soluzione ottima la si può raffinare mediante un metodo di ottimizzazione deterministico. Infine, si può valutare la robustezza della soluzione trovata tramite un’analisi di affidabilità. Questo procedimento è stato utilizzato nello studio condotto sul contratto di fornitura del gas naturale che sarà oggetto di analisi nel Capitolo II: applicando un iniziale metodo stocastico per ottimizzare il supply chain management della sostanza aeriforme venduta, ci si è accorti come tale processo poteva essere notevolmente semplificato mediante una trasformazione nell’equivalente modello deterministico, la cui risoluzione è stata affidata a software di ottimizzazione.
Di seguito verranno approfonditi e richiamati, dal punto di vista teorico, i modelli quantitativi utilizzati nel caso illustrato nel Capitolo seguente, per comprendere come questi vengano impiegati ed utilizzati nella realtà per risolvere problemi ottimizzatori di varia natura.
3
24
Figura 1.6: Classificazione dei principali modelli matematici utilizzati nella trattazione.
1.3 Fondamenti di programmazione lineare e non lineare
Prima di proseguire con la trattazione dei metodi di ottimizzazione deterministici e stocastici, occorre fare un accenno ad una classe notevolmente importante ed ampia di problemi di ottimizzazione, ossia i problemi di programmazione lineare (PL). Questi problemi sono caratterizzati dal fatto che tutte le relazioni tra le variabili in gioco sono lineari e che queste ultime possono assumere un insieme di valori reali. In particolare, è la struttura della funzione obiettivo che determina la caratteristica di linearità del modello.
Per quanto l’assunzione di linearità nei fenomeni possa apparire piuttosto restrittiva, questa particolare categoria di programmazione ha un forte interesse pratico. Infatti, in molte situazioni reali, i componenti di un sistema reagiscono in maniera abbastanza lineare alle decisioni prese, quindi molti problemi e processi possono essere modellati con precisione in termini lineari. In genere, i problemi rientranti nella sfera della PL, riguardano la minimizzazione dei costi o la massimizzazione dei profitti, rispettando determinati requisiti.
Un problema di ottimizzazione lineare si presenta nella seguente formula ed è caratterizzato dalle seguenti proprietà:
è una matrice reale e ,
La funzione obiettivo è lineare, ovvero tale che per ogni e per ogni . La funzione è lineare se e solo se esiste tale che
Modelli matematici Deterministici (input fissi) Stocastici (input 'probabili')
25 L’insieme ammissibile è definito da un insieme finito di vincoli lineari del tipo
dove e .
Il focus della nostra trattazione si incentra principalmente sui problemi di programmazione non lineare: il modello stocastico, applicato al contratto di fornitura del gas, viene semplificato e risolto in un equivalente modello deterministico non lineare. Questo termine farebbe pensare che, in questa categoria, rientrino tutti quei problemi che non hanno caratteristiche di linearità; ossia quando, nei problemi esaminati, la funzione obiettivo e i vincoli non sono lineari. In realtà, non è proprio così dal momento che la programmazione non lineare è una disciplina molto complessa. Una classe molto importante di problemi ottimizzatori, dal punto di vista applicativo in questo settore, è quella dei problemi di programmazione convessa. Prima di passare alla descrizione di questa categoria di problemi di ottimo, è necessario fare dei richiami sulle seguenti definizioni.
Definizione 1: Dato un insieme , si dice che è un insieme convesso se, scelti
comunque due punti e scelto uno scalare si ha che .
Definizione 2: Sia un insieme convesso e sia si dice che è
convessa su se comunque scelti due punti e scelto uno scalare si
ha che ; si dice che f è strettamente
convessa su C se comunque scelti due punti con e scelto uno scalare si ha che .
26
Definizione 3: Sia un insieme convesso aperto. Se è continuamente
differenziabile su allora:
è convessa su C se e solamente se per ogni si ha
è strettamente convessa su C se e solamente se per ogni con si
ha
A questo punto, un problema di programmazione convessa è un problema di minimizzazione del tipo:
in cui è un insieme convesso e è una funzione convessa su .
1.4 Programmazione deterministica
La programmazione deterministica viene utilizzata per analizzare i problemi di ottimo più rigorosi, che non presentano elementi stocastici; dove la conoscenza dei dati è nota con certezza a priori. Infatti, non tutti i comportamenti o i fenomeni sono di tipo probabilistico, cioè non sono dovuti esclusivamente all’azione del caso.
Un processo viene definito deterministico quando, partendo da uno stato iniziale , applicata una data trasformazione , si giunge sempre allo stato finale
Altre volte, il processo deterministico deriva da ipotesi fatte sul problema osservato. In questo caso, sarà importante utilizzare un adeguato modello teorico per analizzare la problematica da risolvere: il modello infatti, attraverso la conoscenza dei dati iniziali (input), permette di determinare in maniera univoca e certa i dati finali (output) e si configura come uno schema teorico derivante da un determinato ragionamento a monte, capace di semplificare un comportamento complesso all’andamento di poche variabili, poste in relazione tra loro secondo una dipendenza di tipo funzionale. La bontà del modello dipenderà dal grado di aderenza che esso ha con la realtà analizzata.
È ormai noto che ci sono diversi modi per trattare l’incertezza in un problema di ottimizzazione. Ad esempio, partendo dal problema analizzato nei paragrafi precedenti per cui:
27
s.v.
una possibile formulazione deterministica consiste nello stimare un valore di come ad esempio il suo valore atteso , sia esso e quindi risolvere il problema:
In questo caso, la funzione obiettivo non dipende più dalla variabile , bensì dal valore fissato Il problema viene trasformato in un problema deterministico, dal momento che le variabili coinvolte sono tutte variabili con valori fissi e prestabiliti.
Questo tipo di modello rappresenta una sorta di semplificazione: i dati esaminati, privi della componente probabilistica, per questo più semplici ma meno affidabili, spesso non sono molto aderenti e conformi al problema reale. Questo approccio, benché giustificabile in alcuni ambiti applicativi, potrebbe portare a soluzioni non ottime.
1.5 Programmazione stocastica
La programmazione stocastica è un framework per la modellizzazione dei problemi di ottimo in condizioni di incertezza, fondato su soluzioni matematiche-ottimizzatorie che incorporano elementi probabilistici. Il suo obiettivo è, appunto, quello di identificare le decisioni ottime in problemi che coinvolgono elementi non certi. Tale programmazione fa riferimento ad un ambiente di analisi in condizioni di rischio, un ambiente cioè, dove l’incertezza viene rappresentata in termini di natura probabilistica attraverso l’utilizzo di variabili aleatorie, di cui la funzione di distribuzione di probabilità è nota, o almeno stimabile. Le principali proprietà della programmazione stocastica sono le seguenti:
Here-and-now, vale a dire che l’obiettivo è il miglioramento delle decisioni che devono essere prese nel presente, prima che qualunque variabile possa realizzarsi,
Ricorsione, le decisioni prese nel presente possono essere, almeno in parte, corrette e riviste in tempi successivi,
Informazione e osservazione, le decisioni future possono rispondere a informazioni che si sono rese disponibili da quando sono state prese le decisioni
28
iniziali. Le informazioni vengono modellate sulla base delle osservazioni delle variabili,
Convessità, metodi risolutivi sviluppati sotto l’ipotesi restrittiva di convessità,
Indipendenza delle misure di probabilità dalle decisioni, per cui si assume che le variabili siano indipendenti dalle decisioni.
Uno degli aspetti più caratteristici della programmazione stocastica è il processo ricorsivo, un processo dinamico in cui le decisioni si alternano alle osservazioni. Si pensi al seguente processo:
decisione iniziale osservazione decisione di ricorso osservazione decisione di ricorso osservazione decisione di ricorso
In questo processo, che si rinnova e si ripete ad intervalli regolari, abbiamo uno stadio iniziale in cui viene presa la decisione e successivamente stadi di ricorsione, ciascuno formato da una osservazione, in cui una variabile si realizza, e da una decisione, ovvero la risposta all’osservazione appena avvenuta. Infine, si ottiene un vettore di decisioni:
con e un vettore di osservazioni, ossia la storia di tutte le osservazioni effettuate: con
Il costo del processo ricorsivo è espresso tramite una funzione con ( che può assumere valori nello spazio esteso dei reali, arrivando anche al valore .
Lo scopo del processo di ottimizzazione sarebbe quello di risolvere il seguente problema:
29
Supponiamo di essere nello stadio k-esimo e di suddividere il vettore delle osservazioni in due sottovettori:
1. , informazione disponibile, 2. , incertezza residua.
Questo sarà utile nel processo ottimizzatorio dato che, per produrre una decisione iniziale le variabili non saranno mai veramente osservate ma, al più, si potrà supporre che lo siano state. Per esempio, al generico stadio k, si determinerà supponendo che siano state compiute le osservazioni Dunque, allo stadio k conviene determinare una funzione di ricorsione definita sullo spazio :
Con la funzione si specificano nel presente, le risposte da dare ad ogni possibile
realizzazione delle prime k osservazioni. Le risposte, o strategie, sono funzioni ovvero:
( ( (
Si indica con U l’insieme di tutte le possibili funzioni di questo tipo . La
componente dipende da e non da Questa proprietà, il non anticipo delle strategie, serve a garantire che le decisioni non sono basate sulla conoscenza di eventi futuri e non vengono prese prima che questi si verifichino. Il problema finale sarà dunque il seguente:
dove viene ricavato mediante la precedente equazione.
Indicato il ragionamento ricorsivo di cui si serve questo tipo di programmazione, contraddistinto dall’avvicendarsi di decisioni e realizzazioni delle variabili, viene mostrato come implementare un linguaggio matematico di questo tipo. Il punto di partenza è rappresentato da un modello deterministico sottostante. Se alcuni dei parametri del modello non sono esattamente determinabili e se le variazioni di questi parametri non noti influenzano notevolmente il modello stesso, viene impiegato un processo di ottimizzazione stocastico. Ad esempio, la scelta di lanciare un nuovo prodotto o un nuovo servizio sul mercato da parte di un’azienda, non può prescindere dall’incertezza relativa l’andamento dei profitti negli anni a venire: l’azienda dovrà necessariamente acquisire informazioni relative al nuovo prodotto o servizio e, per fare
30
ciò, potrà mettere in atto diverse strategie. Può prendere in considerazione i dati relativi quel determinato prodotto offerto o in una specifica area geografica o ad un determinato
target di clientela, oppure può condurre un’analisi di mercato. Tutti questi espedienti,
forniscono stime della domanda del nuovo prodotto lanciato, anche molto diverse tra loro. Anziché valutare le stime ottenute singolarmente, esse vengono tutte racchiuse in un unico modello stocastico, affinché la soluzione delineata sia più efficace ed efficiente possibile. Proprio la numerosità e la complessità delle alternative e dei risultati ottenuti, richiede l’utilizzo di un approccio più avanzato, rappresentato dall’ottimizzazione stocastica appunto, per mettere a punto strategie che ben si confanno ad un panorama di esiti così vasto.
La programmazione stocastica dunque, rappresenta sotto forma di variabili casuali tutti quei parametri di un problema considerati incerti. Parametri non certi e aleatori possono essere, ad esempio, i costi di distribuzione, che dipendono a loro volta dai costi del carburante, caratterizzati da oscillazioni imprevedibili; oppure i rendimenti dei raccolti influenzati dalle condizioni e dalle variazioni climatiche, che non possono essere predette con accuratezza. È, dunque, uno strumento molto versatile in grado di adattarsi alle specifiche caratteristiche di ciascun problema.
Dal punto di vista teorico, in un modello stocastico l’insieme di tutti gli output o eventi, viene indicato con , in modo che Si denotano, invece, con A tutti gli
altri eventi combinati o ibridi, nati dall’unione di due output distinti. Ad ogni evento A è associato un valore di probabilità, , tale che
e se . Il set contenente i tre parametri , A, è lo spazio di probabilità che deve soddisfare un certo numero di condizioni.
È possibile definire diverse variabili casuali da associare ad uno spazio di probabilità, vale a dire tutte le variabili che sono influenzate dagli eventi casuali di A. In termini
generali, un modello di programmazione stocastica può essere rappresentato come segue:
s.v.
31
dove è l’insieme dei vincoli deterministici; mentre l’uguaglianza rappresenta i vincoli stocastici in cui i coefficienti della matrice e del vettore dei termini dipendono dal risultato del fenomeno aleatorio . L’ottimizzazione del modello consiste, generalmente, nella massimizzazione dei rendimenti attesi o, viceversa, nella minimizzazione dei costi attesi.
Per comprendere meglio l’argomento, seguirà un esempio noto nella letteratura della programmazione stocastica. Lo schema con cui verrà sviluppato l’esempio è il seguente:
Sviluppo del modello deterministico,
Analisi delle variabili con conseguente individuazione di quelle stocastiche,
Progettazione del modello stocastico,
Analisi di scenario, ossia costruzione o campionamento dei possibili eventi futuri necessari per risolvere il problema. Registrati tutti i possibili scenari, si procede con la scelta della decisione ritenuta migliore,
Scelta del metodo risolutivo. Quest’ultimo, nell’ambito della programmazione stocastica, oltre ad essere ben distinto dalla fase di modellizzazione, ha una doppia valenza: la soluzione designata andrà simultaneamente a rappresentare sia le azioni e le decisioni da intraprendere per il normale funzionamento del sistema, detto anche scenario base, sia le azioni da intraprendere per modificare tale scenario in seguito al verificarsi di una qualsiasi delle realizzazioni dei parametri, studiate con la relativa probabilità di realizzazione stimata. Il punto più critico sarà, dunque, stimare e associare una corretta funzione di probabilità agli eventi e ai parametri di un sistema.
1.5.1 Un problema di pianificazione: the farmer’s problem
Un fattore decide di destinare i suoi 1.000 ettari di terra alla coltivazione di grano tenero, grano duro, orzo, avena e altri cereali. È necessario dunque, decidere la quantità di terreno da destinare ad ogni tipo di coltura in modo da individuare la
32
, rappresenta gli ettari destinati al grano tenero, quelli destinati al grano duro, quelli destinati all’orzo, gli ettari coltivati ad avena e il numero di ettari destinati ad altri cereali. Il vettore della domanda di tutti i cereali è
; il vettore dei prezzi di vendita per ettaro delle colture è . Il costo in euro per la coltivazione di un ettaro di terreno destinato al
cereale -esimo sarà , mentre la quantità in quintali del cereale -esimo prodotto da un ettaro di terreno messo a coltura sarà . Il problema consiste quindi nel massimizzare il profitto dell’agricoltore, tenendo conto della quantità di cereali prodotta , dei costi sostenuti per le coltivazioni e dei prezzi di vendita sul mercato
Per risolvere il problema, bisogna impostare i vincoli richiesti in questo caso specifico. Il primo vincolo è quello inerente gli ettari di terreno destinati ad esser coltivati, il secondo riguarda la quantità totale in quintali prodotta del cereale -esimo che non deve essere inferiore alla domanda per quel cereale stesso.
s.v. con
Gli altri dati del problema utili per la sua risoluzione, sono raffigurati sotto forma tabellare. Fin qui il modello delineato è un modello di tipo deterministico, dal momento che non si tiene conto delle eventuali situazioni climatiche che potrebbero far variare la produttività dei raccolti. Per rendere il modello più realistico, bisognerà generare degli scenari tramite modelli matematici, ossia fare delle previsioni che siano in grado di anticipare gli impatti futuri di determinati eventi che si andranno effettivamente a verificare. Ad esempio, in questo tipo di problema sarà indispensabile andare a considerare gli effetti che i cambiamenti climatici avranno sulle varie colture dell’agricoltore: ci potrebbero essere dei fenomeni di piovosità capaci di influenzare positivamente o negativamente il raccolto, ripercuotendosi in questo modo anche sul profitto dell’agricoltore.
33
Prod.tà (q) Prezzi (p) Costi (c) Domanda (d) Prod.tà media
Grano t. 37,88 18,875 12,25 9.000 37,9
Grano d. 27,9 16,85 9,5 10.500 27,9
Orzo 29,88 17,9 7,7 3.000 29,9
Avena 26,02 17,9 6,9 2.000 26,0
Altro 20,84 19,5 12,1 4.000 20,8
Tabella 1.1: Dati per la soluzione del problema deterministico. Fonte: Abaffy, Allevi, Bertocchi, Moriggia, (2010).
La tabella 1.2 mostra la variazione dei prodotti coltivati in entrambi gli scenari delineati
Produttività MAX (condiz. favorevole) Produttività min (condiz. sfavorevole) Grano t. 42,1 27,9 Grano d. 32,7 20,1 Orzo 35,4 20,5 Avena 30,6 19,7 Altro 25,2 16
Tabella 1.2: Produttività massima e minima (quintali per ettaro).
Fonte: Abaffy, Allevi, Bertocchi, Moriggia, (2010).
Nel caso di condizioni climatiche favorevoli, tutti i vincoli impostati risultano essere soddisfatti. La soluzione del problema è rappresentata in tabella:
Caso Favorevole Grano t. 370,06 Grano d. 321,10 Orzo 84,75 Avena 65,36 Altro 158,73 Profitto in Euro 627.883,58
Tabella 1.3: Soluzione del problema stocastico nel caso favorevole. Fonte: Abaffy, Allevi, Bertocchi, Moriggia, (2010).
34
Se invece le condizioni climatiche fossero sfavorevoli e la produzione non
riuscisse a soddisfare la domanda , vengono introdotti due vettori aggiuntivi. Il vettore rappresenta le quantità in ettari da acquistare per il singolo cereale -esimo; è il vettore dei prezzi di acquisto. Il nuovo modello sarà:
I nuovi vincoli da rispettare sono invece:
s.v.
con
con
con
In caso di produttività sfavorevole, l’agricoltore, non riuscendo a soddisfare la domanda di cereali, sarà costretto ad acquistare la parte di cui ha bisogno; quindi acquisterà quantità positive di
Visto che il processo stocastico altro non è che un modello matematico adatto a studiare l'andamento dei fenomeni che seguono leggi casuali, vengono assegnate determinate probabilità ai diversi scenari che si possono verificare.
Tabella 1.4: Soluzione del problema stocastico nel caso sfavorevole.
Fonte: Abaffy, Allevi, Bertocchi, Moriggia, (2010).
Caso Sfavorevole y Grano t. 322,58 0 Grano d. 429,56 1.865,94 Orzo 146,34 0 Avena 101,52 0 Altro 0 4.000 Profitto in Euro 318.473,75
35
La variabile viene indicizzata con che rappresenta il tipo di cereale da acquistare in caso di sottoproduzione ed indica lo scenario della condizione climatica (1 = favorevole, 2 = normale, 3 = sfavorevole):
Le probabilità associate ai tre scenari sono per il tempo favorevole, per il tempo normale e per quello sfavorevole. Includendo i tre possibili scenari, si ottiene un modello in forma estesa di programmazione stocastica:
con i seguenti vincoli da rispettare:
s.v.
con
con
con con
La soluzione del problema stocastico, molto più articolata e complessa, può essere riassunta così:
3
Ettari Y Totale Domanda
Condizioni Favorevoli Grano t. 446,39 42,1 18.793,03 0 18.793,03 9.000 Grano d. 376,34 32,7 12.306,45 0 12.306,45 10.500 Orzo 100,400 35,4 3.554,217 0 3.554,217 3.000 Avena 76,86 30,6 2.352,037 0 2.352,037 2.000 Altro 0,00 25,2 0 4.000 4.000 4.000 Condizioni Normali Grano t. 446,39 37,9 16.909,27 1,42E-14 16.909,27 9.000 Grano d. 376,34 27,9 10.500 0 10.500 10.500 Orzo 100,400 29,9 3.000 0 3.000 3.000 Avena 76,86 26,0 2.000 0 2.000 2.000 Altro 0,00 20,8 0 4.000 4.000 4.000 Condizioni Sfavorevoli Grano t. 446,39 27,9 12.454,29 4.000 16.454,29 9.000 Grano d. 376,34 20,1 7.564,516 2.935,484 10.500 10.500 Orzo 100,400 20,5 2.058,233 9.417,671 3.000 3.000 Avena 76,86 19,7 1.514,22 485,7802 2.000 2.000 Altro 0,00 16,0 0 4.000 4.000 4.000
Tabella 1.5: Soluzione del problema stocastico nei tre scenari possibili.
36
1.5.2 Programmazione stocastica a due stadi con ricorso
I modelli di programmazione stocastica più ampiamente applicati e studiati sono i modelli a due stadi. Qui il decisore, intraprende un'azione nella prima fase dopo la quale si verifica un evento casuale che influenza l'esito della decisione inizialmente intrapresa. Una seconda decisione di ricorso, quindi, viene presa nel secondo stadio, in modo da compensare eventuali effetti negativi che potrebbero essersi verificati, a seguito della decisione della prima fase.
Decisione Osservazione di Decisione
Primo stadio Secondo stadio
Per spiegare teoricamente il modello a due stadi si parte da un problema di programmazione lineare:
s.v.
dove la variabile decisionale e i coefficienti , ,
e . La notazione indicherà la riga i-esima della matrice , la
i-esima componente del vettore . Si supponga che gli elementi della matrice e le componenti del vettore dipendano dalla variabile aleatoria , dove indica l’insieme di supporto di Viene indicata con la famiglia degli ‘eventi’, cioè l’insieme dei sottoinsiemi di e con la distribuzione di probabilità di . Quindi, per ogni sottoinsieme o , la probabilità è nota. Il problema iniziale può essere riscritto come segue:
s.v.
