jueves, 31 de octubre de 2013

Empate para la variable básica que sale - degeneración

Ahora supóngase que el empate ocurre entre dos o más variables básicas al elegir la variable que sale en la parte 2 del paso iterativo. Importa cúal se escoge? En teoría, sí, y en una forma crítica debido a que puede ocurrir las siguientes sucesión de eventos. Primero, todas las variables empatadas se hacen cero al mismo tiempo cuando aumenta el valor de la variable entrante. Por tanto aquellos que no se eligieron como variable básica que sale también tendrán un valor de tanto, aquellas que no se eligieron como variable básica que sale también tendrán un valor de cero en la nueva solución básica factible. Segundo si una de estas variables básicas degeneradas sigue con valor de cero hasta que se selecciona como variable básica que sale en una iteración posterior, la variable básica entrante deberá también quedar con valor de cero (ya que no puede crecer sin que la variable básica que sale se vuelva negativa), entonces el valor de Z permanecerá sin cambio. Tercero, si Z permanece igual en lugar de mejorar cada iteración, el método símplex puede caer en un ciclo que repite la misma secuencia de soluciones periódicamente, en lugar de aumentar en algún momento para llegar a la solución óptima. De hecho, se han construido ejemplos artificiales que se quedan atrapados en un ciclo perpetuo de este tipo.

Por fortuna, aunque en teoría es posible que haya ciclos perpetuos, ha sido en extremo raro que tengan lugar en problemas prácticos. Si ocurriera un ciclo siempre se puede salir de el cambiando la elección de la variable básica que sale. Aún más, se han dado reglas especiales para romper empates que siempre evitan los ciclos. Sin embargo, estas reglas prácticamente se han ignorado en las aplicaciones reales, y no se repetirán en este texto. Para los propósitos del lector, se recomienda romper los empates arbitrariamente y seguir el proceso sin preocuparse de las variables degeneradas que pueden resultar.

No hay comentarios.:

Publicar un comentario