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
