Algoritmo fuera de lugar

El algoritmo fuera de lugar es un algoritmo que calcula la solución al problema de flujo de costo mínimo en una red de flujo . Fue publicado en 1961 por DR Fulkerson  ^[1] y se describe aquí. ^[2] El análogo del flujo en estado estacionario en una red de nodos y arcos puede describir una variedad de procesos. Los ejemplos incluyen sistemas de transporte y acciones de asignación de personal. Los arcos generalmente tienen parámetros de costo y capacidad. Un problema recurrente es el de intentar determinar la ruta de mínimo coste entre dos puntos de una red capacitada. La idea del algoritmo es identificar arcos fuera de lugar y modificar la red de flujo hasta que todos los arcos estén en orden y se haya alcanzado un flujo de costo mínimo. El algoritmo se puede utilizar para minimizar el costo total de un flujo restringido en una red orientada.

Algoritmo

Para empezar, el algoritmo toma un único ciclo y un conjunto de números de nodo. Luego busca arcos desequilibrados. Si no se encuentra ninguno, el algoritmo está completo. Si es necesario aumentar o disminuir el flujo para equilibrar un arco, el algoritmo buscará una ruta que aumente o disminuya el flujo respectivamente. Si no se encuentran caminos para mejorar el sistema, entonces no hay flujo viable. Esto se hace hasta que todos los arcos estén en orden, momento en el que se completa el algoritmo.

Supongamos que la red tiene n nodos y m arcos orientados. Escribimos si el arco tiene nodo inicial y nodo terminal . Sea el flujo a lo largo del arco (de nodo a nodo ). Defina y como los límites de capacidad superior e inferior del flujo en arco . Las capacidades pueden ser finitas o infinitas en algunos o todos los arcos, ya sea para los límites superior o inferior. El problema que se trata de resolver es minimizar: sujeto a: ${\displaystyle j~(i,i^{1})}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle i^{1}}$ ${\displaystyle x(j)}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle i^{1}}$ ${\displaystyle c^{-}(j)}$ ${\displaystyle c^{+}(j)}$ ${\displaystyle j}$ ${\displaystyle \sum _{j=1}^{m}d(j)x(j)}$

${\displaystyle \sum _{j:j~(i,i^{1})}x(j)-\sum _{j:j~(i^{1},i)}x(j)=0}$por cada (1) ${\displaystyle i=1,....,n}$

, y:

${\displaystyle c^{-}(j)\leq x(j)\leq c^{+}(j)}$por cada (2) ${\displaystyle j=1,....,n}$

Si un flujo dado x satisface (1), entonces el flujo se conserva en cada nodo y lo llamamos circulación. Si el flujo x satisface (2) decimos que es factible.

Complejidad

Tiempo de ejecución:

• El algoritmo termina dentro de iteraciones. ${\displaystyle O(mU)}$
• El cálculo dominante es el cálculo del camino más corto.
• El tiempo de ejecución total es: ${\displaystyle O(m^{2}U+mUn\log(n))}$

Referencias

1. DR Fulkerson (marzo de 1961). "Un método fuera de lugar para problemas de flujo de costo mínimo". Revista de la Sociedad de Matemáticas Industriales y Aplicadas . 9 (1): 18–27. JSTOR  2099013.
2. Durbin, EP; Kroenke, DM (diciembre de 1967). El algoritmo fuera de lugar: una introducción - Memorando RM-5472-PR (PDF) . Santa Mónica, California, Estados Unidos: The Rand Corporation . Consultado el 16 de enero de 2018 .

^[1]

enlaces externos

• Algoritmo fuera de lugar en YouTube (en español)

1. Cambridge, Universidad de (julio de 2012). "Algoritmo fuera de kilter" (PDF) . www.maths.cam.ac.uk .