Imagini matematice

Transport Monge

Transportul optim este o problemă veche, formulată de Monge în secolul al XVIII-lea. Acesta constă în găsirea celui mai economic mod, de exemplu în timp, de a transporta obiecte între un set de puncte de plecare și puncte de final. Acest articol discută această problemă, dificultatea de a găsi o soluție atunci când există multe puncte și ilustrează unele aplicații. Un articol însoțitor care urmează să fie publicat în curând prezintă reformularea lui Kantorovitch a problemei lui Monge, care i-a permis să devină un instrument esențial atât în teorie, cât și în practică.

Gaspard Monge, pe lângă faptul că este un mare matematician, a participat activ la revoluția franceză și a creat Ecole Polytechnique, precum și Ecole Normale Supérieure. Motivat de aplicațiile militare, în 1781 a formulat problema transportului optim [1]: și-a pus problema calculării celui mai economic mod de a transporta pământul între două locuri pentru a face terasamente.

Problema lui Monge

Pentru a ilustra problema și formularea sa matematică, să ne uităm la modul optim de distribuire a cornurilor de la brutării la cafenele dimineața la Paris. Pentru simplitate, să presupunem că există doar șase brutării și cafenele, care pot fi văzute în figura următoare (brutăriile sunt în roșu, iar cafenelele sunt albastre).
Să presupunem că toate brutăriile produc același număr de cornuri și că toate cafenelele necesită, de asemenea, același număr de cornuri.
În textul său original, Monge presupune că costul deplasării unei unități de masă este egal cu distanța parcursă, dar putem folosi orice cost adecvat problemei la îndemână.
Costul de minimizat pe care îl vom lua în considerare este timpul total al călătoriilor și scriem $ C_ $ timpul dintre brutărie $ \ iC \ in \ $ și cafenea $ \ jC \ in \ $. De exemplu, avem $ C _, \ Blu> = 10 $, ceea ce înseamnă că există o călătorie de zece minute între numărul brutăriei $ \ Red $ și numărul cafenelei $ \ Blu $.

Pentru a satisface constrângerea de aprovizionare, fiecare brutărie trebuie conectată la o singură cafenea și fiecare cafenea trebuie conectată la o singură brutărie. Acest lucru implică în special faptul că există la fel de multe cafenele pe cât sunt brutării. Vom nota
\ [\ si: \ iC \ in \ \ longmapsto \ jC \ in \ \]
o astfel de alegere de conexiuni. O astfel de alegere numim $ \ if $ de conexiuni care satisfac constrângerea de aprovizionare este o permutare.

Costul de transport asociat cu o astfel de permutare este suma costurilor $ C_ $ selectate de permutație $ \ si $, adică
\ [\ begin \ text (\ si) \ eqdef C _, \ si (\ Red)> + C _, \ si (\ Red)> + C _, \ si (\ Red)> + C _, \ si (\ Red)> + C _, \ si (\ Red)> + C _, \ si (\ Red)>. \ Sfârșit \]
De exemplu, pentru permutația ($ \ ref $) prezentată în figura anterioară, obținem ca cost
\ [\ begin C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> = 10 + 7 + 15 + 10 + 14 + 9 = 65. \ end \]

Problema lui Monge constă în căutarea unei permutații $ \ si $ care are costul minim, adică rezolvarea problemei de optimizare
\ [\ begin \ umin \ text (\ si), \ end \]
unde notăm cu $ \ Si_6 $ setul de permutări al setului $ \ $.


Cost = 64	Cost = 65	Cost = 66	Cost = 152

Figura anterioară prezintă exemple de permutări cu costuri diferite. Putem vedea astfel că permutația ($ \ ref $) nu este cea mai bună: există, de exemplu, o altă permutare care are un cost de 64. Dar este cea mai bună? Se pare că da, putem într-adevăr să testăm toate permutările de $ \ $ pe un computer și să le calculăm costul. Câte permutări există în total? Pentru a efectua acest număr, vedem că există șase opțiuni de atribuire posibile de la $ \ Red $ la $ \ si (\ Red) \ în \, \ ldots, \ Blu \> $, apoi cinci opțiuni posibile de atribuire $ \ Red $ la $ \ if (\ Red) $ în setul $ \< \Blu,\ldots,\Blu \>$ pe care îl excludem $ \ si (\ Red) $ și așa mai departe. Numărul total de posibilități este deci de 6 $ \ ori 5 \ ori 4 \ ori 3 \ ori 2 \ ori 1 = 720 $ pe care îl notăm cu 6 $! $, „Factorial 6”. Dacă luăm în considerare un număr de $ n $ de brutării, atunci numărul permutațiilor care trebuie testate pentru a găsi cele mai bune este $ n! = n \ times (n-1) \ times \ cdots \ times 2 \ times 1 $. Acest număr crește extrem de rapid cu $ n $, de exemplu 70 $! \ aproximativ 1.198 \ ori 10 ^ $, comparați cu neuronii $ 10 ^ $ din creier și cu atomii de $ 10 ^ $ din univers. Prin urmare, această strategie exhaustivă de căutare este posibilă numai pentru valori foarte mici de $ n $.

În 1D și 2D

Au durat aproape 200 de ani pentru ca idei noi să apară pentru a calcula eficient un transport optim $ \ sigma $ chiar și pentru valori mari de $ n $. Aceste progrese matematice vor fi detaliate în articolul însoțitor. Să începem cu un caz în care transportul optim este calculat cu ușurință. Cazul cel mai de bază este atunci când punctele care trebuie potrivite sunt de-a lungul unei axe 1D, de exemplu dacă cafenelele și brutăriile sunt situate de-a lungul unei linii de metrou. De asemenea, este necesar ca costul $ C_ $ să fie distanța de-a lungul acestei axe (de exemplu, timpul de călătorie cu metroul între stații).