Conclusiones PERT y CPM (II)

Al mismo tiempo que todos estos modelos se ocupan de optimizar la operación de una red existente, el problema del árbol de mínima expansión es un ejemplo sobresaliente de un modelo para optimizar el diseño de una nueva red.

Este capítulo apenas ha tocado la superficie de lo que hasta la fecha se ha desarrollado en el campo de la metodología de redes. Por su naturaleza combinatoria, con frecuencia los problemas de redes son difíciles de resolver, pero se han hecho grandes avances en el desarrollo de técnicas poderosas de modelado y de metodologías de solución que incluso amplían el panorama de nuevas e importantes aplicaciones. De hecho, los nuevos algoritmos han permitido resolver aplicaciones. De hecho, los nuevos algoritmos han permitido resolver con éxito algunos problemas complejos de redes de gran tamaño.

La técnica de redes más utilizada ha sido la de sistemas tipo PERT para la planeación y el control de proyectos. Ha resultado una herramienta valiosa  en la organización de la planeación al probar diferentes opciones, revelar las dimensiones globales y los detalles del plan del proyecto, establecer las responsabilidades gerenciales bien entendidas e identificar en forma realista lo que se puede esperar del proyecto. También establece las bases para que la gerencia tome acciones anticipadas contra posibles problemas durante el desarrollo del proyecto. Aunque no es una panacea, ha sido una gran ayuda para el administrador en numerosas ocasiones.

Conclusiones PERT y CPM (I)

Las redes de ciertos tipos surgen en una amplia variedad de contextos. Las representaciones de redes son muy útiles para visualizar las relaciones y conexiones entre las componentes del sistema. Con frecuencia debe mandarse un flujo de algún tipo a través de la red y es necesario tomar una decisión sobre la mejor manera de hacerlo. En este capítulo se introdujeron dos tipos de modelos y algoritmos de optimización de redes que constituyen una herramienta poderosa para tomar tales decisiones.

El problema del flujo de costo mínimo juega un papel central entre estos nuevos modelos de optimización de redes, tanto por ser una aplicación tan extensa como porque se pueden resolver con gran eficiencia por el método símplex de redes. Dos de sus casos especiales, incluidos en este capítulo, el problema de la ruta más corta y el problema del flujo máximo, también son modelos importantes de optimización de redes, al igual que los otros tres casos especiales presentados en el capítulo 7 (el problema de transporte, el problema de trasbordo y el problema de asignación).

Elección entre PERT y CPM

La elección entre el enfoque de las tres estimaciones de PERT y el método de trueques entre el tiempo y el costo del CPM depende fundamentalmente del tipo de proyecto y de los objetivos gerenciales. El PERT es en particular apropiado cuando se maneja mucha incertidumbre al predecir los tiempos de las actividades y cuando es importante controlar de una manera efectiva la programación del proyecto; por ejemplo, la mayor parte de los proyectos de investigación  y desarrollo caen dentro de esta categoría. Por otro lado, el CPM resulta muy apropiado cuando se pueden predecir bien los tiempos de las actividades (quizá con base en la experiencia) y cando estos tiempos se pueden ajustar con facilidad (por ejemplo, si se cambian tamaños de brigadas), al igual que cuando es importante planear una combinación apropiada entre el tiempo y el costo del proyecto. Este último tipo lo representan muchos proyectos de cosntrucción y mantenimiento.

En la actualidad, las diferencias entre las versiones actuales de PERT y CPM no son marcadas como se han descrito. Muchas versiones de PERT permiten emplear una sola estimación (la más probable) para cada actividad y omiten así la investigación probabilística. Una versión llamada PERT/Costo considera también combinaciones de tiempo y costo en forma parecida al CPM.

Formulación de programación lineal (VII)

La figura 10.31 proporciona una base útil para la toma de decisiones del administrador sobre el valor de T (y la solución óptima correspondiente para xij), cuando los efectos importantes de la duración del proyecto (distintos a los costos directos) son en esencia intangibles. 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 10.31 con una curva de costo indirecto total mínimo (supervisión, instalaciones, intereses, multas contractuales) contra t, como se muestra en la figura 10.32. 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.

Formulación de programación lineal (VI)

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 10.31, Esta información se puede obtener cuando se usa programación lineal paramétrica para obtener la solución óptima como una función 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.

Formulación de programación lineal (V)

Considérese una solución para las variables xij tal que toda trayectoria de la red es crítica y requiere un tiempo T. Si los valores de las yk satisfacen la propiedad anterior, entonces las yk son los verdaderos tiempos más próximos con yn = T exactamente y la solución completa para las xij y yk satisface todas las restricciones. Sin embargo, si alguna yi se hace un poco más grande, esto crearía una reacción en cadena en la que alguna yj se tendría que hacer un poco más grande para satisfacer todavía las restricciones yi + xij ≤ yj, etc., hasta que en última instancia, yn debe hacerse 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 yk sean más grandes de lo necesario para satisfacer las restricciones yi + xij ≤ yj.

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 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.

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.

Enfoque de tres estimaciones de PERT (V)

La tercera suposición es que el tiempo del proyecto tiene una distribución normal. La lógica de esta suposición es que este tiempo es la suma de muchas variables aleatorias independientes y la versión general del teorema del límite central implica que la distribución de probabilidad de tal suma es aproximadamente normal en diversas condiciones. Entonces, dadas la media y la variancia, es sencillo encontrar la probabilidad de que esta variable aleatoria normal (tiempo del proyecto) sea menor que el tiempo de terminación programado.

Como ejemplo supóngase que el proyecto de construcción de una casa de la figura 10.27 se programa para terminarse en 50 días hábiles y que tanto el valor esperado como la variancia de los tiempos de cada actividad resultaron ser iguales a las estimaciones dadas en la figura 10.28. Entonces, al sumar las cantidades (por separado) sobre una ruta crítica, los dos, el valor esperado y la variancia del tiempo del proyecto son 44, por que la desviación estándar es Raiz de 44 = 6.63. Así, el tiempo de terminación programado está alrededor de 0.9 desviaciones estándar del tiempo esperado del proyecto. La tabla A5.1 da una probabilidad aproximada de 1 - 0.1841 = 0.82 de que este programa se cumpla.

Enfoque de tres estimaciones de PERT (IV)

Nótese que el medio intervalo (a+b)/2 se encuentra a la mitad entre a y b, de manera que te es la media arimética ponderada de la mdoa y la mitad del intervalo, con un peso de dos tercios para la moda. Aunque la suposición de una distribución beta es arbitraria, sirve para el propósito de localizar el valor esperado respecto a m, a y b de una manera que parece ser razonable.

DEspués de calcular el valor esperado y la variancia estimados para cada una de las actividades, se necesitan tres suposiciones adicionales (o aproximaciones) para poder calcular la probabilidad de terminar el proyecto a tiempo. Una es que los tiempos de las actividades son estadísticamente independientes. Una segunda es que la ruta crítica (en términos de los tiempos esperados) siempre requiere un tiempo total mayor que cualquier otra ruta. Esto implica que el valor esperado y la variancia del tiempo del proyecto son exactamente la suma de los valores esperados y las variancias (respectivamente) de los tiempos para las actividades sobre la ruta crítica.

Enfoque de tres estimaciones de PERT (III)

Para obtener la estimación del valor esperado (te), también es necesaria una suposición sobre la forma de la distribución de probabilidad. Se supone que la distribución es (al menos aproximadamente) una distribución beta. Este tipo de distribución tiene la forma que se muestra en la figura 10.29, que es razonable para este propósito.

Si se usa el modelo ilustrado en la figura 10.29, el valor esperado del tiempo de una actividad es aproximadamente.

Enfoque de tres estimaciones de PERT (II)

Se hacen dos suposiciones para convertir m, a y b en estimaciones del valor esperado (tc) y la variancia (σ²) del tiempo que requiere la actividad. Una suposición es que σ, la desviación estándar (raíz cuadrada de la variancia), es igual a un sexto del intervalo de los requerimientos de tiempo razonablemente posibles; esto es,

es la estimación deseada de la variancia. El razonamiento para hacer esta suposición es que se considera que las colas de muchas distribuciones de probabilidad (como en la distribución normal) están más o menos a tres desviaciones estándar de la media, de manera que existe una dispersión de alrededor de seis desviaciones estandar entre las colas. Por ejemplo, las cartas de control que se usan normalmente para el control estadístico de calidad están construidas de manera que la dispersión entre los límites de control se estima en seis desviaciones estándar.

Enfoque de tres estimaciones de PERT (I)

Hasta ahora se ha supuesto implícitamente que se pueden obtener estimaciones con una exactitud razonable del tiempo requerido para cada actividad del proyecto. En la realidad, con frecuencia existe bastante incertidumbre sobre cuáles serán estos tiempos; de hecho se trata de una variable aleatoria que tiene una cierta distribución de probabilidad. La versión original de PERT toma en cuenta esta incertidumbre usando tres tipos diferentes de estimaciones para los tiempos de las actividades, con el fin de obtener información básica sobre su distribución de probabilidad. Esta información para todos los tiempos de las actividades se utiliza para estimar la probabilidad de determinar el proyecto en la fecha programada.

Las tres estimaciones empleadas por PERT para cada actividad son una estimación más probable, una estimación optimista y una estimación pesimista. La estimación más probable (denotada por m) intenta ser la estimación más realista del tiempo que puede consumir una actividad. En términos estadísticos, es una estimación de la moda (el punto más alto) de la distribución de probabilidad para el tiempo de la actividad. La estimación optimista (denotada por a) procura ser el tiempo poco probable pero posible si todo sale mal. En términos estadísticos, se trata en esencia de una estimación de la cota superior de la distribución de probabilidad. En la figura 10.29 se muestra la localización ideal de estas tres estimaciones con respecto a la distribución de probabilidad.

Planeación y control de proyectos con PERT-CPM (X)

Resulta interesante observar en la tabla 10.8  que mientras que todos los eventos sobre la ruta crítica (inclusive el 4 y el 7) necesariamente tienen holgura cero; no es así para la actividad (4,7) ya que su tiempo estimado es menor que la suma de los tiempos estimados para las actividades (4,5) y (5,7). En consecuencia, estas últimas actividades están en la ruta critica, pero la actividad (4,7) no lo está.

ESta información sobre los tiempos más cercanos y más lejanos, las holguras y la ruta crítica, es invaluable para el administrador del proyecto. Entre otras cosas, le permite investigar el efecto de posibles mejoras en la planeación para determinar en dónde debe hacerse un esfuerzo especial para mantenerse a tiempo y evaluar el impacto de los retrasos.

Planeación y control de proyectos con PERT-CPM (IX)

Si se verifican en la tabla 10.8 las actividades que tienen holgura cero, se observa que el ejemplo de la construcción de una casa tiene una ruta crítica, 1→ 2→ 3→ 4→ 5→ 7→ 9→ 12→ 13,como se muestra en la figura 10.28 con las flechas más oscuras. Esta secuencia de actividades críticas debe mantenerse estrictamente a tiempo, si se quiere evitar retrasos en la terminación del proyecto. Otros proyectos pueden tener más de una ruta crítica; por ejemplo, nótese lo que pasaría en la figura 10.28 si el tiempo estimado de la actividad (4,6) se cambiara de 6 a 10.