Matematika képek
Monge szállítás
Az optimális közlekedés régi probléma, amelyet Monge fogalmazott meg a 18. században. Ez abból áll, hogy megtaláljuk a leggazdaságosabb módszert - például időben - a tárgyak szállításához a kiindulási pontok és a végpontok között. Ez a cikk ezt a problémát, a megoldás megtalálásának nehézségeit tárgyalja, ha sok pont van, és néhány alkalmazást bemutat. Egy hamarosan megjelenő kísérő cikk bemutatja Kantorovitch Monge problémájának újrafogalmazását, amely lehetővé tette számára, hogy elméletben és a gyakorlatban is alapvető eszközzé váljon.
Gaspard Monge amellett, hogy nagyszerű matematikus, aktívan részt vett a francia forradalomban, és létrehozta az Ecole Politechnikát, valamint az Ecole Normale Supérieure-t. Katonai alkalmazások motiválta 1781-ben megfogalmazta az optimális közlekedés problémáját [1]: feltette magának azt a kérdést, hogy kiszámítsák-e a föld gazdaságosabb szállítási módját két hely között a töltések kialakításához.
Monge problémája
A probléma és annak matematikai megfogalmazásának szemléltetése érdekében vizsgáljuk meg a pékségektől a párizsi reggeli kávézókig terjedő kifli optimális elosztási módját. Tegyük fel, hogy az egyszerűség kedvéért csak hat pékség és kávézó van, amelyek a következő ábrán láthatók (a pékségek pirosak, a kávézók kékek).
Tegyük fel, hogy minden pékség ugyanannyi kiflit gyárt, és hogy minden kávézóban ugyanannyi kifli szükséges.
Eredeti szövegében Monge azt feltételezi, hogy a tömegegység mozgatásának költsége megegyezik a megtett távolsággal, de felhasználhatunk bármilyen, a kérdéses problémának megfelelő költséget.
A minimalizálandó költség, amelyet figyelembe fogunk venni, az utazások teljes ideje, és $ C_ $ értéket írunk a pékség $ \ iC \ in \ $ és a $ $ jc \ in \ $ között. Például $ C _, \ Blu> = $ 10, ami azt jelenti, hogy tíz perces út van a $ \ Red $ pékség és a $ \ Blu $ kávézó között.
Az ellátási korlátok kielégítése érdekében minden pékségnek egyetlen kávézóhoz, és minden kávézóhoz egyetlen pékséghez kell kapcsolódnia. Ez különösen azt jelenti, hogy ahány kávézó van, annyi pékség is. Megjegyezzük
\ [\ si: \ iC \ in \ \ longmapsto \ jC \ in \ \]
a kapcsolatok ilyen választása. Az ilyen választást $ \ ha az ellátási kényszert kielégítő kapcsolatok $ értéke permutációnak nevezzük.
Az ilyen permutációhoz kapcsolódó szállítási költség a $ C_ $ költségek összege, amelyet a $ \ si $ permutáció választott ki, vagyis
\ [\ begin \ text (\ si) \ eqdef C _, \ si (\ Red)> + C _, \ si (\ Red)> + C _, \ si (\ Red)> + C _, \ si (\ Piros)> + C _, \ si (\ Piros)> + C _, \ si (\ Piros)>. \ end \]
Például az előző ábrán látható permutációhoz ($ \ ref $) költségként kapjuk meg
\ [\ kezdődik C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> = 10 + 7 + 15 + 10 + 14 + 9 = 65. \ vég \]
Monge problémája egy $ \ si $ permutáció keresése, amelynek a legkisebb költsége van, vagyis az optimalizálási probléma megoldása
\ [\ begin \ umin \ text (\ si), \ end \]
ahol $ \ Si_6 $ -val jelöljük a $ \ $ halmaz permutációinak halmazát.
| Költség = 64 | Költség = 65 | Költség = 66 | Költség = 152 |
Az előző ábra különböző költségű permutációk példáit mutatja. Így láthatjuk, hogy a permutáció ($ \ ref $) nem a legjobb: van például egy másik permutáció, amelynek költsége 64. De vajon a legjobb? Kiderült, hogy igen, valóban tesztelhetjük a $ \ $ összes permutációját egy számítógépen, és kiszámíthatjuk azok költségét. Hány permutáció van összesen? A számlálás elvégzéséhez látjuk, hogy hatféle hozzárendelési lehetőség áll rendelkezésre: $ \ Red $ - $ \ si (\ Red) \ in \, \ ldots, \ Blu \> $, majd öt lehetséges választási lehetőség a $ \ Red $ hozzárendeléséhez. $ \ if (\ Red) $ értékre a $ \ halmazban< \Blu,\ldots,\Blu \>$, amelyet kizárunk a $ \ si (\ Red) $ stb. A lehetőségek teljes száma tehát 6-szorosa 5-szerese 4-szerese 3-szor 2-szerese 1 = 720 $, amelyet 6 dollárral jelölünk! $, "Factorial 6". Ha figyelembe vesszük számos $ n $ pékséget, akkor a legjobb megtalálásához tesztelendő permutációk száma $ n! = n \ szor (n-1) \ szor \ cdots \ szor 2 \ szer 1 $. Ez a szám rendkívül gyorsan növekszik $ n $ -val, például 70 USD-vel! \ kb 1,198 \ x 10 ^ $, hasonlítsa össze az agyban található $ 10 ^ $ neuronokkal és a világegyetem $ 10 ^ $ atomjaival. Ez a kimerítő keresési stratégia ezért csak nagyon kicsi $ n $ értékek esetén lehetséges.
1D-ben és 2D-ben
Közel 200 évbe telt, mire új ötletek születtek, hogy hatékonyan kiszámolják az optimális közlekedési $ \ sigma $ -ot, még $ n $ nagy értékek esetén is. Ezeket a matematikai haladásokat a kísérő cikk részletezi. Kezdjük egy olyan esettel, amelyben az optimális szállítás könnyen kiszámítható. A legalapvetőbb eset az, amikor az egyeztetendő pontok 1D tengely mentén helyezkednek el, például, ha a kávézók és pékségek metró mentén helyezkednek el. Szükséges az is, hogy a $ C_ $ költség legyen a tengely mentén mért távolság (például az állomások közötti metróval történő utazási idő).