• catene di Markov
• gestione di un inventario
• iterazione funzionale
• Metodi numerici
• metodo di Aberth
• partizionamento regolare

Nella tesi viene presentato un problema di gestione di un inventario, in cui
un rivenditore deve decidere la quantita' di merci da ordinare periodicamente
ad una fabbrica, al fine di rifornire il suo inventario e soddisfare la domanda
dei clienti. Nello specifico, l’ordine inoltrato alla fine di un certo periodo
e` dato da un’opportuna combinazione convessa della domanda registrata in
tale periodo e dell’ordine effettuato alla fine di quello precedente.
Questo problema viene modellizzato mediante una catena di Markov e,
dal punto di vista numerico, la sua risoluzione e` ricondotta al problema del
calcolo del vettore invariante di probabilita`, cioe` al calcolo del vettore riga
π = (π_i )i∈N con infinite componenti che verifica le seguenti proprieta`:

π = πP,

la sommatoria di tutte le componenti e' 1

π_i > 0 ∀i

dove P e` la matrice di transizione della catena di Markov introdotta nella
modellizzazione del problema. Nello specifico, la matrice P e' di tipo G/M/1
definita da due blocchi A_0 e A_d che risultano fortemente strutturati: A_0 e` bidiagonale
inferiore a blocchi e di Toeplitz a blocchi, mentre A_d ha rango basso. La
dimensione di tali blocchi dipende dai dati del problema di partenza; essa
cresce notevolmente nel caso in cui siano presenti due rivenditori nella catena
di commercio. Considerando dei dati idonei a rappresentare una situazione
reale, la dimensione nel caso con uno o due rivenditori e` rispettivamente
1120 × 1120 e 31360 × 31360.
Nel caso G/M/1,
il calcolo del vettore invariante puo` essere ricondotto alla risoluzione
di un’equazione matriciale non lineare. Nel caso specifico quasta equazione e`:

X = A_0 + X ^d A_d . (1)

L’obiettivo principale della tesi e` stato quello di studiare metodi numerici
specifici per il calcolo di π in modo da sfruttare efficientemente la struttura
della matrice P per ridurre il costo computazionale e l’ingombro di memoria.
Particolare attenzione e` stata rivolta all’inizializzazione degli algoritmi e al
calcolo del prodotto, della traccia e dell’inversa delle matrici di interesse.
Sono state analizzate due classi di metodi numerici per il calcolo della
minima soluzione non negativa R dell’equazione matriciale (1): la prima e`
basata su iterazioni funzionali della forma

X_n+1 = F (X_n) per n ≥ 1

dove F(·) e` una funzione matriciale che rispetta particolari proprieta` e 0 ≤ X0 ≤ R, la seconda sul calcolo della decomposizione spettrale di R tramite il metodo di Aberth e la risoluzione di sistemi lineari singolari.
Tali metodi, benche ́ sfruttino le strutture delle matrici, sono inutilizzabili
nel caso con due rivenditori, in quanto la dimensione e` estremamente grande
(ad esempio 31360 × 31360) e i tempi di calcolo diventano eccessivamente lunghi.
Per questo sono stati analizzati ulteriori metodi numerici che approssimano direttamente
il vettore π senza risolvere l’equazione matriciale (1).
Un algoritmo si basa sul metodo delle potenze, l’altro su un partizionamento
regolare della matrice (I − P T ). Inoltre, e` stata presentata un’euristica per
risolvere le problematiche relative alla dimensione infinita della matrice P .
Gli algoritmi descritti sono stati implementati in MATLAB e sono stati
effettuati confronti, sia in termini di tempo di calcolo che di accuratezza, tra
i vari metodi. I risultati ottenuti sono stati infine commentati relativamente
al modello matematico proposto. Si e` mostrato, in particolare, per quali
parametri del modello viene raggiunto l’obiettivo di rendere omogenea la
dimensione degli ordini inoltrati alla fabbrica, senza incrementare i costi per
il rivenditore.