mercoledì 12 febbraio 2014

Il problema del trasporto ottimale (1 - Monge, nel piano)

Figlio di un venditore ambulante, Gaspard Monge nacque a Beaune nel 1746 durante l’Ancien Régime. A causa delle sue notevoli doti matematiche, le autorità militari lo ammisero come assistente in una scuola di formazione militare per il disegno geometrico, alla quale non avrebbe potuto iscriversi per le sue umili origini. Inventò da solo la geometria descrittiva, e l’utilità del metodo era così evidente che fu nominato professore all’età di 22 anni, a patto che la sua teoria fosse rimasta segreto militare, ad uso esclusivo degli ufficiali di più alto grado. Nel 1780 gli fu assegnata la cattedra di matematica all’Università di Parigi. 

Monge fu un ardente rivoluzionario, ministro della Marina, membro del Direttorio, si occupò della riforma del calendario, della riforma delle unità di misura, di lavori pubblici e di istruzione. Scampò per un pelo alla ghigliottina durante il Terrore e, tornato a Parigi, divenne docente all’École Normale e poi all’École Polytechnique, che aveva fondato. Era amico intimo di Napoleone che seguì anche durante la spedizione in Egitto. Dopo il 18 Brumaio, fu membro del Senato conservatore. La maggior parte della sua opera fu dedicata alla geometria, che trattò in diverse opere pubblicate a cura dell’École Polytechnique. Tra di esse Applicazione dell'algebra alla geometria (1805) e Applicazione dell'analisi alla geometria (1816). La quarta edizione di quest’opera, rivista da Monge poco prima della sua morte, contiene tra l’altro la soluzione di un'equazione differenziale alle derivate parziali del secondo ordine. Privato di ogni carica dopo la restaurazione, morì a Parigi il 28 luglio 1818. 

Oltre che al suo lavoro di geometra, la fama di Gaspard Monge si deve oggi soprattutto alla “memoria” del 1781 intitolata Mémoire sur la théorie des déblais et des remblais, il primo lavoro in cui ci si occupa di trasporto ottimale di una massa. Il problema affrontato è esposto dall’autore all’inizio dell’opera: 

«Quando si deve trasportare della terra da un luogo all’altro, è d’uso chiamare Déblai il volume di terra che di deve trasportare, e quello di Remblai allo spazio che essa deve occupare dopo il trasporto. Siccome il prezzo del trasporto di una molecola, a parità di tempo impiegato, è proporzionale al suo peso e allo spazio che si deve farle percorrere, e perciò il prodotto del trasporto totale deve essere proporzionale alla somma dei prodotti delle molecole moltiplicate per lo spazio percorso da ciascuna, ne consegue che, essendo il déblai e il remblai dotati di forma e posizione, non è indifferente che una certa molecola del déblai sia trasportata in un luogo o in un altro del remblai, esiste invece una certa distribuzione da seguire delle molecole dal primo al secondo, in modo che la somma dei prodotti sia minima possibile, e il prezzo del trasporto totale sia altrettanto minimo. […] È la soluzione a questo problema che mi propongo di trovare qui».


Con un linguaggio più semplice e conciso, la domanda è la seguente: dato uno scavo di terra (déblai), qual è la maniera migliore di estrarlo e trasportarlo in un posto dove possa essere utilizzato come materiale per una nuova costruzione (remblai)? Il problema è di grande importanza perché il trasporto è caro, e lo si vuole rendere il meno costoso possibile. Nonostante la sua intenzione dichiarata, Monge non diede una soluzione soddisfacente del problema. Alla fine della sua opera, non esitò a riconoscere di non aver risolto il problema pratico, ma si dichiarava comunque soddisfatto d’aver trovato qualche nuova proprietà delle superfici curve.

Il trasporto nel piano - Il testo è diviso in due parti, a seconda che il problema si ponga nel piano o in uno spazio a 3 dimensioni. In questa prima parte ci occuperemo solamente del problema nelle 2 dimensioni. 

Spostare della terra da un luogo all’altro del piano è un problema concreto, che nasceva da una effettiva esigenza nell’ambito delle costruzioni militari. Indichiamo con D1 il luogo del déblai, che supponiamo limitato da una curva giacente nel piano. Allo stesso modo, il remblai D2 è limitato da una curva. Per semplificare, Monge suppone che la densità del materiale sia costante e che D1 e D2 abbiano la stessa superficie. 

Per trasportare la terra da D1 a D2, bisogna inviare la “molecola di terra” situata in un punto (x,y) di D1 verso il punto F(x,y) di D2. F rappresenta una certa applicazione di D1 verso D2. Ciò significa che per ogni sottodominio D di D1, l’area di D (proporzionale alla massa del materiale) è uguale a quella di F(D). 

Il prezzo di un tale trasporto F è “proporzionale alla somma dei prodotti dei [pesi delle] molecole moltiplicati per lo spazio percorso”. La molecola situata nel punto (x,y) possiede un peso (proporzionale a) dxdy e viene trasportata per una distanza || F(x,y) – (x,y)||. In formula, il prezzo del trasporto è pertanto proporzionale a:

Il problema di Monge consiste perciò nel trovare il trasporto ammissibile che possiede il costo minore.

La prima grande intuizione del saggio, semplice e bella, oggi la chiameremmo un lemma:

«Le traiettorie seguite da due punti qualunque non possono incontrarsi tra le loro estremità».


La prova risiede nel fatto che la linea retta è il cammino più corto tra due punti. Se un trasporto invia il punto A su a e B su b e se i segmenti Aa e Bb si intersecano, si può modificare il trasporto decidendo di inviare la molecola A sulla molecola b e B su a; il prezzo del trasporto sarà minore perché la somma delle distanze Ab + Ba è minore di Aa + Bb. Si tratta di un’idea feconda. 

Consideriamo ora una retta che incontra prima il déblai e poi il remblai. Se le parti dei due domini che sono dallo stesso lato di questa retta hanno la stessa area, si dice che la retta è equisecante. Sulla figura di Monge, BDbd è una equisecante che taglia i déblais e i remblais in due parti BAD e bad che hanno la stessa area. Monge afferma che il trasporto ottimale deve necessariamente trasportare BAD su bad.


Sfortunatamente, questa affermazione è falsa, nel senso che non è così generale come sembra. Anche Monge lo sa e, otto pagine più avanti, si legge che “la soluzione precedente è illusoria”. Più precisamente, non è sempre valida. La prova si vede dalla figura: se un punto K di BAD è trasportato da un’altra parte, ad esempio in k, poiché le aree delle due parti sono le stesse, bisogna allora che un punto esterno a BAD, ad esempio L, sia trasportato all’esterno di bad in l. Monge conclude che Kk e Ll si incrociano, come nella figura, ma in realtà non è difficile trovare delle situazioni che smentiscono questo assunto. In ogni caso, questo secondo “lemma” è vero in molti casi interessanti, e possiamo procedere come se Monge avesse ragione. 

Una retta nel piano dipende da due parametri, come risulta dall’equazione generale esplicita y = mx + q. La condizione che una retta sia un’equisecante esprime una relazione tra m e q. Monge afferma che le equisecanti formano una famiglia che dipende da un solo parametro. 

La descrizione delle famiglia di rette a un parametro nel piano era ben nota a Monge. Supponiamo che si abbia una retta Δ(t) che dipende dal parametro t. Le due rette infinitamente vicine Δ(t) e Δ(t+dt) si incontrano in un certo punto p(t) che descrive una curva al variare di t. Questa curva è chiamata inviluppo della famiglia di rette Δ(t). Allo stesso modo, data una curva, si può considerare la famiglia delle sue tangenti in punti diversi: si tratta di una famiglia a un solo parametro. Nella figura, l’inviluppo è rappresentato a sinistra. La situazione ottimale, quella in cui la soluzione di Monge funziona, è quella in cui il déblai e il remblai si trovano dallo stesso lato rispetto all’inviluppo. La soluzione di Monge è allora molto semplice: per ogni equisecante, si trasporta BD su bd

Rimane da sapere come trasportare ciascuno degli intervalli BD sull’intervallo bd corrispondente. La sola restrizione è di fare in modo che la massa sia preservata. Lo si può fare in molte maniere, se non si impongono delle condizioni di continuità, ma Monge suggerisce di trasportare in maniera crescente, in modo che il punto B sia trasportato nel punto b, e il punto D in d

Se l’inviluppo penetra nel luogo del déblai o in quello del remblai, la dimostrazione non funziona più. Monge lo sa. Egli suggerisce di dividere il déblai e il remblai in parti scelte opportunamente (non dice come) e di applicare il metodo precedente alle singole parti. 

Le figure che seguono, che dovrebbero chiarire la situazione, sono tratte da una memoria di Charles Dupin pubblicata nel 1822. A sinistra si tratta di trasportare in modo ottimale la forma ovoidale superiore sul dominio a forma di fagiolo. Bisogna innanzitutto chiarire perché nella figura le traiettorie non sono segmenti: Dupin, per superare il suo maestro, considera un caso un po’ più realistico in cui il terreno non è perfettamente piano e le traiettorie sono allora ciò che noi oggi chiamiamo geodesiche invece che dei segmenti. Ciò nonostante, il problema trattato da Dupin è sostanzialmente lo stesso. Si osserva che le equisecanti si tagliano all’interno del déblai: l’inviluppo è mal posizionato.


A destra Dupin rappresenta il trasporto ottimale, che non è continuo. Esso presenta una discontinuità lungao una curva di rottura DD’D’’D’’’. Bisogna immaginare che il trasporto ottimale comporti in qualche modo la rottura del dominio ovoidale lungo questa curva. 

(continua)

Riferimento principale: Étienne Ghys, «Gaspard Monge» — Images des Mathématiques, CNRS, 2012.

Nessun commento:

Posta un commento