Matematika képek
Kantorovich szállítása
Ez a cikk folytatja ezt a cikket Monge közlekedési problémájáról. Elmagyarázza a második világháború idején Leonyid Kantorovics által javasolt átfogalmazást. Ez az újrafogalmazás kiterjedt matematikai elemzésre, valamint számos probléma alkalmazására alkalmas. Az optimális közlekedést választott eszközzé teszi az adattudomány legutóbbi robbanásának kezelésére.
Leonid Kantorovich szovjet matematikus és közgazdász, aki az 1940-es években forradalmasította az optimális közlekedési elméletet. Kutatása olyan gyakorlati megfontolásokból nőtt ki, amelyek foglalkoztatták a második világháború előtt és után. Fontos szerepet játszott az erőforrások optimális elosztásának biztosításában, különösen Leningrád ostromakor. Ugyanakkor részt vett a modern optimalizálás fejlesztésében, amelynek számos alkalmazott területen hatalmas hatása volt. Így 1975-ben megszerezte a közgazdasági Nobel-díjat, mert elméletének első alkalmazásai (de természetesen nem az egyetlenek!) Ezen a területen jelentek meg.
A Kantorovich-probléma
Monge problémája [1], amelyet az első részben részletezünk, a $ \ si \ in \ Si_n $ permutáció megkereséséből áll, amelynek minimális költsége van. Ez azt jelenti, hogy van egy költségmátrixunk $ (C _, \ Blu>) _, \ Blu = 1> ^ n $ (például a pontok közötti utazási idő), és meg akarjuk oldani az optimalizálás problémáját
\ [\ begin \ label \ umin \ text (\ si) \ eqdef \ sum_> C _, \ si (\ Red)> \ vég \]
Kantorovitch [2] központi gondolata az, hogy módosítsa Monge problémáját úgy, hogy a permutációk halmazát nagyobb, de egyszerűbb halmazra cseréli. Először is azt vesszük észre, hogy a $ \ si \ in \ Si_n $ permutációt egy $ P $ permutációs mátrix használatával reprezentálhatjuk, amely bináris mátrix (0-val és 1-gyel töltve), amelynek mérete $ n \ -szer annyi, mint $ P_ = 0 $, kivéve, ha $ \ jC = \ si (\ iC) $, ebben az esetben $ P_ = 1 $. Például $ n = 3 $ pont esetén a permutációk
$ (\ Red, \ Red, \ Red) \ mapsto (\ Blu, \ Blu, \ Blu) $ (azonosság),
$ (\ Red, \ Red, \ Red) \ mapsto (\ Blu, \ Blu, \ Blu) $ és
A $ (\ Red, \ Red, \ Red) \ mapsto (\ Blu, \ Blu, \ Blu) $ értékeket $ 3 \ 3x szorzatú mátrixok képviselik
\ [\ 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 \ elején 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \ end. \ end \]
A következőkben $ \ Pp_n $ -val jelöljük a $ n halmazát! $ Permutációs mátrixok, amelyek mérete $ n \ -szerese n $.
Mivel a mátrix bináris, csak $ n $ nem nulla elemek egyenlőek 1-vel, kicserélhetjük az $ n $ kifejezések összegét, amelyek a ($ \ ref $) -ban definiált $ \ text (\ si) $ -ban jelennek meg. a $ n \ szorzatának n $ index ($ i \, iC, \ jC) $ halmazának összegével, azaz ha $ P $ az $ \ if $ -hoz társított permutációs mátrix, akkor
\ [\ begin \ text (\ si) = \ sum_ ^ n \ sum_ ^ n P_ C_. \ end \]
Így helyettesíthetjük a Monge-problémát ($ \ ref $) egyenértékű problémával
\ [\ begin \ label \ umin
\ összeg_ ^ n \ összeg_ ^ n P_ C_. \ end \]
A Monge-Kantorovitch-ekvivalencia
A bisztokasztikus mátrixok halmaza nagyobb, mint a permutációs mátrixoké, $ \ Pp_n \ részhalmaz \ Bb_n $, így megvan az egyenlőtlenség