Modelos de Red

Optimizar redes como las de transporte, de comunicación, sistemas de vuelos de aeropuertos, rutas de navegación, rutas entre ciudades, entre otros.

2 conjuntos de símbolos

Nodos o Vértices

Son las localidades o ciudades en un mapa (representados por puntos

forman una cadena

problemas de la trayectoria mas corta

determina la ruta más corta entre un origen y un destino en una red de transporte.

cada arco tiene una longitud asociada a el como tal.

el algoritmo de Dijkstra

problemas de flujo maximo

las mayores cantidades que pueden fluir através de una red.

elegir cualquier trayectoria del inicio (original) a la terminación (destino) con algo de flujo.

cada nodo tienen una capacidad que limita la cantidad de producto que se podría enviar através del arco

determinar la cantidad máxima de petroleo vía tubería de un nodo a otro, teniendo en cuenta que este debe pasar por una o todas las estaciones. (los arcos representan las tuberías de distintos díametros)

Problemas de árbol de expansión mínima

Une los nodos de una red mediante la longitud mínima total de las ramas de conexión

seleccionar cualquier nodo de la red y conectarlo al nodo más cercano que minimice la distancia total.

determinar el conjunto de arcos de una red que conecta los nodos tal que minimiza la suma de la longitud de los arcos

si cada nodo de una red, representa una computadora en la universidad estatal, entonces el arco(i,j) representa un cable subterraneo que conecta la computadora i con la computadora j.

Modelos de programación de proyectos CPM - PERT

la programación de proyectos de gran tamaño, que implican muchas actividades y se conoce el tiempo de cada una con certeza

determinar la cantidad de tiempo requerido para completar un proyecto.

con certeza la duración de una actividad, se puede usar el método PERT para estimar la probabilidad de que el proyecto se complete en una fecha específica

para resolver

Arcos

pueden ser los caminos, los canales de navegación o los patrones de vuelo de un avión.