ANALISIS DE REDEDES

C. a Dra. Matilde Mejía Mondragón

Investigación de Operaciones

ANÁLISIS DE REDES

PERT - CPM

Hay una multitud de situaciones en Investigación de
C. a Dra. Matilde Mejía Mondragón

Investigación de Operaciones

Modelos de Redes:

Operaciones, que se pueden modelar y resolver

como

redes

(nodos

conectados

por

ramas).

Algunas encuestas recientes informan quehasta el
70% de los problemas de programación matemática
en el mundo real se pueden representar como
modelos relacionados con redes.

1. Producción.
C. a Dra. Matilde Mejía Mondragón

Investigación de Operaciones

La representación de redes se utiliza en:

2. Distribución.
3. Planeación de proyectos.
4. Localización de proyectos.
5. Administración de recursos.
6. Planeaciónfinanciera.
7. Otras áreas

redes:

C. a Dra. Matilde Mejía Mondragón

Investigación de Operaciones

Existen 5 tipos importantes de modelos de

1. El problema de la ruta más corta.
2. El problema del árbol de mínima expansión.
3. El problema del flujo máximo.
4. El problema del flujo del costo mínimo.
5. Planeación y control de proyectos.

C. a Dra. Matilde Mejía MondragónInvestigación de Operaciones

OPTIMIZACIÓN DE REDES
Se ha desarrollado una terminología
relativamente extensa para describir los tipos
de redes y sus componentes.
Una red consiste en un conjunto de puntos y
un conjunto de líneas que unen ciertos pares
de puntos.

C. a Dra. Matilde Mejía Mondragón

Investigación de Operaciones

Los puntos se llaman nodos (o vértices) enlazados
con líneasllamadas arcos (o ligaduras, aristas o
ramas). La notación para describir una red es (N,A),
donde N es el conjunto de nodos y A es el conjunto
de arcos. Ejemplo de una red (N,A):
1

5

3

2

4

N= (1,2,3,4,5)
A=

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

3

2
C. a Dra. Matilde Mejía Mondragón

Investigación de Operaciones

I. Determine los conjuntos N y A enlas redes de
las siguientes figuras:

5

1

3

4

1

4

2

II. Trace la red definida por:
N= 1,2,3,4,5,6
A= (1,2), (1,5), (2,3), (2,4), (3,4), (3,5), (4,3),
(4,6), (5,2), (5,6)

que unen dos nodos pasando por otros nodos,
independientemente de la dirección de flujo en
C. a Dra. Matilde Mejía Mondragón

Investigación de Operaciones

UNA RUTA es una sucesión de arcosdistintos

cada arco.
Ejemplos:

2

1

5

5

1

3

4

en sus puntos terminales; por ejemplo, AB sería el
C. a Dra. Matilde Mejía Mondragón

Investigación de Operaciones

Los arcos se etiquetan dando nombre a los nodos

arco entre los nodos A y B. Los arcos de una red
pueden tener un flujo de algún tipo que pasa por
ellos.
B

A

una dirección (como en una calle de unsentido), se
C. a Dra. Matilde Mejía Mondragón

Investigación de Operaciones

Si el flujo a través de un arco se permite sólo en

dice que el arco es un arco dirigido. La dirección se
indica agregando una cabeza de flecha al final de la
línea que representa el arco.

permite un flujo positivo en una dirección y flujo
cero en la dirección opuesta.
C. a Dra. Matilde Mejía MondragónInvestigación de Operaciones

Se dice que UN ARCO es dirigido u orientado si

Al etiquetar un arco dirigido con el nombre de los
nodos que une, siempre se pone primero el nodo
de donde viene, después el nodo a donde va, esto
es, un arco dirigido del nodo A al nodo B debe

etiquetarse como AB y no como BA. Otra manera
de etiquetarlo es A

B.

direcciones (como una tubería que se puedeusar
C. a Dra. Matilde Mejía Mondragón

Investigación de Operaciones

Si el flujo a través de un arco se permite en ambas

para bombear fluido en ambas direcciones), se dice
que el arco es un arco no dirigido.

Para ayudar a distinguir entre los dos tipos de arcos,
con frecuencia se hará referencia a los arcos no
dirigidos con el sugestivo nombre de ligadura.

nodos distintos...