método de redes

Frage	Antworten
Métodos de redes.	En general, una red es la representación gráfica de un proceso, serie de actividades interconectadas o la distribución de puntos geográficos específicos, por ejemplo, un mapa carretero o la distribución de una red de computadoras representada en un diagrama, aunque existen muchos más contextos donde se aplican las redes.
Red.	Conjunto de puntos llamados nodos (o vértices) y líneas que los unen llamadas arcos (o ligaduras, aristas o ramas). Los arcos se etiquetan con los nombres de los nodos en sus puntos terminales, por ejemplo, AB es el arco entre los nodos A y B.
Trayectoria dirigida.	Una trayectoria dirigida del nodo i al nodo j, es una sucesión de arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el flujo del nodo i al nodo j, a través de esta trayectoria, es factible.
Red conexa.	Una red conexa es una red en la que cada par de nodos esta conectado. Se dice que dos nodos están conectados si la red contiene al menos una trayectoria no dirigida entre ellos aparte.
Capacidad de arco.	Es la cantidad máxima de flujo (quizás infinito) que puede circular en un arco dirigido.
Nodo fuente (o nodo de origen).	Tiene la propiedad de que el flujo que sale del nodo excede al flujo que entra a él.
Nodo demanda (o nodo destino).	Es el caso contrario al nodo fuente, donde el flujo que llega excede al que sale de él.
Nodo de transbordo (o nodo intermedio).	Satisface la conservación del flujo, es decir, el flujo que entra es igual al que sale.
Planeación y control de proyectos con Pert.	En 1958 aparece el sistema PERT (evaluación de programa y técnica de revisión), el cual fue desarrollado por Booz, Allen y Hamilton, científicos de la oficina naval de proyectos espaciales y la división de sistemas de armamentos de la corporación Lockheed Aircraft. La técnica demostró tanta utilidad que ha ganado amplia aceptación tanto en el gobierno como en el sector privado. El método PERT fue probado en la construcción del submarino Polaris y se dice que redujo en dos años la conclusión del proyecto.
Terminología Actividad.	En términos generales, se considera actividad a la serie de operaciones realizadas por una persona o grupo de personas en forma continua, sin interrupciones, con tiempos medibles de iniciación y terminación. Las actividades pueden ser físicas o mentales, como construcción, tramites, estudios, inspecciones, dibujos, etcétera.
Relación entre actividades.	Es la forma lógica como se conectan las diferentes actividades del proyecto. Esta relación se puede obtener por antecedentes o por secuencia. Por antecedentes se les preguntara a los responsables de los procesos cuales actividades deben quedar terminadas para ejecutar cada una de las que aparecen en la lista. Debe tenerse especial cuidado de que todas cada una de las actividades tengan por lo menos un antecedente excepto en el caso de ser actividades iniciales, en cuyo caso su antecedente será cero (0). Si la relación se hace por secuencia, se preguntar a los responsables de la ejecución cuales actividades deben hacerse al terminar cada una de las que aparece en la lista.
Matriz de secuencia o de precedencia.	Es la matriz en donde se coloca cada una de las actividades del proyecto y sus actividades secuenciales o precedentes. En el caso de la matriz de precedencia, esta formada por tres columnas, la primera contiene el numero de actividad, la segunda las actividades que preceden a la actividad mostrada en la primera columna y la ultima, una columna de anotaciones, la cual se utiliza para aclarar cualquier detalle del proyecto. La matriz de secuencia tiene también tres columnas, la primera contiene las actividades que conforman el proyecto, la segunda contiene las actividades que están después de la actividad de la primera columna, mientras que la tercera es una columna de anotaciones.
Consideraciones de tiempo Matriz de tiempos.	Es la matriz que contiene el tiempo que necesita cada actividad para completarse. Todos los cálculos se hacen con la suposición de que los tiempos de actividad son determinísticos. Para esto se necesita estimar tres tiempos: a) Tiempo pesimista. Es el mayor tiempo posible en que se puede realizar una actividad, esto como consecuencia de un desperfecto de la maquinaria o errores de los operadores, falta de materia prima, etcétera. b) Tiempo optimista. Es el menor tiempo posible en el que se puede realizar una actividad, esto como consecuencia de que todos los factores sean favorables c) Tiempo más probable. Es el tiempo modal, es decir, es el tiempo que mas se repite en la realización de la actividad.
Evento.	Se Llama evento al momento de iniciación o terminación de una actividad.
Red de proyecto.	Es la representación gráfica del proyecto, contiene cada una de las actividades a realizar, además de sus interrelaciones y secuencias. En este caso, los nodos de la red son los eventos del proyecto que se conectan a través de los arcos de la red o aristas, los cuales solo representan la secuenciación del proyecto y en ningún caso su longitud forma determinan el tiempo que requiere cada actividad.
Explicación del sistema PERT	Lo primero que nos interesa de un proyecto es hacer una estimación del tiempo que necesitaremos para concluirlo. Una forma de realizar esta estimación es utilizando la gráfica de Gantt, la cual es un cronograma de tiempos, en la que el eje vertical contiene las actividades del proyecto y en el eje horizontal anotamos el tiempo. Para graficar cada una de las actividades utilizamos el siguiente algoritmo: 1. Se grafican las actividades iniciales, es decir, aquella que no tienen actividades precedentes. Para graficar cada una de las actividades se traza una línea horizontal a la altura de donde se etiqueta la actividad, la longitud de la recta es igual al tiempo esperado de la actividad, utilizando la escala del eje horizontal. 2. Se grafican las actividades que tienen como precedente las actividades del paso anterior. La línea horizontal se traza a partir de donde termina la actividad precedente. Si una actividad depende de dos actividades o mas, tenemos que igualar la longitud de todas estas actividades a la mas larga, para ello trazamos una línea punteada.
Algoritmo del método PERT.	Dada la lista de actividades, la relación de precedencia y los tiempos pesimista, optimista y mas probable de las actividades de un proyecto, se hace lo siguiente: 1. Estimar los tiempos esperados de cada actividad. 2. Construir la red de proyectos. Nota. Recuerda que entre dos eventos solo debe existir una actividad, en caso contrario se añaden actividades ficticias. 3. Determinar los tiempos para eventos. Esto es, debemos determinar la terminación próxima y la terminación lejana de cada evento utilizando las siguientes fórmulas: a) La terminación próxima de un evento (TPE) es igual a la terminación próxima del evento anterior más el tiempo esperado de la actividad (TEA,) del evento anterior al evento j. Si hay dos trayectorias que lleguen a un evento se toma la de mayor tiempo. Al evento inicial se le asigna una terminación próxima igual a cero (TPE, = 0). b) La terminación lejana de cada evento (TLE) se calcula de derecha a izquierda en la red y es igual a la terminación lejana del evento posterior menos el tiempo esperado de la actividad posterior al evento.
Problemas de la ruta más corta	El problema de la ruta mas corta tiene por objetivo determinar la ruta mínima entre un origen y un destino determinados utilizando la información disponible en una red y cumpliendo con las especificaciones de distancia, conexiones existentes, etcétera. El algoritmo analiza la red a partir del origen, identificando en orden ascendente la ruta mas corta hasta cada uno de los nodos desde el origen hasta alcanzar el nodo destino. Esto es partir de una red establecida, conexa y no dirigida con nodos origen y destino. A cada arco no dirigido se asocia una distancia no negativa. El objetivo es determinar la ruta más corta, decir, la trayectoria con la mínima distancia total, desde el origen hasta el destino.
Algoritmo de la ruta mas corta	Objetivo de la n-ésima iteración. Encontrar el n-ésimo nodo más cercano al origen (este paso se repetirá para n=1, 2, hasta que el n-ésimo nodo más cercano sea el nodo destino). Datos para la n-ésima iteración. Son los n-1 nodos más cercanos al origen (encontrados en las iteraciones previas), incluida su y ruta más corta y la distancia desde el origen (estos nodos y el origen se llaman nodos resueltos, el resto son nodos no resueltos). Candidatos para el n-ésimo nodo más cercano. Cada nodo resuelto que tiene conexión directa por una ligadura con uno o más nodos no resueltos, proporciona un candidato y éste es el nodo no resuelto que tiene la ligadura más corta (los empates proporcionan candidatos adicionales).
Problemas de flujo máximo	Cuando se pretende maximizar el flujo a través de una red, considerando como inicio de la red un nodo llamado fuente y como nodo final un nodo llamado destino y tomando en cuenta que el flujo en los arcos es solo en la dirección que en el diagrama de la red se indica, se tiene un problema de flujo máximo, en el cual el objetivo es maximizar la cantidad total de flujo de la fuente al destino. Este tipo de problema tiene una amplia gama de aplicaciones dentro de las cuales se pueden mencionar: Maximizar el flujo de cualquier fluido a través de una tubería. Maximizar el flujo de vehículos por un sistema carretero. Maximizar el flujo de insumos o productos desde los proveedores hacia los clientes de cualquier tipo de empresa.
Algoritmo de la trayectoria de aumento:	Se identifica una trayectoria de aumento encontrando alguna trayectoria dirigida del origen al destino en la red residual, tal que cada arco sobre esta trayectoria tiene capacidad residual estrictamente positiva (si no existe una, los flujos netos asignados constituyen un patrón del flujo optimo). 2. Se identifica la capacidad residual c* de esta trayectoria de aumento encontrando el mínimo de las capacidades residuales de los arcos sobre esta trayectoria. Se aumenta en c* el flujo de esta trayectoria. 3. Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de aumento. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. Se regresa al paso 1

Nächster

Beschreibung

Zusammenfassung der Ressource

ähnlicher Inhalt

	Erstellt von Carlos Ruiz vor fast 4 Jahre