Математически изображения
Транспорт Monge
Оптималният транспорт е стар проблем, формулиран от Мондж през 18 век. Състои се в намирането на най-икономичния начин, например във времето, за транспортиране на обекти между набор от начални и крайни точки. Тази статия разглежда този проблем, трудността да се намери решение, когато има много точки, и илюстрира някои приложения. Съпътстваща статия, която ще бъде публикувана скоро, представя преформулирането на Канторович на проблема на Мондж, което му позволява да се превърне в основен инструмент както на теория, така и на практика.
Гаспард Монж, освен че е велик математик, участва активно във Френската революция и създава Ecole Polytechnique, както и Ecole Normale Supérieure. Мотивиран от военни приложения, през 1781 г. той формулира проблема за оптималния транспорт [1]: той си задава въпроса за изчисляване на най-икономичния начин за транспортиране на земята между две места, за да се направят насипи.
Проблемът на Мондж
За да илюстрираме проблема и неговата математическа формулировка, нека разгледаме оптималния начин за разпределяне на кроасани от пекарни до кафенета сутрин в Париж. За по-простота, нека приемем, че има само шест пекарни и кафенета, което може да се види на следващата фигура (пекарните са в червено, а кафетата в синьо).
Да приемем, че всички пекарни произвеждат еднакъв брой кроасани и че всички кафенета също изискват еднакъв брой кроасани.
В оригиналния си текст Мондж изказва хипотезата, че цената на преместване на единица маса е равна на изминатото разстояние, но можем да използваме всяка цена, подходяща за разглеждания проблем.
Разходите за минимизиране, които ще разгледаме, са общото време на пътуванията и ние пишем $ C_ $ времето между пекарната $ \ iC \ in \ $ и кафенето $ \ jC \ in \ $. Например имаме $ C _, \ Blu> = 10 $, което означава, че има десетминутно пътуване между пекарната номер $ \ Red $ и номера на кафе $ \ Blu $.
За да се задоволи ограничението на доставките, всяка пекарна трябва да бъде свързана с едно кафене и всяко кафене трябва да бъде свързано с една пекарна. Това предполага по-специално, че има толкова кафенета, колкото пекарни. Ще отбележим
\ [\ si: \ iC \ in \ \ longmapsto \ jC \ in \ \]
такъв избор на връзки. Ние наричаме такъв избор $ \ ако $ от връзки, отговарящи на ограничението на доставката, са пермутация.
Транспортната цена, свързана с такава пермутация, е сумата от разходите $ C_ $, избрани от пермутацията $ \ si $, т.е.
\ [\ begin \ text (\ si) \ eqdef C _, \ si (\ Red)> + C _, \ si (\ Red)> + C _, \ si (\ Red)> + C _, \ si (\ Червен)> + C _, \ si (\ Червен)> + C _, \ si (\ Червен)>. \ край \]
Например за пермутацията ($ \ ref $), показана на предишната фигура, получаваме като цена
\ [\ започнете C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> = 10 + 7 + 15 + 10 + 14 + 9 = 65. \ край \]
Проблемът на Мондж се състои в търсене на пермутация $ \ si $, която има минималната цена, т.е. решаване на проблема с оптимизацията
\ [\ начало \ umin \ текст (\ si), \ край \]
където ние обозначаваме с $ \ Si_6 $ множеството пермутации на множеството $ \ $.
| Разходи = 64 | Разходи = 65 | Разходи = 66 | Разходи = 152 |
Предишната фигура показва примери за пермутации с различни разходи. По този начин можем да видим, че пермутацията ($ \ ref $) не е най-добрата: има например друга пермутация, която струва 64. Но дали е най-добрата? Оказва се, че да, наистина можем да тестваме всички пермутации на $ \ $ на компютър и да изчислим тяхната цена. Колко пермутации има общо? За да извършим това преброяване, виждаме, че има шест възможни варианта за присвояване от $ \ Red $ до $ \ si (\ Red) \ in \, \ ldots, \ Blu \> $, след това пет възможни избора за присвояване на $ \ Red $ до $ \ if (\ Red) $ в комплекта $ \< \Blu,\ldots,\Blu \>$, което изключваме $ \ si (\ Red) $ и т.н. Следователно общият брой възможности е $ 6 \ по 5 \ по 4 \ по 3 \ по 2 \ по 1 = 720 $, които обозначаваме с $ 6! $, "Факториал 6". Ако разгледаме брой $ n $ пекарни, тогава броят на пермутациите, които трябва да се тестват, за да се намери най-доброто, е $ n! = n \ пъти (n-1) \ пъти \ cdots \ по 2 \ по 1 $. Това число нараства изключително бързо с $ n $, например $ 70! \ приблизително 1,198 \ по 10 ^ $, сравнете с $ 10 ^ $ невроните в мозъка и $ 10 ^ $ атомите във Вселената. Следователно тази изчерпателна стратегия за търсене е възможна само за много малки стойности от $ n $.
В 1D и 2D
Отне почти 200 години, за да се появят нови идеи за ефективно изчисляване на оптимален транспорт $ \ sigma $ дори при големи стойности от $ n $. Тези математически постижения ще бъдат подробно описани в придружаващата статия. Нека започнем със случай, в който лесно се изчислява оптималният транспорт. Най-основният случай е, когато точките, които трябва да се съчетаят, са по 1D ос, например ако кафенета и пекарни са разположени по линията на метрото. Също така е необходимо цената $ C_ $ да е разстоянието по тази ос (например времето за пътуване с метро между станциите).