Investigacion De Operaciones

UNIDAD I. MODELO DE REDES

Red: conjunto de nodos conectados por arcos.

Nodo: es un punto en la red a donde llegan arcos y de donde salen. También se le conoce como vértice de la red.

Arco: es la línea que une dos nodos, representa el flujo de nacimientos de información de un nodo a otro. También puede representar cosas a enviar, actividades en secuencia, entre otros.

Los arcos pueden ser:

Direccionados: fluyen en una sola dirección.

Bidireccionados: fluye en ambas direcciones.

Los arcos toman valores de acuerdo al tipo de problema a resolver:

Distancias

Valores Cantidades

Tiempos

NOMENCLATURA

Ruta: Es el conjunto de arcos y nodos en una red donde se observa una cadena.

Cadena: el conjunto de arcos y nodos que forman un recorrido pero no hay circuitos cerrados.

Recorrido: un conjunto de nodos y los respectivos que unen. Un recorrido parte de un nodo y termina en el mismo o en otro de la red.

Recorrido: 1-1 Ruta: longitud de la ruta= a+g+j Cadena:

Unir todos los nodos de una red

*Árbol de extensión mínima con el mínimo de arcos.

*Camino mas corto Hallar una ruta de un nodo a otro en la red.

CASOS DE *Ruta critica De una lista de actividades secuenciales, la idea

ESTUDIO se construye una red y se encuentran las actividades

EN REDES criticas.

*Flujo máximo hay una capacidad en los arcos y un flujo actual

en ellos, la idea es equilibrar el flujo en todos los

arcos de la red para hacerlo optimo.

ÁRBOL DE EXTENSIÓN MÍNIMA

Para una red con “n” nodos, un árbol de extensión es un grupo de n-1 arcos que conectan todos los nodos de la red y que no contienen circuitos cerrados.

Ejemplo: sea la red

Tiene los siguientes arboles:

Longitud del árbol= 12+4=16

b) Longitud del árbol=12+7=19

c) Longitud del árbol=4+7=11

Un árbol de extensión con una longitud mínima en una red es un árbol de extensión mínima.

Algoritmo de solución

Empezar con cualquier nodo de la red y unirlos con el más próximo.

Escoger un nodo (no conectado) que este más próximo a los anteriores y unirlo.

Repetir el proceso hasta encontrar el árbol de extensión mínima.

Ejemplo:

Encontrar el árbol de extensión mínima de la red.

El árbol de extensión mínima de red. Longitud=1+1+2+2+2+2=10

Ejemplo:

El servicio de parques nacionales desea desarrollar una zona para el turismo, se han señalado ya sitios en el área para llegar a ellos en automóvil. Estos sitios y las distancias en km entre ellos que se presentan en la tabla para dañar lo menos posible al medio ambiente, el servicio de parques desea minimizar el numero de km necesario par proporcionar acceso deseado. Determinar como deberán construirse los caminos para este objetivo.

Entrada Parque Cascada Formación rocosa Mirador Pradera

Entrada Parque ------- 7.1 19.5 19.1 25.7

Cascada 7.1 ----- 8.3 16.2 13.2

Formación rocosa 19.5 8.3 ------ 18.1 5.2

Mirador 19.1 16.2 18.1 ----- 17.2

Pradera 25.7 13.2 5.2 17.2 ------

El árbol es: Longitud= 7.1+16.2+8.3+5.2=36.8 km

Hallar el árbol de extensión mínima de red:

Longitud=5+3+3+4=15

Longitud=3+3+5+4=15

Longitud=3+3+5+4=15

Dibujar el árbol de extensión mínima de la red:

Longitud=13

Longitud=13

FLUJO MÁXIMO EN REDES

Se pueden modelar muchas situaciones mediante una red en la cual se considera que los arcos tienen la capacidad de limitar la cantidad de un producto que se puede enviar atreves de arco.

En estas situaciones frecuentemente se desea transportar la máxima cantidad de flujo desde un punto de partida (llamado frente) hacia un punto final (llamado pozo).

Nodo fuente= So

Nodo pozo= Si

Casos de 1. Cuando un flujo factible es optimo.

Estudio 2. Cuando un flujo factible no es optimo, modificarlo y

obtener un flujo nuevo optimo, ósea un flujo mejorado.

NOMENCLATURA:

Capacidad del arco

Flujo actual en el arco

Sea la red:

...