Formulación de programación lineal (IV)

Una propiedad interesante de una solución óptima para este modelo es que (en circunstancias normales) toda trayectoria de la red será una ruta crítica que requiere un tiempo T. La razón es que una solución de este tipo satisface las restricciones yn ≤ T, mientras que evita los costos adicionales en que se incurre por acortar el tiempo de cualquier trayectoria.

La clave de esta formulación es la manera en que se introducen las yk al modelo mediante las restricciones yi + xij - yi ≤ 0, con el fin de proporcionar los tiempos más proximos para los respectivos eventos (dados los valores de las xij en la solución básica factible actual). Como los tiempos más próximos se tienen que obtener en orden, todas estas yk son necesarias nada más para obtener finalmente el valor correcto de yn (para los valores actuales de las xij) reforzando así la restricción yn ≤ T. Sin embargo, obtener el valor correcto requiere que el valor de cada yj (incluso el de yn) sea la cantidad más pequeña que satisface todas las restricciones yi + xij ≤ yj. Ahora se hará una descripción breve de por qué (en circunstancias normales) esta propiedad cumple para una solución óptima.