En matemáticas y economía, la teoría del transporte o teoría del transporte es un 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, AN Tolstoi fue uno de los primeros en estudiar matemáticamente el problema del transporte . En 1930, en la colección Transportation Planning Volume I para el Comisariado Nacional de Transporte de la Unión Soviética, publicó un artículo "Métodos para encontrar el kilometraje mínimo en el transporte de carga en el espacio". [2] [3]
El matemático y economista soviético Leonid Kantorovich logró importantes avances en este campo durante la Segunda Guerra Mundial . [4] En consecuencia, el problema, tal como se afirma, a veces se conoce como el problema del transporte de Monge-Kantorovich . [5] La formulación de programación lineal del problema del transporte también se conoce como el problema del transporte de Hitchcock - Koopmans . [6]
Motivación
Minas y fabricas
Supongamos que tenemos una colección de m minas de extracción de mineral de hierro, y una colección de n fábricas que utilizan el mineral de hierro que las minas producen. Supongamos, por el bien del argumento de que estas minas y fábricas forman dos disjuntos subconjuntos M y F del plano euclidiano R 2 . Supongamos también que tenemos una función de costo c : R 2 × R 2 → [0, ∞), de modo que c ( x , y ) es el coste del transporte de un envío de hierro de x a y . Por simplicidad, ignoramos el tiempo necesario para realizar el transporte. También asumimos que cada mina puede abastecer solo a una fábrica (sin dividir los envíos) y que cada fábrica requiere precisamente un envío para estar en operación (las fábricas no pueden trabajar a la mitad o al doble de capacidad). Después de haber hecho los supuestos anteriores, un plan de transporte es una biyección T : M → F . En otras palabras, cada mina m ∈ M suministra precisamente una fábrica objetivo T ( m ) ∈ F y cada fábrica es abastecida precisamente por una mina. Deseamos encontrar el plan de transporte óptimo , el plan T cuyo costo total
es el menor de todos los posibles planes de transporte de M a F . Este caso especial motivador del problema del transporte es un ejemplo del problema de la asignación . Más específicamente, equivale a encontrar una coincidencia de peso mínima en un gráfico bipartito.
Mover libros: la importancia de la función de costes
El siguiente ejemplo simple ilustra la importancia de la función de costos para determinar el plan de transporte óptimo. Supongamos que tenemos n libros de igual ancho en un estante (la línea real ), dispuestos en un solo bloque contiguo. Deseamos reorganizarlos en otro bloque contiguo, pero desplazamos el ancho de un libro hacia la derecha. Se presentan dos candidatos obvios para el plan de transporte óptimo:
- mover todos los n libros un libro de ancho a la derecha ("muchos movimientos pequeños");
- mueva el libro más a la izquierda n anchos de libro hacia la derecha y deje todos los demás libros fijos ("un gran movimiento").
Si la función de coste es proporcional a la distancia euclidiana ( c ( x , y ) = α | x - y |), entonces estos dos candidatos son tanto óptima. Si, por otro lado, elegimos la función de costo estrictamente convexa proporcional al cuadrado de la distancia euclidiana ( c ( x , y ) = α | x - y | 2 ), entonces la opción "muchos movimientos pequeños" se convierte en el minimizador único. .
Tenga en cuenta que las funciones de costo anteriores consideran solo la distancia horizontal recorrida por los libros, no la distancia horizontal recorrida por un dispositivo utilizado para levantar cada libro y mover el libro a su posición. Si se considera el último, 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 acredita a FL Hitchcock : [7]
- Supongamos que hay m fuentes para una mercancía, con unidades de suministro en x i y n sumideros para la mercancía, con la demanda en y j . Si es el costo unitario de envío desde x i a y j , encontrar un flujo que satisface la demanda de suministros y minimiza el coste de flujo. Este desafío logístico fue abordado por DR Fulkerson [8] y en el libro Flows in Networks (1962) escrito con LR Ford Jr .. [9]
A Tjalling Koopmans también se le atribuyen las 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, se ve algo diferente debido al desarrollo de la geometría y la teoría de la medida de Riemann . El ejemplo de las fábricas de minas, 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 deseemos mantener abiertas todas las minas y fábricas, y permitir que las minas suministren más de una fábrica y que las fábricas acepten hierro de más de una mina.
Sean X e Y dos espacios métricos separables de modo que cualquier medida de probabilidad en X (o Y ) sea una medida de radón (es decir, son espacios de radón ). Sea c : X × Y → [0, ∞] una función medible de Borel . Dadas las medidas de probabilidad μ en X y ν en Y , la formulación de Monge del problema de transporte óptimo es encontrar un mapa de transporte T : X → Y que se dé cuenta del mínimo
donde T * ( μ ) denota el impulso hacia adelante de μ por T . Un mapa T que alcanza este mínimo ( es decir, lo convierte en un mínimo en lugar de un mínimo) se denomina "mapa de transporte óptimo".
La formulación de Monge del problema de transporte óptimo puede estar mal planteada, porque a veces no hay T que satisfaga T ∗ ( μ ) = ν : esto sucede, por ejemplo, cuando μ es una medida de Dirac pero ν no lo es.
Podemos mejorar esto adoptando la formulación de Kantorovich del problema de transporte óptimo, que consiste en encontrar una medida de probabilidad γ en X × Y que alcance el mínimo
donde Γ ( μ , ν ) denota la colección de todas las medidas de probabilidad sobre X × Y con marginales μ en X y ν en Y . Se puede demostrar [10] que siempre existe un minimizador para este problema cuando la función de costo c es semicontinua más baja y Γ ( μ , ν ) es una colección ajustada de medidas (que está garantizada para los espacios de radón X e Y ). (Compare esta formulación con la definición de la métrica de Wasserstein W 1 en el espacio de medidas de probabilidad.) Sigurd Angenent , Steven Haker y Allen Tannenbaum dieron una fórmula de descenso de gradiente para la solución del problema de Monge-Kantorovich . [11]
Fórmula de dualidad
El mínimo del problema de Kantorovich es igual a
donde el supremo corre sobre todos los pares de funciones acotadas y continuas y tal que
Interpretación económica
La interpretación económica es más clara si se invierten los signos. Dejar representan 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 firme . Configuración y , el problema de Monge-Kantorovich reescribe:
Solución del problema
Transporte óptimo en la línea real
Para , dejar denotar la colección de medidas de probabilidad en que tienen finito -ésimo momento . Dejar y deja , dónde es una función convexa .
- Si no tiene átomo , es decir, si la función de distribución acumulativa de es una función continua , entonceses un mapa de transporte óptimo. Es el mapa de transporte óptimo único si es estrictamente convexo.
- Tenemos
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 de que los márgenes y son discretos, deja y ser las masas de probabilidad asignadas respectivamente a y , y deja ser la probabilidad de un asignación. La función objetivo en el problema primordial de Kantorovich es entonces
y la restricción se expresa como
y
Para ingresar esto en un problema de programación lineal , necesitamos vectorizar la matrizapilando sus columnas o sus filas , llamamosesta operacion. En el orden de la columna principal , las restricciones anteriores se reescriben como
y
dónde es el producto Kronecker , es una matriz de tamaño con todas las entradas de unos, y es la matriz de identidad del tamaño . Como resultado, el establecimiento, la formulación de programación lineal del problema es
S t
que se puede ingresar fácilmente en un solucionador de programación lineal a gran escala como Gurobi (consulte el capítulo 3.4 de Galichon (2016) [12] ).
Estuche semidiscreto
En el caso semidiscreto, y es una distribución continua sobre , tiempo es una distribución discreta que asigna masa de probabilidad al sitio . En este caso, podemos ver [14] que los problemas primarios y duales de Kantorovich se reducen respectivamente a:
En el caso cuando , se puede demostrar que el conjunto de asignado a un sitio en particular es un poliedro convexo. La configuración resultante se llama diagrama de potencia . [15]
Caso normal cuadrático
Asume el caso particular , , y dónde es invertible. Entonces uno tiene
La prueba de esta solución aparece en Galichon (2016). [12]
Espacios Hilbert separables
Dejar ser un espacio Hilbert separable . Dejar denotar la colección de medidas de probabilidad en tales que tienen finito -ésimo momento; dejar denotar esos elementos que son regulares gaussianos : sies cualquier medida gaussiana estrictamente positiva en y , luego además.
Dejar , , por . 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
Además, si tiene soporte limitado , entonces
por -casi todos para algunos Lipschitz localmente , c- cóncavo y potencial máximo de Kantorovich. (Aquídenota el derivado de Gateaux de.)
Regularización entrópica
Considere una variante del problema discreto anterior, donde hemos agregado un término de regularización entrópica a la función objetivo del problema primario.
S t y
Se puede demostrar que el problema de la regularización dual es
donde, en comparación con la versión no regularizada, la restricción "dura" en la anterior dual () ha sido reemplazado por una penalización "suave" de esa restricción (la suma de las términos). Las condiciones de optimalidad en el problema dual se pueden expresar como
- Eq. 5.1:
- Eq. 5.2:
Denotando como el matriz de término , resolver el dual es, por tanto, equivalente a buscar dos matrices positivas diagonales y de tamaños respectivos y , tal que y . La existencia de tales matrices generaliza el teorema de Sinkhorn y las matrices se pueden calcular utilizando el algoritmo de Sinkhorn-Knopp , [16] que simplemente consiste en buscar iterativamentepara resolver la Ecuación 5.1 , ypara resolver la Ecuación 5.2 . El algoritmo de Sinkhorn-Knopp es, por tanto, un algoritmo de descenso de coordenadas en el problema dual regularizado.
Aplicaciones
El transporte óptimo de Monge-Kantorovich ha encontrado aplicaciones en una amplia gama en diferentes campos. Entre ellos están:
- Registro y deformación de imágenes [17]
- Diseño de reflector [18]
- Recuperación de información de la sombragrafía y la radiografía de protones [19]
- Tomografía sísmica y sismología de reflexión [20]
Ver también
- Métrica de Wasserstein
- Función de transporte
- Algoritmo húngaro
- Planificación del transporte
- La distancia del motor de la tierra
Referencias
- ^ G. Monge. Mémoire sur la théorie des déblais et des remblais. Histoire de l'Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année , páginas 666–704, 1781.
- ^ Schrijver, Alexander , Optimización combinatoria , Berlín; Nueva York: Springer, 2003. ISBN 3540443894 . Cf. p. 362
- ^ Ivor Grattan-Guinness, Ivor, Enciclopedia compañera de la historia y la filosofía de las ciencias matemáticas , Volumen 1, JHU Press, 2003. Cf. p.831
- ^ L. Kantorovich. Sobre la translocación de masas. CR (Doklady) Acad. Sci. URSS (NS), 37: 199-201, 1942.
- ^ Cédric Villani (2003). Temas en transporte óptimo . American Mathematical Soc. pag. 66. ISBN 978-0-8218-3312-4.
- ^ Singiresu S. Rao (2009). Optimización de la ingeniería: teoría y práctica (4ª ed.). John Wiley e hijos. pag. 221. ISBN 978-0-470-18352-6.
- ^ Frank L. Hitchcock (1941) "La distribución de un producto de varias fuentes a numerosas localidades", MIT Journal of Mathematics and Physics 20: 224-230 MR0004469 .
- ^ DR Fulkerson (1956) Problema de transporte de Hitchcock , corporación RAND.
- ^ LR Ford Jr. y DR Fulkerson (1962) § 3.1 en Flujos en redes , página 95, Princeton University Press
- ^ L. Ambrosio, N. Gigli y G. Savaré. Flujos de gradiente en espacios métricos y en el espacio de medidas de probabilidad . Conferencias de Matemáticas ETH Zürich, Birkhäuser Verlag, Basel. (2005)
- ^ Angenent, S .; Haker, S .; Tannenbaum, A. (2003). "Minimización de flujos para el problema Monge-Kantorovich". SIAM J. Math. Anal . 35 (1): 61–97. CiteSeerX 10.1.1.424.1064 . doi : 10.1137 / S0036141002410927 .
- ^ a b c Galichon, Alfred . Métodos de transporte óptimos en economía . Prensa de la Universidad de Princeton, 2016.
- ^ Rachev, Svetlozar T. y Ludger Rüschendorf. Problemas de transporte masivo: Volumen I: Teoría . Vol. 1. Springer, 1998.
- ↑ Santambrogio, Filippo. Transporte óptimo para matemáticos aplicados . Birkhäuser Basel, 2016. En particular, el capítulo 6, sección 4.2.
- ^ Aurenhammer, Franz (1987), "Diagramas de potencia: propiedades, algoritmos y aplicaciones", SIAM Journal on Computing , 16 (1): 78–96, doi : 10.1137 / 0216006 , MR 0873251.
- ^ Peyré, Gabriel y Marco Cuturi (2019), "Transporte óptimo computacional: con aplicaciones a la ciencia de datos", Fundamentos y tendencias en el aprendizaje automático: vol. 11: núm. 5-6, págs. 355-607. DOI: 10.1561 / 2200000073 .
- ^ Haker, Steven; Zhu, Lei; Tannenbaum, Allen; Angenent, Sigurd (1 de diciembre de 2004). "Transporte masivo óptimo para registro y deformación". Revista Internacional de Visión por Computador . 60 (3): 225–240. CiteSeerX 10.1.1.59.4082 . doi : 10.1023 / B: VISI.0000036836.66311.97 . ISSN 0920-5691 . S2CID 13261370 .
- ^ 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 .
- ^ 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). "Shadowgraphy cuantitativo y radiografía de protones para modulaciones de gran intensidad". Revisión E física . 95 (2): 023306. arXiv : 1607.04179 . Código bibliográfico : 2017PhRvE..95b3306K . doi : 10.1103 / PhysRevE.95.023306 . PMID 28297858 . S2CID 13326345 .
- ^ 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 de forma de onda completa" . Revista Geofísica Internacional . 205 (1): 345–377. Código bibliográfico : 2016GeoJI.205..345M . doi : 10.1093 / gji / ggw014 .
Otras lecturas
- Brualdi, Richard A. (2006). Clases de matrices combinatorias . Enciclopedia de las matemáticas y sus aplicaciones. 108 . Cambridge: Cambridge University Press . ISBN 978-0-521-86565-4. Zbl 1106.05001 .