Incorporación de la técnica de la cota superior (I)

El primer concepto es incorporar la técnica de la cota superior presentada enla sección 9.1, para manejar con eficiencia las restricciones de capacidad de arco xij ≤ uij. Así, ej lugar de tratar estas restricciones como restricciones funcionales, se manejan como restricciones de no negatividad. Por lo tanto, se toman encuenta sólo al determinar la variable básica que sale. En particular, conforme se hace crecer la variable básica entrante, la variable básica que sale es la primera variable básica que llega, ya sea a su cota inferior (0) o bien a su cota superior (uij). xij = uij - yij, sustituye a una variable no básica en su cota superior xuj = uij, de manera que yij = 0 se convierte en la variable no básica. Véanse en la sección 9.1 más detalles.

En el contexto actual, yij tiene una interpretación interesante en la red. Siempre que yij se convierta en una variable básica con valor estrictamente positivo (≤ uij), se puede pensar en este vapor como en un flujo del nodo j al nodo i (o sea en la dirección "equivocada', a través del arco i→j) que en la actualidad cancela la cantidad del flujo previamente asignado (xij =uij) del nodo i al nodo j. Así, si xij = uij - yij sustituye a xij = uij, también se está sustituyendo el arco real i→j por su arco inverso j→i, en donde este nuevo arco tiene capacidad uij (la cantidad máxima del flujo xij= uij que se puede cancelar) y costo unitario -cij (ya que cada unidad de flujo cancelada ahorra cij). Para reflejar el flujo de xij = uij a través del arco eliminado, se cambia esta cantidad de flujo neto generada del nodo i al nodo j disminuyendo bi en uij unidades e incrementando bi en uij unidades. Después, si la yij se convierte en la variable básica que sale llegando a su cota superior, yij = uij se reemplaza por yij = uij - xij, con xij = 0 como la nueva variable no básica, con lo que el proceso anterior se invierte (el arco  j→i se sustituye por el arco i→j, etc. ) para regresar a la configuración original.