Selección de la variable básica entrante (I)

Para comenzar una iteración del método símplex de redes, recuérdese que el criterio del método símplex estándar para elegir la variable básica entrante es escoger la variable no básica que, al aumentar su valor, mejore el valor de Z más rápido. Ahora se verá cómo se hace esto sin tener tabla símplex.

A manera de ilustración, considérese la variable no básica xAC en la solución inicial básica factible, es decir, el arco no básico A→C. Aumentar xAC a algún valor θ significa que debe agregarse a la red el arco A→C con flujo θ que se muestra en la figura 10.16. Si se agrega un arco no básico a un árbol de expansión, siempre se crea un ciclo no dirigido único; el ciclo en este caso se ve en la figura 10.17 como AC-CE-DE-AD. La figura 10.17 muestra también el efecto de agregar el flujo θ al arco A→C sobre los otros flujos en la red. En particular, el flujo aumenta en  θ en los arcos que tienen la misma dirección que A→C  en el ciclo (el arco C→E), mientras que el flujo neto disminuye en θ para otros arcos cuya dirección es opuesta a    A→C en el ciclo (los arcos D→E y A→D). En este último caso, el nuevo flujo, en efecto, cancela un flujo de θ en la dirección opuesta. El nuevo flujo θ no afecta los arcos que no están en el ciclo (B→C).