Archivi autore: Marco Caoduro

Il commesso viaggiatore… Alla scoperta della Programmazione Lineare

Lascia una risposta

Amazon riceve decine di milioni di nuovi ordini ogni giorno. Un numero che solo a pensarlo può dare un senso di stordimento.

Mettiamoci nei panni di uno dei servizi di spedizione a cui questa grande compagnia si appoggia. Il flusso di pacchi da gestire è enorme e per aumentare al massimo il profitto bisogna trovare un modo per ridurre al minimo il percorso di ogni spedizioniere.

Qui salta fuori il famoso problema del “Commesso viaggiatore”, ossia come trovare il tragitto più breve che passi per un insieme finito di punti nello spazio.

In questo post cercheremo di cogliere la reale complessità del problema e di risolverlo andando così… alla scoperta della Programmazione Lineare.

Cos’è il Travelling Salesman Problem?

Nell’introduzione abbiamo visto come il problema che stiamo analizzando nasca da un contesto prettamente concreto. Per cercare di capire come risolverlo la prima cosa da fare è sempre la stessa: fare conoscenza con il problema. Per fare questo, solitamente, i matematici non seguono alla lettera le regole del galateo, ma si mettono a dividere tutto in pezzi e a dare un nome ad ogni componente.

Noi da aspiranti matematici faremo lo stesso!

Definiamo quindi un insieme contenente tutti i punti da raggiungere, e un insieme T che rappresenti i possibili tragitti con la loro lunghezza: se esiste un percorso che va da a   di lunghezza .

Utilizzando il vettore , di cui ogni componente rappresenta un tragitto all’interno del percorso considerato (vedremo poi meglio come è fatto), definiamo una funzione che assegna ad ogni percorso la sua lunghezza.

Il problema si può ora vedere in modo più formale come: trovare il vettore   tale per cui  sia minimo.

Forse tutto questo matematichese ti ha confuso un po’, ma se provi a rileggere il tutto con attenzione ti accorgerai che non abbiamo fatto altro che riscrivere in formula il problema di prima.

Ora puoi dire che come era scritto inizialmente era molto più semplice (e ti daremmo ragione), ma questa nuova veste dà al quesito un aspetto più trattabile da un punto di vista matematico/computazionale.

Per trovare una soluzione al problema del commesso viaggiatore andiamo a scoprire uno degli strumenti più potenti nel campo dell’ottimizzazione lineare: la Programmazione Lineare.

Preliminari alla Programmazione Lineare

Prima di riuscire a riscrivere il problema dobbiamo introdurre il concetto di funzione lineare.

Diciamo funzione lineare una funzione del tipo dove .

Guardandola bene possiamo capire che il termine lineare significa semplicemente che l’argomento della funzione è di primo grado.

Analogamente diciamo che un vincolo è lineare se è nella forma  dove e .

Ricerchiamo l’ottimo con la PL

A questo punto vogliamo esprimere un percorso tramite il vettore . Come facciamo?

Una possibile soluzione è la seguente: definiamo una variabile per ogni possibile tragitto. Ad esempio identifica il tragitto dal punto  al punto . Ora poniamo  uguale a 1 se il tragitto è compreso nel percorso considerato, 0 altrimenti.

Ricordandoci del significato di  possiamo finalmente costruire la nostra tanto sudata funzione lineare .

Ci resta soltanto da porre delle condizioni che obblighino il percorso analizzato a passare per tutti i punti.

Ne servono 3!

, ossia ogni punto ha solo un percorso “entrante” …

, ossia ogni punto ha solo un percorso “uscente”….

e

, ossia le uniche possibilità sono utilizzare un tragitto (1) o non considerarlo (0).

(Per correttezza si dovrebbe utilizzare una quarta condizione per evitare la presenza di sottocircuiti non connessi che però qui tralasciamo per semplicità).

Formalizzazione del problema del commesso viaggiatore

Riassumendo tutto quello che abbiamo detto il Travelling Salesman Problem diventa:

sotto le condizioni

Molto bene… E ora?

Abbiamo dato una veste molto elegante al nostro problema, ma come lo risolviamo?

Il bello della programmazione lineare è proprio questo, “non ci interessa”!

Una volta scritto il problema secondo questo formalismo è sufficiente delegarlo ad un buon risolutore.

Qui trovate una spiegazione di come risolvere problemi del genere utilizzando Excel.

Per capire cosa succede all’interno di questi applicativi bisognerebbe aprire una lunghissima e complessa parentesi sul metodo del simplesso. Lascio ai più curiosi l’occasione di approfondire (poi se serve un aiuto scriveteci pure 🙂 ).

Il lato oscuro del commesso viaggiatore

Siamo quasi alla fine e sembra ormai che per i servizi di spedizione il problema delle consegne sia stato risolto. Tutto va bene finché il numero di punti di consegna non aumenta e il nostro metodo non riesce più a fornire una soluzione.

La modellizzazione che abbiamo fatto è infatti NP-completa e quindi il tempo di esecuzione del nostro metodo cresce in modo non polinomiale (e quindi MOLTO velocemente) al crescere del numero di punti analizzati.

E’ proprio questa difficoltà che apre lo scenario ad altre tecniche di risoluzione. L’ideale sarebbe trovare un algoritmo polinomiale, ma non sappiamo ancora se questo è possibile (l’argomento della NP vs P è stato accennato recentemente qui).

Per ora sembra che, nel caso in cui il percorso debba passare per un numero elevato di punti, non si possa trovare la soluzione ottima al problema del commesso viaggiatore in tempi ragionevoli. In pratica quindi si deve abbandonare la speranza di trovare l’ottimo ed accontentarsi di una sua approssimazione.

Futuri viaggi del commesso

Entriamo così nel mondo dell’euristica dove si va a cercare di trovare dei buoni candidati per ottenere l’ottimo utilizzando tecniche di tipo probabilistico/stocastico.

Queste metodologie sono molto interessanti e suggestive. Nel futuro andremo quindi a richiamare il nostro commesso per partire con lui in un nuovo viaggio… alla scoperta del Calcolo Stocastico!

Come abbiamo visto in questo articolo spesso molti problemi della vita quotidiana vengono affrontati facendo uso del sapere matematico.

Questo mi fa pensare che chi dedica la vita allo studio della matematica non sia poi così folle!

Spero che l’articolo ti sia piaciuto, a presto 😉

Marco

Caffè Matematico n°1 – Paradossi Probabilistici

2 Repliche

Il titolo affiancato dal numero 1 fa intuire che qualcosa di nuovo si sta muovendo. 

Eccoci al primo episodio del “Caffè Matematico”! Questa nostra nuova rubrica ha l’intento di accompagnarvi nelle brevi pause giornaliere con delle piccole chicche matematiche.

I testi (speriamo 🙂 ) saranno coincisi e chiari, mentre la scadenza sarà settimanale.

Pronti, partenza…via!

La teoria delle probabilità è in fondo soltanto senso comune ridotto a calcolo.

 

Pierre Simon Laplace, Teoria analitica delle probabilità , 1812

Dopo aver letto questa frase mi sono perso ad apprezzarne la veridicità e allo stesso tempo l’essenziale semplicità. Poi però mi sono chiesto… allora perché esistono dei paradossi probabilistici?

In questo breve articolo cercheremo di dare una risposta a questa domanda e scoprire quali sono i paradossi più famosi della teoria della probabilità.

Cos’è un paradosso? E perché Laplace si “sbagliava”?

La parola paradosso deriva dall’unione delle parole greche παρά (contro) e δόξα (opinione). Un paradosso è infatti un fatto che appare inaccettabile in quanto in contrasto con il senso comune. L’esistenza di queste stranezze, nel mondo probabilistico, va in parte a “dare torto” all’affermazione di Laplace (le virgolette sono d’obbligo ogni volta che contraddico parzialmente il grande matematico! 🙂 ).

A mio parere la presenza di questi fatti mette in luce la profonda bellezza e forza della matematica: quando il senso comune cade in errore il rigore del linguaggio matematico capta la stranezza e tramite il suo formalismo la spiega e ne motiva la presenza.

Quello che faremo da ora in poi sarà appunto questo. Prima ci faremo ingannare dell’intuizione fornendo risposte sbagliate ai paradossi, poi ci armeremo di qualche proprietà matematica per correggere il tiro.

 

Il paradosso delle tre carte

Supponiamo di avere tre carte che per semplicità chiameremo A, B e C. La prima carta è bianca su entrambe le sue facce. La seconda è rossa su entrambi i lati. La terza infine ha una faccia rossa e una bianca.

Immaginiamo ora di inserire A, B e C in una scatola, di estrarre una carta e di porla sul tavolo con solo una faccia visibile. Siamo quindi in grado di vedere il colore di questa che ipotizziamo sia il rosso. Ci chiediamo che probabilità ha l’altra faccia di essere rossa?

Risposta di pancia…   ! Visto che la carta in questione da una parte è rossa può essere soltanto B o C. Abbiamo quindi una possibilità su due che la faccia coperta sia rossa.

Purtroppo però l’istinto ci inganna e dobbiamo chiamare la ragione per riportarci sulla giusta strada.

Risoluzione del paradosso delle tre carte

La nostra prima supposizione che la carta in questione possa essere solamente B o C era ovviamente corretta, ma dobbiamo fare attenzione ad un particolare. Definiamo B come (R1B, B2B) indicando che il lato uno è rosso e il lato due è bianco e C come (R1C, R2C).

Detto questo il lato sopra il tavolo potrebbe essere R1B ,R1C o R2C . Se  il lato è R1B allora l’altro sarà bianco, ma se è R1C o R2C  allora in entrambi i casi l’altra faccia sarà rossa.

Abbiamo dunque 2 casi favorevoli su 3 e la probabilità cercata è quindi    e non    come supposto inizialmente!

 

Il paradosso del secondo figlio

Andiamo dritti al problema come è stato proposto da Martin Gardner sulle pagine del Scientific American:

“Il signor Smith ha due bambini. Almeno uno dei due è un maschio. Qual è la probabilità che entrambi i bambini siano maschi?”

La risposta data al volo è ancora   , ossia potrebbe essere maschio (primo caso favorevole) o femmina (secondo caso sfavorevole).

Anche questa volta sbagliamo!

La soluzione corretta è analoga a quella di prima, ma ormai la nostra pausa caffè sta per finire. E’ ora di rimettersi al lavoro e  rimandare al prossimo espresso una nuova carica di paradossi (dobbiamo ancora parlare di Monty Hall e dei compleanni!).

Vi lascio soltanto un aiuto dando una seconda formulazione del problema che appare meno ambigua. ( Se non riesci a risolverlo chiedi pure nei commenti 🙂 )

Il signor Smith ha due bambini. Non sono due femmine. Qual è la probabilità che entrambi i bambini siano maschi?

 

Questo è il nostro primo esperimento di articolo breve nel formato compatibile con quasi tutte le macchinette per il caffè in commercio ( 😉 ).

Se l’idea ti piace e avresti voglia di leggere altri piccoli spunti matematici faccelo sapere che ci impegneremo per scrivere il più possibile!

 

D’altronde, come mi ha detto una volta Davide citando Paul Erdös,  “Un matematico è una macchina che trasforma caffè in teoremi”!

 

Ci rileggiamo presto!

 

Marco

Come è nata la probabilità – Il dilemma di De Méré (e una semplice risoluzione)

1 Replica

La probabilità è forse una delle branche della matematica più affascinanti e con i risvolti pratici più interessanti. L’idea alla base di questa disciplina è stimolante: indagare il caos e dargli una sorta di ordine, racchiuderlo tra le raffinate cornici matematiche per riuscire ad ammirarlo e tentare di comprenderlo.

La probabilità nella vita quotidiana

Oggi il calcolo delle probabilità ci pervade in molti contesti del nostro vivere quotidiano. Il meteo che controlliamo la mattina prima di uscire ci dà delle previsioni usando un linguaggio probabilistico. La distribuzione delle carte da gioco, così come delle tessere iniziali del Ruzzle con cui giochiamo nei nostri telefonini (o forse è ormai un gioco fuori moda?) sono calcolate usando strumenti probabilistici.

Le applicazioni ovviamente non si fermano qui, infatti anche lo studio dei mercati (come per esempio i famosi test Montecarlo), molti test ingegneristici e l’analisi di quelli che ultimamente ci piace chiamare Big Data si fondano sulla probabilità.

L’alba del calcolo probabilistico

Una delle peculiarità di questa materia è che possiamo determinare la sua nascita con un anno preciso, il 1654. Fu proprio in questa data che Antoine Gombaud Cavalier de Méré, un nobile francese, nonché accanito giocatore d’azzardo scrisse una lettera a due dei più grandi matematici del tempo per cercare di comprendere il motivo delle sue continue perdite nel gioco dei dadi.

I due matematici in questione erano Blaise Pascal e Pierre de Fermat (famoso anche per il suo celebre Ultimo Teorema). Il problema in questione, invece, era il seguente: lanciando un paio di dadi 24 volte si hanno più possibilità di vincita scommettendo a favore o contro il verificarsi di almeno un doppio sei?

(Provate pure a cercare una soluzione, prima di concludere l’articolo faremo un tentativo assieme!)

Con un modo di dire, in questo caso molto azzeccato, possiamo affermare che ormai “i dadi erano tratti”. Ricevuto l’input, i due pensatori iniziarono una corrispondenza sul tema che rapidamente si allargò ad altri matematici facendo sì che l’argomento diventasse molto dibattuto.

Quello che contraddistinse questo avvenimento dagli studi precedenti su problemi analoghi fu che, oltre a risolvere il problema nel suo caso particolare, si andarono a ricercare delle caratteristiche che accomunavano i vari problemi introducendo così i primi formalismi e le basi teoriche del calcolo della probabilità.

Sviluppi successivi 

Personalmente mi piace vedere la lettera di de Méré come un sasso lanciato in uno stagno. Inizialmente vediamo solamente una piccola pietra, ma in un batter d’occhio da quel punto si iniziano a formare una miriade di onde circolari.

A seguito del primo scambio epistolare tra il nobile francese e i due matematici gli sviluppi della materia avvennero, come le increspature d’acqua nello stagno, in tutte le direzione e per mano di numerosi (e grandissimi) matematici. Non potendo racchiudere in un articolo un enorme capitolo della storia della matematica mi limiterò a citarvi alcuni dei passaggi più importanti.

Inizialmente facciamo un piccolo passo avanti nel 1657 quando viene pubblicato “Tractatus de ratiociniis in ludo aleae”. Un’opera, scritta da Christiaan Huygens, che presenta la risoluzione formale del problema dei dadi e altri dilemmi come la ‘divisione delle parti’  e la ‘rovina del giocatore’ (non mi dilungo nella spiegazione di questi ultimi problemi, ma se ti incuriosiscono chiedi pure nei commenti. Il secondo è uno dei miei preferiti).

Successivamente, agli inizi del Settecento, Jakob Bernoulli enuncia e dimostra la ‘Legge Empirica del Caso’ o più comunemente detta ‘Legge dei Grandi Numeri’. Tralasciando l’enunciato formale diciamo volgarmente (perdonatemi formalisti 🙂 ) che questo è il teorema che ci assicura che se lanciassimo una moneta non truccata un numero elevato di volte la percentuale delle teste sarebbe molto simile a quella delle croci.

A questo punto ci avviciniamo all’Ottocento e immancabilmente arriva lui, Friedrich Carl Gauss (per capire meglio il mio immancabilmente clicca qui). Il matematico tedesco definisce la distribuzione normale, soprannominata anche distribuzione a campana per la sua forma caratteristica. Questa particolare distribuzione permette di dare una buona approssimazione di fenomeni casuali a valori reali concentrati intorno ad un singolo valore medio. Per questa sua caratteristica è usatissima in fisica ed è alla base della teoria degli errori.

Concludiamo infine il nostro piccolo viaggio con Kolmogorov che, nel 1933, diede alla probabilità una formulazione assiomatica definitiva. La stessa che si studia ancora oggi nei vari corsi universitari.

Risoluzione del problema di de Mèrè

Prima di lasciarvi volevo, come promesso, mettere con voi le mani in pasta e provare a capire come risolvere il problema dei dadi di de Méré (non sia mai che torni utile in qualche giocata con gli amici).

Per prima cosa enunciamo tre fatti basilari che ci permetteranno di risolvere il dilemma:

  1. La probabilità che un certo avvento accada si può calcolare semplicemente come rapporto tra i casi favorevoli e i casi totali. Come si può intuire questo valore è compreso tra 0 (nessuna possibilità) e 1 (evento certo).
  2. Se la probabilità che un evento A si verifichi è P(A), allora l’eventualità che A non accada è 1-P(A). Questo fatto si può facilmente intuire pensando che i casi totali sono dati dalla somma dei casi favorevoli e quelli sfavorevoli. Quindi 1-P(A) = (casi totali – casi a favore)/(casi totali) = (casi a sfavore)/(casi totali)
  3. La probabilità che due eventi non dipendenti tra di loro avvengano contemporaneamente è data dal prodotto di tali probabilità o, più formalmente, dati A e B indipendenti tra loro si ha P(A ∩ B) = P(A)*P(B)

Detto questo passiamo alla pratica!

Lanciando due dadi i possibili scenari sono (1,1); (1,2);..(4,1);(4,2)…(6,6) in tutto 36. Quindi la probabilità di ottenere un doppio 6 è 1/36 e di conseguenza la probabilità di non ottenerlo è 1 – 1/36 = 35/36.

Per ora abbiamo usato soltanto i primi due principi, non ci resta che usare l’ultimo e andare dritti alla soluzione.

Considerando che ogni lancio dei dadi non dipende da quelli precedenti (in gergo si dice infatti che il dado “non ha memoria”) possiamo misurare la probabilità di ottenere una coppia diversa da (6,6) in 24 lanci successivi come (35/36)^24.

Fatto questo abbiamo ottenuto il contrario di quello che volevamo, ma per sistemare le cose basta usare nuovamente la seconda proprietà: 1 – (35/36)^24 = 0.491404.

Scommettere sul doppio sei potrebbe costarci caro!

 

Questo è il mio primo articolo qui su MathOne. Ho deciso di iniziare con un tema a me caro e spero che il risultato ti sia piaciuto. Se hai qualche consiglio o vuoi chiedermi qualche approfondimento non esitare.

Il bello del blog è proprio la condivisione!

Marco