En optimización matemática , la regla de Bland (también conocida como algoritmo de Bland , regla anticíclica de Bland o regla pivote de Bland ) es un refinamiento algorítmico del método simplex para la 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 símplex original comienza con una solución factible básica arbitraria y luego cambia la base para disminuir el objetivo de minimización y encontrar una solución óptima. Por lo general, el objetivo disminuye 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 símplex original se repite indefinidamente. Se queda estancado en una solución factible básica (una esquina del politopo factible) y cambia las bases de manera cíclica sin disminuir el objetivo de minimización.
Estos ciclos se evitan mediante la regla de Bland, que consiste en elegir una columna para entrar y una columna para salir de la base.
La regla de Bland fue desarrollada por Robert G. Bland , ahora profesor emérito 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]
Se utiliza la regla de Bland durante una iteración del método símplex para decidir primero en qué columna (conocida como variable de entrada ) y luego en qué fila (conocida como variable de salida ) de la tabla pivotar. Suponiendo que el problema es minimizar la función objetivo, el algoritmo se define de forma general de la siguiente manera:
Se puede demostrar formalmente que, con la regla de selección de Bland, el algoritmo simplex nunca es cíclico, por lo que se garantiza que terminará en un tiempo acotado.
Si bien la regla de pivote de Bland es teóricamente importante, desde una perspectiva práctica es bastante ineficiente y tarda mucho tiempo en converger. En la práctica, se utilizan otras reglas de pivote y casi nunca se produce el ciclo. [4] : 72–76
En el contexto abstracto de los matroides orientados , la regla de Bland se repite en algunos ejemplos. Una clase restringida de matroides orientados en la que la regla de Bland evita los ciclos ha sido denominada "matroides orientados de Bland" por Jack Edmonds . Otra regla de pivote, el algoritmo criss-cross , evita los ciclos en todos los programas lineales de matroides orientados. [5]