Teoria De Redes 153x3a

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


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


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).


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


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)


5

2 1

7

4 3

6

CAMINO DE 4 A 7 CICLO


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


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


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.


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


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


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: M, PERT (RUTA MAS LARGA)


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


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


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.


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


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


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.


10

3 1 2

2 8

3

1 6

9 3

4 4

2 5

3 1 4

6


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.


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.


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.

Teoria De Redes 153x3a

Overview 4q3b3c

More details 26j3b

Related Documents 171j1w

Teoria De Redes 153x3a

Pl Teoria De Redes 6194v

Teoria De Redes Electricas 2o3z1a

Teoria De Redes Delta-estrella 5e1ro

Teoria De Grafos Y Redes 3l5o4n

Teoria De Las Redes Sociales x182j

More Documents from "r2d2" 4m1l24

Sistema De Abastecimiento q71d

Demanda Efectiva 6ja5y

Teoria De Redes 153x3a