Tarea de transporte

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 3 de junio de 2021; la verificación requiere 1 edición .

El problema del transporte ( el problema de Monge-Kantorovich ) es un problema matemático de programación lineal de un tipo especial. [1] [2] Puede ser visto como un problema del plan óptimo para el transporte de mercancías desde los puntos de partida hasta los puntos de consumo, con costos de transporte mínimos.

De acuerdo con la teoría de la complejidad computacional, el problema de transporte está incluido en la clase de complejidad P. Cuando el volumen total de ofertas (bienes disponibles en los puntos de partida) no es igual al volumen total de demanda de bienes (bienes) solicitados por los puntos de consumo, el problema del transporte se denomina desequilibrado ( abierto ).

Planteamiento del problema

El problema del transporte (clásico) es el problema del plan óptimo para transportar un producto homogéneo desde puntos homogéneos de disponibilidad a puntos homogéneos de consumo en vehículos homogéneos (cantidad predeterminada) con datos estáticos y un enfoque lineal (estas son las principales condiciones del problema).

Para la tarea de transporte clásica se distinguen dos tipos de tareas: el criterio de costo (lograr un mínimo de costos de transporte) o distancias y el criterio de tiempo (se dedica el mínimo tiempo al transporte). Bajo el nombre de problema de transporte se define una amplia gama de problemas con un solo modelo matemático, estos problemas están relacionados con problemas de programación lineal y pueden ser resueltos por el método óptimo. Sin embargo, un método especial para resolver un problema de transporte puede simplificar significativamente su solución, ya que el problema de transporte se desarrolló para minimizar el costo de transporte.

Formulación matemática del problema

La carga homogénea se concentra en los proveedores en volúmenes . Esta carga debe ser entregada a los consumidores en volúmenes . - el costo de transportar bienes desde el proveedor hasta el consumidor . Se requiere elaborar un plan de transporte que le permita exportar completamente los productos de todos los fabricantes, satisfaga completamente las necesidades de todos los consumidores y otorgue un mínimo de costos totales de transporte. Denotar como el volumen de transporte desde el proveedor hasta el consumidor . [3] $metro$ ${\displaystyle a_{1},a_{2},....a_{m))$ $norte$ ${\displaystyle b_{1},b_{2},....b_{n))$ $c_{ij}$ $i$ $j$ $x_{ij}$ $i$ $j$

{\displaystyle \sum _{j=1}^{n}x_{ij}=a_{i))

{\ estilo de visualización i = 1,2,...,m}

{\ estilo de visualización \ suma _ {i = 1} ^ {m} x_ {ij} = b_ {j}}

{\ estilo de visualización j = 1,2,...,n}

\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}\rightarrow \min

Historia de la búsqueda de métodos de solución

El problema fue formalizado por primera vez por el matemático francés Gaspard Monge en 1781 [4] . El matemático y economista soviético Leonid Kantorovich [5] logró avances en la solución del problema durante la Gran Guerra Patriótica . Por lo tanto, a veces este problema se denomina problema de transporte de Monge-Kantorovich .

Métodos de solución

El problema de transporte clásico puede resolverse por el método símplex , pero debido a una serie de características puede resolverse de forma más sencilla (para problemas de baja dimensión).

Las condiciones del problema se colocan en la tabla, ingresando en las celdas la cantidad de carga transportada de a carga , y en celdas pequeñas, las tarifas correspondientes . $Ai}$ $b_j$ $X_{ij}\geqslant0$ ${\ Displaystyle C_ {ij}}$

Mejora iterativa del plan de transporte

Encontrar la línea de base

Se requiere determinar el plan básico y, a través de operaciones sucesivas, encontrar la solución óptima. El plan de referencia se puede encontrar mediante los siguientes métodos: "esquina noroeste" , "elemento mínimo" , doble preferencia y aproximación de Vogel .

Método de esquina noroeste (diagonal o mejorado)

En cada etapa, la celda superior izquierda del resto de la tabla se llena con el máximo número posible. Llenar de tal manera que la carga se elimine por completo o la necesidad quede completamente satisfecha . $Ai}$ $b_j$

Método de elementos mínimos

Una forma de resolver el problema es el método del elemento mínimo (más pequeño) . Su esencia radica en minimizar la redistribución lateral de bienes entre los consumidores.

Algoritmo:

De la tabla de valores, se selecciona el costo más bajo y se ingresa el mayor de los números en la celda que le corresponde.
Las filas de proveedores se verifican para una fila con inventario usado y las columnas de clientes para una columna cuyos requisitos se satisfacen por completo. Tales columnas y filas no se consideran más.
Si no todos los consumidores están satisfechos y no todos los proveedores han agotado los bienes, regrese al paso 1, de lo contrario, el problema está resuelto.

Iteraciones

Después de encontrar el plan de transporte básico, debe aplicar uno de los algoritmos para su mejora, acercándose al óptimo.

Método de caída de piedras
Método de los potenciales .

Solución de teoría de grafos

Consideramos un gráfico bipartito en el que los puntos de producción están en la parte superior y los puntos de consumo en la parte inferior. Los puntos de producción y consumo están conectados en pares por bordes de rendimiento infinito y precio por unidad de flujo . ${\ Displaystyle C_ {ij}}$

La fuente está unida artificialmente al lóbulo superior . La capacidad de los bordes desde la fuente hasta cada punto de producción es igual al stock de producto en ese punto. El costo por unidad de flujo de estos bordes es 0.

Del mismo modo, se une al drenaje del lóbulo inferior . El rendimiento de las costillas desde cada punto de consumo hasta el fregadero es igual a la demanda del producto en ese punto. El costo por unidad de flujo para estos bordes también es 0.

A continuación, se resuelve el problema de encontrar el flujo máximo del costo mínimo ( mincost maxflow ). Su solución es similar a encontrar el caudal máximo en el algoritmo de Ford-Fulkerson . Sólo en lugar del flujo complementario más corto, se busca el más barato. En consecuencia, esta subtarea no utiliza la búsqueda en amplitud , sino el algoritmo Bellman-Ford . Cuando se devuelve un flujo , el costo se considera negativo.

El algoritmo "mincost maxflow" se puede ejecutar de inmediato, sin encontrar una línea de base. Pero en este caso, el proceso de decisión será algo más largo. La ejecución del algoritmo “mincost maxflow” tiene lugar en no más que operaciones. ( es el número de aristas, es el número de vértices). Con datos seleccionados al azar, generalmente se requiere mucho menos: el orden de las operaciones. $O(v^{2}e^{2})$ $mi$ $v$ $O(ve)$

Al resolver un problema de transporte desequilibrado, se utiliza una técnica para equilibrarlo. Para ello, introduce destinos o salidas ficticias. La implementación del problema de equilibrio del transporte es necesaria para poder aplicar el algoritmo de solución basado en el uso de tablas de transporte.

Generalizaciones

El problema del transporte en la configuración de la red

En esta variante, los puntos no se dividen en puntos de partida y puntos de consumo, todos los puntos son iguales, pero la producción viene dada por un número positivo y el consumo por uno negativo. El transporte se lleva a cabo en una red determinada, en la que los arcos pueden conectar cualquier punto, incluidos productor-productor, consumidor-consumidor.

El problema se resuelve mediante un método de potenciales ligeramente modificado , prácticamente igual que el ajuste clásico.

Problema de transporte con restricciones de ancho de banda

Una variante del problema de transporte en una configuración de red, en la que se especifica el rendimiento máximo de algunos arcos.

El problema se resuelve mediante un método de potenciales un poco complicado .

Problema de transporte multiproducto

Una variante de una tarea de transporte en la que hay varios productos (los puntos pueden producir/consumir varios productos). Para algunos arcos, se establece un límite de rendimiento (sin este límite, la tarea se divide en tareas separadas por producto).

El problema se resuelve por el método simplex (se usa la expansión de Danzig- Wulf, los problemas de transporte de un solo producto se usan como subtareas).

Notas

↑ A. V. Kuznetsov, N. I. Kholod, L. S. Kostevich. Una guía para la resolución de problemas en programación matemática . - Minsk: Escuela Superior , 1978. - S. 110.
↑ Diccionario de cibernética / Editado por el académico V. S. Mikhalevich . - 2do. - Kyiv: Edición principal de la Enciclopedia soviética ucraniana que lleva el nombre de M. P. Bazhan, 1989. - 751 p. - (C48). — 50.000 copias. - ISBN 5-88500-008-5 .
↑ Korbut, 1969 , pág. 28
↑ Monge G. Mémoire sur la théorie des deblais et de 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.
↑ Kantorovich L. Sobre la translocación de masas // CR (Doklady) Acad. ciencia URSS (NS), 37:199-201, 1942.

Enlaces

tarea de transporte
Algoritmos para encontrar el caudal máximo
http://kb.mista.ru/article.php?id=859 Solución del problema de transporte en 1C:Enterprise 8.2

Literatura

Korbut A.A. , Finkelstein Yu.Yu. Programación discreta. - M. : Nauka, 1969. - 368 p.