Camino más corto
Los problemas conocidos como problemas del camino mínimo o camino más corto, tratan como su nombre indica de hallar la ruta mínima o más corta entre dos puntos. Este mínimo puede ser la distancia entre los puntos origen y destino o bien el tiempo transcurrido para trasladarse desde un punto a otro. Se aplica mucho para problemas de redes de comunicaciones.
Este tipo de problemas pueden ser resueltos por el método del Simplex, sin embargo existen otros métodos más eficientes como por ejemplo el algoritmo de Dijkstra o el de Bellman-Ford.
Ejemplo
Una persona tiene que desplazarse a diario de un pueblo 1 a otro 7. Está estudiando cual es el trayecto más corto usando un mapa de carreteras. Las carreteras y sus distancias están representadas en la figura siguiente:
Se determinan las variables de decisión, en este caso:
- Xij: acción de desplazarse del pueblo i al j (0 indica que no hay desplazamiento y 1 que sí hay desplazamiento)
Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen del balance entre los posibles caminos que parten desde cada pueblo y los que llegan hasta él (obviando los caminos que nos devuelvan al punto de partida y los que provengan del punto de destino):
- Balance de caminos del pueblo 1: X12 + X13 = 1
- Balance de caminos del pueblo 2: X24 + X25 – X12 – X42 – X52 = 0
- Balance de caminos del pueblo 3: X34 + X36 – X13 – X43 – X63 = 0
- Balance de caminos del pueblo 4: X42 + X43 + X45 – X24 – X34 – X54 = 0
- Balance de caminos del pueblo 5: X52 + X54 + X57 – X25 – X45 =
Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados valores, … En este caso las restricciones son que las variables deben ser booleanas (0 no se toma el camino, 1 se toma), y por lo tanto no pueden ser negativas:
- Xij ≥ 0
- Xij es booleano
Se determina la función objetivo:
- Minimizar Z = 12·X12 + 4·X13 + 5·X24 + 3·X25 + 2·X34 + 10·X36 + 5·X42 + 2·X43 + 10·X45 + 3·X52 + 10·X54 + 2·X57 + 10·X63 + 4·X67
Flujo máximo
En algunas redes circula por los arcos un flujo (envío o circulación de unidades homogéneas de algún producto: automóviles en una red de carreteras, litros de petróleo en un oleoducto, bits por un cable de fibra óptica) desde el origen o fuente al destino, también denominado sumidero o vertedero. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:
- El flujo es siempre positivo y con 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.
En el caso de que el origen o el destino no existan en el problema, se añaden ficticiamente utilizando arcos unidireccionales de capacidad infinita, como en grafo mostrado a continuación:
- Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción completa del flujo entre el origen y el destino. La capacidad de corte es igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes posibles en la red , el corte con la menor capacidad proporciona el flujo máximo en la red.
El siguiente grafo ilustra 3 cortes: el Corte 1 con capacidad 60, el Corte 2 con capacidad 110 y el Corte 3 con capacidad 70. Todo lo que podemos obtener de los 3 cortes es que el flujo máximo en la red no excede de 60 unidades. No podemos saber cual es el flujo máximo hasta que se hayan enumerado todos los cortes en la red:
Las capacidades se identifican como sigue: por ejemplo, para el arco (3,4), el límite de flujo es de 10 unidades de 3 a 4 y de 5 unidades de 4 a 3.
Algoritmo 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.
La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino.
Consideraremos las capacidades iniciales del arco que une el nodo i y el nodo j como Cij y Cji. Estas capacidades iniciales irán variando a medida que avanza el algoritmo, denominaremos capacidades residuales a las capacidades restantes del arco una vez pasa algún flujo por él, las representaremos como cij y cji.
Para un nodo j que recibe el flujo del nodo i, definimos una clasificación [aj,i] donde aj es el flujo del nodo i al nodo j.
Ejemplo: Determinar el flujo máximo en la red siguiente:
Iteración 1:
Determinamos las residuales iniciales (cij,cji) iguales a las capacidades iniciales (Cij,Cji).
- Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
- Paso 2: S1={2,3,4} (no vacío).
- Paso 3: k=3 ya que c13=max{c12,c13,c14}={20,30,10}=30. Hacemos a3=c13=30 y clasificamos el nodo 3 con [30,1]. Tomamos i=3 y repetimos el paso 2.
- Paso 2: S3={4,5}
- Paso 3: k=5 y a5=c35=max{10,20}=20. Clasificamos el nodo 5 con [20,3]. Logramos la penetración, vamos al paso 5.
- Paso 5: La ruta de la penetración se determina de las clasificaciones empezando en el nodo 5 y terminando en el nodo 1, es decir, 5→[20,3]→3→[30,1]→1.
Entonces la ruta es N1={1,3,5} y f1=min{a1,a3,a5}={∞,30,20}=20. Las capacidades residuales a lo largo de esta ruta son:
(c13,c31)=(30-20, 0+20)=(10,20)
(c35,c53)=(20-20, 0+20)=(0,20)
Iteración 2:
- Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
- Paso 2: S1={2,3,4}.
- Paso 3: k=2 y a2=c12=max{20,10,10}=20. Clasificamos el nodo 2 con [20,1]. Tomamos i=2 y repetimos el paso 2.
- Paso 2: S2={3,5}
- Paso 3: k=3 y a3=c23=max{30,40}=40. Clasificamos el nodo 3 con [40,2]. Tomamos i=3 y repetimos el paso 2.
- Paso 2: S3={4} (c35=0, el nodo 1 ya ha sido clasificado y el nodo 2 cumple ambas condiciones, por tanto los nodos 1, 2 y 5 no pueden ser incluidos en S3).
- Paso 3: k=4 y a4=c34=10. Clasificamos el nodo 4 con [10,3]. Tomamos i=4 y repetimos el paso 2.
- Paso 2: S4={5}
- Paso 3: k=5 y a5=c45=20. Clasificamos el nodo 5 con [20,4]. Logramos la penetración, vamos al paso 5.
- Paso 5: La ruta de la penetración es: 5→[20,4]→4→[10,3]→3→[40,2]→2→[20,1]→1.
Entonces la ruta es N2={1,2,3,4,5} y f2=min{∞,20,40,10,20}=10. Las capacidades residuales a lo largo de esta ruta son:
(c12,c21)=(20-10, 0+10)=(10,10)
(c23,c32)=(40-10, 0+10)=(30,10)
(c34,c43)=(10-10, 5+10)=(0,15)
(c45,c54)=(20-10, 0+10)=(10,10)
Iteración 3:
- Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
- Paso 2: S1={2,3,4}.
- Paso 3: k=2 y a2=c12=max{10,10,10}=10, rompemos el empate arbitrariamente. Clasificamos el nodo 2 con [10,1]. Tomamos i=2 y repetimos el paso 2.
- Paso 2: S2={3,5}
- Paso 3: k=3 y a3=c23=max{30,30}=30. Clasificamos el nodo 3 con [30,2]. Tomamos i=3 y repetimos el paso 2.
- Paso 2: S3 vacío ya que c34=c35=0. Vamos al paso 4 para retroceder.
- Paso 4: La clasificación [30,2] nos dice que el nodo inmediatamente precedente es el 2. Eliminamos el nodo 3 de una consideración posterior en esta iteración. Tomamos i=2 y repetimos el paso 2.
- Paso 2: S2={5}
- Paso 3: k=5 y a5=c25=30. Clasificamos el nodo 5 con [30,2]. Logramos la penetración, vamos al paso 5.
- Paso 5: La ruta de la penetración es: 5→[30,2]→2→[10,1]→1.
Entonces la ruta es N2={1,2,5} y f3=min{∞,10,30}=10. Las capacidades residuales a lo largo de esta ruta son:
(c12,c21)=(10-10, 10+10)=(0,20)
(c25,c52)=(30-10, 0+10)=(20,10)
Iteración 4:
- Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
- Paso 2: S1={3,4}.
- Paso 3: k=3 y a3=c13=max{10,10}=10. Clasificamos el nodo 3 con [10,1]. Tomamos i=3 y repetimos el paso 2.
- Paso 2: S3={2}
- Paso 3: k=2 y a2=c32=10. Clasificamos el nodo 2 con [10,3]. Tomamos i=2 y repetimos el paso 2.
- Paso 2: S2={5}
- Paso 3: k=5 y a5=c25=20. Clasificamos el nodo 5 con [20,2]. Logramos la penetración, vamos al paso 5.
- Paso 5: La ruta de la penetración es: 5→[20,2]→2→[10,3]→3→[10,1]→1.
Entonces la ruta es N4={1,3,2,5} y f4=min{∞,10,10,20}=10. Las capacidades residuales a lo largo de esta ruta son:
(c13,c31)=(10-10, 20+10)=(0,30)
(c32,c23)=(10-10, 30+10)=(0,40)
(c25,c52)=(20-10, 10+10)=(10,20)
Iteración 5:
- Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
- Paso 2: S1={4}.
- Paso 3: k=4 y a4=c14=10. Clasificamos el nodo 4 con [10,1]. Tomamos i=4 y repetimos el paso 2.
- Paso 2: S4={3,5}
- Paso 3: k=3 y a3=c23=max{15,10}=15. Clasificamos el nodo 3 con [15,4]. Tomamos i=3 y repetimos el paso 2.
- Paso 2: S3 vacío ya que c32=c34=c35=0. Vamos al paso 4 para retroceder.
- Paso 4: La clasificación [15,4] nos dice que el nodo inmediatamente precedente es el 4. Eliminamos el nodo 3 de una consideración posterior en esta iteración. Tomamos i=4 y repetimos el paso 2.
- Paso 2: S4={5}
- Paso 3: k=5 y a5=c45=10. Clasificamos el nodo 5 con [10,4]. Logramos la penetración, vamos al paso 5.
- Paso 5: La ruta de la penetración es: 5→[10,4]→4→[10,1]→1.
Entonces la ruta es N2={1,4,5} y f3=min{∞,10,10}=10. Las capacidades residuales a lo largo de esta ruta son:
(c14,c41)=(10-10, 0+10)=(0,10)
(c45,c54)=(10-10, 10+10)=(0,20)
Iteración 6:
No son posibles más penetraciones, debido a que todos los arcos fuera del nodo 1 tienen residuales cero. Vayamos al paso 6 para determinar la solución.
- Paso 6: El flujo máximo en la red es F=f1+f2+…+f5=60 unidades. El flujo en los diferentes arcos se calcula restando las últimas residuales obtenidas en la última iteración de las capacidades iniciales:
Árbol de expansión mínima
Un árbol de expansión, árbol generador o árbol recubridor T de un grafo conexo, no dirigido G es un árbol compuesto por todos los vértices y algunas (quizá todas) de las aristas de G. Informalmente, un árbol de expansión de G es una selección de aristas de G que forman un árbol que cubre todos los vértices. Esto es, cada vértice está en el árbol, pero no hay ciclos. Por otro lado, todos los puentes de G deben estar contenidos en T.
Un árbol de expansión o árbol recubridor de un grafo conexo G puede ser también definido como el mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.
En ciertos campos de la teoría de grafos es útil encontrar el mínimo árbol de expansión de un grafo ponderado. También se han abordado otros problemas de optimización relacionados con los árboles de expansión, como el máximo árbol de expansión, el máximo árbol que cubre al menos k vértices, el mínimo árbol de expansión con k aristas por vértice como máximo (árbol de expansión de mínimo grado, MDST por sus siglas en inglés), el árbol de expansión con el máximo número de hojas (estrechamente relacionado con el problema del menos conjunto dominante y conexo), el árbol de expansión con el menor número de hojas (relacionado con el problema del camino hamiltoniano), el árbol de expansión de mínimo diámetro o el árbol de expansión de la mínima dilación.
Algoritmo de Kruskal
Para poder comprender el algoritmo de kruskal será necesario revisar primer el tutorial de Union-Find.
Como trabaja:
Primeramente ordenaremos las aristas del grafo por su peso de menor a mayor. Mediante la técnica greedy Kruskal intentara unir cada arista siempre y cuando no se forme un ciclo, ello se realizará mediante 
Union-Find. Como hemos ordenado las aristas por peso comenzaremos con la arista de menor peso, si los vértices que contienen dicha arista no están en la misma componente conexa entonces los unimos para formar una sola componente mediante Union(x , y), para revisar si están o no en la misma componente conexa usamos la función SameComponent(x , y) al hacer esto estamos evitando que se creen ciclos y que la arista que une dos vértices siempre sea la mínima posible.
PERT Y CPM
Dos son los orígenes del método del camino crítico: el método PERT (Program Evaluation and Review Technique) desarrollo por la Armada de los Estados Unidos de América, en 1957, para controlar los tiempos de ejecución de las diversas actividades integrantes de los proyectos espaciales, por la necesidad de terminar cada una de ellas dentro de los intervalos de tiempo disponibles. Fue utilizado originalmente por el control de tiempos del proyecto Polaris y actualmente se utiliza en todo el programa espacial.
El método CPM (Crítical Path Method), el segundo origen del método actual, fue desarrollado también en 1957 en los Estados Unidos de América, por un centro de investigación de operaciones para la firma Dupont y Remington Rand, buscando el control y la optimización de los costos de operación mediante la planeación adecuada de las actividades componentes del proyecto.
Ambos métodos aportaron los elementos administrativos necesarios para formar el método del camino crítico actual, utilizando el control de los tiempos de ejecución y los costos de operación, para buscar que el proyecto total sea ejecutado en el menor tiempo y al menor costo posible.
La principal diferencia entre los métodos es la manera en que se realizan los estimativos de tiempo.
PERT
- Probabilístico.
- Considera que la variable de tiempo es una variable desconocida de la cual solo se tienen datos estimativos.
- El tiempo esperado de finalización de un proyecto es la suma de todos los tiempos esperados de las actividades sobre la ruta crítica.
- Suponiendo que las distribuciones de los tiempos de las actividades son independientes, (una suposición fuertemente cuestionable), la varianza del proyecto es la suma de las varianzas de las actividades en la ruta crítica.
- Considera tres estimativos de tiempos: el más probable, tiempo optimista, tiempo pesimista.
CPM
- Deterministico. Ya que considera que los tiempos de las actividades se conocen y se pueden variar cambiando el nivel de recursos utilizados.
- A medida que el proyecto avanza, estos estimados se utilizan para controlar y el progreso. Si ocurre algún retardo en el proyecto,
- se hacen esfuerzos por lograr que el proyecto quede de nuevo en programa cambiando la asignación de recursos.
- Considera que las actividades son continuas e interdependientes, siguen un orden cronológico y ofrece parámetros del momento oportuno del inicio de la actividad.
- Considera tiempos normales y acelerados de una determinada actividad, según la cantidad de recursos aplicados en la misma.
El campo de acción de este método es muy amplio, dada su gran flexibilidad y adaptabilidad a cualquier proyecto grande o pequeño. Para obtener los mejores resultados debe aplicarse a los proyectos que posean las siguientes características:
- Que el proyecto sea único, no repetitivo, en algunas partes o en su totalidad.
- Que se deba ejecutar todo el proyecto o parte de el, en un tiempo mínimo, sin variaciones, es decir, en tiempo crítico.
- Que se desee el costo de operación más bajo posible dentro de un tiempo disponible.
Dentro del ámbito aplicación, el método se ha estado usando para la planeación y control de diversas actividades, tales como construcción de presas, apertura de caminos, pavimentación, construcción de casas y edificios, reparación de barcos, investigación de mercados, movimientos de colonización, estudios económicos regionales, auditorias, planeación de universitarias, distribución de tiempos de salas de operaciones, ampliaciones de fábrica, planeación de itinerarios para cobranzas, de venta, censos de población, etc., etc.
- Enseña una disciplina lógica para planificar y organizar un programa detallado de largo alcance.
- Proporciona una metodología Standard de comunicar los planes del proyecto mediante un cuadro de tres dimensiones (tiempo, personal; costo).
- Identifica los elementos (segmentos) más críticos del plan, en que problemas potenciales puedan perjudicar el cumplimiento del programa propuesto.
- Ofrece la posibilidad de simular los efectos de las decisiones alternativas o situaciones imprevistas y una oportunidad para estudiar sus consecuencias en relación a los plazos de cumplimiento de los programas.
- Aporta la probabilidad de cumplir exitosamente los plazos propuestos.
- En otras palabras: CPM es un sistema dinámico, que se mueve con el progreso del proyecto, reflejando en cualquier momento el STATUS presente del plan de acción.
Para aplicar CPM o PERT se requiere conocer la lista de actividades que incluye un proyecto. Se considera que el proyecto esta terminado cuando todas las actividades han sido completadas. Para cada actividad, puede existir un conjunto de actividades predecesoras que deben ser completadas antes de que comience la nueva actividad. Se construye una malla o red del proyecto para graficar las relaciones de precedencia entre las actividades. En dicha representación grafica, cada actividad es representada como un arco y cada nodo ilustra la culminación de una o varias actividades.
Consideremos un proyecto que consta de solo dos actividades A y B. Supongamos que la actividad A es predecesora de la actividad B. La representación grafica de este proyecto se muestra en la figura. Así, el nodo 2 representa la culminación de la actividad A y el comienzo de la actividad B.
Ejemplo:
Árbol de expansión mínima
Union-Find. Como hemos ordenado las aristas por peso comenzaremos con la arista de menor peso, si los vértices que contienen dicha arista no están en la misma componente conexa entonces los unimos para formar una sola componente mediante Union(x , y), para revisar si están o no en la misma componente conexa usamos la función SameComponent(x , y) al hacer esto estamos evitando que se creen ciclos y que la arista que une dos vértices siempre sea la mínima posible.
