Cpm- Ruta Critica

Métodos de Camino Crítico
Conceptos Base:
* Un grafo simple dirigido diremos que es grafo ponderado si tiene asociado una función W: A —> R llamada función de ponderación. La imagen de cada arco determinada por los vértices Vi y Vj la llamaremos peso del arco y lo denotaremos por Wij.
* Sea G un grafo ponderado finito, llamaremos matriz de peso del grafo G a la siguiente matriz deorden nxn:
W=[Aij] / Aij = { Wij si (Vi, Vj) pertenecen a A;{ infinito si (Vi, Vj) no pertenecen a A;
Cada arco o arista tiene un peso, por ejemplo en el grafo dirigido Wbd = 21.
Grafo A / Grafo B

La matriz de peso contendrá el peso de los arcos/aristas, si el vértice x no es adyacente con y en la matriz pondremos Wxy = ∞
Las matrices de pesos de los grafos anteriores son:

* En un grafoponderado llamamos peso de un camino a la suma de los pesos de los arcos que lo forman.
* En un grafo ponderado llamamos camino más corto entre dos vértices al camino de peso mínimo entre dichos vértices.
* En un grafo ponderado llamamos camino más largo (o crítico) entre dos vértices al camino de peso máximo entre dichos vértices.
Ejemplo:

Ejemplo:
Peso del camino A,C
Wab + Wbc = 4Camino más corto A, F
Camino críticio A, F
Wab + Wbc + Wcd + Wdf = 10 (mayor peso)
Wae + Wef = 8 (menor peso)
CAMINOS MÁS CORTOS
Suponemos que:
* los pesos asociados a los arcos son todos no negativos.
* el grafo es dirigido.
* los vértices están numerados de 1 a n, de forma que Wij representa el peso del arco (i,j) y que el vértice 1 es el origen del camino. Además, Uj denotaráel peso del camino más corto de 1 a j.
Teorema: Sea 1, …., k, ….., j un camino más corto entre los vértices 1 y j de un grafo ponderado G. Entonces las secciones de este camino 1, ….., k, ….., j son los caminos más cortos entre los vértices respectivos.
Corolario: Supongamos que en un grafo ponderado tenemos un camino más corto entre los vértices 1 y j. Sea k el vértice inmediatamente anteriora j en este camino. Entonces la sección de este camino desde 1 a k es el camino más corto entre estos dos vértices. Además: Uj= Uk + Wkj
Ecuaciones de Bellman
U1 = 0
Uj = min{Uk + Wkj}           j = 2, …., n        (siendo k diferente de j)
GRAFOS ACÍCLICOS. MÉTODO DEL CAMINO CRÍTICO
Teorema: Un grafo dirigido no tiene circuitos si y sólo si existe una numeración de los vértices para la quese cumple que si (i,j) es un arco del grafo entonces i < j.
Con esta numeración, las ecuaciones de Bellman quedan así:
U1 = 0
Uj = min[Uk + Wkj}       j = 2, …. , n        (siendo k < j)
Los grafos ponderados

Uno de los clásicos problemas que la teoría de grafos puede organizar es la ordenación.
La ordenación se puede representar como la programación de ejecución de la un trabajo,asignando recursos y fijando las fechas de ejecución de las tareas que lo componen.

Modelado de los problemas de ordenamientos
Clásicamente las tareas sujetas a restricciones temporales se modelan con un grafo ponderado. Si se considera entonces el problema sin restricciones de recursos, los algoritmos de caminos, aplicados a este grafo, permiten calcular las secuencias de fechas más tempranas ymás tardías, de comienzo y finalización de las tareas, como veremos más adelante. Se trata entonces de encontrar un ordenamiento optimal en el espacio de soluciones del problema, restringido solamente a ligaduras temporales, o relaciones de sucesión en el tiempo. Este es llamado problema central de los ordenamientos. Existen variantes de modelado que permiten la introducción de restricciones derecursos, por ejemplo redes de Petri temporizadas, grafos bivaluados, entre otros.

Ordenamiento de Tareas:
Se trata de ordenar, en una duración minimal, un conjunto I = {1,...n} de tareas sujetas
a restricciones temporales del tipo desigualdad de potencial:
tj - ti aij, i,j I
donde ti (respectivamente tj) es la fecha de comienzo de la tarea i (resp. j) y aij un real
cualquiera.
El...