En la optimización matemática , la regla de Bland (también conocido como el algoritmo de Bland , de las reglas anti-ciclo de Bland o regla de pivote de Bland ) es un refinamiento algorítmica del método simplex para optimización lineal .
Con la regla de Bland, el algoritmo simplex resuelve problemas de optimización lineal factibles sin ciclos. [1] [2] [3]
El algoritmo simplex original comienza con una solución factible básica arbitraria y luego cambia la base para aumentar el objetivo de maximización y encontrar una solución óptima. Por lo general, el objetivo aumenta en cada paso y, por lo tanto, después de un número limitado de pasos se encuentra una solución óptima. Sin embargo, hay ejemplos de programas lineales degenerados, en los que el algoritmo simplex original funciona para siempre. Se atasca en una solución básica factible (una esquina del politopo factible) y cambia las bases de forma cíclica sin aumentar el objetivo de maximización.
La regla de Bland evita estos ciclos al elegir una columna para ingresar la base.
La regla de Bland fue desarrollada por Robert G. Bland , ahora profesor de investigación de operaciones en la Universidad de Cornell , mientras era investigador en el Centro de Investigación de Operaciones y Econometría en Bélgica. [1]
Algoritmo
Uno usa la regla de Bland durante una iteración del método simplex para decidir primero en qué columna (conocida como la variable de entrada ) y luego en qué fila (conocida como la variable de salida ) en el cuadro pivotar. Suponiendo que el problema es minimizar la función objetivo, el algoritmo se define vagamente de la siguiente manera:
- Elija la columna no básica con el número más bajo (es decir, la más a la izquierda) con un costo negativo (reducido).
- Ahora, entre las filas, elija la que tenga la relación más baja entre el lado derecho (transformado) y el coeficiente en el cuadro dinámico donde el coeficiente es mayor que cero. Si la proporción mínima es compartida por varias filas, elija la fila con la columna (variable) básica con el número más bajo.
Se puede probar formalmente que, con la regla de selección de Bland, el algoritmo simplex nunca cicla, por lo que se garantiza que terminará en un tiempo limitado.
Si bien la regla de pivote de Bland es teóricamente importante, desde una perspectiva práctica es bastante ineficiente y lleva mucho tiempo converger. En la práctica, se utilizan otras reglas de pivote y el ciclismo casi nunca ocurre. [4] : 72–76
Extensiones a matroides orientados
En el contexto abstracto de las matroides orientadas , la regla de Bland se repite en algunos ejemplos. Una clase restringida de matroides orientados en los que la regla de Bland evita el ciclismo ha sido denominada "matroides orientados a Bland" por Jack Edmonds . Otra regla pivotante, el algoritmo entrecruzado , evita ciclos en todos los programas lineales matroides orientados. [5]
Notas
- ↑ a b Bland (1977) .
- ↑ Christos H. Papadimitriou, Kenneth Steiglitz (29 de enero de 1998). Optimización combinatoria: algoritmos y complejidad . Publicaciones de Dover. págs. 53 –55.
- ^ Universidad de Brown - Departamento de Ciencias de la Computación (2007-10-18). "Notas sobre el algoritmo simplex" (PDF) . Consultado el 17 de diciembre de 2007 .
- ^ Gärtner, Bernd; Matoušek, Jiří (2006). Comprensión y uso de la programación lineal . Berlín: Springer. ISBN 3-540-30697-8.: 44–48
- ^ Fukuda, Komei ; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Métodos entrecruzados: una nueva visión de los algoritmos de pivote" (PDF) . Programación Matemática, Serie B . Amsterdam: North-Holland Publishing Co. 79 (1–3): 369–395. doi : 10.1007 / BF02614325 . Señor 1464775 . S2CID 2794181 .
Otras lecturas
- Bland, Robert G. (mayo de 1977). "Nuevas reglas de pivote finito para el método simplex". Matemáticas de la investigación operativa . 2 (2): 103–107. doi : 10.1287 / moor.2.2.103 . JSTOR 3689647 . Señor 0459599 .
- George B. Dantzig y Mukund N. Thapa. 2003. Programación Lineal 2: Teoría y Extensiones . Springer-Verlag.
- Kattta G. Murty, Programación lineal , Wiley, 1983.
- Evar D. Nering y Albert W. Tucker , 1993, Programas lineales y problemas relacionados , Academic Press.
- M. Padberg, Optimización lineal y extensiones , segunda edición, Springer-Verlag, 1999.
- Christos H. Papadimitriou y Kenneth Steiglitz, Optimización combinatoria: algoritmos y complejidad , Reedición corregida con un nuevo prefacio, Dover. (Ciencias de la Computación)
- Alexander Schrijver , Teoría de la programación lineal y entera . John Wiley e hijos, 1998, ISBN 0-471-98232-6 (matemático)
- Michael J. Todd (febrero de 2002). "Las múltiples facetas de la programación lineal". Programación matemática . 91 (3): 417–436. doi : 10.1007 / s101070100261 . S2CID 6464735 . (Encuesta invitada, del Simposio Internacional de Programación Matemática).