Appunti del corso Sistemi di servizio e simulazione Massimo Roma

01 mar 2018

Esame:

Compito scritto, durata 3 ore. Parte di teoria e parte di esercizi. Due quesiti corporici (dimostrazione o teorema

fondamentale), il secondo descrittivo (di minore valore), di solito il primo vale 8 il secondo 3-4. 3 esercizi scritti, punteggio

variabile. Il totale fa 32. La lode si ottiene con 31-32, 30.5 è 30, ma negli altri casi si arrotonda per eccesso.

Per superare la prova bisogna fare almeno la metà dei punti di teoria, e ovviamente superare come somma il 18.

Possibilità di preappello.

In cosa consiste il corso

Corso diviso in due parti:

1) molto analitica, teoria delle code. Questa ci prenderà poco piu di metà corso. Dimostrazioni...vedremo la parte basilare

2) studiare la simulazione. Useremo i pacchetti software simulatori. I due simulatori usati dal professore sono Arena

e Simio.

Di cosa ci occupiamo

SISTEMI DI SERVIZIO: - TEORIA DELLE CODE

Un sistema è caratterizzato da parti che interagiscono tra di loro al fine di raggiungere uno scopo. Nel nostro caso un

sistema di servizio è caratterizzato da arrivo di utenti che richiedono un servizio, questo è erogato da dei server. L’arrivo

dei clienti è casuale, i tempi con cui i server erogano i servizi sono casuali, quindi è inevitabile la formazione di una coda.

Un sistema di servizio è anche un aeroporto (servente è la pista), ci possono essere ritardi, bisogna gestire al meglio

questo sistema. Sistemi di trasmissione di dati, ci sono dei buffer (code), questi sistemi vengono anche denominati

SISTEMI A CODA. Sistemi complicati perché c’è di mezzo l’aleatorietà. Si tratta di modelli stocastici.

Parte analitica: analisi 1, serie numeriche. Servono concetti di calcolo delle probabilità per via dei fenomeni aleatori.

UN MODELLO DI TRAFFICO

Grafo, ogni nodo è una fermata, però è un fenomeno aleatorio, non deterministico.

Alla fine delle dispense c’è un capitolo che non fa parte del programma di esame ma serve per dare una ripassata ai

concetti di base che servono per l’esame.

SIMULAZIONE - AD EVENTI DISCRETI

Differisce dai sistemi dove esiste il tempo, per noi il tempo è scandito in maniera discreta, faremo scattare il tempo

all’accadimento di un evento.

La necessità di utilizzare problemi quantitativi è ben consolidata. La ricerca operativa è quella disciplina che cerca di

fornire un sistema di supporto alle decisioni: fornire al decisore (colui che deve selezionare la strategia) un ventaglio di

soluzioni basate su un approccio scientifico non solo su un’intuizione euristica. Tutto ciò si fa attraverso la costruzione di

un modello.

Se ho un problema reale lo posso studiare attraverso una sperimentazione diretta oppure attraverso un modello

La sperimentazione diretta nella maggior parte dei casi non è

fattibile, allora si usa il modello.

Un MODELLO è una struttura appositamente costruita per

rappresentare uja situazione. Posso avere modelli fisici o

matematici.

Un modello fisico è un modello reale, concreto, in scala.

Noi ci occupiamo di modelli matematici (ottimizzazione, grafi,

problemi). La soluzione logica del problema si può determinare

secondo due approcci:

1) soluzione analitica o numerica. Cioè posso determinare una

forma chiusa della soluzione del problema

Risolvere questo potrebbe essere molto

complicato perché per dimensioni grandi

non è praticabile.

Posso usare degli algoritmi (tipo

il simplesso)

Ci sono casi in cui la soluzione esatta numerica non si riesce a calcolare, ci si accontenta di una buona apporossimazione

avendo stimato un gap, per problemi molto difficili si usano le euristiche. Ci sono problemi che non possono essere trattati

neanche in questo modo.

Qui entra in ballo la simulazione. Per poter adottare questo strumento dobbiamo avere a monte un modello adeguato di

simulazione. La costruzione di un modello non è una procedura sistematica, ci sono delle linee di guida ma si possono

creare diversi modelli.

Quando costruiamo un modello abbiamo sempre l’esigenza di VALIDARLO, ciò significa che la soluzione che otteniamo in

qualsiasi forma o modo dobbiamo calarla nella realtà e vedere se ha un significato fisico.

Esempio:

moto rettilineo uniforme s=vt

Particolarmente semplice, possiamo farne anche una trattazione analitica. È un modello valido? Se devo modellare un

qualcosa che ha un andamento simile allora si, ma se devo modellare ad esempio il traffico di Roma non è un modello

valido. Fase di VERIFICA E VALIDAZIONE, devo essere sicuro che il modello riproduca il fenomeno in esame.

Il modello matematico che useremo sarà un modello di simulazione, ci occuperemo di questa fase.

Modello di simulazione

È uno strumento che mi permette di replicare il funzionamento di un sistema di tipo stocastico, che ha dentro delle

problematiche legate alla stocasticità. La differenza fondamentale di questi modelli (rispetto alla programmazione

lineare) è la funzione che ha il computer nella soluzione. Nella simulazione il computer rappresenta il modello

Legame funzionale tra variabili e realtà nel caso dei PL, qui invece il legame è di tipo logico funzionale. La

corrispondenza non è più variabili quantità, ma variabile funzionamento. Abbiamo l’oggetto (in senso informatico) che

rappresenta la situazione in corrispondenza con gli elementi reali. Questo ci permette di ropridurre il funzionamento del

sistema che esiste, ma ci permette anche di realizzare un modello per realtà che non esistono (sono in fase di

progettazione), permette quindi di capire come funzionerà questo sistema secondo quello che ho stabilito. Aspetto

duplice:

1) riproduce l’evoluzione di una realtà già esistente.

2) funzionamento di una realtà che ancora non esiste.

Differenza tra modello di ottimizzazione e uno di simulazione

OTTIMIZZAZIONE:

Sistema WHAT BEST

Cerchiamo massimo o minimo di una funzione nell’insieme ammissibile

SIMULAZIONE:

Analisi di scenario: sistema WHAT IF, non trova la soluzione ottima ma dice cosa succede al sistema se vario

i parametri.

L’analisi di scenario esamina un numero finito di alternative e sceglie la migliore tra queste, non la migliore in assoluto.

Per assurdo per trovare la soluzione ottima dovremmo esaminare un numero infinito di soluzioni.

02 mar 2018 Richiami di calcolo delle probabilità

Densità di probabilità discreta

Leggi congiunte di variabili aleatorie

Distribuzioni condizionate

Somma di variabili aleatorie indipendenti

Momento di ordine r Sono misure di dispersione, serviranno nella

simulazione

Distribuzioni discrete

Geometrica

(Successo al primo tentativo)

Binomiale

Numero di successi in prove ripetute

Poisson

Arrivi casuali al sistema Distribuzioni continue

Uniforme in [a,b]

Esponenziale

Normale

Di Erlang Per k=1 abbiamo la curva in blu

Per k che tende all’infinito abbiamo le altre curve

Quindi al variare di k abbiamo una famiglia di distribuzioni

Ad Erlang sono attribuite diverse formule

In generale possiamo fare successioni di numeri e di variabili aleatorie, la difficoltà sta nel definire le convergenze.

Prendiamo una successione di variabili aleatorie esistono tanti modi di definire la convergenza

Convergenza con probabilità 1

Legge forte dei grandi numeri

Supponiamo di avere una successione di variabili aleatorie indipendenti identicamente distribuite (IID)

Teorema del limite centrale

Questo è un altro modo di convergere, convergenza in distribuzione

Queste cose non si trovano sulle dispense

08 mar 2018 Introduzione alla teoria delle code

Un sistema a coda è un sistema in cui si prevedono arrivi casuali di utenti che richiedono un servizio erogato da uno o più

serventi. Arrivo casuale, tempo di servizio casuale, l’erogazione del servizio è un tempo casuale, si creano file di attesa.

L’utente non è necessariamente una persona, può essere anche un semilavorato che viaggia nell’impianto, un aereo che

aspetta che si liberi la pista, i pacchetti di dati sulla rete internet.

Progettare e gestire un sistema a coda:

Guadagno dall’erogazione del servizio, quindi più servizi erogo più guadagno. L’utente che arriva vorrebbe non fare la fila,

ci sono dei tempi di attesa che hanno dei cosi, ci sono delle statistiche americane che hanno stimato quanto un amerficano

medio perde in un anno delle sue ore lavorative, numeri molto alti. Per soddifare l’utente che arriva dovrei aumentare il

numero dei serventi, altrimenti potrebbe accadere che l’utente arriva, vede una fila troppo lunga e non entra, il non entrare

è una perdita di guadagno. Vorrei quindi evitare che la gente rinunci al servizio, potrei aumentare la rapidità del servizio

(scelte dimensionali del sistema di servizio) questo però aumenta i costi, potrei a quel punto avere tanti serventi che non

lavorano nei momenti in cui non c’è fila. Lo studio che faremo ci permetterà di rispondere ai questiti tipici:

1) se configuro il sistema di servizio in un certo modo qual è il tempo medio che l’utente che arriva dovrà aspettare?

2) qual è la probabilità che l’utente in arrivo non debba fare la fila?

3) qual è il numero migliore di serventi che devo mettere affinchè l’attesa media sia minore di 5 minuti?

Si fanno delle misure di prestazione del sistema, cioè delle grandezze che ci danno informazioni molto importanti per

quanto riguarda il funzionamento del sistema stesso.

Campi di applicazione (alcuni esempi):

1) traffico auto su una rete stradale, di deterministico c’è poco, è un problema di flusso (sistemi di trasporto)

2) trasmissione email (sistemi di comunicazione)

3) tubature

4) pasaggio clienti auto al casello autostradale

Tutte situazioni in cui ci sono delle stocasticitá

Calcolo parallelo, sincronismo ecc

5) servizi commerciali (supermercato, uffici pubblici...) servizi sociali (ospedalieri ecc)

6) sistemi di produzione, sistemi di manutenzione

Componenti fondamentali di un sistema di servizi

1) Si chiama POPOLAZIONE l’insieme di tutti i potenziali clienti (utenti) che noi assumeremo sempre essere

indistinguibili tra di loro (l’utente è un’identità). Potenzialmente possiamo considerarla infinita. È importante vedere se la

popolazione è finita o infinita, la trattazione è più difficile nel momento in cui la popolazione è finita, questo perché se la

popolazione è finita il numero di utenti che stanno nel sistema influenza il numero degli utenti fuori dal sistema. Se si può

ipotizzare la popolazione infinita la trattazione è più semplice.

2) SERVENTI, in particolare il NUMERO, di solito lo indichiamo con “s”.

Potrebbero lavorare sia in serie che in parallelo, l’ipotesi che faremo nella maggior parte dei casi sarà che operano in

parallelo.

3) SCHEMA DI ARRIVO devo specificare in che modo gli utenti arrivano al sistema, fornendo quindi i tepi di interarrivo

ti è il tempo di interarrivo tra l’(i-1)-esimo e l’i-esimo cliente

Var aleatorie di cui è nota la distribuzione di probabilità

Se fosse deterministica dovrei dare un numero preciso dei tempi di interarrivo

4) SCHEMA DI SERVIZIO riguarda la specificazione del tempo che il servente o i serventi impiegano ad erogare

il servizio Variabili aleatorie anche in questo caso. Anche di queste dobbiamo supporre nota la distribuzione di

probabilità

ASSUNZIONE: nel caso in cui ci sono più serventi (in parallelo) si supporrà sempre che operano con lo stesso schema

di servizio

5) CAPACITÀ DEL SISTEMA

Nella realtà può accadere che lo spazio fisico (buffer) dove ci sono i clienti in coda sia limitato, SISTEMA A CAPACITÀ

LIMITATA: nel momento in cui il sistema ha raggiunto la capacità massima il cliente che arriva deve rinunciare al servizio.

L’eventuale rinuncia in inglese solitamente viene chiamata fenomeno di BALKING.

Quando parlo di capacità parlo della capacità del sistema non solo della coda, quindi devo considerare come massimo

numero di clienti in coda la capacità del sistema meno il numero dei serventi.

Capacità del sistema = clienti in coda + clienti serviti

6) DISCIPLINA DELLA CODA

La più comune è FIRST IN FIRST OUT, chiamata anche FCFS (first come first served)

LIFO last in first out, anche qui potrebbe essere LCFS

SIRO service in random order, ho l’operatore che ha uno scatolone di oggetti che deve mettere nella macchina, c’è una

coda di oggeti nello scatolone, l’ntente li prende in ordine casuale

Ci sono situazioni in cui la scelta è basata sul criterio di priorità (esempio al pronto soccorso) PRI (priority)

Invece di avere una sola coda potrei avere

diverse file, quando l’utente arriva può

scegliere dove andare a fare la fila

Per ogni utente che entra nel sistema potrò quantificare il suo tempo di attesa in coda

Variabili:

1) Per ogni utente che entra nel sistema potrò quantificare il suo tempo di attesa in coda

2) tempo di permanenza nel sistema dell’i-esimo utente

Assumeremo che: Notazione di Kendall

È una stringa di lettere e numeri separate dallo / A/B/s/c/p/Z

1) A identifica lo schema di arrivo: distribuzione

2) B identifica lo schema di servizio: distribuzione

A e B possono avere le seguenti distribuzioni:

M markoviana (esponenziale)

D discreta

Ek Erlang di parametro k

G distribuzione generale

3) s è il numero dei serventi: numero

4) c è la capacità: numero, supporremo che sia infinita

5) p è la popolazione: di solito infinita

6) Z è la disciplina della coda: FIFO LIFO SIRO PRI FCFS LCFS

Posso scrivere anche solo questo, sottintendo le cose scritte sopra

Grandezze: Quanto sto utilizzando quel servente

Se fosse più grande di 1 vorrebbe dire che il sistema non

riesce a supportare il numero di clienti

Se ho capacità finita il sistema si autoregola, quindi non importa il valore del ρ, così anche nel caso di popolazione

finita. In tutti gli altri casi dovremo imporre che il ρ sia minore di 1. Il ρ prossimo a 1 indica che il servente sta

lavorando molto

n(t) è una variabile aleatoria. Se faccio variare t varierà n(t), quindi in realtà non ho solo una variabile aleatoria ma ho una

famiglia di variabili aleatorie che dipendono dal tempo t

Le famiglie di VA si chiamano processi stocastici

Esempio n.1

Copisteria con 4 serventi

il tempo che occorre a scrivere una pagina è distribuito esponenzialmente con una media di 5 minuti

Arrivi clienti esponenziali di media 1 ogni 30 min

Singola coda

Lavori eseguiti nell’ordine in cui arrivano

Se non ci metto nient’altro va bene

La copiesteria non accetta più lavori quando ne ha già 20 nel sistema

Chi paga un prezzo più alto ha priorità

Esempio n.2

Catena di montaggio dalla quale esce un pezzo ogni 10 minuti, ognuno di questi poi deve essere collaudato, tempo

medio collaudo distribuito esponenzialmente con media 18 minuti, è effettuato indipendentemente da due collaudatori

L’ingresso nel sistema è l’uscita dal montaggio

che prendono a caso un pezzo di quelli nel buffer di attesa e lo lavorano.

9 mar 2018

Un sistema di coda è definio da tutti gli elementi prima detti, dal punto di vista del funzionamento bisogna invece

calcolare il processo degli arrivi e quello delle uscite. N(t) è una variabile aleatoria che indica il numero degli utenti

all’interno del sistema al tempo t. Si chiama anche STATO DEL SISTEMA AL TEMPO t.

Possiamo definire il numero di utenti in coda presenti (nq(t)). Se consideriamo al variare di t (tempo) quella diventa una

famiglia di variabili aleatorie. Questa famiglia si chiama PROCESSO STOCASTICO A TEMPO CONTINUO (continuo

perché l’indice di questo processo è un parametro continuo).

Ora dobbiamo stimare delle MISURE DI PRESTAZIONE DEL SISTEMA. Si tratta di quelle grandezze di cui dobbiamo

tenere conto se vogliamo andare a valutare come funziona il sistema e come possiamo andarlo a modificare. Dire che

un sistema ha raggiunto la stazionarietà vuol dire che esistono dei limiti finiti. Esiste per questi sistemi un istante

temporale per cui dopo di quello i sistemi si trovano ad essere invarianti.

Misure di prestazione

Andremo ad esaminare tali misure in condizioni stazionarie. Quali sono le grandezze di interesse? Sono essenzialmente 4:

1) N che indica il numero medio di utenti nel sistema

2) N^q che indica il numero medio di utenti in coda

3) T che indica il tempo medio di permanenza nel sistema

4) T^q che indica il tempo di permanenza nella coda

La cosa importante è dare un’esatta definizione di tali quantità. Occorre dire cosa si

intende matematicamente con tali simboli. Quello che stiamo per fare è dare una

definizione di queste 4 quantità mediante la pk(t) che è la probabilità che nel sistema vi

siano k utenti.

Il raggiungimento dello stato di stazionarietà vuol dire che esiste il limite finito di p, con t che tende all’infinito. Non tutti i

sistemi arrivano a tale stato, noi assumeremo sempre che questa ipotesi sia verificata nei nostri studi.

Come definiamo N e T?

Immagino di disporre di due funzioni a(t), che indica il numero totale di utenti arrivati al sistema al tempo t, e b(t) che indica il

numero totale di utenti serviti e quindi usciti dal sistema al tempo t. Facciamo un diagramma cartesiano di questa situazione

con singolo servente e disciplina di coda FIFO.

EEGONOMICITÀ: tale proprietà comporta l’uguaglianza:

La prima uguaglianza vale perché per i sistemi a coda che andiamo a verificare vale

l’ergonomicità.

Il fatto che i limiti esistano è dato dalla stazionarietà.

Legge di Little

Legame importantissimo tra λ, N e T. È valida per qualunque sistem