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:

Propiedades del flujo en la red:

El flujo en el arco (i,j) si esta por debajo de la capacidad del arco (i,j) entonces se puede aumentar el flujo atreves del arco. Así sea I la etiqueta del conjunto de arcos con esta propiedad.

El flujo del arco (i,j) es máximo, es decir ya supero la capacidad en este caso, se puede reducir el flujo a través del arco. Entonces sea R la etiqueta para el conjunto de arcos con esta propiedad.

Algoritmo de fera-fulkensan:

Paso 1. Etiquetar la fuente.

Paso 2. Etiquetar los nodos y los arcos menos ao. ao=arco que en que se denota el flujo actual en toda la red.

Si el nodo “X” esta etiquetado, el nodo “Y” no etiquetado y el arco (x,y) forma parte de I, entonces etiqueta el nodo “y” y el arco (x,y). En este caso el arco es un arco hacia adelante.

Si el nodo “Y” no esta etiquetado, el nodo “X” esta etiquetado y el arco (y,x) forma parte de R, entonces etiqueta el nodo “y” y el arco (y,x). En este caso el arco es un arco hacia atrás

Paso 3. Seguir con este proceso de etiquetado hasta etiquetar el pozo o hasta no poder etiquetar más vértices.

Si el proceso de etiquetado termina con el etiquetado del pozo, entonces habrá una cadena de arcos (llamada C) que va de la fuente al pozo.

Ajustando los arcos de esta cadena se considera el flujo factible y se aumenta el flujo total de la fuente al pozo.

Para cada arco hacia adelante en que i(x,y) la cantidad en la cual se puede aumentar el flujo en el (x,y) sin la restricción de la capacidad.

Arco (x,x) sea

K= min i(x,y)

(x,y) ∈ cn I

K= min r(x,y)

(x,y) ∈ cnR

Lo mismo sucede disminuyendo el flujo en el área tipo R.

Ejemplo: sea la red, mejorar el flujo en la red.

ao= 2

CADENA 1-3-5 CADENA 1-3-4-5 CADENA 1-2-3-5 CADENA 1-2-4-5

i(1,3)=1 i(1,3)=1 i(1,2)=1 i(1,2)=1

i(3,1)=1 i(3,4)=1 i(3,5)=1 i(2,4)=3

Min I=1 i(4,5)=3 min I=1 i(4,5)=3

Min I =1 min I=1

ao= 4

Es el flujo mejorado.

PROBLEMA DEL CAMINO MÁS CORTO

Consiste en encontrar el camino, cuya longitud sea mínima, que conecte el nodo inicial (o cualquier otro nodo que se elija) con el nodo final (o cualquier otro).

Características:

No todos los nodos con conectados.

Se busca hacer una nota que identifique la mínima distancia.

SEA LA RED:

...