trabajo

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

CONCEPTOS BÁSICOS
Arcos no
dirigidos

Gráficano dirigida
1

5

2

7

4

6 Arcos
dirigidos Nodos

3

Gráfica dirigida
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Á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.

















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á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.






ÁRBOL DE G





GRAFICA G











ÁRBOLGENERADOR 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 cortade 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 productoposible 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í
comolas 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
• Problemadel 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
•...