Matematica e… code

Dalle code al supermercato alla teoria delle code


Sorridi... Domani sarà peggio.

Se sei di buon umore, non ti preoccupare. Ti passerà.

Uomini e nazioni agiranno razionalmente solo dopo aver esaurito ogni altra possibilità

Gli amici vanno e vengono, i nemici si accumulano.

E' normalmente poco pratico preoccuparsi in anticipo di eventuali ostacoli: se non ce ne sono, qualcuno si preoccuperà di crearvene.

Se non capite una parola in un brano scientifico, ignoratela. Il brano ne potrà benissimo fare a meno.

Un idiota in un posto importante è come un uomo in cima a una montagna: tutto gli sembra piccolo e lui sembra piccolo a tutti.

Non si perde mai nessun libro prestandolo, a eccezione di quelli cui si tiene particolarmente.

Per quanto uno cerchi e si informi prima di comprare un qualsiasi articolo lo troverà a minor prezzo da un'altra parte non appena l'avrà' acquistato.

Ogni ordine che può essere frainteso è stato frainteso.

Dal Primo libro delle Leggi di Murphy di Arthur Bloch

Siamo davanti alle casse del supermercato, e dobbiamo decidere dove convenga metterci in coda. Calcoliamo quante persone ci sono in ogni fila, il volume delle merci nei vari carrelli e decidiamo. Ma inevitabilmente ci saranno code più veloci della nostra. Questa situazione, e altre simili, sono state codificate nelle cosiddette Leggi di Murphy, una delle quali afferma proprio: “Scegli la coda che vuoi, non sarà mai la più veloce”. E c’è anche la legge inversa: “Se la tua coda è la più veloce, allora sei nella coda sbagliata”. Ovvero, …soltanto per errore possiamo aver scelto la coda più veloce.

Edward A. Murphy Jr.

Edward A. Murphy Jr., era un ingegnere che cinquant’anni fa lavorava al Centro di Ricerca della U.S. Air Force, e aveva notato come i tecnici impegnati nel suo laboratorio compromettessero ogni esperimento con inevitabili errori: “Se qualcosa può andar storto – dichiarò sconsolato e rassegnato, in una conferenza stampa – andrà sicuramente storto”, If something can go wrong, it will. La battuta fece il giro degli ambienti scientifici, venne arricchita da nuove leggi, applicate alle situazioni più diverse e il tutto venne raccolto da Arthur Bloch in una serie di divertenti libretti, dal titolo Leggi di Murphy. Ad oggi, sono usciti tre libri di “murphologia”, ovvero collezioni di pensieri murphologici, tradotti in italiano da Longanesi, che propone quest’anno anche L’Agenda di Murphy 2006, con gli aforismi più recenti.
Sospettiamo che siano stati proprio i matematici i primi a pubblicizzare le leggi di Murphy, per giustificare l’enorme difficoltà di studiare scientificamente le code, alla disperata ricerca dei modelli matematici che risolvano il problema. E’ questo l’argomento della Teoria delle code, che studia le linee di attesa, una teoria di grande importanza, basti pensare alle gravi implicazioni economiche che possono derivare da code e rallentamenti. Inoltre è fondamentale in informatica, per una corretta trasmissione di dati e per il funzionamento di Internet. Noi possiamo vederne soltanto alcuni esempi, indicativi comunque del ruolo essenziale, sovente sottovalutato, della matematica nella vita quotidiana.

Il primo esempio, molto semplice, è la coda di auto a un incrocio stradale, dove un semaforo stabilisce i tempi di scorrimento del traffico tra due vie. Su una delle vie il semaforo ha un intervallo di 20 secondi per il verde e di 40 secondi per il rosso, quindi a ciclo fisso con una durata di 60 secondi. Nei 20 secondi di verde, immaginiamo che possano passare 10 auto. Se ogni 60 secondi passano meno di 10 auto, il traffico scorre normalmente. Ma cosa succede quando nei 60 secondi arrivano 11 auto? Di queste ne passeranno soltanto dieci e una rimarrà bloccata. Nel minuto successivo le macchine che non riescono a passare saranno 2, e la coda continuerà ad aumenta ad ogni ciclo del semaforo. Dopo trenta minuti ci saranno 30 auto in coda. Il traffico andrà in tilt quando la coda crescerà fino a raggiungere il semaforo precedente della stessa via, impedendo così alle auto in attesa a quel semaforo di passare. Si creerà un ingorgo impossibile, crescerà il nervosismo degli automobilisti bloccati, con imprecazioni e insulti che naturalmente complicheranno ancor più la situazione. E non è un problema da poco, visto che in Italia, chi vive nelle città con più di 500.000 abitanti, perde mediamente 177 ore ogni anno, a causa del traffico.

Vediamo un’altra situazione. Siamo in autostrada, in un momento di gran traffico, con una fila di auto che sta viaggiando ai 100 km/h, la prima auto della fila incontra un veicolo che viaggia ai 90 km/h ed è costretta a rallentare per mantenere la distanza di sicurezza. L’auto che la segue, a sua volta rallenta, ma non più rispetto all’auto che viaggiava ai 90 km/h, ma rispetto all’auto che la precede e quindi a una velocità ancora più bassa. E il rallentamento si propaga progressivamente di auto in auto, fino a fermare il traffico, che riparte poi, superato il rallentamento, con una nuova accelerazione progressiva, finché tutte le auto viaggiano alla fine ai 100 km/h.
Riprendiamo l’esempio di un supermercato, ma di piccole dimensioni, che abbia soltanto tre casse, con le file dei clienti in attesa. Il calcolo delle probabilità, già a livello intuitivo, suggerisce che solo una delle tre code potrà essere la più veloce, mentre due saranno più lente: si ha quindi una probabilità su tre di azzeccare la coda più favorevole e due probabilità su tre, cioè il doppio, di sbagliare coda. E questa è una conferma - quasi banale - della legge di Murphy.
La coda del supermercato può essere una coda di grande stress, ma ha un certo vantaggio rispetto ad altri tipi di code. Infatti nelle ore di sovraffollamento si può intervenire aprendo nuove casse. Per favorire i clienti, in genere, vengono aperte casse speciali, ad esempio per chi ha un numero ridotto di articoli da pagare. Ma questo non allevia il disagio dei clienti in coda, anzi lo aumenta, perché è facile dimostrare come i tempi di attesa siano inferiori con casse tutte uguali. Può succedere infatti che in certi momenti non ci sia nessuno alla cassa speciale e questa rimane quindi inutilizzata. Inoltre le casse speciali penalizzano i clienti migliori, quelli che hanno fatto una spesa maggiore, obbligati a fermarsi alle code più lunghe. La soluzione? Forse arriverà con i nuovi dispositivi wireless e smart card che consentiranno una registrazione automatica della nostra spesa, senza obbligo di fermarci alla cassa.

Siméon-Denis Poisson, 1781-1840

Naturalmente, la matematica può fare molto di più: se non riesce a risolvere una volta per tutte il problema delle code, fornisce comunque i dati per prendere le decisioni migliori. Siméon-Denis Poisson (1781-1840) è il matematico e fisico francese che ha svolto studi fondamentali in diversi campi e nel calcolo delle probabilità. In particolare, un suo libro sulle statistiche giudiziarie è considerato all'origine della teoria delle code. Poisson presenta una formula che è diventata preziosa. Eccola:

dove Pm è la variabile casuale poissoniana che indica la probabilità che un dato evento si verifichi m volte.
a è il parametro della legge di Poisson, e rappresenta la frequenza media di accadimento dell'evento osservato.
e è il cosiddetto numero di Eulero, un numero trascendente che vale approssimativamente 2,718281828… ed è la base dei logaritmi naturali.
Un esempio può chiarirci le idee.

Pensiamo a una partita del campionato di calcio: per sapere quanti goal potranno essere segnati nel corso della partita, è sufficiente applicare la formula sostituendo ad a il numero medio di goal segnati negli incontri precedenti tra le due squadre e a m i goal che si possono prevedere per la partita attuale. Così, con a=2, cioè se la media dei goal delle partite precedenti fosse 2, e con m=1, nella previsione di un solo goal nella partita, ricaveremmo dalla formula Pm=0,271: la probabilità di vedere un goal nella partita è circa di 3 su 10, mentre scende a 0,180 (circa due su 10) la probabilità di tre goal e quella di averne sei scende a 0,017.
Pensiamo ancora a un negozio in cui arrivi in media un cliente ogni minuto. Qual è la probabilità che ne arrivino quattro sempre in un minuto? In questo caso a = 1 e m = 4, dalla formula ricaviamo 0,02, ovvero 1 su 50. Una formula utilissima, quindi, che si può applicare a problemi di traffico o di code di qualsiasi tipo.

Agner Krarup Erlang, 1878-1929

E’ quanto intuì Agner Krarup Erlang (1878-1929), un ingegnere danese che, a fine Ottocento, partendo dagli studi di Poisson, elaborò un modello matematico delle telecomunicazioni allo scopo di fissare le dimensioni delle reti telefoniche ai costi più bassi. Per i suoi risultati straordinari Erlang viene considerato il fondatore della teoria delle code e, in suo omaggio, l'unità di misura del traffico telefonico è stata battezzata Erlang.
Nella pratica quotidiana, però, in quale considerazione vengono tenute queste teorie? Ritorniamo all'esempio dei semafori. Immaginiamo che un addetto rilevi le auto che passano a un incrocio, che i dati vengano elaborati secondo la teoria delle code e che i tempi dei semafori vengano stabiliti secondo i risultati ottenuti. Questo può accadere, a volte, per le principali vie di comunicazione di una città. Ma nelle normali vie si è ancora fermi ai vecchi semafori a tempi fissi. Peccato che la matematica sia poco amata, potrebbe aiutarci a vivere meglio.
Anche la teoria della complessità può essere d’aiuto in certi casi. L’aeroporto di New York, ad esempio, per risolvere i problemi del grande traffico di aerei in arrivo e in partenza, ha studiato un sistema complesso particolare, uno sciame di un alveare, nel quale sono presenti fino a cinquantamila api che entrano ed escono dall’alveare senza creare grandi ingorghi. E sono state proprio le api a suggerire le soluzioni per il traffico dell’aeroporto.

Federico Peiretti
Da LA STAMPA, TuttoScienze,18/01/06

PER SAPERNE DI PIU’

Per chi è debole in matematica:
Rob Eastaway e JeremyWyndham - Probabilità, numeri e code. La matematica nascosta nella vita quotidiana, Edizioni Dedalo, 2003.

R. Larson e A. Odoni., Urban Operations Research, Prentice-Hall, 1981. Disponibile in rete:
http://web.mit.edu/urban_or_book/www/book/

Il primo libro delle Leggi di Murphy di Arthur Bloch:
http://www.cli.di.unipi.it/~scotto/HeS/Murphyindex.html

Una presentazione matematica della Teoria delle code, Teoria delle probabilità e delle code, di Ludovica Adacher:
http://adacher.dia.uniroma3.it/automazione1/TeoriaCode.pdf

Dalla Wikipedia:
http://it.wikipedia.org/wiki/Variabile_casuale_Poissoniana
http://en.wikipedia.org/wiki/Queueing_theory

Introduzione alla teoria delle code, di Robert Cooper (sono 361 pagine):
http://www.cse.fau.edu/~bob/publications/IntroToQueueingTheory_Cooper.pdf

I link:
http://www2.uwindsor.ca/~hlynka/queue.html