Cpm

 CPM 

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 importancia primordial al tiempo (explícitamente), el CPM asigna la misma importancia al tiempo y al costo y pon esto de relieve al construir un a curva de tiempo-costo para cada actividad, con la que se muestra en la figura 4. Esta curva representa la relación entre el costo directo presupuestado para la actividad y su tiempo de duración resultante. Figura 4. Curva tiempo-costo para la actividad (i,j). Por lo general la grafica se basa en dos puntos: el normal y el intensivo o de quiebre. El punto normal da el costo y el tiempo necesario cuando la actividad se realiza en la forma normal, sin incurrir en costos adicionales (horas extras de mano de obra, equipo o materiales especiales para ahorrar tiempo, etc.), Para acelerar la actividad. Por el contrario, el punto de quiebre proporciona el tiempo y el costo necesario cuando se realiza la actividad en forma intensiva o de quiebre, esto es se acelera completamente sin reparar en costos, con el fin de reducir su tiempo de duración lo mas que se pueda. Como una aproximación, se supone entonces que todos los trueques intermedios entre tiempo y costos son posibles y que se encuentran sobre el segmento de línea que une a estos dos puntos. (Obsérvese en el segmento de línea oscuro en la Fig. 4). Así, las únicas estimaciones que tienen que obtener el personal del proyecto son el costo y el tiempo para estos dos puntos. El objetivo fundamental del CPM es determinar el trueque entre tiempo y costo que debe emplearse en cada actividad para cumplir con el tiempo de terminación del proyecto que se programo a un costo mínimo. Una forma de determinar la combinación optima del tiempo y costo es aplicar programación lineal. para descubrir esto, es necesario introducir notación nueva, parte de la cual se resume en la figura 4. Sea Dij = tiempo normal para la actividad (i , j) C Dij? = costo (directo) normal para la actividad (i , j) dij = tiempo de quiebre para la actividad (i , j) Cdij = costo (directo) de quiebre para la actividad (i , j) Las variables de decisión para el problema son xij donde xij = tiempo de duración de la actividad (i , j)

Entonces existe una varible de decisión xij para cada actividad, pero no lo hay par alos 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 Xjj denótese la pendiente de la línea que pasa por los puntos normal y de quiebre para la actividad (i , j) por

tambien definase Kij como la intersección con el eje del costo directo de esta linea, com se muestra en la fig. 4, por tanto, costo directo de la actividad (i , j) = Kij + Sij xij, en consecuencia,

costo directo total del proyecto = en donde la sumatoria se extiende sobre todas las actividades (i , j). Ahora se puede establecer y formular matemáticamente el problema. El problema: dado un tiempo T (máximo) de terminación del proyecto, selecciónese la xjj que minimice el costo directo total del proyecto. Formulación De Programación Lineal. Para tomar en cuenta el tiempo de terminación 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 determinística 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 simplex trata a las variables auxiliares igual que a las variables de decisión (xij ) normales. Para ver cómo se introducen las yk a la formulación, considérese el evento 7 de la figura 1 Por definición, su tiempo más próximo es: y7 = máx {y4 + x47, y5 + x57}, En otras palabras y7 es la cantidad más pequeña tal que las dos restricciones siguientes se cumplen:

y4 + x47 < y7

y5 + x45 < y7,

por lo que estas dos restricciones se pueden incorporar directamente a la formulación de programación lineal (después 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 simples 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. 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,

que se puede expresar en la forma apropiada como

Para continuar con los preparativos para escribir el modelo completo de programación lineal, se etiquetan Evento 1 = inicio del proyecto Evento n = terminación del proyecto, con lo que

=0

= tiempo de terminación. .

Nótese también que 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 a maximizar Por tanto, el problema de programación lineal es encontrar las (y las correspondientes) tales que

Maximizar

Sujeta a:

 Para todas las actividades (i , j)

Desde un punto de vista computacional, este modelo se puede mejorar algo al sustituir todas las por

en todo el modelo, para que el primer conjunto de restricciones funcionales () se sustituya por las restricciones de no negatividad

Es conveniente también introducir restricciones de no negatividad para el resto de las variables:

aunque estas variables ya estaban forzadas a ser no negativas al establecer y1 = 0, debido a

las restricciones y

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 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 al modelo mediante las restricciones , con el fin de proporcionar los tiempos más próximos para los respectivos eventos (dados los valores de las en la solución básica factible actual). Como los tiempos más próximos se tienen que obtener en orden, todas estas son necesarias nada más para obtener finalmente el valor correcto de (para los valores actuales de las ), reforzando así la restricción . Sin embargo, obtener el valor correcto requiere que el valor de cada (incluso el de ) sea la cantidad más pequeña que satisface todas las restricciones . Ahora se hará una descripción breve de por qué (en circunstancias normales) esta propiedad se cumple para una solución óptima.

Considérese una solución para las variables tal que toda trayectoria de la red es crítica y requiere un tiempo T. Si los valores de las satisfacen la propiedad anterior, entonces las son los verdaderos tiempos más pr6ximos con exactamente y la solución completa para las y satisface todas las restricciones. Sin embargo, si alguna se hace un poco más grande, esto crearía una reacción en cadena en la que alguna se tendría que hacer un poco más grande para satisfacer todavía las restricciones etc., hasta que en última instancia, deba hacerse un poco más grande y se viole la restricción. La única manera de evitar esto con una un poco más grande, es hacer que los tiempos de duración de algunas actividades (posteriores al evento i) sean un poco más pequeñas, aumentando con esto el costo. Por lo tanto, una solución óptima evitará que las sean más grandes de lo necesario para satisfacer las restricciones .

El problema, como se estableció aquí, supone que se ha fijado una fecha de entrega específica T (tal vez por contrato) para la terminación del proyecto. En realidad, algunos proyectos no tienen una fecha de entrega, en cuyo caso no está claro el valor que debe asignarse a T en la formulación de programación lineal. En este tipo de situaciones, la decisión sobre T (que resulta ser la duración del proyecto en la solución óptima), de hecho depende de cuál es el mejor trueque entre el costo total y el tiempo total del proyecto. La información básica que se necesita para tomar esta decisión es cómo cambia el costo directo total mínimo al cambiar el valor de T en la formulación anterior, como se muestra en la figura 5. Esta información se puede obtener cuando se usa progranlflci6n lineal parametrica para obtener la solución óptima como una funci6n de T en todo el intervalo. Existen procedimientos aún más eficientes, para obtener esta información, que explotan la estructura especial del problema. La figura 5 proporciona una base útil para la toma de decisiones del administrador sobre el valor de T (y la solución óptima correspondiente para) cuando los efectos importantes de la duración del proyecto (distintos a los costos directos) son en esencia intangible. Ahora bien, cuando estos otros efectos que son básicamente financieros (costos indirectos ), es apropiado combinar la curva del costo directo total de la figura 5 con una curva de costo indirecto total mínimo (supervisión, instalaciones, intereses, multas contractuales) contra t, como se muestra en la figura 6. La suma de estas curvas proporcionará la curva del costo total mínimo del proyecto para distintos valores de T. El valor óptimo de T será entonces aquél que minimice esta curva de costo total.