Teoria De Redes

Lic. Sonia Castro Ynfantes

Lic. Sonia Castro Ynfantes

Lic. Sonia Castro Ynfantes

EN ALGUNOS PROBLEMAS DE OPTIMIZACIÓN PUEDE SER ÚTIL REPRESENTAR EL PROBLEMA A TRAVÉS DE UNA GRÁFICA: ruteo de vehículos, distribución de producto, programa de actividades en un proyecto, redes de comunicación, etc.  MODELOS DE REDES: algoritmos especiales 

Lic. Sonia Castro Ynfantes

ES UN CONJUNTO DE NODOS (N) Y ARCOS (A) QUE CONECTAN LOS NODOS. NOTAMOS G=(N,A)  LOS NODOS SE NUMERAN : 1,2,...,n  LOS ARCOS SE DENOTAN (i,j) indicando que une el nodo i al nodo j 

i j

Lic. Sonia Castro Ynfantes



Un arco (i,j) es dirigido si conecta i con j pero no j con i. i j



Una gráfica G=(N,A) es dirigida si sus arcos están dirigidos. En una gráfica no dirigida (i,j) y (j,i) representan el mismo arco ( no dirigido).

Lic. Sonia Castro Ynfantes

Gráfica no dirigida

Arcos no dirigidos 5

2 1

7

4

6 Arcos dirigidos Nodos

3

Gráfica dirigida

5

2 1

7

4 3

Nodos

6

Lic. Sonia Castro Ynfantes

Un Camino o Ruta del nodo i al nodo j es una secuencia de arcos que unen el nodo i con el nodo j: (i,i1), (i1,i2), (i2,i3),...,(ik,j). Ruta de k arcos.  Un Ciclo es un camino que une un nodo consigo mismo:(i,i1), (i1,i2), (i2,i3),...,(ik,i) 

Lic. Sonia Castro Ynfantes

5

2 1

7

4 3

6

CAMINO DE 4 A 7 CICLO

Lic. Sonia Castro Ynfantes





1

UNA SUBGRÁFICA G’=(N’,A’) DE UNA GRÁFICA G=(N,A) es un conjunto de nodos y arcos de G: N’∈ N y G’ ∈ G. UNA GRÁFICA G=(N,A) ES CONEXA si para cada par de nodos i,j ∈ N existe un camino que conecte el nodo i con el nodo j. 2 4

3

1 5

GRAFICA G: Conexa

2 4

3

1 5

SUBGRAFICA G: no conexa

2

4 SUBGRÁFICA G’: conexa

Lic. Sonia Castro Ynfantes



1

UN ÁRBOL de una gráfica G=(N,A) es una subgráfica G’=(N’,A’) de G que es conexa y no contiene ciclos. Si el Árbol contiene todos los nodos de G (N’=N) se dice que es un Árbol Generador.

2 4 GRAFICA G

2

1

3

ÁRBOL DE G 4

5 1

2 4

3 5

ÁRBOL GENERADOR DE G

Lic. Sonia Castro Ynfantes

Una RED es una gráfica con uno o mas valores asignados a los nodos y/o a los arcos: Nodos: (ai)demanda, oferta, eficiencia, confiabilidad. Arcos: (cij) costo, distancia, capacidad Ejemplos: representar a través de una red : red de agua potable, red de comunicación, red logística.



Lic. Sonia Castro Ynfantes

PROBLEMAS: encontrar la ruta más corta de la planta al centro de distribución pasando por ciudades intermedias. Problemas de transbordo. Política de reemplazo de equipo.  MODELO de la RUTA MÁS CORTA: dada una red dirigida G=(N,A) con distancias asociadas a los arcos (cij), encontrar la ruta más corta del nodo i al nodo j, donde i,j∈N 

Lic. Sonia Castro Ynfantes

PROBLEMAS Y MODELOS DE REDES PROBLEMAS: transportar la mayor cantidad de producto posible a través de una red de distribución: ductos, tráfico vehicular.  MODELO de FLUJO MÁXIMO: dada una red dirigida G=(N,A) con capacidades en los arcos (cij) encontrar la mayor cantidad de flujo total de un nodo fuente a un nodo destino 

Lic. Sonia Castro Ynfantes

PROBLEMAS Y MODELOS DE REDES PROBLEMAS: programar las actividades de un proyecto y determinar el tiempo requerido para terminar el proyecto así como las actividades “críticas”  MODELO: CPM, PERT (RUTA MAS LARGA) 

Lic. Sonia Castro Ynfantes

PROBLEMAS Y MODELOS DE REDES PROBLEMAS: redes de comunicaciones. Conectar todos los nodos con el mínimo costo.  MODELO DEL ÁRBOL GENERADOR MINIMAL: dada una red conexa no dirigida G=(N,A) con costos cij en cada arco (i,j) ∈ A, encontrar el Árbol Generador de costo mínimo 

Lic. Sonia Castro Ynfantes

PROBLEMAS Y MODELOS DE REDES Problema del Agente Viajero: encontrar el camino más corto saliendo de un nodo y regresando al mismo.  MODELO DEL AGENTE VIAJERO: encontrar un ciclo en una red (dirigida o no dirigida ). Un (camino) ciclo que no repite nodos es un (camino) o ciclo Hamiltoniano.  NO SIEMPRE EXISTE 

Lic. Sonia Castro Ynfantes

RED PLANA: que puede representarse en el plano sin cruzar arcos. Útil en ruteo  CICLO DE EULER: UN CICLO QUE INCLUYE CADA ARCO SOLO UNA VEZ. (Solo existe en una gráfica si esta tiene un número par de arcos incidentes en cada vértice (Euler). Útil en ruteo. 

Lic. Sonia Castro Ynfantes

LAYOUT: distribución física de instalaciones  MANUFACTURA CELULAR: separa componentes en familias de partes y máquinas en células de manufactura  PROGRAMACIÓN DE LA PRODUCCIÓN EN EL TIEMPO 

Lic. Sonia Castro Ynfantes

Los problemas de transporte, transbordo, camino mas corto, flujo máximo,red de proyectos(CPM) son casos especiales del modelo de FLUJO DE COSTO MÍNIMO EN UNA RED y pueden resolverse con una forma especial del Simplex .

Lic. Sonia Castro Ynfantes

Los nodos de la red representa las estaciones de transbordo de un sistema de transporte en una ciudad. Los arcos representan las rutas posibles y las distancias representan el tiempo de recorrido que depende de las paradas. El origen está en el nodo 1 y en el nodo 6 se encuentra el final del recorrido. Se quiere encontrar la ruta mas corta del origen a cada nodo de transbordo y en particular la ruta mas corta al destino final.

Lic. Sonia Castro Ynfantes

10

3 1 2

2 8

3

1 6

9 3

4 4

2 5

3 1 4

6

Lic. Sonia Castro Ynfantes

Paso 1. Asignar al nodo 1 al rótulo permanente [0,I]; la I indica que el nodo 1 es el nodo inicial ; y el 0, que la distancia del nodo 1 hacia sí mismo es cero. Paso 2. Determinar rótulos tentativos para los nodos a los que puede llegarse en forma directa desde el nodo 1.. El primer número de cada marcación es la distancia directa entre el nodo 1 y el nodo en cuestión; a esta parte de la etiqueta se la denomina valor de distancia. El segundo número de cada rótulo, al que se denomina valor del nodo precedente, señala el nodo que antecede en la ruta desde el nodo 1 hasta el nodo en cuestión. Paso 3. Identificar el nodo con la etiqueta tentativa que tenga el menor valor de distancia, y considerarlo como rotulado en forma permanente. Si todos los nodos tiene etiquetas permanentes, ir al paso 4.

Lic. Sonia Castro Ynfantes

Paso 4.Considérese todos los nodos que no tiene marcación permanente y a los que se puede llegar en forma directa desde el nuevo nodos con el rótulo permanente que estableció en el paso 3. Calcular para estos nodos las etiquetas tentativas de la siguiente manera: a. Si el nodo carece de etiqueta permanece y que se considera, tiene una marcación tentativa, obtener la suma del valor de distancia del nuevo nodo etiquetado permanentemente, y la distancia directa de este último nodo al nodo en cuestión. Si esta suma es inferior al valor de la distancia del nodo considerado, igualar a esta suma el valor de distancia para este nodo; además. Hacer que el valor del nodo precedente sea igual al nodo recién marcado como permanente y que arrojó la menor distancia. Continuar al paso3. b. Si el nodo que no tiene etiqueta permanente y que se está evaluando carece de rótulo tentativo, se crea una con valor de distancia igual a la suma del valor de distancia en el nuevo nodo etiquetado como permanente y la distancia directa desde ese nodo al que recientemente se le asignó la marcación permanente hasta el nodo en cuestión. El valor del nodo precedente es igual al nodo recién etiquetado en forma permanente. Ir al paso 3.

Lic. Sonia Castro Ynfantes

Paso 5. Los rótulos permanentes identifican la distancia más corta desde el nodo 1 hasta cada uno de los demás nodos, y el nuevo precedente sobre la ruta más corta. Se puede encontrar la ruta más corta hasta un determinado nodo, partiendo de éste, y yendo hacia sus precedentes. Continuando esta acción hacia atrás en la red se obtiene una ruta más corta desde el nodo 1 hasta el nodo en cuestión.