jueves, 11 de diciembre de 2014

Correspondencia entre soluciones básicas factibles y árboles de expansión factibles (II)

Entonces, las soluciones básicas factibles se pueden obtener "resolviendo" árboles de expansión como se resume a continuación:

una solución de árbol de expansión se obtiene como sigue:

  1. Para los arcos que no están en un árbol de expansión (los arcos no básicos), se igualan a cero las variables correspondientes (xij o yij).
  2. Para los arcos que si están en el árbol de expansión (los arcos básicos), se obtienen los valores de las variables correspondientes (xij o yij) en el sistema de ecuaciones lineales dado por las restricciones de los nodos.
(En realidad, el método símplex de redes obtiene los valores de la nueva solución básica factible a partir de la actual de una manera mucho más eficiente, sin resolver este sistema de ecuaciones desde el principio.) Nótse que este proceso de solución no considera ni las restricciones de no negatividad de árbol de expansión que se obtiene puede o no ser factibles respecto a estas restricciones; esto lleva a la siguiente definición.

No hay comentarios.:

Publicar un comentario