REDES

OPTIMIZACIÓN EN REDES
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

GRÁFICA
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

CONCEPTOS BÁSICOS
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).

Arcos no
dirigidos

Gráfica no dirigida

1

5

2

Gráfica dirigida

7

4

6 Arcosdirigidos Nodos

3

1

5

2

7

4
3

Nodos

6

CONCEPTOS BÁSICOS
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)

CONCEPTOS BÁSICOS

1

5

2

7

4
3

6

CAMINO DE 4 A 7
CICLO

CONCEPTOS BÁSICOS
Una subgráficaG’=(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.

1



















GRAFICA G: Conexa SUBGRAFICA G:
no conexa


SUBGRÁFICA G’:
conexa

CONCEPTOS BÁSICOS
 UN ÁRBOL de una gráfica G=(N,A) es una subgráficaG’=(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.








ÁRBOL DE G




GRAFICA G











ÁRBOL GENERADOR DE G

CONCEPTOS BÁSICOS
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 Y MODELOS DE REDES
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 distanciasasociadas a los arcos (cij), encontrar la ruta
más corta del nodo i al nodo j, donde i,jN

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: CPM, 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OTROS CASOS ESPECIALES
 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.

OTRAS APLICACIONES A II
 LAYOUT: distribución física de instalaciones
 MANUFACTURA CELULAR: separa...