Modelo DE Redes - Investigacion y ejercicios propuesto PDF

Preview

Summary

Investigacion y ejercicios propuesto...

Description

Esmeraldas, 24 de Noviembre del 2020 Nombre: Mosquera Lavayen Lincoln A.

Ingeniería Mecánica 4to “A”

MODELO DE REDES Definición El análisis de redes es el área encargada de analizar las redes mediante la teoría de redes (conocida más genéricamente como teoría de grafos). Las redes pueden ser de diversos tipos:    

Social Transporte Eléctrica Biológica

  

Internet Información Epidemiología

Cuando se habla de una red, se entiende como un grupo de individuos que, en forma agrupada o individual, se relacionan con otros con un fin específico, caracterizado por la existencia de flujo de información. Las redes pueden tener muchos o pocos actores y una o más clases de relaciones entre pares de actores. La modelación de redes permite la resolución de múltiples problemas de programación matemática mediante la implementación de algoritmos especiales creados para tal fin, conocidos como Algoritmos de optimización de redes.

Algoritmo del á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 Č0pierde 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 de flujo capacitado con costo mínimo Dada una red con requerimientos mínimos se desea encontrar el valor mínimo de flujo que debe pasar a través de una red. Una condición necesaria para que el modelo tenga solución factible es que S bi=0, es decir, que el flujo total generado en los nodos origen sea igual al flujo total absorbido por los nodos destino. Cuando esta condición no se cumple (problemas de transporte no balanceado en los que la oferta es diferente a la demanda) se generan nodos ficticios que generen o que absorban flujo. Los costos asociados a los arcos que parten o llegan a estos nodos son cero. Con frecuencia bi y uij son valores enteros. Las variables xij son variables enteras y no se requiere agregar esta condición al modelo (unimodularidad). Para este tipo de problemas podemos ubicar las siguientes clasificaciones o grandes aplicaciones: Ruta más Corta Problema de Transporte Problema de Asignación Problema de Transbordo Flujo de Personal A continuación, se describe el problema del flujo de costo mínimo: La red es una red dirigida conexa. Al menos uno de los nodos es nodo fuente. Al menos uno de los nodos es nodo demanda. El resto de los nodos son nodos de trasbordo. Se permite el flujo a través de un arco sólo en la dirección indicada por 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.) La red tiene suficientes arcos como suficiente capacidad para permitir que todos los flujos generados por los nodos fuente lleguen a los nodos demanda. El costo del flujo a través del arco es proporcional a la cantidad de ese flujo, donde se conoce el costo por unidad. 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).

Método de CPM. Ruta crítica Todo proyecto se descompone en actividades, relacionadas directamente o no, que se desarrollan secuencialmente o simultáneamente. Controlar la duración de cada una es ganar influencia en el tiempo total de ejecución y, por eso, supone uno de los mayores retos de la gestión de proyectos complejos. El Diagrama de Gantt, la técnica más frecuentemente empleada para administrar tareas en función de su duración estimada, puede no ser suficiente para garantizar el control que se requiere sobre las operaciones y los recursos cuando los proyectos aumentan de volumen o de número. En estos casos, la solución reside en la utilización del CPM (Critical Path Method), también conocido como el método de la ruta crítica. Fases para la planificación de un proyecto con CPM 

Paso 1: Actividades del proyecto

La primera fase corresponde a identificar todas las actividades que intervienen en el proyecto, sus interrelaciones, sucesiones, reglas de precedencia. Con la inclusión de cada actividad al proyecto se debe cuestionar respecto a que actividades preceden a esta, y a cuales siguen inmediatamente esta finalice. Además, deberá relacionarse el tiempo estimado para el desarrollo de cada actividad.



Paso 2: Diagrama de la red

Con base en la información obtenida en la fase anterior y haciendo uso de los conceptos básicos para diagramar una red, obtendremos el gráfico del proyecto:



Paso 3: Calcular la red

Para el cálculo de la red se consideran 3 indicadores, T1, T2 y H. Estos indicadores se calculan en cada evento o nodo (entiéndase nodo entonces como un punto en el cual se completan actividades y se inician las subsiguientes. T1: Tiempo más temprano de realización de un evento. Para calcular este indicador deberá recorrerse la red de izquierda a derecha y considerando lo siguiente:  T1 del primer nodo es igual a 0.  T1 del nodo n = T1 del nodo n-1 (nodo anterior) + duración de la actividad que finaliza en el nodo n.  Si en un nodo finaliza más de una actividad, se toma el tiempo de la actividad con mayor valor.

En este caso para el cálculo del T1 en el nodo 4, en el que concurren la finalización de 3 actividades, 2 de ellas ficticias (Fb y Fd, cuyos tiempos son cero) y una es la actividad C. En este caso deberá considerarse el mayor de los T1 resultantes: T1 (nodo 3) + Fb = 4 + 0 = 4

T1 (nodo 2) + C = 3 + 2 = 5

T1 ( nodo 5) + Fd = 5 + 0 = 5 Así entonces, el T1 del nodo 4 será igual a 5 (el mayor valor). T2: Tiempo más tardío de realización del evento. Para calcular este indicador deberá recorrerse la red de derecha a izquierda y considerando lo siguiente:  T2 del primer nodo (de derecha a izquierda) es igual al T1 de este.  T2 del nodo n = T2 del nodo n-1 (nodo anterior, de derecha a izquierda) – duración de la actividad que se inicia.

 Si en un nodo finaliza más de una actividad, se toma el tiempo de la actividad con menor valor.

En este caso para el cálculo del T2 del nodo 2, en el que concurren el inicio de varias actividades deberá entonces considerarse lo siguiente:

T2 nodo 3 – B = 5 – 1 = 4

T2 nodo 4 – C = 5 – 2 = 3

T2 nodo 5 – D = 5 – 2 = 3 Así entonces, el T2 del nodo 2 será 3, es decir el menor valor. H: Tiempo de holgura, es decir la diferencia entre T2 y T1. Esta holgura, dada en unidades de tiempo corresponde al valor en el que la ocurrencia de un evento puede tardarse. Los eventos en los cuales la holgura sea igual a 0 corresponden a la ruta crítica, es decir que la ocurrencia de estos eventos no puede tardarse una sola unidad de tiempo respecto al cronograma establecido, dado que en el caso en que se tardara retrasaría la finalización del proyecto.

Las actividades críticas por definición constituyen la ruta más larga que abarca el proyecto, es decir que la sumatoria de las actividades de una ruta crítica determinará la duración estimada del proyecto. Puede darse el caso en el que se encuentren más de una ruta crítica, como es el caso del problema que hemos desarrollado. Ruta crítica 1:

Esta ruta se encuentra compuesta por las actividades A, C y E. La duración del proyecto será de 9 horas.

Ruta Crítica 2:



Paso 4: Establecer el cronograma

Para establecer un cronograma deberán considerarse varios factores, el más importante de ellos es la relación de precedencia, y el siguiente corresponde a escalonar las actividades que componen la ruta crítica de tal manera que se complete el proyecto dentro de la duración estimada.

Método PERT El método o diagrama PERT es una técnica que permite dirigir la programación de un proyecto. Consiste en la representación gráfica de una red de tareas, que, cuando se colocan en una cadena, permiten alcanzar los objetivos de un proyecto. Fue diseñada por la marina de los Estados Unidos para permitir la coordinación del trabajo de miles de personas que tenían que construir misiles con cabezas nucleares POLARIS. En su etapa preliminar, el método PERT incluye lo siguiente: el desglose preciso del proyecto en tareas, el cálculo de la duración de cada tarea, la designación de un director del proyecto que se encargue de asegurar la supervisión de dicho proyecto, de informar, en caso de ser necesario, y de tomar decisiones en caso de que existan variaciones de las proyecciones. La red PERT (a veces denominada gráfico PERT) consta de los siguientes elementos: Tareas (a veces denominadas actividades o etapas), representadas por una flecha. Se le asigna a cada una de las tareas un código y una duración. Sin embargo, la longitud de la flecha es independiente de la duración de la tarea. Etapas, es decir, el inicio y el final de la tarea. Cada tarea tiene una etapa de inicio y una de finalización. Con excepción de las etapas iniciales y finales, cada etapa final es una etapa de inicio de la siguiente tarea. Las etapas generalmente están numeradas y representadas por un círculo, pero en algunos otros casos pueden estar representadas por otras formas (cuadrados, rectángulos, óvalos, etc.). Fases para la planificación de un proyecto con PERT 

Paso 1: Actividades del proyecto

La primera fase corresponde a identificar todas las actividades que intervienen en el proyecto, sus interrelaciones, sucesiones, reglas de precedencia. Con la inclusión de cada actividad al proyecto se debe cuestionar respecto a que actividades preceden a esta, y a cuales siguen inmediatamente esta finalice. Además, deberán relacionarse los tiempos estimados para el desarrollo de cada actividad. A diferencia del método CPM, el método PERT asume tres estimaciones de tiempo por cada actividad, estas estimaciones son: Tiempo optimista (a): Duración que ocurre cuando el desarrollo de la actividad transcurre de forma perfecta. En la práctica suele acudirse al tiempo récord de desarrollo de una actividad, es decir, el mínimo tiempo en que una actividad de esas características haya sido ejecutada. Tiempo más probable (m): Duración que ocurre cuando el desarrollo de la actividad transcurre de forma normal. En la práctica suele tomarse como el tiempo más frecuente de ejecución de una actividad de iguales características. Tiempo pesimista (b): Duración que ocurre cuando el desarrollo de la actividad transcurre de forma deficiente, o cuando se materializan los riesgos de ejecución de la actividad.



Paso 2: Calcular el tiempo estimado (Duración promedio) y la varianza

Para efectos de determinar la ruta crítica del proyecto se acude al tiempo de duración promedio, también conocido cómo tiempo estimado. Este tiempo es determinado a partir de las estimaciones como:

El cálculo del tiempo estimado deberá hacerse entonces para cada actividad. Por ejemplo para la actividad A:

Además de calcular el tiempo estimado, deberá calcularse la varianza de cada actividad. El cálculo de esta medida de dispersión se utiliza para determinar la incertidumbre de que se termine el proyecto de acuerdo al programa. Para efectos del algoritmo PERT, el cálculo de la varianza se hará a partir de sus estimaciones tal cómo se muestra a continuación:

El cálculo de la varianza deberá hacerse entonces para cada actividad. Por ejemplo para la actividad A:

Para las actividades del tabulado mencionado en el Paso 1, los tiempos estimados y varianzas serían las siguientes:



Paso 3: Diagrama de red

Con base en la información obtenida en la fase anterior y haciendo uso de los conceptos básicos para diagramar una red, obtendremos el gráfico del proyecto (los tiempos relacionados con cada actividad en el gráfico corresponden a los tiempos estimados):



Paso 4: Calcular la red

Para el cálculo de la red se consideran 3 indicadores, T1, T2 y H. Estos indicadores se calculan en cada evento o nodo (entiéndase nodo entonces como un punto en el cual se completan actividades y se inician las subsiguientes. T1: Tiempo más temprano de realización de un evento. Para calcular este indicador deberá recorrerse la red de izquierda a derecha y considerando lo siguiente:  T1 del primer nodo es igual a 0.  T1 del nodo n = T1 del nodo n-1 (nodo anterior) + duración de la actividad (tiempo estimado) que finaliza en el nodo n.  Si en un nodo finaliza más de una actividad, se toma el tiempo de la actividad con mayor valor.

En este caso para el cálculo del T1 en el nodo 8, en el que concurre la finalización de 2 actividades, deberá considerarse el mayor de los T1 resultantes: T1 (nodo 6) + G = 13 + 6 = 19

T1 (nodo 7) + H = 8 + 4 = 12

Así entonces, el T1 del nodo 8 será igual a 19 (el mayor valor). T2: Tiempo más tardío de realización del evento. Para calcular este indicador deberá recorrerse la red de derecha a izquierda y considerando lo siguiente:  T2 del primer nodo (de derecha a izquierda) es igual al T1 de este.  T2 del nodo n = T2 del nodo n-1 (nodo anterior, de derecha a izquierda) – duración de la actividad que se inicia (tiempo estimado).  Si en un nodo finaliza más de una actividad, se toma el tiempo de la actividad con menor valor.

En este caso para el cálculo del T2 del nodo 1, en el que concurren el inicio de 2 actividades deberá entonces considerarse lo siguiente:

T2 nodo 2 – B = 6 – 6 = 0

T2 nodo 3 – C = 9 – 2 = 7

Así entonces, el T2 del nodo 1 será 0, es decir el menor valor. H: Tiempo de holgura, es decir la diferencia entre T2 y T1. Esta holgura, dada en unidades de tiempo corresponde al valor en el que la ocurrencia de un evento puede tardarse. Los eventos en los cuales la holgura sea igual a 0 corresponden a la ruta crítica, es decir que la ocurrencia de estos eventos no puede tardarse una sola unidad de tiempo respecto al cronograma establecido, dado que en el caso en que se tardara retrasaría la finalización del proyecto.

Las actividades críticas por definición constituyen la ruta más larga que abarca el proyecto, es decir que la sumatoria de las actividades de una ruta crítica determinará la duración estimada del proyecto. Puede darse el caso en el que se encuentren más de una ruta crítica.

Ruta crítica

Esta ruta se encuentra compuesta por las actividades A, C, E, G, I, J. La duración del proyecto sería de 22 semanas.



Paso 5: Cálculo de la varianza, desviación estándar y probabilidades

La varianza y la desviación estándar para la culminación del proyecto se relacionan con las actividades que comprenden la ruta crítica. Así entonces, para calcular la varianza basta con sumar las varianzas de las actividades A, C, E, G, I y J:

La desviación estándar corresponde a la raíz cuadrada de la varianza del proyecto, es decir:

Con la información que acabamos de obtener podemos efectuar cálculos probabilísticos de terminación del proyecto. Por ejemplo, sí se nos pide hallar la probabilidad de que el proyecto se culmine antes de 26 semanas, procederíamos de la siguiente forma y siguiendo la teoría de distribución normal:

Buscando este valor en una tabla de distribución normal encontramos que equivale a 0,9612, es decir que la probabilidad de culminar el proyecto en 26 semanas o menos es del 96,12%.



Paso 6: Establecer el cronograma

Para establecer un cronograma deberán considerarse varios factores, el más importante de ellos es la relación de precedencia, y el siguiente corresponde a escalonar las actividades que componen la ruta crítica de tal manera que se complete el proyecto dentro de la duración estimada....