PRIMERA UNIDAD

TEMA:01

          

                  PROBLEMA DEL CAMINO MAS CORTO

Se refiere a una red en la cual cada arco (i,j) tiene asociado un número -->Cij, el cual se intercepta como la distancia, costo o tiempo desde el nodo i hasta el nodo j. Un camino entre 2 nodos es cualquier secuencia de arcos que conecten.

El objeto consiste en encontrar el camino más corto o de menor costo desde un nodo específico hasta cada uno de los demás nodos.

ALGORITMO DE LA RUTA MAS CORTA:

1. El objetivo de la n-sima interacción es encontrar el n-sino nodo más cercano al origen.

2. Para la n-sima interacción n-1 nodos más cercanos al origen(encontrados, en las interacciones previas, incluida la ruta más corta y la distancia desde el origen.

3. Cada nodo resuelto que tiene conexión directa por una ligadura con 1 ó más nodos no resueltos proporcionan candidatos adicionales)

4. Para cada nodo resuelto y de sus candidatos se suman las distancias entre ellas y la distancia de la ruta mas corta desde el origen a ese nodo no resuelto.

El  candidato con la distancia total mas pequeña, es el n-ésimo nodo más cercano.

TEMA 02 : 

PROBLEMA DEL FLUJO MAXIMO

Se trata de enlazar un nodo fuente y un nodo destino a traves de una red de arcos, que tienen una capacidad de flujo máximo admisible.

- Caracteristicas: 

1) Todo flujo a traves de una red conexa dirigida. Se origina en un nodo llamado fuente y termina en otro nodo llamado destino. 

2) Los nodos restantes se les llama nodo de transbordo.

3) Se permite el flujo a traves de un arco, solo en la direccion indicada por la flecha donde la cantidad maxima de flujo esta dada por la capacidad del arco.

En la fuente todos los arcos señalan habia afuera y en el destino todos los arcos señalan hacia el norte.

4) El objeivo e maximizar la cantidad total de flujo de la fuente al destino.

Esta cantidad se mide en cualquiera de las dos maneras equivalentes, esto es la cantidad que sale de la fuente la cantidad que entra al destino. 

Flujo: 

Es la circulacion de unidades homogeneas de algun producto o sustancia que atraviesa una suerficie en una unidad de tiempo.

Capacidad de flujo:

Es la cantidad maxima de flujo que puede ingresar por el nodo fuente y salir por el nodo destino.

• USO DEL ALGORITMO DE FLUJO MAXIMO
  Este algoritmo se utiliza para reducir los embotellamientos entre ciertos puntos de partida y destino de una red, por ejemplo:
                                                 > Sistema de vía publica
                                                 > Transporte de petroleo
                                                 > Distribucion de energia electrica

TEMA:03

                            ÁRBOL DE EXPANSIÓN MINIMA








Esta técnica implica conectar todos los puntos de una red, al tiempo que minimiza la distancia entre ellos, tiene gran aplicación en las compañías telefónicas, para conectar entre sí varias ciudades, minimizando longitud total del cable. Para su solución se emplean los algoritmos de PRIM ó KRUSKAL.

ALGORITMO DE PRIM:

1. Seleccione inicialmente, cualquier nodo y conectar con el más próximo, que contenga el arco de menor costo.

2. Completar la red interactivamente, identificando el nodo no conectado que este más cercano ó de menor costo.

3. Agregar a este nodo el conjunto de nodos conectados. En caso de empate, este se rompe en forma arbitraria.

4. En cada etapa del proceso interactivo, la atención se centra en aquellos nodos que ya se han ensamblado. Repetir este paso hasta que se hagan conectando todos los nodos.

ALGORITMO DE KRUSKAL:

1.Comienze seleccionando el arco de menor longitud.

2.En cada interacción agregue el siguiente arco de menor longitud del conjuto de arcos disponibles, teniendo la precaución de no formar ningún ciclo.

3. El algoritmo finalizará, cuando todos los arcos estén conectados.
Si  N= n° de nodos, entonces la solución óptima, debe incluir n-1 arcos.



TEMA:04

                                      PERT Y CPM

Los modelos de redes se pueden usar como ayuda en la programación de proyectos complejos, que incluyan muchas actividades. Si se conoce con certeza la duración de cada actividad en el proyecto, sin retrasar la terminación del proyecto.

Si no se conoce con certeza la duración de las actividades, se puede utilizar la técnica de evaluación y revisión de proyectos(PERT), para estimar la probabilidad de que se termine el proyecto en la fecha limite.

El PERT Y CPM tuvieron sus orígenes en los años 50, ambos son métodos, que llevan a la determinación de un programa de tiempo, ya que estos dos algoritmos, fueron desarrollados con el mismo fin, controlar las dos variables más importantes en el desarrollo de cualquier proyecto, tiempo y recursos.

Existen 6 pasos comunes, para ambos PERT Y CPM. El procedimiento es el siguiente:

1. Definir el proyecto y todas sus actividades.

2. Desarrollar la relación entre las actividades. Decidir que actividad debe preceder a otras.

3. Dibujar la red que conecta todas las actividades.

4. Asignar estimaciones de tiempo de cada actividad.

5. Calcular la trayectoria con el tiempo más largo a través de la red, llamada ruta crítica

6. Usar la red para ayudar a planear, programar, supervisar y controlar el proyecto.