Formulación de programación lineal (I)

Para tomar en cuenta el tiempo de terminacion del proyecto en la formulación de programación lineal del problema, se necesita una variable más para cada evento. Esta variable adicional es:

yk = tiempo más próximo (desconocido) para el evento k, el cual es una función deterministica de xij.

Cada yk es una variable auxiliar, es decir, una variable que se introduce al modelo por ser conveniente en la formulación y que no representa una decisión. El método símplex trata a las variables auxiliares igual que a las variables de decisión (xij) normales.

Para ver como se introducen las yk a la formulación, considérese el evento 7 de la figura 10.27. Por definición, su tiempo más proximo es

por lo que estas dos restricciones se pueden incorporar directamente a la formulación de programación lineal (déspues de pasar y7 al lado izquierdo para obtener la forma apropiada). Aún más, adelante se verá por qué la solución óptima que se obtiene con el método símplex para el modelo completo hará de manera automática que el valor de y7 sea la cantidad más pequeña que satisface estas restricciones, por lo que no se necesitan más restricciones para incorporar la definición de y7 al modelo.