Hispanopedia Wiki
Articulo de referencia

La regla de Bland

En optimización matemática , la regla de Bland (también conocida como algoritmo de Bland , regla anticiclónica de Bland o regla pivote de Bland ) es un refinamiento algorítmico ...

Hispanopedia WikiContenido en espanolLectura gratuita

En optimización matemática , la regla de Bland (también conocida como algoritmo de Bland , regla anticiclónica 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 simplex original parte de una solución básica factible arbitraria y luego cambia de base para disminuir el objetivo de minimización y encontrar una solución óptima. Generalmente, el objetivo disminuye en cada paso, por lo que, tras un número limitado de pasos, se encuentra una solución óptima. Sin embargo, existen ejemplos de programas lineales degenerados, en los que el algoritmo simplex original entra en un bucle infinito. Se estanca en una solución básica factible (un vértice del politopo factible ) y cambia de base de forma cíclica sin disminuir el objetivo de minimización.

La regla de Bland para elegir una columna que entra y una columna que sale de la base evita este tipo de ciclos.

La regla de Bland fue desarrollada por Robert G. Bland mientras era investigador asociado en el Centro de Investigación Operativa y Econometría en Bélgica. [ 1 ]

Algoritmo

Durante una iteración del método simplex, se utiliza la regla de Bland para decidir primero qué columna (conocida como variable de entrada ) y luego qué fila (conocida como variable de salida ) del tableau pivotar. Suponiendo que el problema consiste en minimizar la función objetivo, el algoritmo se define de forma general como sigue:

  1. Elija la columna no básica con el número más bajo (es decir, la que está más a la izquierda) y un costo negativo (reducido).
  2. Ahora, entre las filas, elija la que tenga la menor razón entre el lado derecho (transformado) y el coeficiente en la tabla dinámica donde el coeficiente sea mayor que cero. Si la razón mínima se encuentra en varias filas, elija la fila con la columna (variable) básica de menor número.

Se puede demostrar formalmente que, con la regla de selección de Bland, el algoritmo simplex nunca entra en ciclo; por lo tanto, se garantiza que terminará dentro de un tiempo limitado.

Si bien la regla del pivote de Bland es teóricamente importante, desde una perspectiva práctica, es bastante ineficiente y tarda mucho tiempo en converger (por ejemplo, el método simplex aplicado al cubo de Klee-Minty ). [ 4 ] En la práctica, se utilizan otras reglas de pivote y rara vez se produce un ciclo. [ 5 ] : 72–76

Extensiones a matroides orientados

En el contexto abstracto de los matroides orientados , la regla de Bland genera ciclos en algunos ejemplos. Jack Edmonds denominó "matroides orientados de Bland" a una clase restringida de matroides orientados en los que la regla de Bland evita los ciclos. Otra regla de pivoteo, el algoritmo de cruce , evita los ciclos en todos los programas lineales de matroides orientados. [ 6 ]

Notas

  1. 1 2 Bland (1977) .
  2. ↑ Christos H. Papadimitriou, Kenneth Steiglitz (29 de enero de 1998). Optimización combinatoria: algoritmos y complejidad . Dover Publications. págs. 53-55 . ISBN  9780486402581.
  3. ↑ Universidad de Brown - Departamento de Ciencias de la Computación (18 de octubre de 2007). "Notas sobre el algoritmo simplex" (PDF) . Consultado el 17 de diciembre de 2007 .
  4. ↑
  5. ↑ Gartner, Bernd; Matoušek, Jiří (2006). Comprensión y uso de la programación lineal . Berlín: Springer. ISBN 3-540-30697-8.: 44–48
  6. ↑ Fukuda, Komei ; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Métodos cruzados: una nueva perspectiva sobre los algoritmos de pivote" ( PDF) . Mathematical Programming, Series B. 79 ( 1–3 ) . Ámsterdam: North-Holland Publishing Co.: 369–395 . doi : 10.1007/BF02614325 . MR 1464775. S2CID 2794181 .   

Fuentes

  • Bland, Robert G. (mayo de 1977). "Nuevas reglas de pivoteo finito para el método simplex". Mathematics of Operations Research . 2 (2): 103– 107. doi : 10.1287/moor.2.2.103 . JSTOR 3689647. MR 0459599 .  
  • Murty, Kattta G. (1983). Programación lineal . Wiley.

Lecturas adicionales

  • 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. (informática)
  • 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". Mathematical Programming . 91 (3): 417– 436. doi : 10.1007/s101070100261 . S2CID 6464735 . (Encuesta por invitación, del Simposio Internacional sobre Programación Matemática).