INVESTIGACIN OPERATIVA

PROGRAMACION DE
PROYECTOS: CPM Y PERT

2015

Introduccin
Un caso particular de los sistemas intermitentes, son los proyectos que se
realizan por nica vez (los procesos y secuencias responden a pedido)
Ejemplo:
Proyectos constructivos (puentes, edificios, etc)
Desarrollo de productos nuevos (investigacin e instalacin de lneas de
produccin, instalacin de equipos, software)
Diseo de campaas publicitarias
Auditorias financieras
Etc.
Todos los proyectos, pequeos o grandes, tienen caractersticas comunes,
entre ellas:
Una combinacin de actividades
Una relacin secuencial entre algunas de las actividades.
( Precedencias)
Una preocupacin por el tiempo: la terminacin del proyecto a
tiempo es importante
Una preocupacin por los recursos: completar el proyecto dentro del
presupuesto tambin es importante

Planeacin del Proyecto (plan del proyecto)

La etapa de planeacin requiere desglosar el proyecto en
actividades de acuerdo a los objetivos y metas establecidos en
ste.
Para cada actividad se debe definir:
El tiempo o duracin de sta
Sus interrelaciones (actividades predecesoras o sucesoras)
Los recursos (materiales, monetarios, personas)
Adems en esta etapa se debe definir:
Organizacin del equipo
Definicin del proyecto
Criterio de desempeo: Tiempo - costo - calidad

Programacin del Proyecto (Programa del proyecto)

Requiere detallar las fechas de inicio y terminacin para cada
actividad, su sincronizacin y secuencia para terminar el proyecto en
un tiempo mnimo, que se denomina programa de camino crtico.
El conocimiento de las tolerancias permisibles o la elasticidad del
programa permite a la administracin la flexibilidad para cumplirlo.
Permite conocer la disponibilidad de los recursos (humanos,
materiales y financieros) importantes para la siguiente etapa del
proyecto.
Control del Proyecto
El control del proyecto no solo requiere informacin sobre el estado
actual sino analiza los posibles cambios cuando surgen dificultades lo
que permite hacer la reprogramacin cuando sea necesario (monitoreo,
revisin y actualizacin).
Debido a la complejidad y al gran nmero de actividades que se
desarrollan simultneamente, el problema de informacin y control es
complejo. Pero hoy se cuenta con software especfico para resolver y
actualizar programas.

Las tcnicas usadas para el anlisis, planificacin y

programacin de proyectos de gran escala estn basados en
la representacin del proyecto con redes de actividades. Las
tcnicas ms usadas son PERT y CPM.
Si la duracin de cada actividad es conocida con certeza,
el Mtodo del Camino o Ruta Crtica (CPM) se usa para
determinar cul es el tiempo requerido para completar el
proyecto. El mtodo CPM tambin permite identificar cuales
actividades pueden ser atrasadas sin afectar la duracin total
del proyecto.
Si la duracin de las actividades no es conocida con
certeza, se aplica la Tcnicas de Revisin y Evaluacin
del Programa (PERT), que permite
determinar la
probabilidad de que un proyecto termine antes de un periodo
definido o se atrase.

Secuencia de acontecimientos y actividades

Un acontecimiento o suceso ocurre cuando se ha verificado

conducen a l han terminado. Se representa por un nodo.

que todas las actividades que

Grafo o
Red
Para que una actividad (
) se haya terminado es
necesario que todas las actividades que la preceden estn
terminadas.
Las actividades preceden o siguen a los acontecimientos
Le
preceden

Le siguen

Las actividades en serie indican

que no puede comenzar un hasta
haber terminado la anterior.
Las actividades en paralelo se
pueden realizar simultneamente

3
3

5
7

Acontecimiento inicial y final

El diagrama de flechas o red
comienza con un evento inicial, que
ramifica en varios caminos que ligan
los distintos eventos y termina con el
evento final.
Los acontecimientos no consumen
tiempo y son principio o fin de una
actividad
fsica
o
mental,
designndose con un nmero.

Acontecimient
o

La actividad es el trabajo necesario para alcanzar un

acontecimiento y consume tiempo, dinero o recursos

A
(activida
d)
15 das
(Duracin)

Utilizacin de las flechas

Con una flecha se suelen indicar actividades; su origen es el acontecimiento
donde se inicia una actividad y su fin es el acontecimiento donde termina.
Estas actividades tienen una duracin nunca negativa, pero que pueden ser
cero llamndose entonces actividades ficticias que no consumen tiempo. Son
indispensables para respetar el orden de precedencia de las actividades.

Actividad Ficticia

7
0 das

Representacin de una Grafo

Actividad Ficticia 4-6

Caminos: 1-2-3-6
1-3-6
1-4-5-6
1-4-6

Acontecimie
nto Inicial 1

Acontecimie
nto Final

Los Grafos no tienen escalas, las longitudes de las flechas o el tamao

de los acontecimientos slo dependen e la claridad deseada para el
grafo y de la necesidad de las precedencias.
En los Grafos no pueden existir circuitos
cerrados o bucles, ya que es absurdo
exigir para una actividad la previa
realizacin de la que le sigue.

Se plantea la siguiente forma de numeracin:

Un acontecimiento inicial es aquel que presenta flechas que salen de l,
pero con ninguna que le llegue, encontrar el acontecimiento inicial y
numerarlo como 1. El proyecto siempre tendr slo un nodo inicial.
Numere todos los nuevos acontecimientos o nodos hasta alcanzar el
acontecimiento final que es aquel que no presenta ninguna flecha
emergente
Todas las actividades estarn entonces identificadas nicamente por sus
nodo inicial y final.

Trazado de grafo
Evitar que las flechas sean curvas, deben ser
rectas para mayor claridad.
Evitar que las flechas se crucen.
Evitar que las flechas posean longitudes
desproporcionadas unas con otras.
Evitar el desorden en la numeracin,
procurando hacer sta de izquierda a derecha
siempre que sea posible.
Evitar flechas ficticias que no sean necesarias.

2.- Representacin como un modelo de Red

Par aplicar CPM o PERT se requiere conocer la lista de actividades
que incluye un proyecto. Las actividades pueden ser representadas
en los nodos o en los arcos de una red.
Ejemplo: Proyecto de construccin de una casa
En la representacin grfica que se muestra a continuacin, las
actividades estn representadas como nodos. En este caso los arcos
o fechas marcar las relaciones de precedencia de las actividades.
Tabla de precedencias
Actividad
A
B
C
D
E

Descripcin
Cimientos paredes
Plomera, electricidad
Techo
Pintura exterior
Pintura interior

Predecesor
Ninguna
A
A
A
B, C

Duracin (sem)
4
2
3
1
5

Actividad
A
B
C
D
E

Descripcin
Cimientos paredes
Plomera, electricidad
Techo
Pintura exterior
Pintura interior

Predecesor
Ninguna
A
A
A
B, C

INICIO

FIN

Duracin (sem)
4
2
3
1
5

Reglas para construir el diagrama de redes:

Una actividad no puede ser representada por ms de un arco de red.
Ninguna actividad puede representarse dos veces en la red
Dos actividades diferentes no pueden identificarse por los mismos
eventos terminal y de inicio.
Actividades ficticias: se utilizan para respetar las relaciones de
precedencia. Son actividades de duracin cero y no tienen asignacin de
recursos. Se les puede dar un nombre.

As, la red de actividades de este proyecto quedara:

Activida
d
A
B
C
D
E
W

Descripcin

Predecesor

Cimientos paredes
Plomera, electricidad
Techo
Pintura exterior
Pintura interior

figura 3

B 2

1
1

A
4

C
3

Ninguna
A
A
A
B, C
B

E
5

D
1

Duracin (sem)
4
2
3
1
5
0

Ejercicio: Desarrolle el diagrama de red para el

siguiente proyecto

ACTIVIDAD
A
B
C
D
E
F

PREDECESORAS
--A, B
A, B
D
C, E

DURACIN (DAS)
6
9
8
7
10
12

 Notacin
TRMINO

INICIO
Tiempo
lo ms
prximo

Tiempo lo
ms tarde o
limite
Tiempo
lo ms
prximo

LSI

ESI

Actividad i-j

di

i
Nmero del
acontecimiento o
suceso

ES h

LS h

EFij
EF hj

Si EF iJ > EF hj

EFJ

LFJ

EFJ= EF iJ
Tiempo lo
ms tarde o
lmite

j
Nmero del acontecimiento o
suceso

Sea:
dij = duracin de la actividad (i,j)
ESi = instante ms temprano de inicio de la actividad (i,j)
ESi= Max { EF de todos los predecesores inmediatos del nodo (i)}
ESi= max [Esi-1 + dij]
EFj = instante ms temprano de trmino de la actividad (i,j)
EFj = ESi + dij
LSi = instante ms tardo de inicio de la actividad (i,j)
LSi = min [LFj - dij]
LFj = instante ms tardo de trmino de la actividad (i,j)
LFj = Min {LSI de todos los sucesores inmediatos de la actividad (i,j)}
LFJ = EFJ

para j= ltimo suceso

i-1
ESi

i-1

EFj LFJ

LSi

dij

MTODO :
Existen dos tipos de holgura:
Holgura Libre FS: tiempo en que una actividad puede ser retrasada sin que
se retrase la iniciacin de la actividad que sigue.

ESI LSI
i

EFj LFj
dij

FSij=EFj (ESI+ dij)

Holgura libre (FSij) de una actividad es la diferencia entre el

tiempo disponible para realizar la actividad , y la duracin de esta,
dij, si se inicia y termina lo ms pronto posible.

ij

ESI LSI
i

EFj LFj
dij

TSij=LFj (ESI+ dij)

La holgura total representa la flexibilidad de la

programacin de actividades relativa al tiempo de
completar el proyecto.
Definicin 3. Una actividad crtica es una actividad
que no puede ser retardada sin afectar la duracin
total de proyecto
Definicin 4: Se denomina ruta crtica a la ruta ms
larga de una red. Esta trayectoria es importante
porque determina la longitud del proyecto. Si alguna
de las actividades en la ruta crtica se retrasa, todo

EJEMPLO:

0
01

Activida
d

Duracin

Precedenc
----A
ia
C
2
7
5
22
74
A
6
2
E
D 2
2

B, D

C, E

B
3

Tiempo de trmino ms
temprano de act B

4
53

F
2
9
95

Tiempo de trmino ms
temprano de act E

Holgura Libre: tiempo en que una actividad puede ser retrasada

sin que se retrase la iniciacin de la actividad que sigue
FSJ =Min {ES de todos los sucesores inmediatos de (i)} - EF J
Holgura Total: Tiempo mximo en que una actividad puede ser
atrasada sin alterar la fecha de trmino del proyecto
TSIJ = LSI - ESI= LFJ - EFJ
EJEMPLO:
Activid
ad

Duraci
n

Predeces ES
ora

---

---

B, D

C, E

EF

LS

LF

TS

EJEMPLO:

0
01

Activida
d

Duracin

Precedenc
----A
ia
C 7 7
2
5
22
74
A
6
2
E
D 2
2

B, D

C, E

3
3

4
53

F
2

9
95

CAMINO CRTICO

Red de tiempo Mnimo-costo mnimo

Cul es el costo mnimo para completar un proyecto en un mnimo
tiempo?
Los dos pares de estimaciones que se usan en CPM se llaman tiempo y
costo normal y tiempo y costo intensivo para cada actividad. La
estimacin normal se refiere al tiempo y el costo para determinar una
actividad suponiendo un nivel de esfuerzo estndar o normal. La
estimacin intensiva supone que se aplica el mayor esfuerzo para
minimizar el tiempo de terminacin de la actividad. El CPM supone que
las estimaciones normal e intensiva guardan relacin lineal
cost
o
CI

CN
tI

El costo unitario de
aceleracin es:

tiemp
o

tN

ki

CN CI
tN tI

Existen tres enfoques para encontrar la red de

tiempo mnimo-costo mnimo:
Comenzar con la red normal e ir reduciendo los
tiempos de terminacin, hasta un mnimo.
Comenzar con la red de todo intensivo y
desintensificar actividades para reducir el costo
sin afectar el tiempo total.
Comenzar con la ruta crtica de la red de todo
intensivo con un tiempo mnimo, pero con todas
las dems actividades normales. Despus
reducir las otras trayectorias como sea
necesario.

Ejemplo:
Normal
Costo ($)
actividad T(sem)
(1,2)
(2,3)
(2,4)
(2,7)
(3,4)

Intensivo
T (sem)
Costo ($)

4
2
3
1
0

1.400
1.500
1.500
600
--

3
1
1
1
0

2.000
2.000
2.500
600
--

3
2
2
2

1.300
300
800
600

2
1
1
1

2.000
500
1.200
1.000

ficticia
(4,5)
(4,6)
(5,7)
(6,7)

RED EN TIEMPO NORMAL

0
01

Normal
Costo ($)
actividad T(sem)
(1,2)
(2,3)
(2,4)
(2,7)
(3,4)

4
2
3
1
0

1.400
1.500
1.500
600
--

3
2
2
2

1.300
300
800
600

ficticia
(4,5)
(4,6)
(5,7)
(6,7)

4
42

2
6
3
7

3
7

6
7
74

101
05

3
2

2 7
2

106

121
2
1
2

Aceleracin de un proyecto:
El objetivo es disminuir el tiempo de ejecucin del proyecto al mnimo costo.
Pasos :
1.Calcular el costo de aceleracin por perodo, para cada actividad en la red.
2.Con los tiempos actuales de las actividades encontrar la (s ) ruta(s) crtica(s ) en la red; identificar las actividades crticas.
3.Acelerar en una unidad de tiempo el proyecto de acuerdo a:
Existe slo una ruta crtica?
Si: seleccionar la actividad crtica, y acelerar cuando:
a)Todava se puede acelerar.
b)Tiene el menor costo de aceleracin por perodo.
No: Entonces hay ms de una ruta crtica, acelerar una actividad de cada ruta crtica tal que:
c)Cada actividad seleccionada todava se puede acelerar.
d)El costo total por unidad de tiempo sea el menor de todas las actividades
e)Considerar que una misma actividad puede pertenecer a la vez a ms de una ruta crtica, analizar las combinaciones de actividades a reducir elegir la que de
el menor costo.
4.Actualizar los tiempos de las actividades y calcular el nuevo tiempo total del proyecto. Si ya se logr la fecha de entrega deseada detener el proceso. Si no, volver
al paso 2.
5.Cuando ya no quedan actividades crticas que se puedan acelerar y que resulten en una reduccin del tiempo del proyecto., el proceso termina.
6.Calcular el costo de aceleracin sumando los costos unitarios por actividad acelerada para cada perodo.

Costos Unitarios k
Actividades

CAMINOS

12

23

12-24-45-57

60
0

12-27

60
0

12-24-46-67

60
0

12-23-34-4557

60
0

500

12-23-34-4667

60
0

500

24

3
4

500

45

46

70
0

500

DURACIN DE LOS
CAMINOS

ij

57

67

2
7

400

20
0
70
0

40
0
400

20
0

40
0

Tiempos de ACORTAMIENTOS

D1

D2

D3

D4

D5

D6

D7

1
2

11

10

1
1

11

10

1
1

10

10

1
0

10

10

Actividades acortadas

TA0

TA1

TA3

TA4

TA5

TA6

TA2

24

Costos Unitarios k
Actividades

CAMINOS

12

23

12-24-45-57

60
0

12-27

60
0

12-24-46-67

60
0

12-23-34-4557

60
0

500

12-23-34-4667

60
0

500

24

3
4

500

45

46

70
0

500

DURACIN DE LOS
CAMINOS

ij

57

67

2
7

400

20
0
70
0

40
0
400

20
0

40
0

D1

D2

D3

D4

D5

D6

D7

1
2

11

10

1
1

11

10

1
1

10

10

1
0

10

10

Tiempos de ACORTAMIENTOS

Actividades acortadas

TA0

TA1

TA2

TA3

TA4

TA5

TA6

5
7

24
24
12
46
45
24

COSTOS ASOCIADOS:
Costo Normal: C0 = 8000 $
Acortamiento 1: C1 = 8000 + 400 = 8400 $
Acortamiento 2: C2 =8400+ 500 = 8900 $
Acortamiento 3: C3 =8900 + 600 = 9500 $
Acortamiento 4: C4 =9500+ + 200= 9700 $
Acortamiento 5: C5 =9700+ 700= 10400 $
Acortamiento 6: C6 =10400+ 500 = 10900 $
Acortamiento 7: C7 =10900 +500 = 11400 $
Tiempo estimado de trmino del proyecto= 7
semanas.
Costo del proyecto acelerado: 11.400$

Sistema P.E.R.T: Tcnica de revisin y evaluacin de programas

Este sistema es anlogo al C.P.M en cuanto al trazado del grafo, siendo
vlidas las definiciones dadas para los conceptos:
Actividad
Tiempo mas prximo
Acontecimientos
Tiempo limite Holgura Total
Holgura Libre
Holgura Independiente
Camino Critico
La primera diferencia entre ellos es que en PERT la duracin de cada
actividad , se obtiene por medios probabilsticos, as como la fecha esperada
final (tiempo ms prximo), mientras que, como vimos, el CPM es
determinstico, ya que para la duracin de una actividad se toma slo un
valor, siendo fija por lo tanto la fecha esperada final.

Mtodo PERT
En CPM se asume que la duracin de cada actividad es conocida con certeza.
Claramente en muchas ocasiones este supuesto no es vlido. PERT intenta corregir este error
suponiendo que la duracin de cada actividad es una variable aleatoria de manera tal que el
camino crtico probabilstica y los programas de todas las actividades muestran esta
incertidumbre en lo que se refiere a tiempos.
Hay tres estimaciones de tiempo para cada actividad:
To = tiempo optimista (mnimo tiempo posible para que la actividad sea realizable si todo
marcha bien)
Tp = tiempo pesimista (mximo tiempo que puede demorar la actividad en condiciones
adversas)
Tm = tiempo medio (tiempo ms probable

T0

Tm

Tp

Tiempo
transcurrido

Si Tij es la v.a. asociada a la duracin de la actividad

(i,j) y PERT asume que Tij sigue la distribucin beta
(). Bajo estas suposiciones set tiene:
4t t
E (Tij )

V (Tij )
2

6
(t p t o ) 2
36

Camino Crtico Probabilstico

El supuesto terico del PERT es que cada una de las actividades
tiene distribucin de probabilidades independiente. Si la
trayectoria contiene muchas actividades independientes cada
una con varianza pequea entonces la duracin del proyecto
tiene distribucin normal:

Duracin =
D ~ N( (i,j), 2(i,j) )
(i,j) ruta (i,j) ruta

 T E (Tij )

D D

N (0,1)

(Tij )

T E (Tij )

p ( D T ) Pr D
(T )
2

(
Tij
)

donde (T) corresponde a la funcin de distribucin

acumulada normal estndar.
P(T)

(T)

E(Tij)

Tiempo
transcurrido

Ejemplo

0
01

Activi Predece

to

tp

tm

dad

soras

--

10

--

A,B

E(Tij V(Tij Holgura

)

Total

1,8

13

1,8

13

2,8

A,B

13

12

10

10

0,4

C,E

15

12

12

A
6

9
92

26
265

12

7 D

B
9

9
93

16
164

E
10

26
266

38
387

5. Incertidumbre:
Trabajar con tres estimaciones de tiempo para la ejecucin de las operaciones.
Permite concluir que hay una certeza absoluta de que cada operacin, as
como el proyecto en su conjunto, tendr una duracin igual al tiempo
esperado. Esta incertidumbre es posible cuantificarla y expresarla en trminos
probabilsticas.
Para esto es necesario calcular:
La varianza de cada operacin
La varianza del proyecto
1.-Varianza
Varianza de cada operacin

t2

to

36

Varianza del proyecto

T2 t2

(de operaciones de la ruta crtica)

2.-clculo de la probabilidad de cumplir plazos objetivos

Para proceder al clculo de probabilidades se utiliza una tabla estndar
de reas bajo la curva normal.
La utilizacin de esta tabla requiere efectuar una normalizacin de
variables utilizando las siguientes frmulas:

ts to

t2

TS TO

T2

Donde:
Para una operacin

Para la totalidad del

proyecto

Z = Valor de la variable normalizada

Ts= Plazo objetivo de cumplir el proyecto
ts = Plazo objetivo de cumplir una
operacin
El valor de Z se ubica en la tabla de
reas, la cantidad as determinada nos da
la probabilidad buscada.

TSij=LFj (ESI+ dij)

HOLGURAS
Actividades

TS

ij

FS ij

1-2

5-(0+5)=0

5-(0+5)=0

1-3

6-(0+4)=2

6-(0+4)=2

2-3

6-(5+1)=0

6-(5+1)=0

2-5

13(5+2)=6

13(5+2)=6

3-4

10(6+4)=0

10(6+4)=0

4-5

13(10+3)=0

13(10+3)=0

4-6

17(10+2)=5

17(10+2)=5

5-6
17Por lo tanto TE= 24 (13+4)=0
6-7
24(17+7)=0

17(13+4)=0
24(17+7)=0

Actividad 1-2
H T 5 (0 5) 0
H L 5 (0 5) 0
H I 5 (0 5) 0

H T 17 (10 2) 5
H L 17 (10 2) 5
H I 17 (10 2) 5
Actividad 5-6

Actividad 1-3
H T 6 (0 4) 2
H L 6 (0 4) 2
H I 6 (0 4) 2

H T 17 (13 4) 0
H L 17 (13 4) 0
H I 17 (13 4) 0
Actividad 6-7

Actividad 2-3
H T 6 (5 1) 0
H L 6 (5 1) 0
H I 6 (5 1) 0

H T 24 (17 7) 0
H L 24 (17 7) 0
H I 24 (17 7) 0

Actividad 2-5
H T 13 (5 2) 6
H L 13 (5 2) 6
H I 13 (5 2) 6
Actividad 3-4
H T 10 (6 4) 0
H L 10 (6 4) 0
H I 10 (6 4) 0
Actividad 4-5
H T 13 (10 3) 0
H L 13 (10 3) 0
H I 13 (10 3) 0

Actividad 4-6

TE 24