viernes, 4 de marzo de 2016
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}
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}
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.
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.
Suscribirse a:
Entradas (Atom)