Imagini matematice
Transportul lui Kantorovici
Acest articol urmărește acest articol despre problema de transport a lui Monge. El explică reformularea propusă de Leonid Kantorovich în timpul celui de-al doilea război mondial. Această reformulare se pretează la o analiză matematică extinsă, precum și la aplicarea sa la multe probleme. Acesta face ca transportul optim să fie un instrument de alegere pentru a face față exploziei recente din știința datelor.
Leonid Kantorovich este un matematician și economist sovietic care a revoluționat teoria optimă a transportului în anii 1940. Cercetările sale s-au dezvoltat din considerații practice care l-au ocupat înainte și după cel de-al doilea război mondial. A jucat un rol important în asigurarea unei distribuții optime a resurselor, în special în timpul asediului de la Leningrad. În același timp, a participat la dezvoltarea optimizării moderne, care a avut un impact imens în multe domenii aplicate. A obținut astfel în 1975 Premiul Nobel pentru economie, deoarece primele aplicații (dar cu siguranță nu singurele!) Ale teoriei sale au apărut în acest domeniu.
Problema Kantorovich
Problema lui Monge [1], detaliată în prima parte, constă în căutarea permutației $ \ si \ in \ Si_n $ care are un cost minim. Aceasta înseamnă că avem o matrice de costuri $ (C _, \ Blu>) _, \ Blu = 1> ^ n $ (de exemplu, timpii de deplasare între puncte) și vrem să rezolvăm problema de optimizare
\ [\ begin \ label \ umin \ text (\ si) \ eqdef \ sum_> C _, \ si (\ Red)> \ end \]
Ideea centrală a lui Kantorovitch [2] este de a modifica problema lui Monge prin înlocuirea setului de permutări cu un set mai mare, dar mai simplu. În primul rând observăm că putem reprezenta o permutare $ \ si \ în \ Si_n $ folosind o matrice de permutare $ P $ care este o matrice binară (completată cu 0 și 1) de dimensiune $ n \ times n $ astfel încât $ P_ = 0 $ cu excepția cazului în care $ \ jC = \ si (\ iC) $ caz în care $ P_ = 1 $. De exemplu, pentru $ n = 3 $ puncte, permutările
$ (\ Red, \ Red, \ Red) \ mapsto (\ Blu, \ Blu, \ Blu) $ (identitatea),
$ (\ Red, \ Red, \ Red) \ mapsto (\ Blu, \ Blu, \ Blu) $ și
$ (\ Red, \ Red, \ Red) \ mapsto (\ Blu, \ Blu, \ Blu) $ sunt reprezentate de matrici de dimensiuni $ 3 \ times 3 $
\ [\ begin \ begin 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \ end, \ quad \ begin 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \ end \ quad \ text \ quad \ begin 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \ end. \ Sfârșit \]
În cele ce urmează, notăm cu $ \ Pp_n $ setul de $ n! $ Matrici de permutare de dimensiuni $ n \ times n $.
Deoarece matricea este binară, cu doar $ n $ elemente diferite de zero egale cu 1, putem înlocui suma de $ n $ termeni care apar în $ \ text (\ si) $ definit în ($ \ ref $) cu o sumă peste setul de $ n \ ori n $ indici $ (\ iC, \ jC) $, adică dacă $ P $ este matricea de permutare asociată cu $ \ dacă $, avem
\ [\ begin \ text (\ si) = \ sum_ ^ n \ sum_ ^ n P_ C_. \ Sfârșit \]
Astfel putem înlocui problema Monge ($ \ ref $) cu problema echivalentă
\ [\ begin \ label \ umin
\ sum_ ^ n \ sum_ ^ n P_ C_. \ Sfârșit \]
Echivalența Monge-Kantorovitch
Setul matricilor bistochastice este mai mare decât cel al matricilor de permutare, $ \ Pp_n \ subset \ Bb_n $, astfel încât să avem inegalitatea