En optimización matemática , el algoritmo de red simplex es una especialización teórica de grafos del algoritmo simplex . El algoritmo generalmente se formula en términos de un problema de flujo de costo mínimo . El método simplex de red funciona muy bien en la práctica, normalmente de 200 a 300 veces más rápido que el método simplex aplicado a un programa lineal general de las mismas dimensiones. [ cita requerida ]
Historia
Durante mucho tiempo, la existencia de un algoritmo simplex de red demostrablemente eficiente fue uno de los principales problemas abiertos en la teoría de la complejidad, aunque se disponía de versiones eficientes en la práctica. En 1995, Orlin proporcionó el primer algoritmo polinomial con tiempo de ejecución de dónde es el costo máximo de cualquier borde. [1] Más tarde Tarjan mejoró esto parautilizando árboles dinámicos en 1997. [2] Los algoritmos símplex de red dual fuertemente polinomiales para el mismo problema, pero con una mayor dependencia del número de aristas y vértices en el gráfico, se conocen desde hace más tiempo. [3]
Descripción general
El método de red simplex es una adaptación del algoritmo simplex primario de variable acotada. La base se representa como un árbol de expansión enraizado de la red subyacente, en el que las variables están representadas por arcos y los multiplicadores simplex por potenciales de nodo. En cada iteración, una variable entrante es seleccionada por alguna estrategia de precios, basada en los multiplicadores duales (potenciales de nodo), y forma un ciclo con los arcos del árbol. La variable saliente es el arco del ciclo con el menor flujo creciente. La sustitución del arco entrante por el saliente y la reconstrucción del árbol se llama pivote. Cuando no queda ningún arco no básico elegible para ingresar, se ha alcanzado la solución óptima.
Aplicaciones
El algoritmo de red simplex se puede utilizar para resolver muchos problemas prácticos, entre ellos, [4]
- Problema de transbordo
- Problema de transporte de Hitchcock
- Problema de asignación
- Cadenas y antichains en conjuntos parcialmente ordenados
- Sistema de representantes distintos
- Cubiertas y emparejamiento en gráficos bipartitos
- Problema de catering
Referencias
- ↑ Orlin, James B. (1 de agosto de 1997). "Un algoritmo simplex de red primal de tiempo polinomial para flujos de costo mínimo". Programación matemática . 78 (2): 109-129. doi : 10.1007 / BF02614365 . hdl : 1721,1 / 2584 . ISSN 0025-5610 .
- ^ Tarjan, Robert E. (1 de agosto de 1997). "Árboles dinámicos como árboles de búsqueda mediante euler tours, aplicados al algoritmo de red simplex". Programación matemática . 78 (2): 169-177. doi : 10.1007 / BF02614369 . ISSN 0025-5610 .
- ^ Orlin, James B .; Plotkin, Serge A .; Tardos, Éva (junio de 1993), "Algoritmos polinomiales de red dual simplex", Programación matemática , 60 (1–3): 255–276, CiteSeerX 10.1.1.297.5730 , doi : 10.1007 / bf01580615
- ^ Chvatal, Vasek (1983). "20" . Programación lineal . Macmillan. págs. 320–351 . ISBN 9780716715870.
enlaces externos
- Solución de problemas de red La sección 14, p B-113 muestra un ejemplo de ejecución