INVESTIGACIÓN DE OPERACIONES II

UNIDAD I: REDES-PERT-CPM

INTRODUCCIÓN

Los proyectos a grande escala han existido desde tiempos antiguos, este hecho se expone en la pirámides de Egipto. El problema de la administración de proyectos surgió en la construcción del submarino " Polaris" cuya construcción obtuvo a cargo de la marina de los Estados unidos en 1958; tantos componentes y subcomponentes producidos por diversos fabricantes,donde se necesita una herramienta para programar y controlar el proyecto.

PERT(EVALUACIÓN DE PROGRAMAS Y TÉCNICAS DE REVISIÓN), esta técnica demostró tanto utilidad que ha ganado amplia aceptación en el sector público y privado. Casi al mismo tiempo la compañía Dumpot desarrolló el método de la ruta crítica para controlar el mantenimiento de proyectos de plantas químicas.

El CPM Y PERT son idénticos en concepto y tecnología, la diferencia principal entre ellos es:

• CPM --- Sus tiempos de actividades son Determinísticos.
• PERT--- Sus tiempos de actividades son Probabilísticos o Estocásticas.
• 
  

        1. PROBLEMA DEL CAMINO MÁS CORTO.

Los problemas conocidos como problemas de camino mínimo o camino más corto, tratan como su nombre,indica de hallar la ruta mínima o más corta entre dos puntos. Este mínimo puede ser la distancia entre los puntos origen y destino o bien el tiempo transcurrido para trasladarse desde un punto a otro. Se aplica mucho para problemas de redes de comunicaciones.

Este tipo de problemas pueden ser resueltos por el método del Simplex, sin embargo existen otros métodos más eficientes como por ejemplo el algoritmo de Dijkstra o el de Bellman-Ford.

• Ejemplo(Vídeo):

      2. PROBLEMA DEL FLUJO MÁXIMO.

Nos permite conocer(calcular) la máxima cantidad de cualquier artículo o información que podemos transportar desde un origen hasta un destino.

Pasos a seguir :  

• Primer paso: Elegir una ruta arbitraria.
• Segundo paso: En dicha ruta escoger aquel ramal de menor flujo en ese sentido y transportar por esa ruta la cantidad escogida.
• Hacer esto repetidamente hasta que no sea posible encontrar una ruta con capacidad de flujo.

• Ejemplo(Vídeo):

        3. ÁRBOL DE EXPANSIÓN MÍNIMA.

Este problema surge cuando todos los nodos de una red deben conectar entre ellos, sin formar un loop. El árbol de expansión mínima es apropiado para problemas en los cuales la redundancia es expansiva, o el flujo a lo largo de los arcos se considera instantáneo.

EL TRANSITO DEL DISTRITO METROPOLITANO.

• La ciudad de Vancouver está planificando el desarrollo de una nueva línea en sistemas de tránsito.
• El sistema debe unir 8 residencias y centros comerciales.
• El distrito metropolitano de transito necesita seleccionar un conjunto de líneas que conecten todos los centros a un mínimo costo.
• La red seleccionada debe permitir:

Factibilidad de las líneas que deban ser construidas y mínimo costo posible por línea.

Algoritmo

Los algoritmos que pueden dar solución a este problema son:

• Algoritmo de Dijkstra
• Algoritmo de Kruskal
• Algoritmo de Prim

En este artículo trataremos el algoritmo de Prim como forma de solución para la cobertura mínima, debido a la simplicidad que este algoritmo conlleva puede ser aprovechado sin necesidad de ser un gran experto en programación.

a) Algoritmo de Prim

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y re descubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik. Consiste en un algoritmo de la teoría de los grafos para encontrar un árbol de cobertura mínimo en un grafo conexo (grafo que  para cada par de nodos está conectado por un camino, o sea, si para cualquier par de nodos A y B, existe al menos un camino posible desde B hacia A), no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo (grafo donde hay nodos que no pueden ser conectados por medio de un camino).

•  Traza

Siguiendo el algoritmo de Prim, se tiene:

• Se elige por ejemplo, el nodo 1 y se marca.
• Se elige la arista con menor valor incidente en 1, la (1, 3) = 1 se marca y se marca el otro nodo en el que incide, el 3.
• Se elige la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (1, 2) = 3 se marca y se marca el nodo no marcado, el 2.
• Se elige la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (2, 5) = 5 se marca y se marca el nodo no marcado, el 5.
• Se elige la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 6) = 1  se marca y se marca el nodo no marcado, el 6.
• Se elige la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 7) = 2 se marca y se marca el nodo no marcado, el 7.
• Se elige la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 4) = 6 se marca y se marca el nodo no marcado, el 4.
• FIN. Se finaliza dado que se tiene marcados los 7 nodos del grafo.
• Por tanto el árbol de mínima expansión resultante sería:

•  Ejemplo(Vídeo):

   

   4. RUTA CRÍTICA: PERT Y CPM.

El PERT/CPM fue diseñado para proporcionar diversos elementos útiles de información para los administradores del proyecto. Primero, el PERT/CPM expone la “ruta crítica” de un proyecto. 

Estas son las actividades que limitan la duración del proyecto. En otras palabras, para lograr que el proyecto se realice pronto, las actividades de la ruta crítica deben realizarse pronto. Por otra parte, si una actividad de la ruta crítica se retarda, el proyecto como un todo se retarda en la misma cantidad. Las actividades que no están en la ruta crítica tienen una cierta cantidad de holgura; esto es, pueden empezarse más tarde, y permitir que el proyecto como un todo se mantenga en programa. El PERT/CPM identifica estas actividades y la cantidad de tiempo disponible para retardos. 

Usos.

El campo de acción de este método es muy amplio, dada su gran flexibilidad y adaptabilidad a cualquier proyecto grande o pequeño. Para obtener los mejores resultados debe aplicarse a los proyectos que posean las siguientes características:

• Que el proyecto sea único, no repetitivo, en algunas partes o en su totalidad.
• Que se deba ejecutar todo el proyecto o parte de el, en un tiempo mínimo, sin variaciones, es decir, en tiempo crítico
• .Que se desee el costo de operación más bajo posible dentro de un tiempo disponible.

Dentro del ámbito aplicación, el método se ha estado usando para la planeación y control de diversas actividades, tales como construcción de presas, apertura de caminos, pavimentación, construcción de casas y edificios, reparación de barcos, investigación de mercados, movimientos de colonización, estudios económicos regionales, auditorías, planeación de carreras universitarias, distribución de tiempos de salas de operaciones, ampliaciones de fábrica, planeación de itinerarios para cobranzas, planes de venta, censos de población, etc., etc. 

Diferencias entre Pert y Cpm.

Como se indicó antes, la principal diferencia entre PERT y CPM es la manera en que se realizan los estimados de tiempo. E1 PERT supone que el tiempo para realizar cada una de las actividades es una variable aleatoria descrita por una distribución de probabilidad. E1 CPM por otra parte, infiere que los tiempos de las actividades se conocen en forma determinísticas y se pueden variar cambiando el nivel de recursos utilizados.

La distribución de tiempo que supone el PERT para una actividad es una distribución beta. La distribución para cualquier actividad se define por tres estimados: 

• El estimado de tiempo más probable, m; 
• El estimado de tiempo más optimista, a; y
•  El estimado de tiempo más pesimista, b. 

La forma de la distribución se muestra en la siguiente Figura. E1 tiempo más probable es el tiempo requerido para completar la actividad bajo condiciones normales. Los tiempos optimistas y pesimistas proporcionan una medida de la incertidumbre inherente en la actividad, incluyendo desperfectos en el equipo, disponibilidad de mano de obra, retardo en los materiales y otros factores.

Con la distribución definida, la media (esperada) y la desviación estándar, respectivamente, del tiempo de la actividad para la actividad Z puede calcularse por medio de las fórmulas de aproximación.

El tiempo esperado de finalización de un proyecto es la suma de todos los tiempos esperados de las actividades sobre la ruta crítica. De modo similar, suponiendo que las distribuciones de los tiempos de las actividades son independientes (realísticamente, una suposición fuertemente cuestionable), la varianza del proyecto es la suma de las varianzas de las actividades en la ruta crítica. Estas propiedades se demostrarán posteriormente.

En CPM solamente se requiere un estimado de tiempo. Todos los cálculos se hacen con la suposición de que los tiempos de actividad se conocen. A medida que el proyecto avanza, estos estimados se utilizan para controlar y monitorear el progreso. Si ocurre algún retardo en el proyecto, se hacen esfuerzos por lograr que el proyecto quede de nuevo en programa cambiando la asignación de recursos.

Cálculo de la ruta crítica

La aplicación de pert-cpm deberá proporcionar un programa, especificando las fecha de inicio y terminación de cada actividad. El diagrama de flechas constituye el primer paso hacia el logro de esa meta. Debido a la interacción de las diferentes actividades, la determinación de los tiempos de inicio y terminación, requiere calculo especiales. Estos cálculos se realizan directamente en el diagrama de flechas usando aritmética simple. El resultado final es clasificar las actividades de los proyectos como criticas o no criticas. Se dice que una actividad es critica sin una demora en su comienzo causara una demora en la fecha de terminación del proyecto completo. Una actividad no critica es tal que el tiempo entre su comienzo de inicio mas próximo y de terminación mas tardío (como lo permita el proyecto) es mas grande que su duración real. En este caso. Se dice que la actividad no critica tiene un tiempo de holgura.

•  Ejemplo: