PERT - CPM

PERT: Program Evaluations and Review Technique. (Técnica de revisión y evaluación de programas)

CPM: Critical Path Method (Metodode la ruta critica).

Ruta crítica :

-La Ruta Crítica es la ruta más larga a través de la red .

-Determina la longitud del proyecto .

-Toda red tiene al menos una ruta crítica .

-Es posible que haya proyectos con más de una ruta crítica.

INCERTIDUMBRE EN UNA RED PERT/CPM

Estimación de los tiempos de las actividades

Con el fin de tener en cuenta la incertidumbre, las personas que desarrollaron PERT permitieron a los usuarios utilizar tres estimadores para los tiempos de cada una de las actividades:

1.-  El tiempo más probable (tm): El tiempo que se requiere para terminar la actividad bajo condiciones normales.

2.-       El tiempo pesimista (tp): El tiempo máximo que se necesitaría para terminar la actividad si se encontraran demoras considerables en el proyecto.

3.- El tiempo optimista (to):  El tiempo mínimo que se requiere para terminar la actividad si todo ocurre en forma ideal.

- Utilizando estas tres estimaciones, puede calcularse un tiempo esperado para la duración de una actividad de acuerdo con la siguiente formula:

                           te = ( to + 4tm + tp) / 6

Veamos que ocurre con el tiempo con el caso Sharp en el cual se proporcionan tres estimaciones de los tiempos que se requieren para terminar cada una de las actividades del proyecto.

TABLA

Código de la actividad	Tiempo optimista(to)	Tiempo mas probable(tm)	Tiempo pesimista(tp)
A	3.0	5.5	11.0
B	1.0	1.5	5.0
C	1.5	3.0	4.5
D	1.2	3.2	4.0
E	2.0	3.5	8.0
F	1.8	2.8	5.0
G	3.0	6.5	7.0
H	2.0	4.2	5.2
I	0.5	0.8	2.3
J	0.8	2.1	2.8

 -  Si utilizamos la actividad F como ejemplo, estos datos indican que se estima que la actividad “fabricar envases” requerirá entre 1.8 semanas (estimación optimista) y 5.0 semanas (estimación pesimista), siendo su estimación mas probable 2.8 semanas. El valor que sería probable que ocurriera si la actividad se repitiera varias veces en el tiempo esperado.

                            te = [1.8 + 4(2.8) ] 6 

                                   te =  3.0

La ventaja de tener tres estimaciones de tiempos es que puede calcularse la dispersión de los tiempos de las actividades y puede utilizarse esta información para evaluar la incertidumbre de que el proyecto se termine de acuerdo con el programa.

Se utiliza la varianza como medida para describir la dispersión o variación de las estimaciones de los tiempos de las actividades.

Varianza de los tiempos de actividad =  s_t² = (tp – to) ² /  36

EJEMPLO:

ÁRBOL DE EXPANSIÓN MÍNIMA

REDES ( ARBOL DE EXPANSION MINIMA) 

Modelo de minimización de redes

El modelo de minimización de redes o problema del árbol de mínima expansión tiene que ver con la determinación de los ramales que pueden unir todos los nodos de una red, tal que minimice la suma de las longitudes de los ramales escogidos. No se deben incluir ciclos en al solución del problema.

Para crear el árbol de expansión mínima tiene las siguientes características:

1. Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras potenciales y la longitud positiva para cada una si se inserta en la red. (Las medidas alternativas para la longitud de una ligadura incluyen distancia, costo y tiempo.) 

2. Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un camino entre cada par de nodos. 

3. El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las ligaduras insertadas en la red. 

4. Un árbol de expansión es un árbol que enlaza todos los nodos de la red, también sin permitir ciclos.

Una red con n nodos requiere sólo (n-1) ligaduras para proporcionar una trayectoria entre cada par de nodos. Las (n-1) ligaduras deben elegirse de tal manera que la red resultante formen un árbol de expansión. Por tanto el problema es hallar el árbol de expansión con la longitud total mínima de sus ligaduras.

Algoritmo para construir el árbol de expansión mínima:

1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta (es decir, se agrega una ligadura) al nodo distinto más cercano. 

2. Se identifica el nodo no conectado más cercano a un nodo conectado y se conectan estos dos nodos (es decir, se agrega una ligadura entre ellos). Este paso se repite hasta que todos los nodos están conectados. 

3. Empates: los empates para el nodo más cercano distinto (paso 1) o para el nodo no conectado más cercano (paso 2), se pueden romper en forma arbitraria y el algoritmo debe llegar a una solución optima. No obstante, estos empates son señal de que pueden existir (pero no necesariamente) soluciones optimas múltiples. Todas esas soluciones se pueden identificar si se trabaja con las demás formas de romper los empates hasta el final.

EJEMPLO:

EJEMPLO EN EL PROGRAMA WINQSB

FLUJO MÁXIMO

MÉTODO DE FORD FULKERSON

El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo.

El algoritmo de Ford-Fulkerson tiene como idea buscar rutas en los que se pueda aumentar el flujo, hasta que por fin se alcance el flujo máximo.

Existe un flujo que viaja desde un único lugar de origen hacia un único lugar de destino através de arcos que conectan nodos intermediarios. Los arcos tienen una capacidad máxima de flujo y se trata de enviar desde la fuente al destino la mayor cantidad de flujo posible.

Características:

- El flujo siempre será positivo y siempre tendrá unidades enteras. 

- El flujo a través de un arco es menor o igual que la capacidad. 

- El flujo que entra en un nodo es igual al que sale de él.

PROBLEMA DEL CAMINO MÁS CORTO

El objetivo del problema de la ruta más corta es precisamente encontrar el camino más corto, de menor costo o más rápido, desde un nodo específico hasta cada uno de los demás nodos de la red.

SOLUCIÓN CON EL PROGRAMA WINQSB:

EJM: Usted debe hacer un viaje en auto a ciudades que nunca ha visitado. Estudia un plano para determinar la ruta más corta a su destino, según la ruta que elija, hay otras 5 ciudades: A,B,C,D Y E por las que puede pasar. El plano muestra las Km de cada camino que es una conexión directa entre dos ciudades sin que intervenga. Estas cifras se muestran en las sgte. tabla:

CIUDAD	CIUDAD					DESTINO
	A	B	C	D	E
A		10		70
B			20	55	40
C					50
D					10	60
E						80