CONCEPTO Y APLICACIÓN DE ACUERDO A SU ÁREA DE TRABAJO
- WARSHALL
En informática, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algortimo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica.
El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices.
El algoritmo de Floyd-Warshall puede ser utilizado para resolver los siguientes problemas, entre otros:
- Camino mínimo en grafos dirigidos (algoritmo de Floyd).
- Cierre transitivo en grafos dirigidos (algoritmo de Warshall). Es la formulación original del algoritmo de Warshall. El grafo es un grafo no ponderado y representado por una matriz booleana de adyacencia. Entonces la operación de adición es reemplazada por la conjunción lógica (AND) y la operación menor por la disyunCión lógica (OR).
- Encontrar una expresión regular dada por un lenguaje regular aceptado por un autómata infinito (algoritmo de Kleene).
- Inversión de matrices de números reales (algoritmo de Gauss-Jordan).
- Ruta optima. En esta aplicación es interesante encontrar el camino del flujo máximo entre 2 vértices. Esto significa que en lugar de tomar los mínimos con el pseudocodigo anterior, se coge el máximo. Los pesos de las aristas representan las limitaciones del flujo. Los pesos de los caminos representan cuellos de botella; por ello, la operación de adición anterior es reemplazada por la operación mínimo.
- Comprobar si un grafo no dirigido es bipartito.
- TEORÍA DE GRAFOS
El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, el cual consistía en encontrar un camino que recorriera los siete puentes del río Pregel (
54°42′12″N20°30′56″E) en la ciudad de Königsberg, actualmente Kaliningrado, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos.
- Camino mínimo en grafos dirigidos (algoritmo de Floyd).
- Cierre transitivo en grafos dirigidos (algoritmo de Warshall). Es la formulación original del algoritmo de Warshall. El grafo es un grafo no ponderado y representado por una matriz booleana de adyacencia. Entonces la operación de adición es reemplazada por la conjunción lógica (AND) y la operación menor por la disyunCión lógica (OR).
- Encontrar una expresión regular dada por un lenguaje regular aceptado por un autómata infinito (algoritmo de Kleene).
- Inversión de matrices de números reales (algoritmo de Gauss-Jordan).
- Ruta optima. En esta aplicación es interesante encontrar el camino del flujo máximo entre 2 vértices. Esto significa que en lugar de tomar los mínimos con el pseudocodigo anterior, se coge el máximo. Los pesos de las aristas representan las limitaciones del flujo. Los pesos de los caminos representan cuellos de botella; por ello, la operación de adición anterior es reemplazada por la operación mínimo.
- Comprobar si un grafo no dirigido es bipartito.
54°42′12″N20°30′56″E) en la ciudad de Königsberg, actualmente Kaliningrado, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos.
Luego, en 1847, Gustav Kirchhoff utilizó la teoría de grafos para el análisis de redes eléctricas publicando sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos, conocidas comoleyes de Kirchhoff, considerado la primera aplicación de la teoría de grafos a un problema de ingeniería.
El término «grafo», proviene de la expresión H«graphic notation» usada por primera vez por Edward Frankland3 y posteriormente adoptada por Alexander Crum Brown en 1884, y hacía referencia a la representación gráfica de los enlaces entre los átomos de una molécula.
Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.
Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo deFloyd.
Para la administración de proyectos, utilizamos técnicas como técnica de revisión y evaluación de programas (PERT) en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.
La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse gráficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se transmite y a quiénes.
Se emplea en problemas de control de producción, para proyectar redes de ordenadores, para diseñar módulos electrónicos modernos y proyectar sistemas físicos con parámetros localizados (mecánicos, acústicos y eléctricos).
Se usa para la solución de problemas de genética y problemas de automatización de la proyección (SAPR). Apoyo matemático de los sistemas modernos para el procesamiento de la información. Acude en las investigaciones nucleares (técnica de diagramas de Feynman).5
Los grafos son importantes en el estudio de la biología y hábitat. El vértice representa un hábitat y las aristas (o "edges" en inglés) representa los senderos de los animales o las migraciones. Con esta información, los científicos pueden entender cómo esto puede cambiar o afectar a las especies en su hábitat.
- ESQUINA NOROESTE
El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas de transporte u otros, mediante la consecución de una solución básica inicial que satisfaga todas las restricciones existentes sin que esto implique que se alcance el costo óptimo total.
Este método tiene como ventaja frente a sus similares la rapidez de su ejecución, y es utilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muy elevado.
Su nombre se debe al génesis del algoritmo, el cual inicia en la ruta, celda o esquina Noroeste. Es común encontrar gran variedad de métodos que se basen en la misma metodología de la esquina Noroeste, dado que podemos encontrar de igual manera el método e la esquina Noreste, Sureste o Suroeste.
Se parte por esbozar en forma matricial el problema, es decir, filas que representen fuentes y columnas que representen destinos, luego el algoritmo debe de iniciar en la celda, ruta o esquina Noroeste de la tabla (esquina superior izquierda).
PASO 1:
En la celda seleccionada como esquina Noroeste se debe asignar la máxima cantidad de unidades posibles, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la cantidad asignada a la celda.
PASO 2:
En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del "Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso.
PASO 3:
Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es el caso se ha llegado al final el método, "detenerse".
La segunda es que quede más de un renglón o columna, si este es el caso iniciar nuevamente el "Paso 1".
En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del "Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso.
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
Ahora la cantidad asignada a la esquina noroeste es restada a la demanda de Cali y a la oferta de la "Planta 1", en un procedimiento muy lógico. Dado que la demanda de Cali una vez restada la cantidad asignada es cero (0), se procede a eliminar la columna. El proceso de asignación nuevamente se repite.
Continuamos con las iteraciones.
En este caso nos encontramos frente a la elección de la fila o columna a eliminar (tachar), sin embargo podemos utilizar un criterio mediante el cual eliminemos la fila o columna que presente los costos más elevados. En este caso la "Planta 2".
Nueva iteración.
Una vez finalizada esta asignación, se elimina la "Planta 3" que ya ha sido satisfecha con la asignación de 60 unidades, por ende nos queda una sola fila a la cual le asignamos las unidades estrictamente requeridas y hemos finalizado el método.
El cuadro de las asignaciones (que debemos desarrollarlo paralelamente) queda así:
Los costos asociados a la distribución son:
El costo total es evidentemente superior al obtenido mediante programación lineal , lo cual demuestra lo enunciado en la descripción del algoritmo que cita que no obtiene siempre la mejor solución, sin embargo presenta un cumplimiento de todas las restricciones y una rapidez de elaboración, lo cual es una ventaja en problemas con innumerables fuentes y destinos en los cuales no nos importe más que satisfacer las restricciones.
- RUTA CRÍTICA
El método de la ruta crítica CPM (Critical Path Method) es un algoritmo basado en la teoría de redes diseñado para facilitar la planificación de proyectos. El resultado final del CPM 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 CPM se desarrolla mediante intervalos determinísticos, lo cual lo diferencia del método PERT que supone tiempos probabilísticos.
Regla 1: Cada actividad se debe representar sí y sólo sí, por un ramal o arco.
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.
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á relacionarse el tiempo estimado para el desarrollo de cada actividad.
PASO 2: 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:
Fb y Fd corresponde a actividades ficticias que no consumen tiempo ni recursos.
PASO 3: 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 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 4, en el que concurren la finalización de 3 actividades, 2 de ellas ficticias (Fb y Fd, cuyos tiempos son cero) y una es la actividad C. En este caso deberá considerarse el mayor de los T1 resultantes:
T1 (nodo 3) + Fb = 4 + 0 = 4
T1 (nodo 2) + C = 3 + 2 = 5
T1 ( nodo 5) + Fd = 5 + 0 = 5
Así entonces, el T1 del nodo 4 será igual a 5 (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.
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 2, en el que concurren el inicio de varias actividades deberá entonces considerarse lo siguiente:
T2 nodo 3 - B = 5 - 1 = 4
T2 nodo 4 - C = 5 - 2 = 3
T2 nodo 5 - D = 5 - 2 = 3
Así entonces, el T2 del nodo 2 será 3, 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, como es el caso del problema que hemos desarrollado.
Ruta crítica 1:
Esta ruta se encuentra compuesta por las actividades A, C y E. La duración del proyecto será de 9 horas.
Ruta Crítica 2:
PASO 4: ESTABLECER EL CRONOGRAMA
Para establecer un cronograma deberán considerarse varios factores, el más importante de ellos es la relación de precedencia, y el siguiente corresponde a escalonar las actividades que componen la ruta crítica de tal manera que se complete el proyecto dentro de la duración estimada.
