Resumen Teoría de Redes

Métodos Cuantitativos para la Gerencia. Profesor: CarEmyr Suescum Coelho.

Equipo N° 4. Teoría de Redes.

Contreras, Keibby. C.I 20.851.862

Gutiérrez Gisela. C.I 20.848.787

Monsalve, Ana. C.I 21.526.000

Pacheco, Laxmi. C.I 20.849.366

Ortiz, Sandra. C.I 22.664.349

Rivas, María Daniela. C.I 20.199.901

Vera, Daniela. C.I 20.829.055

Villarreal, Carla. C.I 21.184.136

TEORÍA DE REDES

Reseña histórica.

La teoría de redes tuvo su inicio con el planteamiento del problema de los siete puentes sobre el río Pregel de la ciudad prusiana de Kaliningrado del matemático Euler, quién representó en un dibujo cada parte de tierra por un punto y cada puente por una línea, haciendo la siguiente pregunta: ¿se puede recorrer el esbozo sin repetir las líneas? (figura 1).

En el siglo XX, la teoría cobró un nuevo impulso gracias a la introducción del concepto de análisis de redes sociales; sin embargo, el verdadero desarrollo en redes sociales se llevó a cabo con la introducción de medidas destinadas a la obtención de patrones de conexiones sociales que enlazarán conjuntos de actores en psicología para detectar grupos sociales (interrelación de actores) o las posiciones de los actores en la red (detección de actores estructuralmente similares). Luego, se introduce el socio grama, el cual, es una gráfica de una matriz de datos para el análisis de patrones psicológicos que hace posible la transmisión de la información estructural de la red de forma sencilla y permite destacar la relevancia de los distintos actores que la conforman.

Terminología en la Teoría de Redes.

·    Gráfica: la gráfica es una serie de puntos llamados nodos que van unidos por una unas líneas llamadas ramales o arcos.

·       Red: una red es una gráfica que representa algún tipo de flujo en sus ramales o arcos. En las redes se usa una simbología específica para denotar su tamaño y elementos que la constituyen, dicha notación es la (N, A) donde N representa el número de nodos que contiene la red y A representa el número de arcos o ramales.

·       Cadena: una cadena corresponde a una serie de elementos ramales que van de un nodo a otro. En el siguiente caso se resalta una cadena que va desde el nodo 1 hasta el nodo 7 y se compone por los elementos [1-4, 4-7].  

·         Ruta: una ruta corresponde a los nodos que constituyen una cadena, en este caso [1,4,7].

·        Ciclo: un ciclo corresponde a la cadena que une a un nodo consigo mismo, en este caso el ciclo está compuesto por la cadena [4-3,3-6, 6-7, 7-4].

·   Ramal orientado: también denominado arco orientado es aquel que tiene un sentido determinado, es decir que posee un nodo fuente y un nodo destino.

·   Gráfica orientada: es aquella en la cual todos sus ramales o arcos se encuentran  orientados.

·           Árbol: gráfica en la cual no existen ciclos, como se muestra en la siguiente gráfica.

·       Árbol de expansión: es aquel árbol que enlaza todos los nodos de la red, de igual forma  no permite la existencia de ciclos.

·        Nodo Fuente: es aquel nodo en el cual todos sus ramales o arcos se encuentra orientados hacia afuera.

·      Nodo destino: el nodo destino es aquel nodo en el cual todos sus ramales se encuentran orientados hacia él.

Tipos de redes.

Redes sociales Las redes sociales están compuestas por individuos o grupos de individuos con patrones de contactos o interacciones entre ellos. Ejemplos de este tipo de redes son las relaciones de amistad, de negocios entre directivos de empresas, o entre familias a partir de sus matrimonios y descendencia (genealogías). Al análisis de este tipo de redes se asocian a menudo dificultades de imprecisión y subjetividad, debidas al reducido tamaño de las muestras que emplean y a los métodos utilizados para la recogida de datos: generalmente encuestas, cuestionarios o entrevistas. Para superar estas dificultades los investigadores han probado nuevos métodos de investigación en busca de muestras más numerosas y fiables mediante la utilización de grandes bases de datos.

Redes de información También denominadas redes de conocimiento. El ejemplo clásico de redes reales de esta categoría son las de citas y co-citas de trabajos científicos. Otro ejemplo estudiado de redes de información es la Word Wide Web (no debe confundirse con la Internet física), red que contiene páginas informativas que se enlazan a través de hipervínculos (Faba Pérez et al., 2004; Faba Pérez et al., 2005). Al igual que las redes de citas, en la www también influyen aspectos sociales que trascienden el mero interés informativo de los vínculos.

Redes tecnológicas Son las redes diseñadas para la distribución de electricidad (energía), agua, gas, las redes de transportes (carreteras, ferrocarril, rutas aéreas), las redes telefónicas (sólo las redes físicas de cables y postes, puesto que las redes de llamadas formarían parte de las denominadas redes sociales), o internet, como red de interconexión de ordenadores.

Redes biológicas Son diversos los sistemas biológicos susceptibles de representarse en forma de redes. Las redes de reacciones metabólicas, las redes genéticas, los ecosistemas y cadenas tróficas, las redes neuronales o las vasculares son algunos de los ejemplos de redes biológicas analizadas desde la perspectiva de la teoría de redes. Las redes alimentarias, por ejemplo, pueden ser descritas como un grafo con un conjunto finito de nodos (especies) y un conjunto finito de enlaces que asocian cada uno de esos nodos entre sí. El análisis del grado saliente y entrante (indegree y outdegree) de las redes alimentarias posibilita extraer abstracciones de la complejidad e interconexión entre las distintas comunidades naturales (Berlow, 2004; Montoya, 2003; Montoya; Solé, 2002; Montoya; Solé, 2003).

Las redes también pueden clasificarse según su tamaño (Börner et al., 2007): 4.5.

Redes pequeñas Contiene un máximo de 100 nodos. Ejemplos son algunas redes sociales, de ecosistemas biológicos o de exportación-importación de productos entre países. En ellas es posible mostrar la totalidad de nodos, de sus atributos y de los enlaces que les unen. El tamaño de los nodos suele representar atributos como la importancia, el poder o el nivel de trabajo.

Grandes redes Presentan más de 1.000 nodos, como Internet, las redes telefónicas, las redes de transportes o de carreteras, y algunas redes científicas, entre otras. Algunos de los principales retos que presenta la esquematización de visualizaciones de este tipo de redes son: la extracción de nodos, enlaces y subgrafos que componen su columna vertebral; la poda de enlaces que evite la pérdida de información relevante; el etiquetado adaptado; y el diseño de interacciones sencillas que faciliten la navegación.

Redes de tamaño medio Incluyen más de 100 y hasta 1.000 nodos. Ejemplos destacados son las redes genéticas, la metabólica o las económicas, y algunos tipos de redes científicas. En ellas también es posible representar todos sus nodos, pero no todos sus atributos o etiquetas. En ocasiones, es difícil mostrar la totalidad de sus enlaces, por lo que su número debe reducirse de forma adecuada. Algunas estrategias para su esquematización incluyen la muestra de nodos, enlaces etiquetas y/o atributos destacados, la utilización de metáforas visuales (colores...) o la inclusión de sistemas de referencia con ayudas para la navegación.

Modelo de Redes.

Mundos Pequeños:

En matemática y física una red de mundo pequeño es un tipo de grafo para el que la mayoría de los nodos no son vecinos entre sí, y sin embargo la mayoría de los nodos pueden ser alcanzados desde cualquier nodo origen a través de un número relativamente corto de saltos entre ellos. En el caso de una red social, donde los nodos son personas y los enlaces son el conocimiento/relación entre ellos se puede decir que captura muchos de los fenómenos de las redes de mundo pequeño. Pronto se empezaría a ver que las redes de mundo pequeño son más frecuentes de lo que se presupone y pronto aparecieron otras redes bajo esta categoría: un ejemplo muy claro es la topología de Internet. Este fenómeno ha dado la posibilidad de aplicación de este tipo de redes en diferentes áreas de la ciencia como puede ser el modelado de redes sociales, física, biología, epidemiología, etc.

Redes sin Escala:

        Los nodos del más alto grado son llamados a menudo CENTRO, los cuales sirven para propósitos específicos, aunque esto siempre dependerá en gran medida del dominio.

En este caso los principales centros son seguidos de cerca por los más pequeños y estos a su vez son seguidos por nodos mucho más pequeños y así sucesivamente. Este tipo de jerarquía permite un comportamiento tolerable a fallos ya que si se producen errores al azar y los nodos afectados son de grado pequeño el error que se presenta es insignificante, en cambio si el error se encuentra en nodos grandes la red se convertiría en un conjunto aislado, por lo que los centros son una fuerza y debilidad para este tipo de red

Redes Aleatorias:

         Se dice que una red es aleatoria si la presencia y colocación de sus aristas siguen una distribución aleatoria. Por lo que este tipo de red no puede ser diseñado con ningún criterio concreto. Las redes aleatorias son muy útiles para modelar sistemas muy grandes. Un ejemplo de esto es el enjambre de vehículos aéreos no tripulados.

Entorno a este tipo de red giran importantes teorías, las cuales comenzaron en 1949 cuando Rapoport y sus colaboradores realizaran el 1er intento de modelar una red Aleatoria aproximadamente 1 década más tas tarde se comienza a estudiar exclusivamente esta red y la llamaron teoría de red aleatoria a todas las investigación que sigan este eje.

Un modelo de creación de red Aleatoria es el modelo de Poisson o el modelo Binomial

Tipo de Problemas en la Teoría de Redes:

 El Modelo de la Ruta más corta:

        Se trata de un modelo de red (debido a la forma de diagrama de red usado para su representación), donde cada arco o rama que une dos nodos (elementos) que forman dicha red, viene caracterizado por un valor que representa la distancia (costo o tiempo) desde el nodo origen hasta el nodo destino. Si denominamos ruta o camino, a cualquier secuencia de arcos que conecte el nodo origen con el destino, la resolución consiste en encontrar la más corta posible. Usualmente los arcos no están orientados, es decir, se permite el tráfico en ambos sentidos, salvo que se indique lo contrario (por ejemplo en una calle de dirección.

·         Problema de la Ruta Más Corta

              RentCar está desarrollando un plan de reposición de su flotilla de automóviles para un horizonte de planeación de 4 años, que comienza el 1 de enero de 2001 y termina el 31 de diciembre de 2004. Al iniciar cada año se toma la decisión de si un auto se debe mantener en operación o se debe sustituir. Un automóvil debe estar en servicio durante un año como mínimo, 3 años como máximo. La tabla siguiente muestra el costo de reposición en función del año de adquisición del vehículo y los años que tiene en funcionamiento.

El problema de remplazo de equipo como problema de ruta más corta.

Realizaremos el problema en WinQSB para determinar  el costo total de esta política de reposición.

Del año 2001 al año 2003 hay un costo de 5400bs y de año 2003 al año 2005 hay un costo de 7100bs para un costo total de la política de reposición es de 12500bs.

Flujo Máximo:

Existe un flujo que viaja desde un único lugar de origen hacia un único lugar de destino a través de arcos que conectan nodos intermediarios. Los arcos tienen una capacidad máxima de flujo y se trata de enviar desde la fuente al destina la mayor cantidad posible de flujo.

Hay problemas donde lo importante es la cantidad de flujo que pasa a través de la red como por ejemplo: en las líneas de oleoductos, redes eléctricas o de transmisión de datos. Por esta razón en dichos problemas se determina el flujo máximo que pasa a través de una red.

Problema de flujo Máximo

Tres refinerías (A, B Y C) mandan barriles de petróleo hacia dos terminales  de distribución (D Y E) por una red de oleoductos. Toda la demanda que no se puede satisfacer por la red se adquiere en otras fuentes. La red de tuberías contiene tres estaciones de bombeo ( X, Y ,Z). El producto va por la red en las direcciones que indican las flechas. La capacidad de cada segmento de tuberías se ve directamente en los arcos, y está en millones de barriles por día. 

Resolución

En el cuadro anterior se puede observar que  se debe hacer un solo recorrido para lograr la capacidad máxima en la red de distribución de barriles de petróleo para así obtener un flujo máximo de 20 millones de barriles.

Método Gráfico:

Árbol de Expansión mínima:

El algoritmo del árbol de expansión mínima es un modelo de optimización de redes que consiste en enlazar todos los nodos de la red de forma directa y/o indirecta con el objetivo de que la longitud total de los arcos o ramales sea mínima (entiéndase por longitud del arco una cantidad variable según el contexto operacional de minimización, y que puede bien representar una distancia o unidad de medida).

Sean:

N = {1, 2,3,..., n} el conjunto de nodos de la red.

Ck= Conjunto de nodos que se han enlazado de forma permanente en la iteración k

Čk= Conjunto de nodos que hacen falta por enlazarse de forma permanente.

Paso cero (0): CONCEPTUALIZACIÓN DEL ALGORITMO

Definir los conjuntos C0 = {ø} y Č0 = {N}, es decir que antes del paso 1 no se han enlazado de forma permanente nodo alguno, y por ende el conjunto que representa a los nodos que hacen falta por enlazarse de forma permanente es igual a la cantidad de nodos que existen en la red.

Paso 1:

Se debe de escoger de manera arbitraria un nodo en el conjunto Č0 llamado i el cual será el primer nodo permanente, a continuación se debe de actualizar el conjunto C1 = {i}, que significa que al tiempo en que el conjunto C1 gana el elemento i el conjunto Č0 pierde el elemento i por ende ahora será igual a Č1 = N - {i}, además se debe actualizar el subíndice de los conjuntos k, el cual ahora será igual a 2.

Paso 2: Paso general ¨K¨

Se debe de seleccionar un nodo j del conjunto ČK-1 ("k-1" es el subíndice que indica que se está haciendo referencia al conjunto de la iteración inmediatamente anterior) el cual tenga el arco o ramal con menor longitud con uno de los nodos que se encuentran en el conjunto de nodos de enlace permanente CK-1. Una vez seleccionado se debe de enlazar de forma permanente lo cual representa que pasa a formar parte del conjunto de enlaces permanentes y deja de formar parte del conjunto que todavía se debe conectar para lograr la expansión. Al actualizar el algoritmo en este paso los conjuntos deben de quedar de la siguiente forma.

CK = CK-1 + {j} mientras que ČK = ČK-1 - {j}

El paso general que define k que al mismo tiempo representa a las iteraciones debe de ejecutarse toda vez que el conjunto ČK no sea vacío, cuando este conjunto sea igual a vacío se tendrá el árbol de expansión mínima.

El entendimiento del algoritmo desde el punto de vista algebraico no es quizá el más simple, sin embargo mediante el ejemplo gráfico se verá que es un algoritmo muy sencillo de elaborar.

Problema:

La ciudad de Mérida cuenta con un nuevo plan parcial de vivienda el cual contará con la urbanización de más de 7 proyectos habitacionales que se ubicarán a las afueras de la ciudad. Dado que el terreno en el que se construirá no se encontraba hasta ahora dentro de las zonas urbanizables de la ciudad, el acueducto municipal no cuenta con la infraestructura necesaria para satisfacer las necesidades de servicios públicos en materia de suministro de agua. Cada uno de los proyectos de vivienda inició la construcción de un nodo de acueducto madre, el cual cuenta con las conexiones de las unidades de vivienda propias de cada proyecto (es decir que cada nodo madre solo necesita estar conectado con un ducto madre del acueducto municipal para contar con su suministro). El acueducto municipal al ver la situación del plan parcial debe de realizar las obras correspondientes a la instalación de ductos madres que enlacen todos los nodos del plan con el nodo Meléndez (nodo que se encuentra con suministro de agua y que no pertenece al plan parcial de vivienda, además es el más cercano al mismo), la instalación de los ductos implica obras de excavación, mano de obra y costos de los ductos mismos, por lo cual optimizar la longitud total de los enlaces es fundamental. Las distancias existentes (dadas en kilómetros) correspondientes a las rutas factibles capaces de enlazar los nodos del plan parcial se presentan a continuación. Además la capacidad de bombeo del nodo Meléndez es más que suficiente para satisfacer las necesidades de presión que necesita la red madre.

El acueducto municipal le contacta a usted para que mediante sus conocimientos en teoría de redes construya una red de expansión que minimice la longitud total de ductos y que enlace todos los nodos del plan parcial de vivienda.

Paso 0:

Se definen los conjuntos iníciales C0 = {ø} que corresponde al conjunto de nodos enlazados de forma permanente en la iteración indicada en el subíndice y Č0 = {N = 1,2,3,4,5,6,7,8} que corresponde al conjunto de nodos pendientes por enlazar de manera permanente en la iteración indicada en el subíndice.

Paso 1:

Se debe definir de manera arbitraria el primer nodo permanente del conjunto Č0, en este caso escogeremos el nodo 1 (puede ser cualquier otro), que algebraicamente se representa con la letra i, se procede a actualizar los conjuntos iníciales, por ende C1 = {i} = {1} y Č0 = {N - i} = {2,3,4,5,6,7,8}, actualizamos k por ende ahora será igual a 2.

Paso 2:

Ahora se debe seleccionar el nodo j del conjunto ČK-1 (es decir del conjunto del paso 1) el cual presente el arco con la menor longitud y que se encuentre enlazado con uno de los nodos de enlace permanente del conjunto Ck-1 en el cual ahora solo se encuentra el nodo 1 (es decir que se debe de encontrar un nodo que tenga el arco de menor longitud enlazado al nodo 1).

Los arcos o ramales de color naranja representan los arcos que enlazan el conjunto ČK-1 (es decir del conjunto del paso 1, recordemos que K en este paso es igual a 2, por ende ČK-1= Č1) con los nodos de enlace permanente del conjunto Ck-1 en el cual ahora solo se encuentra el nodo 1, por ende ahora solo falta escoger el de menor longitud, que en este caso es el arco cuya longitud es 2, que enlaza de forma permanente ahora el nodo 2.

Al actualizar los conjuntos quedan así:

C2 = {1,2} y Č2 = {3,4,5,6,7,8}

Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración. Ahora se seleccionará un nuevo nodo j del conjunto Č2que presente el enlace (ramal o arco) de menor longitud con los nodos que se encuentran en el conjunto C2.

Los arcos de color naranja representan los enlaces posibles y dado que existe empate entre las menores longitudes se elige de manera arbitraria, en este caso se representa nuestra elección con un arco de color verde, enlazando de forma permanente ahora el nodo 4.

Al actualizar los conjuntos quedan así:

C3 = {1,2,4} y Č3 = {3,5,6,7,8}

Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.

Lo que representan los arcos naranja y verde es ya conocido, ahora la línea azul interrumpida irá trazando nuestro árbol de expansión final. Dado a que el arco menor es el de longitud 3, ahora se enlazará de manera permanente el nodo 5.

Al actualizar los conjuntos quedan así:

C4 = {1,2,4,5} y Č4 = {3,6,7,8}

Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración:

Ahora se enlazará de manera permanente el nodo 7.

Al actualizar los conjuntos quedan así:

C5 = {1,2,4,5,7} y Č5 = {3,6,8}

Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.

Ahora se enlazará de manera permanente el nodo 6.

Al actualizar los conjuntos quedan así:

C6 = {1,2,4,5,7,6} y Č6 = {3,8}

Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.

Se rompen los empates de forma arbitraria, ahora se enlazará de manera permanente el nodo 3.

Al actualizar los conjuntos quedan así:

C7 = {1,2,4,5,7,6,3} y Č7 = {8}

Ahora se procede a actualizar k ya que se procede a efectuar la última iteración.

Ahora se enlazará de manera permanente el nodo 8.

Al actualizar los conjuntos quedan así:

C8 = {1,2,4,5,7,6,3,8} = {N} y Č8 = {ø}

Por ende se ha llegado al árbol de expansión mínima

Árbol que presenta una longitud total minimizada de 21 kilómetros de ductos

Problema del Flujo De Costo Mínimo.

El problema del flujo de costo mínimo tiene una posición central entre los modelos de optimización de redes; primero, abarca una clase amplia de aplicaciones y, segundo, su solución es muy eficiente. Igual que el problema del flujo máximo, toma en cuenta un flujo en una red con capacidades de arco limitadas. Igual que el problema de la ruta más corta, considera un costo (o distancia) del flujo a través de un arco. Igual que el problema de transporte o el de asignación del capítulo 8, puede manejar varios orígenes (nodos fuente) y varios destinos (nodos demanda) del flujo, de nuevo con costos asociados. En realidad, estos cuatro problemas son casos especiales del problema del flujo de costo mínimo, como se demostrará en esta sección. La razón por la que el problema del flujo de costo mínimo se puede resolver de modo tan eficiente es que se puede formular como un problema de programación lineal y es posible resolverlo con una versión simplifica cada del método simplex llamada método simplex de redes. En la siguiente sección se describirá este algoritmo.

Problema del Flujo De Costo Mínimo 351

A continuación se describe el problema del flujo de costo mínimo.

1.  La red es una red dirigida y conexa.

2.  Al menos uno de los nodos es un nodo fuente.

3.  Al menos uno de los nodos es un nodo demanda.

4.  El resto de los nodos son nodos de trasbordo.

5.  Se permite el flujo a través de un arco sólo en la dirección que indica la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco. (Si el flujo puede ocurrir en ambas direcciones, debe representarse por un par de arcos con direcciones opuestas.)

6.  La red tiene suficientes arcos con suficiente capacidad para permitir que todos los flujos generados por los nodos fuente lleguen a los nodos demanda.

7.  El costo del flujo a través del arco es proporcional a la cantidad de ese flujo, donde se conoce el costo por unidad.

8.  El objetivo es minimizar el costo total de enviar el suministro disponible a través de la red para satisfacer la demanda dada. (Un objetivo alternativo es maximizar la ganancia total del envío.)

Ejemplo:

La Distribuidora Rosal tiene dos fábricas que producen un producto que es necesario enviar a dos bodegas.

Algunos detalles son:

La fábrica 1 está produciendo 80 unidades.

La fábrica 2 está produciendo 70 unidades.

La bodega 1 necesita 60 unidades.

La bodega 2 necesita 90 unidades.

          Costo por ferrocarril  de la fábrica 1 a la Bodega 1 es de 700$ por unidad

          Costo por ferrocarril de la fábrica 2 a la Bodega 2 es de 900$ por unidad

(Cada unidad corresponde a un camión lleno del producto.)

Costo por ferrocarril  de la fábrica 1 a la Bodega 1 es de 700$ por unidad

Costo por ferrocarril de la fábrica 2 a la Bodega 2 es de 900$ por unidad

Planeación y control de Proyectos, PERT y CPM.

PERT, (Program Evaluation and Review Technique o técnica de evaluación y revisión de programas).

CPM, (Critical Path Method o técnica de la ruta crítica).

PERT se desarrollo en la década de 1950 utilizado de amplia forma en la administración de proyectos militares de investigación y desarrollo, PERT fue desarrollado por el Departamento de la Defensa de los estados Unidos de Norteamérica para dar apoyo a la planeación, programación y control de una gran cantidad de trabaos (actividades) asociados con el proyecto. Una de las principales características de Pero, además de su capacidad para identificar los programas y planes que se requieren para las tareas (actividades), es que se puede manejar las incertidumbres que existen en los pronósticos de tiempos para terminar diversas tareas.

            CPM, fue desarrollado de forma independiente de PERP, pero se encuentran estrechamente relacionadas, referidos básicamente a los intercambios entre el costo de un proyectos y su fecha de terminación, se refiere a la reducción del tiempo necesario  para concluir una tarea o actividad, utilizando más trabajadores y/o recursos, lo cual, en la mayoría de los casos se ven reflejados en el incremento de los costos. Con CPM, se supone que el tiempo necesario para concluir las diversas actividades del proyecto se conoce con certidumbre, al igual que la cantidad de recursos que se utilizan. CPM, no se ocupa de tiempos inciertos de tareas o actividades como es el caso de PERT, sino que se refiere a intercambios entre tiempos y costos, sin embargo, no se hace la distinción entre PERT o CPM, sino que se utiliza la designación colectiva PERIT/CPM.

Terminología de PERT/CPM: Definición de actividades y relaciones de precedencia.

            La primera etapa del proceso de PERT/CPM consiste en identificar todas las tareas o actividades asociadas con el proyecto y sus interrelaciones. En cualquier caso, el punto clave es tener, en esta etapa de planeación, una lista precisa y exhaustiva de actividades (y las relaciones correctas de precedencia entre ellas), puesto que todos los cálculos futuros y los programas finales del proyecto dependen de esas actividades (y de sus relaciones). Además de las actividades del proyecto, se requiere también la descripción de actividades (“Predecesores Inmediatos”), referidos a la actividad inmediatamente anterior. Para una actividad determinada, deben terminarse todas las precedentes inmediatas antes que poder comenzar esa actividad.

            Con frecuencia, la identidad de las relaciones de precedencia puede resultar evidente pero es importante que sean completas y precisas. La omisión, así como también la inclusión, de una actividad precedente puede distorsionar en gran medida las relaciones generales entre las actividades.

Estructuras de Red.

            Luego que se ha elaborado una lista completa y precisa de actividades y de sus predecesoras, es posible ilustrar en forma gráfica sus relaciones. En una red PERP/CPM, las flechas o ramas representan actividades y los círculos o nodos se denominan eventos. Las actividades implican tiempo, y por lo general consumen recursos en forma de mano de obra, materiales o dinero. Los eventos no consumen ni tiempo ni recursos sino que, más bien, sirven como “puntos de referencia del proyecto” y representan los puntos lógicos de conexión para asociar las diversas actividades. Sin embargo, no debe intentarse dibujar el diagrama de red sin listar primero todas las actividades, sin haberlas ordenado en alguna forma lógica, y sin haber identificado en la medida de lo posible las relaciones de precedencia. Una vez que se ha desarrollado la red PERT/CPM, puede utilizarse como una verificación visual para asegurarse de que se ha identificado las relaciones apropiadas de precedencia.

           Elementos de un Grafo.

·        
   Actividad Real: Es la realización de un trabajo o tarea elemental que requiere esfuerzo y consumo de tiempo y recursos.

·        

Representación de una Actividad Real: Se hace mediante una flecha de línea sólida, esta línea puede ser quebrada, en zigzag, perpendicular…               

·        Denominación: La Actividad Real se puede nombrar mediante una letra colocada encima o debajo de la flecha mediante o simplemente por número.

·        Evento: Representación gráfica de los momentos de inicio y terminación de cada actividad, no consume tiempo ni recursos.

·         Representación de un Evento: Se puede hacer mediante un triángulo , un círculo…

    Denominación: Cada evento se puede identificar con un número que es colocado en la mitad izquierda de la figura. Nunca debe existir más de dos eventos con la misma denominación.

     Actividad Ficticia: Son aquellas actividades que a pesar de ser diagramadas en un gráfico  no representan esfuerzo de trabajo o consumo de tiempo. Su origen Está determinado por la necesidad de mejorar la indicación, la interrelación, el orden, la confusión, o ambigüedad en la identificación de las diversas actividades. Su representación se hace, mediante líneas punteadas.                        

    Elaboración de la Red.

No existen procedimientos secretos para elaborar con éxito una red adecuada; sin embargo, existen diversas reglas que deben observarse, al igual que diversas “sugerencias” que pueden facilitar la tarea de elaborar la red:

    1.- Antes de que pueda comenzar una actividad, todas las actividades precedentes deben haber terminado.

   2.- Las flechas indican sólo precedencia lógica; ni su longitud ni su dirección tienen significado alguno.

     3.- Cada flecha (actividad) debe comenzar y terminar en un nodo de evento.

   4.-Ningún par de nodos de la red puede estar directamente conectado por más de una flecha.

    5.-Cuando se enumera los nodos es aconsejable, y en particular en una red grande, utilizar múltiplos de 10 para que sea fácil incorporar cualesquiera cambios o adiciones futuros. 

     6.-Todas las flechas de la red deben estar dirigidas, más o menos, de izquierda a derecha. 7.-La clasificación de las actividades (es decir, el listado de las actividades del proyecto) no debe ser más detallado que lo que se requiera para representar un plan de acción lógico y claramente definido. 

    8.-IMPORTANTE: No puede considerarse que se ha producido el evento 3, en tanto no haya ocurrido el evento 2. La flecha de actividad ficticia proporciona esa limitación. 

   Uno de los errores comunes que se cometen en la lógica de las redes es colocar las actividades en la red con base en algún sentido del tiempo (es decir, considerando el momento en que es probable que ocurran).

Actividades Ficticias.

Son todas aquellas actividades que se representan mediante líneas punteadas, y consumen cero tiempo y recursos. Son utilizadas para mostrar relaciones  correctas entre actividades y/o para evitar tener que conectar en forma directa dos nodos a través de más de una flecha (violación de reglas). Aunque es posible que no se requieran actividades ficticias para todas las redes de PERT/CPM, los proyectos grandes y complejos pueden necesitar varias de ellas.

Análisis de una Red PERT/CPM.

Luego que se obtiene una adecuada construcción de la red, se procede a identificar un programa compatible de actividades que permita la terminación del proyecto en una cantidad mínima de tiempo, esto significa que debe identificarse los tiempos iníciales y finales de cada actividad, las relaciones de tiempo entre las actividades y las actividades críticas que deben terminarse de acuerdo con el programa. Para comenzar el análisis, se requiere información respecto al tiempo necesario para terminar cada una de las actividades de la red.

Cálculo de la duración de cada Actividad.

Para la programación de un proyecto es necesario conocer la duración de cada actividad, lo que permitirá conocer la fecha de inicio y terminación más adecuada de cada actividad y la duración total del proyecto. Para la determinación se estima tres posibles duraciones:

1.    Tiempo optimista (To): Es el menor tiempo posible en el cual puede ejecutarse la actividad con lor recursos normales disponibles en la empresa.

2.    Tiempo más probable (Tm): Es la estimación de la duración de la actividad suponiendo que durante su ejecución  puedan presentarse algunos inconvenientes pero cuya solución es un tiempo relativamente adecuado.

3.    Tiempo pesimista (Tp): Es el tiempo que se necesitará para ejecutar la actividad suponiendo que se pueda presentar durante los trabajos muchas dificultades imprevistas.

Una vez calculadas las estimaciones no deben sufrir alteraciones a no ser que haya modificación de los objetivos que quiera alcanzar la empresa o de las restricciones utilizadas en la misma. Con los valores estimados  de las duraciones se determina el Tiempo esperado (Te) para ejecutar la actividad de la siguiente manera: 

Cálculo de las fechas más tempranas para comenzar y terminar cada actividad:

t i: La fecha más temprana para comenzar la actividad.

t j: La fecha más temprana para terminar la actividad.

d i j: La duración de la actividad i j.

Cálculo de las fechas más tardías permisibles para comenzar y terminar cada actividad:

t i: La fecha más temprana para comenzar la actividad.

t j: La fecha más temprana para terminar la actividad.

d i j: La duración de la actividad i j.

Tiempo Flotante.

Después que se han determinado los límites de tiempo para toda la red, puede determinarse el tiempo flotante, o “tiempo de holgura” como con frecuencia se le denomina, para cada actividad. El tiempo flotante se define como la longitud de tiempo en la que se puede demorarse una actividad sin ocasionar que la duración del proyecto general exceda su tiempo programado de terminación. La cantidad de tiempo flotante se calcula tomando la diferencia entre sus tiempos más lejanos de iniciación y más próximos de iniciación, o entre su tiempo más lejano de terminación y el tiempo más próximo de terminación.

Etapas básicas que se utilizan en el proceso de PERT/CPM:

1.    Identificar todas las tareas o actividades asociadas con el proyecto.

2.    Identificar las relaciones de precedencia inmediata para todas las actividades.

3.    Dibujar la red básica para el proyecto, mostrando todas las relaciones de precedencia.

4.    Estimar el tiempo esperado de duración para cada actividad.

5.    Empleando una revisión hacía delante de la red, calcular el tiempo próximo de iniciación y el tiempo próximo de terminación para cada actividad.

6.    Utilizando el tiempo esperado de terminación del proyecto, calculado en la revisión hacia delante de la red, usar el procedimiento de revisión hacia atrás para calcular el tiempo más lejano de iniciación y el tiempo más lejano de terminación para acabar actividad.

7.    Calcular el tiempo flotante (de holgura) asociado con cada actividad.

8.    Identificar la ruta crítica para la red. Las actividades críticas son las que tienen un tiempo flotante (de holgura) cero.

Ruta Crítica.

La ruta crítica para un proyecto es una ruta a través de la red tal que todas sus actividades tienen holgura cero. Las rutas críticas tienen varias propiedades importantes, entre las que se encuentran:

1.    Una red de un proyecto siempre tiene una ruta crítica, y algunas veces tiene más de una.

2.    Todas las actividades que tienen holgura cero deben estar en una ruta crítica, mientras que ninguna actividad que tiene holgura mayor que cero puede estar en una ruta crítica.

3.    Todos los eventos que tienen holgura cero debe estar en una ruta crítica, mientras que ningún evento que tienen holgura mayor que cero puede estar en una ruta crítica.

4.    Una trayectoria a través de la red tal que sus eventos tienen holgura cero no necesariamente es crítica porque una o más actividades sobre esa trayectoria pueden tener holgura mayor que cero.

Variabilidad en la fecha de terminación del proyecto.

Para calcular la ruta crítica se utilizan los tiempos esperados de duración para los tiempos de las actividades; lo que se obtuvo fue una duración esperada para el proyecto, puesto que es probable que cada actividad varié en duración en vez de ser fija. El tiempo de terminación del proyecto será variable, y en particular si existen variaciones considerables en las actividades de la ruta crítica, no significando que se extienda  o amplíe el tiempo de terminación del proyecto. Si las variaciones en los tiempos de las actividades de la ruta crítica dan como resultado que uno o más de los tiempos sean mayores que lo esperado, entonces el tiempo de terminación del proyecto será mayor que el valor calculado. Pero si la variabilidad de las actividades de la ruta crítica da como resultados tiempo de las actividades menores que lo esperado, entonces es probable que la fecha de terminación se dé antes que el tiempo calculado. Se utiliza el término “probable” porque también es posible que variaciones en las actividades sobre rutas no críticas pudieran hacer que, si se demoran lo suficiente, dieran como resultado una nueva crítica que tuviera una duración mayor que la ruta que antes era crítica.

EJERCICIO DE REDES PERT-CPM

1.    La siguiente tabla muestra las actividades para el Proyecto de Construcción de una casa. Grafique la Red PERT-CPM e identifique él o los caminos críticos  con sus respectivas holguras:

ACT	DESCRIPCIÓN	AP	TO	TP	TPE	HOL
A	Excavación.	---	0	1	2	1
B	Cimentación.	---	1	1	1	0
C	Colocación de muros.	B	0	2	4	15
D	Colocación de techo.	A	9	12	27	6
E	Instalación de la Plomería Externa.	C	2	3	4	15
F	Instalación de la Plomería Interna.	B	1	1	1	0
G	Poner recubrimiento exterior.	A,F	2	3	10	0
H	Pintura Exterior.	G	1	1	7	6
I	Trabajo de electricidad.	A,F	2	5	14	13
J	Poner recubrimiento interior.	G	4	6	14	0
K	Instalar pisos.	J,H	2	3	4	0
L	Pintura de interiores.	J	1	1	7	0
M	Colocación de Accesos Externos.	L	1	2	3	0
N	Colocación de Accesos Internos.	M,K	2	4	6	0

 Con N termina el proyecto.

SOLUCIÓN DEL PROBLEMA DE PERT-CPM

      CAMINO CRÍTICO: (B,F,G,J,L,M,N)

 1.    Tiempo esperado de las actividades = Tiempo optimistas + (4) * tiempo más probable + tiempo pesimistas / 6

NOTA: nuestra idea también podría ser mostrarlos como se realiza en Win QSB la red de PERP-CPM

BIBLIOGRAFÍA

· Introducción a la Investigación de Operaciones. Frederick S, Hillier; Gerald J, Lieberman. Editorial McGraw-Hill Interameriacana Editores, S.A. Tercera Edición. 1.997. México, D.F.

·  Métodos Cuantitativos para la Toma de Decisiones en Administración. Charles A, Gallagher; Hugh J, Watson. Impreso en México. Programas Educativos, S.A.

·   Modelos Cuantitativos para Administración. K, Roscoe Davis; Patrick G, Mckeown. Grupo Editorial Iberoamerica. 1.984. Estados Unidos de América.