Los variados problemas que se presentan en programación lineal con el fin de minimizar costos permiten la utilización de algoritmos exclusivos creados para cumplir con este objetivo y comúnmente denominados «algoritmos de optimización de redes».

La mayor cantidad de problemas que se resuelven mediante la utilización de modelación de redes se suelen encontrar en los modelos de transporte. Para su resolución existen dos tipos de modelos: el PERT (program evaluation and review techniques), utilizado para la revisión y evaluación de proyectos, y el CPM (critical path method), utilizado en el desarrollo y control de proyectos.

Recuerde los dos tipos de proyectos en los que se aplican las técnicas que se abordarán en esta unidad. CPM: proyectos determinísticos. PERT: proyectos probabilísticos.

Propósito general

Aprovechar los modelos de control y evaluación de proyectos PERT y CPM para el establecimiento de la ruta crítica en un proyecto.

Propósitos específicos

• Comprender las técnicas PERT y CPM en un problema de optimización de redes.
• Solucionar problemas de redes mediante el algoritmo de optimización de redes.
• Apropiar los conceptos expuestos para la solución de problemas de optimización de redes en el trabajo.
• Comprender y solucionar problemas de ruta crítica.

Una red es un conjunto de puntos llamados nodos que se constituyen en un lugar donde dos o más elementos tienen un enlace común y que muestran cuándo termina una actividad y comienza una nueva. También se refiere a un conjunto de curvas o arcos dirigidos que representan unas actividades denominadas ramas o arcos. Las redes representan las interdependencias y relaciones de precedencia entre las actividades de un proyecto.

Un nodo es un circulo en el diagrama de la construcción de la red que representa un evento o actividad importante en el problema, y constituye el origen o principio y el destino o final de un proyecto a realizar.

El arco es una línea que puede ser curva, que conecta dos nodos en la representación de un proyecto mediante la utilización de redes y que personifica una relación entre estos dos.

Material de apoyo

De acuerdo con Agudelo (2019):

Una de las grandes críticas que de manera regular recibió el gráfico de Gantt fue que presentaba algunas dificultades para planear proyectos. Dicha hipótesis se confirmó a mediados de 1958, cuando la compañía estadounidense DuPont amplió su operación a 300 fábricas, lo cual generó un gran número de actividades.

En tal contexto, los ingenieros Morgan R. Walker y James Killey pusieron a prueba el CPM, que se trata de un concepto determinístico, pues trabaja sobre actividades conocidas que conforman un proyecto, muestra las relaciones de precedencia, las simultáneas y las que continúan, y utiliza un diagrama de red en el que la actividad queda entre los nodos.

Para comprender el concepto de ruta crítica es necesario considerar los siguientes principios:

• Por lo general, la ruta crítica es la ruta más larga a través de la red.
• En toda la red se encuentra al menos una ruta crítica.
• La ruta crítica establece la longitud del proyecto.
• En los proyectos es posible encontrar más de una ruta crítica.
• Necesariamente se debe realizar el desarrollo hacia adelante y hacia atrás para hallar las holguras y encontrar la ruta crítica.

En los problemas de optimización de redes en los que se utiliza el método de la ruta crítica se debe ir hacia adelante para minimizar los costos por medio del siguiente algoritmo:

• Se determina que el valor del nodo inicial, representado por un rectángulo, comience en cero para especificar que el proyecto inicia en cero.
• Se continúa con el valor del nodo siguiente, se toma el del nodo anterior y se le suma la distancia del nodo anterior al nodo siguiente.
• Si ese nodo tiene más arcos que se dirigen a él, se toma el máximo valor encontrado de esas llegadas a ese nodo.
• Al finalizar el recorrido por la red se encuentra el valor con el cual puede terminar el proyecto.

Consulte los esquemas interactivos para conocer los dos métodos de desarrollo de la ruta crítica.

En los problemas de optimización de redes en los que se utiliza el método de la ruta crítica es necesario ir hacia adelante y posteriormente ir hacia atrás. Esto con el fin de minimizar los costos por medio del siguiente algoritmo:

• Se determina el valor del nodo final representado por un triángulo y que comience con el valor total del nodo final, que arrojó como resultado la ruta crítica hacia adelante.
• Se continúa con el valor del nodo anterior, se toma el valor del nodo siguiente y se le suma la distancia del nodo siguiente al anterior.
• Si ese nodo tiene más arcos que se dirigen a él, se toma el mínimo valor encontrado de las llegadas a ese nodo.
• Al finalizar el recorrido por la red hacia atrás se encuentra el valor con el que inició el proyecto que debe ser igual a cero.

En la galería de imágenes que aparece en pantalla se resuelve el mismo ejemplo que en el subtema anterior, pero utilizando el algoritmo expuesto.

Tras encontrar el desarrollo hacia adelante (T1) y hacia atrás (T2) de la ruta crítica se prosigue a desarrollar las holguras (H), que son la diferencia de los tiempos hallados hacia atrás menos los tiempos encontrados hacia delante.

Aquellos nodos en los que el valor sea igual a cero corresponden a la ruta crítica, es decir que la ocurrencia de estos eventos o actividades no pueden demorar una sola unidad de tiempo en relación con el cronograma establecido, dado que en el caso en que se demorara retardaría la terminación del proyecto.

La ruta crítica es aquella en la que las holguras o colchones son iguales a cero.

Los eventos o actividades críticas por axioma componen la ruta más larga que comprende el proyecto, es decir que la suma total de las actividades de una ruta crítica establecerá la duración apreciada del proyecto.

Puede darse el caso en el que se encuentre más de una ruta crítica, pero para efectos del ejemplo trabajado hasta este punto, no es así. Aquellos nodos donde el valor sea igual a cero corresponden a la ruta crítica, por consiguiente se construye tal como aparece en pantalla.

Luego se comprueba que la ruta crítica sea correcta, para lo cual se suman las distancias de los nodos donde el valor de las holguras fue igual a cero y debe arrojar el mismo resultado que el tiempo estimado del proyecto en los tiempos hacia adelante, que en este caso fue diecinueve.

Nodo 1 a nodo 3 cuya distancia es 3.

Nodo 3 a nodo 4 cuya distancia es 3.

Nodo 4 a nodo 5 cuya distancia es 0.

Nodo 5 a nodo 6 cuya distancia es 7.

Nodo 6 a nodo 7 cuya distancia es 6.

Para un total de diecinueve semanas o unidades de tiempo.

Actividad de aprendizaje

Haga clic sobre el enlace para acceder a una actividad que le permitirá poner en práctica los conceptos estudiados sobre el método CPM.

El algoritmo PERT se desarrolla mediante intervalos probabilísticos entre los que está el tiempo optimista, que es el mínimo tiempo en que una actividad transcurre de forma perfecta y se denota con la letra «a»; el tiempo más probable, que es el tiempo normal en que una actividad transcurre de forma frecuente y se denota con la letra «m», y el tiempo pesimista, que es el tiempo en que una actividad transcurre de forma deficiente y se indica con la letra «b».

Consulte la ampliación temática para conocer la aplicación del método PERT en la resolución del ejemplo trabajado en la unidad.

Los modelos de control y evaluación de proyectos PERT y CPM permiten o facilitan la optimización de un proyecto mediante herramientas de programación de redes. Con los métodos de ruta crítica y de evaluación y revisión técnica de un proyecto, dichos modelos son generalmente independientes, pero secuenciales.

Con estos métodos es posible minimizar las unidades de tiempo destinadas a un proyecto y calcular el tiempo en el que se puede realizar. Así mismo, permiten establecer: las posibles fechas de inicio y de terminación del proyecto y de las actividades; las actividades que no se pueden demorar según lo programado para poder mantener la duración prevista en el proyecto, y las actividades que se pueden demorar sin llegar a afectar el tiempo de culminación del proyecto.

El método de la ruta crítica del proyecto tiene como objetivo principal determinar la duración de un proyecto en unidades de tiempo, entendiendo dicha duración como la secuenciación de actividades relacionadas entre sí.

Por otra parte, el método de evaluación y revisión técnica tiene como objetivo programar y controlar proyectos a realizar, en los cuales se genera un grado de incertidumbre, cuando se piensa o entiende que el control sobre las unidades de tiempo es más importante que el control del costo. Este método es una mejor opción que el de la ruta crítica del proyecto.