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.

Formulación de programación lineal (III)

Nótese también que ΣKij es una constante fija que puede eliminarse de la función objetivo, de manera que minimizar el costo directo total para el proyecto es equivalente (véase la sección 4.6) a maximizar Σ(-Sij)xij. Por tanto, el problema de programación lineal es encontrar las xij (y las yk correspondientes) tales que

Formulación de programación lineal (II)

Dentro del proceso e incorporación de estas restricciones para todos los eventos, se tiene que cada variable xij aparecerá en exactamente una restricción de este tipo,

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.

Método CPM para trueques entre tiempo y costo (III)

Entonces existe una variable de decisión xij para cada actividad, pero no hay para los valores de i y j que no tienen una actividad correspondiente.

Para expresar el costo directo de la actividad (i,j) como una función (lineal) de xij, denótese la pendiente de la línea que pasa por los puntos normal y de quiebre para la actividad (i,j) por

Método CPM para trueques entre tiempo y costo (II)

El objetivo fundamental del CPM es determinar el trueque entre el tiempo y costo que debe emplearse en cada actividad para cumplir con el tiempo de terminación del proyecto que se programó a un costo mínimo. Una forma de determinar la combinación óptima de tiempo y costo es aplicar programación lineal. Para describir esto, es necesario introducir notación nueva, parte de la cual se resume en la figura 10.30. Sea.

Método CPM para trueques entre tiempo y costo (I)

Las versiones originales de CPM y PERT difieren en dos aspectos importantes. Primero, el CPM supone que los tiempos de las actividades son deterministicos (es decir, se pueden predecir de manera confiable sin incertidumbre significativa), por lo que no necesita las tres estimaciones que se acaban de describir. Segundo, en lugar de dar una importancial primordial al tiempo (explicitamente), el CPM asigna la misma importancia al tiempo y al costo y se pone esto de relieve al construir una curva de tiempo-costo para cada actividad, como la que se muestra en la figura 10.30. Esta curva representa la relación entre el costo directo presupuestado para la actividad y su tiempo de duración resultante. Por lo general, la gráfica se basa en dos puntos: el normal y el intensivo de quiebre. El punto normal da el costo y el tiempo necesarios cuando la actividad se realiza en la forma normal, sin incurrir en costos adicionales (horas extra de mano de obra, equipo o materiales especiales para ahorrar tiempo, etc.), para celerar la actividad. Por el contrario, el punto de quiebre proporciona el tiempo y el costo necesarios cuando se realiza la actividad en forma intensiva o de quiebre; esto es, se acelera completamente sin reparar costos, con el fin de reducir su tiempo de duración lo más que se pueda. Como una aproximación, se supone entonces que todos los trueques intermedios entre tiempo y costo son posibles y que se encuentran sobre el segmento de línea que une estos dos puntos (obsérvese el segmento de línea oscuro en la figura 10.30). Así, las únicas estimaciones que tiene que obtener el personal del proyecto son el costo y el tiempo para estos dos puntos.