MÉTODO DE PERT

El método PERT (Project Evaluation and Review Techniques), es un algoritmo basado en la teoría de redes diseñado para facilitar la planificación de proyectos. El resultado final de la aplicación de este algoritmo será un cronograma para el proyecto, en el cual se podrá conocer la duración total del mismo, y la clasificación de las actividades según su criticidad. 

El algoritmo PERT se desarrolla mediante intervalos probabilísticos, considerando tiempos optimistas, probables y pesimistas, lo cual lo diferencia del método CPM que supone tiempos determinísticos.

CONCEPTOS BÁSICOS PARA DIAGRAMAR ACTIVIDADES CON REDES

---

Regla 1: Cada actividad se debe representar sí y sólo sí, por un ramal o arco.

www.ingenieriaindustrialonline.com

Regla 2: Cada actividad debe estar identificada por dos nodos distintos. En el caso de existir actividades concurrentes (que inicien al mismo tiempo, o que el inicio de una actividad dependa de la finalización de 2 o más actividades distintas) se debe recurrir a actividades ficticias (representadas por arcos punteados que no consumen ni tiempo ni recursos) para satisfacer esta regla.

Por ejemplo,  la actividad C para su inicio requiere que finalicen A y B. Las actividades A y B inician al mismo tiempo.

www.ingenieriaindustrialonline.com

---

---

FASES PARA LA PLANIFICACIÓN DE UN PROYECTO CON PERT

---

PASO 1: ACTIVIDADES DEL PROYECTO

La primera fase corresponde a identificar todas las actividades que intervienen en el proyecto, sus interrelaciones, sucesiones, reglas de precedencia. Con la inclusión de cada actividad al proyecto se debe cuestionar respecto a que actividades preceden a esta, y a cuales siguen inmediatamente esta finalice. Además, deberán relacionarse los tiempos estimados para el desarrollo de cada actividad. 

A diferencia del método CPM, el método PERT asume tres estimaciones de tiempo por cada actividad, estas estimaciones son:

Tiempo optimista (a): Duración que ocurre cuando el desarrollo de la actividad transcurre de forma perfecta. En la práctica suele acudirse al tiempo récord de desarrollo de una actividad, es decir, el mínimo tiempo en que una actividad de esas características haya sido ejecutada.

Tiempo más probable (m): Duración que ocurre cuando el desarrollo de la actividad transcurre de forma normal. En la práctica suele tomarse como el tiempo más frecuente de ejecución de una actividad de iguales características.

Tiempo pesimista (b): Duración que ocurre cuando el desarrollo de la actividad transcurre de forma deficiente, o cuando se materializan los riesgos de ejecución de la actividad.

PASO 2: ESTIMAR EL TIEMPO ESTIMADO (DURACIÓN PROMEDIO) Y LA VARIANZA

Para efectos de determinar la ruta crítica del proyecto se acude al tiempo de duración promedio, también conocido cómo tiempo estimado. Este tiempo es determinado a partir de las estimaciones como:

El cálculo del tiempo estimado deberá hacerse entonces para cada actividad. Por ejemplo para la actividad A:

Además de calcular el tiempo estimado, deberá calcularse la varianza de cada actividad. El cálculo de esta medida de dispersión se utiliza para determinar la incertidumbre de que se termine el proyecto de acuerdo al programa. Para efectos del algoritmo PERT, el cálculo de la varianza se hará a partir de sus estimaciones tal cómo se muestra a continuación:

El cálculo de la varianza deberá hacerse entonces para cada actividad. Por ejemplo para la actividad A:

Para las actividades del tabulado mencionado en el Paso 1, los tiempos estimados y varianzas serían las siguientes:

PASO 3: DIAGRAMA DE RED

Con base en la información obtenida en la fase anterior y haciendo uso de los conceptos básicos para diagramar una red, obtendremos el gráfico del proyecto (los tiempos relacionados con cada actividad en el gráfico corresponden a los tiempos estimados):

PASO 4: CALCULAR LA RED

Para el cálculo de la red se consideran 3 indicadores, T1, T2 y H. Estos indicadores se calculan en cada evento o nodo (entiéndase nodo entonces como un punto en el cual se completan actividades y se inician las subsiguientes.

T1: Tiempo más temprano de realización de un evento. Para calcular este indicador deberá recorrerse la red de izquierda a derecha y considerando lo siguiente:

• T1 del primer nodo es igual a 0.
• T1 del nodo n = T1 del nodo n-1 (nodo anterior) + duración de la actividad (tiempo estimado) que finaliza en el nodo n.
• Si en un nodo finaliza más de una actividad, se toma el tiempo de la actividad con mayor valor.

En este caso para el cálculo del T1 en el nodo 8, en el que concurre la finalización de 2 actividades, deberá considerarse el mayor de los T1 resultantes:

 

T1 (nodo 6) + G = 13 + 6 = 19

T1 (nodo 7) + H = 8 + 4 = 12

 

Así entonces, el T1 del nodo 8 será igual a 19 (el mayor valor).

T2: Tiempo más tardío de realización del evento. Para calcular este indicador deberá recorrerse la red de derecha a izquierda y considerando lo siguiente:

• T2 del primer nodo (de derecha a izquierda) es igual al T1 de este.
• T2 del nodo n = T2 del nodo n-1 (nodo anterior, de derecha a izquierda) - duración de la actividad que se inicia (tiempo estimado). 
• Si en un nodo finaliza más de una actividad, se toma el tiempo de la actividad con menor valor.

En este caso para el cálculo del T2 del nodo 1, en el que concurren el inicio de 2 actividades deberá entonces considerarse lo siguiente:

 

T2 nodo 2 - B = 6 - 6 = 0

T2 nodo 3 - C = 9 - 2 = 7

 

Así entonces, el T2 del nodo 1 será 0, es decir el menor valor.

H: Tiempo de holgura, es decir la diferencia entre T2 y T1. Esta holgura, dada en unidades de tiempo corresponde al valor en el que la ocurrencia de un evento puede tardarse. Los eventos en los cuales la holgura sea igual a 0 corresponden a la ruta crítica, es decir que la ocurrencia de estos eventos no puede tardarse una sola unidad de tiempo respecto al cronograma establecido, dado que en el caso en que se tardara retrasaría la finalización del proyecto.

Las actividades críticas por definición constituyen la ruta más larga que abarca el proyecto, es decir que la sumatoria de las actividades de una ruta crítica determinará la duración estimada del proyecto. Puede darse el caso en el que se encuentren más de una ruta crítica.

Ruta crítica:

Esta ruta se encuentra compuesta por las actividades A, C, E, G, I, J. La duración del proyecto sería de 22 semanas.

PASO 4: CÁLCULO DE LA VARIANZA, DESVIACIÓN ESTÁNDAR Y PROBABILIDADES

La varianza y la desviación estándar para la culminación del proyecto se relacionan con las actividades que comprenden la ruta crítica. Así entonces, para calcular la varianza basta con sumar las varianzas de las actividades A, C, E, G, I y J:

La desviación estándar corresponde a la raíz cuadrada de la varianza del proyecto, es decir:

Con la información que acabamos de obtener podemos efectuar cálculos probabilísticos de terminación del proyecto. Por ejemplo, sí se nos pide hallar la probabilidad de que el proyecto se culmine antes de 26 semanas, procederíamos de la siguiente forma y siguiendo la teoría de distribución normal:

Buscando este valor en una tabla de distribución normal encontramos que equivale a 0,9612, es decir que la probabilidad de culminar el proyecto en 26 semanas o menos es del 96,12%.

Red PERT

La red PERT (a veces denominada gráfico PERT) consta de los siguientes elementos:

Tareas (a veces denominadas actividades o etapas), representadas por una flecha. Se le asigna a cada una de las tareas un código y una duración. Sin embargo, la longitud de la flecha es independiente de la duración de la tarea.

Etapas, es decir, el inicio y el final de la tarea. Cada tarea tiene una etapa de inicio y una de finalización. Con excepción de las etapas iniciales y finales, cada etapa final es una etapa de inicio de la siguiente tarea. Las etapas generalmente están numeradas y representadas por un círculo, pero en algunos otros casos pueden estar representadas por otras formas (cuadrados, rectángulos, óvalos, etc.).

Tareas ficticias, representadas por una flecha punteada que indica las limitaciones de las cadenas de tareas entre ciertas etapas.

VIDEO DEL METODO!

Ejercicio 2 - Ruta Mas Corta

COMPROBACIÓN SOFTWARE

EJERCICIO 1 - Ruta Mas Corta - Metodo De DIJKSTRA

Ruta Mas Corta - Algoritmo de Dijkstra

El algoritmo de Dijkstra te permite calcular la ruta más corta entre un nodo (tú eliges cuál) y todos los demás nodos en el grafo. Encontrarás una descripción del algoritmo al final de esta página, pero ¡vamos a estudiarlo con un ejemplo explicado! Calcularemos la distancia más corta entre el nodo C y los demás nodos del grafo:

Durante la ejecución del algoritmo, iremos marcando cada nodo con su distancia mínima al nodo C (nuestro nodo elegido). Para el nodo C, esta distancia es 0. Para el resto de nodos, como todavía no conocemos esa distancia mínima, empieza siendo infinita (∞):

También tendremos un nodo actual. Inicialmente, el nodo actual será C (nuestro nodo elegido). En la imagen, marcaremos el nodo actual con un punto rojo.

Ahora, revisaremos los vecinos de nuestro nodo actual (A, B y D) en cualquier orden. Empecemos con B. Sumamos la mínima distancia del nodo actual (en este caso, 0) con el peso de la arista que conecta al nodo actual con B (en este caso, 7), y obtenemos 0 + 7 = 7. Comparamos ese valor con la mínima distancia de B (infinito); el valor más pequeño es el que queda como la distancia mínima de B (en este caso, 7 es menos que infinito):

Bien. Ahora revisaremos al vecino A. Sumamos 0 (la distancia mínima de C, nuestro nodo actual) con 1 (el peso de la arista que conecta nuestro nodo actual con A) para obtener 1. Comparamos ese 1 con la mínima distancia de A (infinito) y dejamos el menor valor:

OK. Repetimos el procedimiento para D:

Genial. Hemos revisado todos los vecinos de C. Por ello, lo marcamos como visitado. Representemos a los nodos visitados con una marca de verificación verde:

Ahora debemos seleccionar un nuevo nodo actual. Ese nodo debe ser el nodo no visitado con la menor distancia mínima, es decir, el nodo con el menor número y sin marca de verificación verde. En este caso, ese nodo es A. Vamos a marcarlo con el punto rojo:

Ahora, repetimos el algoritmo. Revisamos los vecinos de nuestro nodo actual, ignorando los visitados. Esto significa que solo revisaremos B.

Para B, sumamos 1 (la distancia mínima de A, nuestro nodo actual) con 3 (el peso de la arista conectando a A con B) para obtener 4. Comparamos ese 4 con la distancia mínima de B (7) y dejamos el menor valor: 4.

Después, marcamos A como visitado y elegimos un nuevo nodo: D, que es el nodo no visitado con la menor distancia mínima.

Repetimos el algoritmo de nuevo. Esta vez, revisamos B y E.

Para B, obtenemos 2 + 5 = 7. Comparamos ese valor con la distancia mínima de B (4) y dejamos el menor valor (4). Para E, obtenemos 2 + 7 = 9, lo comparamos con la distancia mínima de E (infinito) y dejamos el valor menor (9).

Marcamos D como visitado y establecemos nuestro nodo actual en B.

Casi terminamos. Sólo debemos verificar E. 4 + 1 = 5, que es menos que la distancia mínima de E (9), así que dejamos el 5. Marcamos B como visitado y establecemos E como el nodo actual.

E no tiene vecinos no visitados, así que no verificamos nada. Lo marcamos como visitado.

Como no hay nodos no visitados, ¡terminamos! La distancia mínima de cada nodo ahora representa la mínima distancia entre ese nodo y el nodo C (el nodo que elegimos como nodo inicial).

Aquí está una descripción del algoritmo:

• Marca el nodo inicial que elegiste con una distancia actual de 0 y el resto con infinito.
• Establece el nodo no visitado con la menor distancia actual como el nodo actual A.
• Para cada vecino V de tu nodo actual A: suma la distancia actual de A con el peso de la arista que conecta a A con V. Si el resultado es menor que la distancia actual de V, establécelo como la nueva distancia actual de V.
• Marca el nodo actual A como visitado.
• Si hay nodos no visitados, ve al paso 2.

VÍDEO PARA MAYOR ENTENDIMIENTO DEL TEMA

EJERCICIO 1 METODO DE TRANSPORTE

EJERCICIO HECHO EN SOFTWARE QM

METODO DE TRANSPORTE

El problema general del transporte se refiere a la distribución de mercancía desde cualquier conjunto de centro de suministro, denominados orígenes (fuentes), hasta cualquier conjunto de centros de recepción, llamados destinos, de tal forma que se minimicen los costos totales de distribución. Cada origen tiene que distribuir ciertas unidades a los destinos y cada destino tiene cierta demanda de unidades que deben recibir de los orígenes.

Representación de una red de transporte

Como se puede observar cualquier modelo de transporte se compone de unidades de un bien a distribuir, m orígenes, n destinos, recursos en el origen, demandas en los destinos y costos de distribución por unidad. Adicionalmente, se tienen varios supuestos:

1. Supuesto de requerimientos: cada origen tiene un suministro fijo de unidades que se deben distribuir por completo entre los destinos.
2. Supuesto de costo: el costo de distribuir unidades de un origen a un destino cualquiera es directamente proporcional al número de unidades distribuidas. 
3. Propiedad de soluciones factibles: un problema de transporte tiene soluciones factible si y sólo si la sumatoria de recursos en lo m orígenes es igual a la sumatoria de demandas en los destinos. 
4. Propiedad de soluciones enteras: En los casos en los que tanto los recursos como las demandas toman un valor entero, todas las variables básicas (asignaciones), de cualquiera de las soluciones básicas factibles (inclusive la solución optima), asumen también valores enteros. 

Debido a la particularidad del modelo de transporte la forma tabular Símplex adquiere una estructura que facilita el proceso de asignación a las variables básicas, tal se muestra a continuación:

Forma Tabular Símplex Transporte

En los renglones se ubican los orígenes indicando en la columna de la derecha los recursos (oferta disponible). En las columnas se ubican los distintos destinos indicando en el último renglón los totales  demandados. En el pequeño recuadro ubicado en la margen superior derecha se indica el costo de distribuir una unidad desde el origen hasta ese destino y en la parte inferior de cada recuadro se registran las asignaciones Xi para cada variable. En los casos donde la sumatoria de los recursos y las demanda no sean las mismas, se agrega un origen o destino ficticio con la cantidad que permita cumplir la propiedad de soluciones factibles.

Después de planteado el modelo de transporte, el siguiente paso es obtener una solución básica factible, la cual se puede obtener a partir de cualquiera de los 3 criterios siguientes:

1. Regla de la esquina noroeste.
2. Método de la ruta preferente.
3. Método de aproximación de Vogel 

Antes de explicar el procedimiento para cada uno de estos criterios de asignación para encontrar la solución inicial BF, se debe conocer el número de variables básicas, el cual se determina con la expresión: m + n - 1. En el modelo anterior 3 + 2 - 1 = 4 variables básicas.

• Regla de la esquina noroeste: la primera elección X11, es decir, se inicia la asignación por la esquina noroeste de tabla. Luego se desplaza a la columna de la derecha si todavía quedan recursos en ese origen. De lo contrario se mueve al reglo debajo hasta realizar todas las asignaciones.
• Método de la ruta preferente: se fundamenta en la asignación a partir del costo mínimo de distribuir una unidad. Primero se identifica este costo se realiza la asignación de recursos máxima posible y luego se identifica el siguiente costo menor realizando el mismo procedimiento hasta realizar todas las asignaciones. 
• Método de asignación de Vogel:  para cada reglón y columna, se calcula su diferencia, que se define como la diferencia aritmética entre el costo  unitario más pequeño y el costo menor que le sigue en ese renglón o columna. En el renglón o columna con la mayor diferencia, se le asigna al menor costo unitario. Los empates se pueden romper de manera arbitraria. 

De estos 3 modelos para encontrar la solución inicial BF, el método de Vogel ha sido el más utilizado. Considerando que este criterio toma en cuenta los costos de distribución de forma más eficaz, ya que la diferencia representa el mínimo costo adicional que se incurre por no hacer una asignación en la celda que tiene el menor costo ya sea columna o renglón.

Posterior a esta asignación inicial se requiere un procedimiento que permita las siguientes iteraciones y se obtenga la solución óptima.

Prueba de optimalidad: un solución BF es óptima si y sólo si Cij - Uij -Vij >= 0 para todo (i,j) tal que Xij es no básica. Primeramente para todo variable básica de la solución actual se tiene que Cij - Uij -Vij = 0, por lo que se deduce Cij = Uij -Vij para todo (i,j) tal que Xij es básica. Para los fines de facilitar los diferentes de las diferente ecuaciones resultantes se asume el valor de U1 como cero. 

En cada iteración se determina una variable básica entrante, una variable básica saliente y luego la nueva solución básica factible. Paso 1: la variable de entrada se determina a partir de la relación  Cij - Uij -Vij, donde la variable Xij con el resultado más negativo es la que contribuye en una mejor medida a disminuir el costo total, se debe tener en cuenta que esta disminución va en proporción a la asignación resultante. Paso 2: la variable básica saliente es aquella variable básica que disminuya su valor a cero, es decir, es aquella variable de menor asignación y que participa en la reacción en cadena que se establece para compensar los cambios de asignar valor a la variable entrante que permitan satisfacer las restricciones de recursos y demandas. En este punto, se definen dos tipos variables para receptoras y donadoras, de acuerdo a la variación de signo que se produzca en el polígono que permite la transferencia desde la variable de salida a  la variable entrante. Paso 3: se encuentra la nueva solución BF, sumando el valor de la variable básica saliente a las asignaciones de las celdas receptoras y se resta a las asignaciones de las celdas donadoras.

ALGORITMO DE VOGEL
El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la culminación del método.

PASO 1

Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas.

PASO 2

Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).

PASO 3

De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0).

PASO 4: DE CICLO Y EXCEPCIONES

- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.

- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de costos mínimos, detenerse.

- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine las variables básicas cero por el método del costo mínimo, detenerse.

- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y las demandas se hayan agotado.

---

---

EJEMPLO DEL MÉTODO DE APROXIMACIÓN DE VOGEL

---

Por medio de este método resolveremos el ejercicio de transporte resuelto en módulos anteriores mediante programación lineal.

EL PROBLEMA

Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.

Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

Formule un modelo de programación lineal que permita satisfacer las necesidades de todas las ciudades al tiempo que minimice los costos asociados al transporte.

SOLUCIÓN PASO A PASO

El primer paso es determinar las medidas de penalización y consignarlas en el tabulado de costos, tal como se muestra a continuación.

El paso siguiente es escoger la mayor penalización, de esta manera:

El paso siguiente es escoger de esta columna el menor valor, y en una tabla paralela se le asigna la mayor cantidad posible de unidades, podemos observar como el menor costo es "2" y que a esa celda se le pueden asignar como máximo 60 unidades "que es la capacidad de la planta 3".

Dado que la fila de la "Planta 3" ya ha asignado toda su capacidad (60 unidades) esta debe desaparecer.

Se ha llegado al final del ciclo, por ende se repite el proceso

Iniciamos una nueva interacción

Continuamos con las interacciones,

Iniciamos otra interacción

Al finalizar esta iteración podemos observar como el tabulado queda una fila sin tachar y con valores positivos, por ende asignamos las variables básicas y hemos concluido el método.

Los costos asociados a la distribución son:

De esta manera hemos llegado a la solución a la cual también llegamos mediante programación lineal, definitivamente desarrollar la capacidad para modelar mediante programación lineal y apoyarse de una buena herramienta como WinQSB, STORM, LINGO, TORA etc. termina siendo mucho más eficiente que la utilización de los métodos heurísticos para problemas determinísticos;

Sin embargo, cabe recordar que uno de los errores más frecuentes en los que caen los ingenieros industriales es en tratar de adaptar sus organizaciones a los modelos establecidos, cabe recordar que son los modelos los que deben adaptarse a las organizaciones, lo cual requiere de determinada habilidad para realizar de forma inmediata cambios innovadores para sus fines

                 Un vídeo para mayor entendimiento

Ejercicios En programa QM

imagenes