Investigacion de operaciones

Página 1

INDICE
UNIDAD 2: “ANALISIS DE REDES” Introducción ----------------------------------------------------------------------------------- (3) 2.- ANÁLISIS DE REDES----------------------------------------------------------------------------------- (4)
2.1.- ALGORITMO DE EXPANSION MINIMA-----------------------------------------------------------------(5)

2.1.1.- MÉTODO DE LA ESQUINANOROESTE.----------------------------------------------------- (6) 2.1.2.- PROCEDIMIENTO DE OPTIMIZACIÓN ----------------------------------------------------(7)

2.3 ALGORITMO DE LA RUTA MAS CORTA------------------------------------------------------------------- (8) 2.4PROBLEMA DEL FLUJO MAXIMO-------------------------------------------------------------------------- (12) 2.5.- PROBLEMA DELÁRBOL EXPANDIDO MÍNIMO-----------------------------------------------------2.6.- RUTA CRÍTICA (PERT-CPM) ----------------------------------------------------------------------------CONCLUSIÓN ----------------------------------------------------------------------------------------------------(14) (16) (19)

INGENIERIA EN SISTEMAS COMPUTACIONALES IV SEMESTRE

Página 2

INTRODUCCION

Muchosproblemas comerciales pueden ser resultados a través de modelos de redes, el resultado de un problema de redes garantiza una solución entera, dada su estructura matemática. No se necesitan restricciones adicionales para obtener este tipo de solución además los problemas de redes pueden ser resultados de pequeños algoritmos, no importando el tamaño del problema, tan solo dada su estructura matemática esmás que suficiente para calcular los gastos convenientes en nuestra vida cotidiana. Así como tener en cuenta que las investigación de operaciones las llevamos a cabo en cualquier momento y cualquier lugar desde tu casa hasta en lugares públicos en todos tus gastos que lleves a cabo en tu vida cotidiana y así hacerse una vida más fácil en cuanto a tomar decisiones si llevas a cabo un problema uotro o tal vez el que se te haga más cómodo al llevarlo a cabo.

INGENIERIA EN SISTEMAS COMPUTACIONALES IV SEMESTRE

Página 3

UNIDAD II. ANÁLISIS DE REDES
Una red consiste en una serie de nodos enlazados con arcos (o ramas). La notación para describir una red es (N, A). Donde N es l conjunto de nodos y A es el conjunto de arcos. Por ejemplo: N= {1, 2, 3, 4, 5} A= {(1,2), (1,3), (2,3),(2,5), (3,4), (3,5), (4,2), (4,5)}

Con cada red se asocia algún tipo de flujo, el flujo en una red está limitado por la capacidad de sus arcos, que pueden ser finitos o infinitos. Se dice que un arco es dirigido u orientado si permite un flujo positivo en una dirección, y flujo cero en la dirección opuesta. Una red dirigida tiene todos sus arcos dirigidos. Una ruta es una sucesión de arcos distintosque unen dos nodos pasando por otros nodos, independientemente de la dirección de flujo de cada arco. Una ruta forma un ciclo si conecta un nodo consigo mismo, pasando por otros nodos. Un ciclo es dirigido si consiste en una ruta dirigida. Una red conectada es aquella en que cada dos nodos distintos están enlazados al menos por una ruta. Un árbol es una red conectada que puede consistir sólo enun subconjunto de todos los nodos en ella, donde no se permite ciclos, y un árbol de expansión es un árbol y de un árbol de expansión para la red.

INGENIERIA EN SISTEMAS COMPUTACIONALES IV SEMESTRE

Página 4

2.1 ALGORITMO DE EXPANSION MINIMA

El algoritmo de árbol de expansión mínima enlaza los nodos de una red, en forma directa o indirecta, con la mínima longitud de las ramasenlazantes. Una aplicación característica es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones puede pasar por uno o más poblaciones adicionales. Los pasos del procedimiento son los siguientes. Sea N= {1,2,…, n} el conjunto de nodos de la red y se definen: Ck = conjunto de nodos que se han conectado en forma permanente en la dirección k Ck =...