Prueba

Fundamentos de Investigaci´n de Operaciones
o
Investigaci´n de Operaciones 1
o
CPM y PERT
18 de agosto de 2004

1.

Introducci´n
o

Existen modelos de redes que pueden ser empleados para programar proyectos que comprenden
un gran n´mero de actividades. Si la duraci´n de cada actividad es conocida con certeza, el M´todo
u
o
e
del Camino o Ruta Cr´
ıtica (CPM) puede ser empleadopara determinar cual es el tiempo requerido
para completar el proyecto. El m´todo CPM tambi´n permite identificar cuales actividades pueden
e
e
ser atrasadas sin afectar la duraci´n total del proyecto.
o
Si la duraci´n de las actividades no es conocida con certeza, la T´cnica de Revisi´n y Evaluaci´n
o
e
o
o
del Programa (PERT) puede ser empleado para determinar la probabilidad de que unproyecto termine antes de un per´
ıodo definido.

2.

Representaci´n como un Modelo de Red
o

Para aplicar CPM o PERT se requiere conocer la lista de actividades que incluye un proyecto. Se
considera que el proyecto est´ terminado cuando todas las actividades han sido completadas. Para
a
cada actividad, puede existir un conjunto de actividades predecesoras que deben ser completadasantes de que comience la nueva actividad. Se construye una malla o red del proyecto para graficar
las relaciones de precedencia entre las actividades. En dicha representaci´n gr´fica, cada actividad es
o
a
representada como un arco y cada nodo ilustra la culminaci´n de una o m´s actividades.
o
a
Consideremos un proyecto que consta de s´lo dos actividades A y B. Supongamos que la activio
dad A espredecesora de la actividad B. La representaci´n gr´fica de este proyecto se muestra en la
o
a
figura 2.1. As´ el nodo 2 representa la culminaci´n de la actividad A y el comienzo de la actividad B.
ı,
o

1

A

2

B

3

Figura 2.1: Proyecto de dos actividades A y B
Si suponemos ahora que las actividades A y B deben ser terminadas antes que una actividad C pueda
comenzar, la malladel proyecto queda como se muestra en la figura 2.2. En este caso, el nodo 3 representa que las actividades A y B se han terminado, adem´s del inicio de la actividad C. Si la actividad
a
1

Segundo Semestre 2004

CPM y PERT

A fuera predecesora de las actividades B y C, la red quedar´ como se muestra en la figura 2.3.
ıa

1

A
B

C

3

2
Figura 2.2: Proyecto de tres actividadesA, B y C

B

1

A

2

C

Figura 2.3: Proyecto de tres actividades A, B y C
Dado un conjunto de actividades y su relaciones de predecesi´n, se puede construir una representaci´n
o
o
gr´fica de acuerdo a las siguientes reglas:
a
1. El nodo 1 representa el inicio del proyecto. Por lo tanto, las actividades que parten del nodo 1
no pueden tener predecesoras.
2. El nodo terminal ofinal del proyecto debe representar el t´rmino de todas las actividades incluie
das en la red.
3. Una actividad no puede ser representada por m´s de un arco en la red.
a
4. Dos nodos deben estar conectados por a lo m´s un arco.
a
Para no violar las reglas 3 y 4, a veces es necesario introducir una actividad artificial o dummy que
posee tiempo de duraci´n nulo. Por ejemplo, supongamos que lasactividades A y B son predecesoras
o
de la actividad C y adem´s comienzan al mismo tiempo. En este caso, una primera representaci´n
a
o
podr´ ser la indicada en la figura 2.4. Sin embargo, la red de la figura 2.4 viola la regla 4. Para corregir
ıa
este problema, se introduce una actividad artificial indicada con un arco segmentado en la figura 2.5.
La red de la figura 2.5 refleja el hecho de que laactividad C tiene como predecesoras a A y B, pero
sin violar la regla 4. En otros casos, se deben agregar actividades artificiales para no violar la regla 3.
A
1

2

C

B
Figura 2.4: A y B predecesoras de C
Para ilustrar la representaci´n de proyectos m´s complejos, consideremos el proyecto definido en el
o
a
Cuadro 2.1. En este caso, dado que las actividades C y D tienen los...