INVESTIGACION DE OPERACIONES

Aplicación de la vida real. Ahorro de recursos federales para viáticos
Las oficinas del gobierno federal de Estados Unidos están localizadas en la mayoría delas ciudades en los Estados Unidos, y se requiere que los empleados federales asistan a conferencias de desarrollo y cursos de capacitación que se ofrecen por todo el país. La ubicación de la ciudad donde se efectuarán las conferencias yeventos de capacitaciónpuede impactar los viáticos. El objetivo del estudio es determinar la ubicación óptima
de la ciudad anfitriona de una conferencia o evento de entrenamiento programado. Se estima que para el año fiscal de 1997, el modelo desarrollado ahorró al menos$400,000. El caso 4 del capítulo 26 en el sitio web proporciona los detalles.






ALCANCE Y DEFINICIÓN DE MODELOS DEREDES
Muchas situaciones de investigación de operaciones pueden modelarse y resolverse como redes (nodos conectados por ramas); a continuación tenemos algunos ejemplos de aplicación:
1. Diseño de una red de oleoductos para gas natural a una determinada distancia de
la costa para conectar los cabezales de los pozos en el Golfo de México a un
punto de distribución costero con el objetivo deminimizar el costo de construcción
de los oleoductos.
2. Determinación de la ruta más corta entre dos ciudades en una red existente de
carreteras.
3. Determinación de la capacidad máxima (en toneladas por año) de una red de
oleoductos para lodos de carbón que unen minas de carbón en Wyoming con
plantas eléctricas en Houston (los oleoductos para lodos transportan carbón al
bombear agua a través detuberías especialmente diseñadas).
4. Determinación del cronograma (fechas de inicio y terminación) para las actividades
de un proyecto de construcción.
5. Determinación del itinerario de flujo de costo mínimo desde campos petroleros
hasta refinerías a través de una red de oleoductos.
La solución de estas situaciones se logra por medio de varios algoritmos de optimización
de redes.
1. Árbolde mínima expansión
2. Algoritmo de la ruta más corta
3. Algoritmo de flujo máximo
4. Algoritmo de la ruta crítica (CPM)























Una red consiste en un conjunto de puntos y un conjunto de líneas que unen ciertos pares de
puntos. Los puntos se llaman nodos (o vértices) Las líneas se llaman arcos (o ligaduras, aristas o
ramas)”

La notación paradescribir una red es (N,A), donde N es el conjunto de nodos, y A es el conjunto de arcos











Se dice que un arco está dirigido u orientado si permite el flujo positivo sólo en una dirección. Una red dirigida tiene todos los arcos dirigidos







.Los nodos no orientados (los no dirigidos) son aquellos cuyos vértices se encuentran unidos por riatas:Vértices (nodos): (x1, x2, x3, x4, x5, x6)
Aristas: x1x2, x1x6, x2x3, etc., x1 y x2 son extremos de una arista.

Una ruta es un conjunto de arcos que unen dos nodos distintos, y que pasan a través de otros nodos en la red.
Por ejemplo, los arcos (1,2), (2,3), (3,4) y (4,5) forman una ruta entre los nodos 1 y 5. Una ruta forma un ciclo o un bucle si conecta un nodo de vuelta a sí mismo a través deotros nodos. En la figura 6.1, los arcos
(2,3), (3,4) y (4,2) forman un ciclo. Se dice que una red está conectada si cada dos nodos distintos están conectadosen al menos una ruta.
figura 6.1 ejemplo de una red



ÁRBOL DE EXPANSIÓN MÍNIMA
El problema del árbol de expansión mínima tiene algunas similitudes con la versión principal del
problema de la ruta más corta.En ambos casos se considerauna red no dirigida y conexa. Los dos problemas involucran también el hecho de seleccionar un conjunto de ligaduras con la longitud total más corta entre todos los conjuntos de ligaduras que satisfacen cierta propiedad.Para el árbol de expansión mínima la propiedad que se requiere es que las ligaduras seleccionadas deben proporcionar una trayectoria entre cada par de nodos.
El problema del árbol...