Teoría del transporte (matemáticas)

Estudio del transporte óptimo y asignación de recursos

En matemáticas y economía, la teoría del transporte o teoría del transporte es el nombre que se le da al estudio del transporte óptimo y la asignación de recursos . El problema fue formalizado por el matemático francés Gaspard Monge en 1781. ^[1]

En la década de 1920, A. N. Tolstoi fue uno de los primeros en estudiar matemáticamente el problema del transporte . En 1930, en la colección Planificación del transporte, volumen I, para el Comisariado Nacional de Transporte de la Unión Soviética, publicó un artículo titulado "Métodos para hallar el kilometraje mínimo en el transporte de carga en el espacio". ^{[2] [3]}

El matemático y economista soviético Leonid Kantorovich realizó importantes avances en este campo durante la Segunda Guerra Mundial . ^[4] En consecuencia, el problema tal como está planteado a veces se conoce como el problema de transporte de Monge-Kantorovich . ^[5] La formulación de programación lineal del problema de transporte también se conoce como el problema de transporte de Hitchcock - Koopmans . ^[6]

Motivación

Minas y fábricas

Supongamos que tenemos una colección de minas que extraen mineral de hierro y una colección de fábricas que utilizan el mineral de hierro que producen las minas. Supongamos, a modo de argumento, que estas minas y fábricas forman dos subconjuntos disjuntos y del plano euclidiano . Supongamos también que tenemos una función de costo , de modo que es el costo de transportar un envío de hierro desde a . Para simplificar, ignoramos el tiempo que lleva realizar el transporte. También suponemos que cada mina puede abastecer solo a una fábrica (sin división de envíos) y que cada fábrica requiere precisamente un envío para estar en funcionamiento (las fábricas no pueden funcionar a la mitad o al doble de su capacidad). Habiendo hecho las suposiciones anteriores, un plan de transporte es una biyección . En otras palabras, cada mina abastece precisamente a una fábrica objetivo y cada fábrica es abastecida por precisamente una mina. Deseamos encontrar el plan de transporte óptimo , el plan cuyo costo total ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle F}$ ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle c:\mathbb {R} ^{2}\times \mathbb {R} ^{2}\to [0,\infty )}$ ${\displaystyle c(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle T:M\to F}$ ${\displaystyle m\in M}$ ${\displaystyle T(m)\in F}$ ${\displaystyle T}$

${\displaystyle c(T):=\sum _{m\in M}c(m,T(m))}$

es el menor de todos los planes de transporte posibles de a . Este caso especial motivador del problema de transporte es una instancia del problema de asignación . Más específicamente, es equivalente a encontrar una correspondencia de peso mínima en un gráfico bipartito . ${\displaystyle M}$ ${\displaystyle F}$

Traslado de libros: la importancia de la función de costes

El siguiente ejemplo simple ilustra la importancia de la función de costo para determinar el plan de transporte óptimo. Supongamos que tenemos libros de igual ancho en un estante (la línea real ), dispuestos en un solo bloque contiguo. Deseamos reorganizarlos en otro bloque contiguo, pero desplazados un ancho de libro hacia la derecha. Se presentan dos candidatos obvios para el plan de transporte óptimo: ${\displaystyle n}$

1. mover todos los libros un ancho de libro hacia la derecha ("muchos movimientos pequeños"); ${\displaystyle n}$
2. Mueva los libros que están más a la izquierda hacia la derecha y deje todos los demás libros fijos ("un gran movimiento"). ${\displaystyle n}$

Si la función de costo es proporcional a la distancia euclidiana ( para algunos ), entonces estos dos candidatos son óptimos . Si, por otro lado, elegimos la función de costo estrictamente convexa proporcional al cuadrado de la distancia euclidiana ( para algunos ), entonces la opción de "muchos movimientos pequeños" se convierte en el único minimizador. ${\displaystyle c(x,y)=\alpha \|x-y\|}$ ${\displaystyle \alpha >0}$ ${\displaystyle c(x,y)=\alpha \|x-y\|^{2}}$ ${\displaystyle \alpha >0}$

Obsérvese que las funciones de costo anteriores consideran únicamente la distancia horizontal recorrida por los libros, no la distancia horizontal recorrida por un dispositivo utilizado para recoger cada libro y moverlo a su posición. Si se considera esta última, entonces, de los dos planes de transporte, el segundo siempre es óptimo para la distancia euclidiana, mientras que, siempre que haya al menos 3 libros, el primer plan de transporte es óptimo para la distancia euclidiana al cuadrado.

Problema de Hitchcock

La siguiente formulación del problema de transporte se atribuye a FL Hitchcock : ^[7]

Supongamos que existen fuentes de un producto, con unidades de oferta en y sumideros para el producto, con una demanda en . Si es el costo unitario de envío desde a , encuentre un flujo que satisfaga la demanda de suministros y minimice el costo del flujo. Este desafío en logística fue abordado por DR Fulkerson ^[8] y en el libro Flows in Networks (1962) escrito con LR Ford Jr. ^[9]. ${\displaystyle m}$ ${\displaystyle x_{1},\ldots ,x_{m}}$ ${\displaystyle a(x_{i})}$ ${\displaystyle x_{i}}$ ${\displaystyle n}$ ${\displaystyle y_{1},\ldots ,y_{n}}$ ${\displaystyle b(y_{j})}$ ${\displaystyle y_{j}}$ ${\displaystyle a(x_{i},\ y_{j})}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$

A Tjalling Koopmans también se le atribuyen formulaciones de la economía del transporte y la asignación de recursos.

Formulación abstracta del problema

Formulaciones de Monge y Kantorovich

El problema del transporte, tal como se plantea en la literatura moderna o más técnica, parece algo diferente debido al desarrollo de la geometría de Riemann y la teoría de la medida . El ejemplo de las minas y las fábricas, por simple que sea, es un punto de referencia útil cuando se piensa en el caso abstracto. En este contexto, permitimos la posibilidad de que no queramos mantener todas las minas y fábricas abiertas al negocio y permitir que las minas abastezcan a más de una fábrica y que las fábricas acepten hierro de más de una mina.

Sean y dos espacios métricos separables tales que cualquier medida de probabilidad en (o ) es una medida de Radon (es decir, son espacios de Radon ). Sea una función medible por Borel . Dadas las medidas de probabilidad en y en , la formulación de Monge del problema de transporte óptimo es encontrar un mapa de transporte que realice el ínfimo ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle c:X\times Y\to [0,\infty ]}$ ${\displaystyle \mu }$ ${\displaystyle X}$ ${\displaystyle \nu }$ ${\displaystyle Y}$ ${\displaystyle T:X\to Y}$

${\displaystyle \inf \left\{\left.\int _{X}c(x,T(x))\,\mathrm {d} \mu (x)\;\right|\;T_{*}(\mu )=\nu \right\},}$

donde denota el avance de por . Un mapa que alcanza este ínfimo ( es decir, lo convierte en un mínimo en lugar de un ínfimo) se denomina "mapa de transporte óptimo". ${\displaystyle T_{*}(\mu )}$ ${\displaystyle \mu }$ ${\displaystyle T}$ ${\displaystyle T}$

La formulación de Monge del problema de transporte óptimo puede estar mal planteada, porque a veces no hay ninguna solución satisfactoria : esto sucede, por ejemplo, cuando es una medida de Dirac pero no lo es. ${\displaystyle T}$ ${\displaystyle T_{*}(\mu )=\nu }$ ${\displaystyle \mu }$ ${\displaystyle \nu }$

Podemos mejorar esto adoptando la formulación de Kantorovich del problema de transporte óptimo, que consiste en encontrar una medida de probabilidad que alcance el ínfimo. ${\displaystyle \gamma }$ ${\displaystyle X\times Y}$

${\displaystyle \inf \left\{\left.\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right|\gamma \in \Gamma (\mu ,\nu )\right\},}$

donde denota la colección de todas las medidas de probabilidad en con marginales en y en . Se puede demostrar ^[10] que siempre existe un minimizador para este problema cuando la función de costo es semicontinua inferior y es una colección ajustada de medidas (lo cual está garantizado para espacios de Radon y ). (Compare esta formulación con la definición de la métrica de Wasserstein en el espacio de medidas de probabilidad). Sigurd Angenent , Steven Haker y Allen Tannenbaum dieron una formulación de descenso de gradiente para la solución del problema de Monge-Kantorovich . ^[11] ${\displaystyle \Gamma (\mu ,\nu )}$ ${\displaystyle X\times Y}$ ${\displaystyle \mu }$ ${\displaystyle X}$ ${\displaystyle \nu }$ ${\displaystyle Y}$ ${\displaystyle c}$ ${\displaystyle \Gamma (\mu ,\nu )}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle W_{p}}$

Fórmula de dualidad

El mínimo del problema de Kantorovich es igual a

${\displaystyle \sup \left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\psi (y)\,\mathrm {d} \nu (y)\right),}$

donde el supremo recorre todos los pares de funciones acotadas y continuas y tal que ${\displaystyle \varphi :X\rightarrow \mathbb {R} }$ ${\displaystyle \psi :Y\rightarrow \mathbb {R} }$

${\displaystyle \varphi (x)+\psi (y)\leq c(x,y).}$

Interpretación económica

La interpretación económica es más clara si se invierten los signos. Sea , para el vector de características de un trabajador, para el vector de características de una empresa y para la producción económica generada por el trabajador emparejado con la empresa . Si se establece y , el problema de Monge-Kantorovich reescribe: que tiene dual  : donde el ínfimo recorre una función acotada y continua y . Si el problema dual tiene una solución, se puede ver que: de modo que se interpreta como el salario de equilibrio de un trabajador de tipo , y se interpreta como la ganancia de equilibrio de una empresa de tipo . ^[12] ${\textstyle x\in X}$ ${\textstyle y\in Y}$ ${\textstyle \Phi (x,y)=-c(x,y)}$ ${\textstyle x}$ ${\textstyle y}$ ${\textstyle u(x)=-\varphi (x)}$ ${\textstyle v(y)=-\psi (y)}$ $${\displaystyle \sup \left\{\int _{X\times Y}\Phi (x,y)d\gamma (x,y),\gamma \in \Gamma (\mu ,\nu )\right\}}$$ $${\displaystyle \inf \left\{\int _{X}u(x)\,d\mu (x)+\int _{Y}v(y)\,d\nu (y):u(x)+v(y)\geq \Phi (x,y)\right\}}$$ ${\textstyle u:X\rightarrow \mathbb {R} }$ ${\textstyle v:Y\rightarrow \mathbb {R} }$ $${\displaystyle v(y)=\sup _{x}\left\{\Phi (x,y)-u(x)\right\}}$$ ${\textstyle u(x)}$ ${\textstyle x}$ ${\textstyle v(y)}$ ${\textstyle y}$

Solución del problema

Transporte óptimo en la línea real

Para , denotemos la colección de medidas de probabilidad en que tienen un momento finito . Sean y sean , donde es una función convexa . ${\displaystyle 1\leq p<\infty }$ ${\displaystyle {\mathcal {P}}_{p}(\mathbb {R} )}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle p}$ ${\displaystyle \mu ,\nu \in {\mathcal {P}}_{p}(\mathbb {R} )}$ ${\displaystyle c(x,y)=h(x-y)}$ ${\displaystyle h:\mathbb {R} \rightarrow [0,\infty )}$

1. Si no tiene átomos , es decir, si la función de distribución acumulativa de es una función continua , entonces es un mapa de transporte óptimo. Es el único mapa de transporte óptimo si es estrictamente convexo. ${\displaystyle \mu }$ ${\displaystyle F_{\mu }:\mathbb {R} \rightarrow [0,1]}$ ${\displaystyle \mu }$ ${\displaystyle F_{\nu }^{-1}\circ F_{\mu }:\mathbb {R} \to \mathbb {R} }$ ${\displaystyle h}$
2. Tenemos

${\displaystyle \min _{\gamma \in \Gamma (\mu ,\nu )}\int _{\mathbb {R} ^{2}}c(x,y)\,\mathrm {d} \gamma (x,y)=\int _{0}^{1}c\left(F_{\mu }^{-1}(s),F_{\nu }^{-1}(s)\right)\,\mathrm {d} s.}$

La prueba de esta solución aparece en Rachev & Rüschendorf (1998). ^[13]

Versión discreta y formulación de programación lineal

En el caso en que los márgenes y son discretos, sean y las masas de probabilidad asignadas respectivamente a y , y sea la probabilidad de una asignación. La función objetivo en el problema primal de Kantorovich es entonces ${\textstyle \mu }$ ${\textstyle \nu }$ ${\textstyle \mu _{x}}$ ${\textstyle \nu _{y}}$ ${\textstyle x\in \mathbf {X} }$ ${\textstyle y\in \mathbf {Y} }$ ${\textstyle \gamma _{xy}}$ ${\textstyle xy}$

${\displaystyle \sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\gamma _{xy}c_{xy}}$

y la restricción se expresa como ${\textstyle \gamma \in \Gamma \left(\mu ,\nu \right)}$

${\displaystyle \sum _{y\in \mathbf {Y} }\gamma _{xy}=\mu _{x},\forall x\in \mathbf {X} }$

y

${\displaystyle \sum _{x\in \mathbf {X} }\gamma _{xy}=\nu _{y},\forall y\in \mathbf {Y} .}$

Para introducir esto en un problema de programación lineal , necesitamos vectorizar la matriz apilando sus columnas o sus filas , a esta operación la llamamos . En el orden de columna principal , las restricciones anteriores se reescriben como ${\textstyle \gamma _{xy}}$ ${\textstyle \operatorname {vec} }$

${\displaystyle \left(1_{1\times \left\vert \mathbf {Y} \right\vert }\otimes I_{\left\vert \mathbf {X} \right\vert }\right)\operatorname {vec} \left(\gamma \right)=\mu }$y ${\displaystyle \left(I_{\left\vert \mathbf {Y} \right\vert }\otimes 1_{1\times \left\vert \mathbf {X} \right\vert }\right)\operatorname {vec} \left(\gamma \right)=\nu }$

donde es el producto de Kronecker , es una matriz de tamaño con todas las entradas de unos y es la matriz identidad de tamaño . Como resultado, al establecer , la formulación de programación lineal del problema es ${\textstyle \otimes }$ ${\textstyle 1_{n\times m}}$ ${\textstyle n\times m}$ ${\textstyle I_{n}}$ ${\textstyle n}$ ${\textstyle z=\operatorname {vec} \left(\gamma \right)}$

${\displaystyle {\begin{aligned}&{\text{Minimize }}&&\operatorname {vec} (c)^{\top }z\\[4pt]&{\text{subject to:}}&&z\geq 0,\\[4pt]&&&{\begin{pmatrix}1_{1\times \left\vert \mathbf {Y} \right\vert }\otimes I_{\left\vert \mathbf {X} \right\vert }\\I_{\left\vert \mathbf {Y} \right\vert }\otimes 1_{1\times \left\vert \mathbf {X} \right\vert }\end{pmatrix}}z={\binom {\mu }{\nu }}\end{aligned}}}$

que se puede ingresar fácilmente en un solucionador de programación lineal a gran escala (ver capítulo 3.4 de Galichon (2016) ^[12] ).

Caso semidiscreto

En el caso semidiscreto, y es una distribución continua sobre , mientras que es una distribución discreta que asigna masa de probabilidad al sitio . En este caso, podemos ver ^[14] que los problemas de Kantorovich primal y dual respectivamente se reducen a: para el primal, donde significa que y , y: para el dual, que puede reescribirse como: que es un problema de optimización convexa de dimensión finita que puede resolverse mediante técnicas estándar, como el descenso de gradiente . ${\textstyle X=Y=\mathbb {R} ^{d}}$ ${\textstyle \mu }$ ${\textstyle \mathbb {R} ^{d}}$ ${\textstyle \nu =\sum _{j=1}^{J}\nu _{j}\delta _{y_{i}}}$ ${\textstyle \nu _{j}}$ ${\textstyle y_{j}\in \mathbb {R} ^{d}}$ $${\displaystyle \inf \left\{\int _{X}\sum _{j=1}^{J}c(x,y_{j})\,d\gamma _{j}(x),\gamma \in \Gamma (\mu ,\nu )\right\}}$$ ${\textstyle \gamma \in \Gamma \left(\mu ,\nu \right)}$ ${\textstyle \int _{X}d\gamma _{j}\left(x\right)=\nu _{j}}$ ${\textstyle \sum _{j}d\gamma _{j}\left(x\right)=d\mu \left(x\right)}$ $${\displaystyle \sup \left\{\int _{X}\varphi (x)d\mu (x)+\sum _{j=1}^{J}\psi _{j}\nu _{j}:\psi _{j}+\varphi (x)\leq c\left(x,y_{j}\right)\right\}}$$ $${\displaystyle \sup _{\psi \in \mathbb {R} ^{J}}\left\{\int _{X}\inf _{j}\left\{c\left(x,y_{j}\right)-\psi _{j}\right\}d\mu (x)+\sum _{j=1}^{J}\psi _{j}\nu _{j}\right\}}$$

En el caso en que , se puede demostrar que el conjunto de asignado a un sitio particular es un poliedro convexo. La configuración resultante se denomina diagrama de potencia . ^[15] ${\textstyle c\left(x,y\right)=\left\vert x-y\right\vert ^{2}/2}$ ${\textstyle x\in \mathbf {X} }$ ${\textstyle j}$

Caso normal cuadrático

Supongamos el caso particular , , y donde es invertible. Entonces se tiene ${\textstyle \mu ={\mathcal {N}}\left(0,\Sigma _{X}\right)}$ ${\textstyle \nu ={\mathcal {N}}\left(0,\Sigma _{Y}\right)}$ ${\textstyle c(x,y)=\left\vert y-Ax\right\vert ^{2}/2}$ ${\textstyle A}$

${\displaystyle \varphi (x)=-x^{\top }\Sigma _{X}^{-1/2}\left(\Sigma _{X}^{1/2}A^{\top }\Sigma _{Y}A\Sigma _{X}^{1/2}\right)^{1/2}\Sigma _{X}^{-1/2}x/2}$

${\displaystyle \psi (y)=-y^{\top }A\Sigma _{X}^{1/2}\left(\Sigma _{X}^{1/2}A^{\top }\Sigma _{Y}A\Sigma _{X}^{1/2}\right)^{-1/2}\Sigma _{X}^{1/2}Ay/2}$

${\displaystyle T(x)=(A^{\top })^{-1}\Sigma _{X}^{-1/2}\left(\Sigma _{X}^{1/2}A^{\top }\Sigma _{Y}A\Sigma _{X}^{1/2}\right)^{1/2}\Sigma _{X}^{-1/2}x}$

La prueba de esta solución aparece en Galichon (2016). ^[12]

Espacios de Hilbert separables

Sea un espacio de Hilbert separable . Sea la colección de medidas de probabilidad en que tienen momento finito -ésimo; sea aquellos elementos que son regulares gaussianos : si es cualquier medida gaussiana estrictamente positiva en y , entonces también. ${\displaystyle X}$ ${\displaystyle {\mathcal {P}}_{p}(X)}$ ${\displaystyle X}$ ${\displaystyle p}$ ${\displaystyle {\mathcal {P}}_{p}^{r}(X)}$ ${\displaystyle \mu \in {\mathcal {P}}_{p}(X)}$ ${\displaystyle g}$ ${\displaystyle X}$ ${\displaystyle g(N)=0}$ ${\displaystyle \mu (N)=0}$

Sea , , para . Entonces el problema de Kantorovich tiene una solución única , y esta solución es inducida por un mapa de transporte óptimo: es decir, existe un mapa de Borel tal que ${\displaystyle \mu \in {\mathcal {P}}_{p}^{r}(X)}$ ${\displaystyle \nu \in {\mathcal {P}}_{p}(X)}$ ${\displaystyle c(x,y)=|x-y|^{p}/p}$ ${\displaystyle p\in (1,\infty ),p^{-1}+q^{-1}=1}$ ${\displaystyle \kappa }$ ${\displaystyle r\in L^{p}(X,\mu ;X)}$

${\displaystyle \kappa =(\mathrm {id} _{X}\times r)_{*}(\mu )\in \Gamma (\mu ,\nu ).}$

Además, si tiene soporte acotado , entonces ${\displaystyle \nu }$

${\displaystyle r(x)=x-|\nabla \varphi (x)|^{q-2}\,\nabla \varphi (x)}$

para -casi todos para algún potencial localmente Lipschitz , -cóncavo y de Kantorovich máximo . (Aquí denota la derivada de Gateaux de .) ${\displaystyle \mu }$ ${\displaystyle x\in X}$ ${\displaystyle c}$ ${\displaystyle \varphi }$ ${\displaystyle \nabla \varphi }$ ${\displaystyle \varphi }$

Regularización entrópica

Consideremos una variante del problema discreto anterior, donde hemos añadido un término de regularización entrópica a la función objetivo del problema primal.

${\displaystyle {\begin{aligned}&{\text{Minimize }}\sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\gamma _{xy}c_{xy}+\varepsilon \gamma _{xy}\ln \gamma _{xy}\\[4pt]&{\text{subject to: }}\\[4pt]&\gamma \geq 0\\[4pt]&\sum _{y\in \mathbf {Y} }\gamma _{xy}=\mu _{x},\forall x\in \mathbf {X} \\[4pt]&\sum _{x\in \mathbf {X} }\gamma _{xy}=\nu _{y},\forall y\in \mathbf {Y} \end{aligned}}}$

Se puede demostrar que el problema dual regularizado es

${\displaystyle \max _{\varphi ,\psi }\sum _{x\in \mathbf {X} }\varphi _{x}\mu _{x}+\sum _{y\in \mathbf {Y} }\psi _{y}v_{y}-\varepsilon \sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)}$

donde, en comparación con la versión no regularizada, la restricción "dura" en el dual anterior ( ) ha sido reemplazada por una penalización "blanda" de esa restricción (la suma de los términos ). Las condiciones de optimalidad en el problema dual pueden expresarse como ${\textstyle \varphi _{x}+\psi _{y}-c_{xy}\geq 0}$ ${\textstyle \varepsilon \exp \left((\varphi _{x}+\psi _{y}-c_{xy})/\varepsilon \right)}$

Ecuación 5.1: ${\displaystyle \mu _{x}=\sum _{y\in \mathbf {Y} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)~\forall x\in \mathbf {X} }$

Ecuación 5.2: ${\displaystyle \nu _{y}=\sum _{x\in \mathbf {X} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)~\forall y\in \mathbf {Y} }$

Denotando como la matriz del término , resolver el dual es por lo tanto equivalente a buscar dos matrices diagonales positivas y de tamaños respectivos y , tales que y . La existencia de tales matrices generaliza el teorema de Sinkhorn y las matrices pueden calcularse utilizando el algoritmo de Sinkhorn-Knopp , ^[16] que simplemente consiste en buscar iterativamente para resolver la ecuación 5.1 , y para resolver la ecuación 5.2 . El algoritmo de Sinkhorn-Knopp es por lo tanto un algoritmo de descenso de coordenadas en el problema dual regularizado. ${\textstyle A}$ ${\textstyle \left\vert \mathbf {X} \right\vert \times \left\vert \mathbf {Y} \right\vert }$ ${\textstyle A_{xy}=\exp \left(-c_{xy}/\varepsilon \right)}$ ${\textstyle D_{1}}$ ${\textstyle D_{2}}$ ${\textstyle \left\vert \mathbf {X} \right\vert }$ ${\textstyle \left\vert \mathbf {Y} \right\vert }$ ${\textstyle D_{1}AD_{2}1_{\left\vert \mathbf {Y} \right\vert }=\mu }$ ${\textstyle \left(D_{1}AD_{2}\right)^{\top }1_{\left\vert \mathbf {X} \right\vert }=\nu }$ ${\textstyle \varphi _{x}}$ ${\textstyle \psi _{y}}$

Aplicaciones

El transporte óptimo de Monge-Kantorovich ha encontrado aplicaciones en una amplia gama de campos diferentes. Entre ellos se encuentran:

• Registro y deformación de imágenes ^[17]
• Diseño de reflectores ^[18]
• Recuperación de información de la sombríagrafía y la radiografía de protones ^[19]
• Tomografía sísmica y sismología de reflexión ^[20]
• La amplia clase de modelos económicos que involucra propiedades sustitutivas brutas (entre otros, modelos de emparejamiento y elección discreta ).

Véase también

• Métrica de Wasserstein
• Función de transporte
• Algoritmo húngaro
• Planificación del transporte
• Distancia de la excavadora
• Ecuación de Monge-Ampère

Referencias

1. G. Monge. Mémoire sur la théorie des déblais et des remblais. Histoire de l'Académie Royale des Sciences de Paris, con les Mémoires de Mathématique et de Physique pour la même année , páginas 666–704, 1781.
2. Schrijver, Alexander , Optimización combinatoria, Berlín; Nueva York: Springer, 2003. ISBN  3540443894 . Cfr. pag. 362
3. Ivor Grattan-Guinness, Ivor, Enciclopedia complementaria de la historia y la filosofía de las ciencias matemáticas, Volumen 1, JHU Press, 2003. Cf. p.831
4. L. Kantorovich. Sobre la translocación de masas. CR (Doklady) Acad. Sci. URSS (NS), 37:199–201, 1942.
5. Cédric Villani (2003). Temas de transporte óptimo . American Mathematical Soc., pág. 66. ISBN 978-0-8218-3312-4.
6. Singiresu S. Rao (2009). Optimización de ingeniería: teoría y práctica (4.ª ed.). John Wiley & Sons. pág. 221. ISBN 978-0-470-18352-6.
7. Frank L. Hitchcock (1941) "La distribución de un producto desde varias fuentes a numerosas localidades", MIT Journal of Mathematics and Physics 20:224–230 MR 0004469.
8. DR Fulkerson (1956) Problema de transporte de Hitchcock, Corporación RAND.
9. LR Ford Jr. y DR Fulkerson (1962) § 3.1 en Flujos en redes , página 95, Princeton University Press
10. L. Ambrosio, N. Gigli y G. Savaré. Flujos de gradientes en espacios métricos y en el espacio de medidas de probabilidad. Lecciones de matemáticas en la Escuela Politécnica Federal de Zúrich, Birkhäuser Verlag, Basilea (2005)
11. Angenent, S.; Haker, S.; Tannenbaum, A. (2003). "Minimización de flujos para el problema de Monge–Kantorovich". SIAM J. Math. Anal . 35 (1): 61–97. CiteSeerX 10.1.1.424.1064 . doi :10.1137/S0036141002410927. 
12. Galichon, Alfred . Métodos óptimos de transporte en economía . Princeton University Press, 2016.
13. Rachev, Svetlozar T. y Ludger Rüschendorf. Problemas de transporte masivo: Volumen I: Teoría . Vol. 1. Springer, 1998.
14. Santambrogio, Filippo. Transporte óptimo para matemáticos aplicados . Birkhäuser Basel, 2016. En particular el capítulo 6, sección 4.2.
15. Aurenhammer, Franz (1987), "Diagramas de potencia: propiedades, algoritmos y aplicaciones", SIAM Journal on Computing , 16 (1): 78–96, doi :10.1137/0216006, MR  0873251.
16. Peyré, Gabriel y Marco Cuturi (2019), "Transporte óptimo computacional: con aplicaciones a la ciencia de datos", Fundamentos y tendencias en aprendizaje automático: vol. 11: n.º 5-6, págs. 355-607. DOI: 10.1561/2200000073.
17. Haker, Steven; Zhu, Lei; Tannenbaum, Allen; Angenent, Sigurd (1 de diciembre de 2004). "Transporte de masa óptimo para registro y deformación". Revista internacional de visión artificial . 60 (3): 225–240. CiteSeerX 10.1.1.59.4082 . doi :10.1023/B:VISI.0000036836.66311.97. ISSN  0920-5691. S2CID  13261370. 
18. Glimm, T.; Oliker, V. (1 de septiembre de 2003). "Diseño óptico de sistemas de reflector único y el problema de transferencia de masa de Monge–Kantorovich". Revista de Ciencias Matemáticas . 117 (3): 4096–4108. doi :10.1023/A:1024856201493. ISSN  1072-3374. S2CID  8301248.
19. Kasim, Muhammad Firmansyah; Ceurvorst, Luke; Ratan, Naren; Sadler, James; Chen, Nicholas; Sävert, Alexander; Trines, Raoul; Bingham, Robert; Burrows, Philip N. (16 de febrero de 2017). "Sombragrafía cuantitativa y radiografía de protones para modulaciones de gran intensidad". Physical Review E . 95 (2): 023306. arXiv : 1607.04179 . Código Bibliográfico :2017PhRvE..95b3306K. doi :10.1103/PhysRevE.95.023306. PMID  28297858. S2CID  13326345.
20. Metivier, Ludovic (24 de febrero de 2016). "Medición del desajuste entre sismogramas utilizando una distancia de transporte óptima: aplicación a la inversión completa de la forma de onda". Revista Geofísica Internacional . 205 (1): 345–377. Bibcode :2016GeoJI.205..345M. doi : 10.1093/gji/ggw014 .

Lectura adicional

• Brualdi, Richard A. (2006). Clases de matrices combinatorias . Enciclopedia de matemáticas y sus aplicaciones. Vol. 108. Cambridge: Cambridge University Press . ISBN 978-0-521-86565-4.Zbl 1106.05001  .