Investigacion De Operaciones: Redes

Introducción.
En multitud de situaciones, en investigación de operaciones que se pueden modelar y resolver como redes (nodos conectados por ramas). Permiten una representación visual clara de muchos problemas que se pueden resolver con otras técnicas que resultan de esta manera más claros. El ejemplo más sencillo es encontrar el camino más corto para ir de un lugar a otro.
La representación delos resultados suele ser, además, perfectamente compresible incluso para la persona con menor conocimiento en el manejo de este tipo de representaciones graficas. Algunas aplicaciones de las redes se dan en distintos rubros, entre otras, algunas especialmente interesantes en ingeniería son:
• Diseño de una red de gasoductos.
• Determinación de la ruta más corta entre dos ciudades, en una red decarreteras.
• Determinación del cronograma de las actividades en un proyecto.
• Organización y distribución de las ventanillas en un centro de servicios para los clientes.
• Determinación del flujo máximo que puede circular por la red de comunicaciones.
• Estudio de la red vial de una ciudad o de la red telefónica de una marca.
• Problemas de canalización de aguas.
• Rutas optimas para ladistribución y recolección de mercancías.
• Determinación de los puntos críticos que garantizan el control o la fluidez de una red de comunicaciones.
• Secuencia optima de tareas en un taller de producción.
• Las relaciones de parentesco dentro de un clan.
La solución de esas situaciones y otras parecidas se logra con una variedad de algoritmos de optimización de redes, entre otros:
1. Árbolde expansión mínima.
2. Algoritmo de la ruta más corta.
3. Algoritmo del flujo máximo.
4. Algoritmo de red capacitada con costo mínimo.
5. Algoritmo de la ruta crítica.
 
Teoría De Grafos
El origen de la teoría de grafos se debe a Euler y su famoso problema de los siete puentes de la ciudad de Koinigsberg que consistía en:
El rio que rodea la Isla de Kueipof en Koinigsberg se divide en dosbrazos. Sobre los brazos del rio estaban construidos siete puentes y para los habitantes era motivo de distracción descubrir el itinerario de manera que pudieran regresar al punto de partida, después de haber cruzado los siete puentes pero pasando solo una vez por cada uno de ellos.
La investigación que realizo Euler para resolver este problema fue presentada en la Academia de Ciencias de SanPetersburg. La obra de Euler puede considerarse como el comienzo de la Teoría de Grafos, que forma parte de la topología, rama de las matemáticas que Leibniz llamó “Geometría de la Posición”.
Euler, para mayor claridad, sustituyó cada uno de los trozos de tierra firme por un punto y cada puente por un trazo, dando lugar a un esquema. Así, la isla está representada por el punto al cual llegan cincotrazos, pues son cinco los puentes que van a ella. La figura resultante es un grafo (un grafo es un conjunto de puntos llamados "vértices o nodos" del grafo y un conjunto de líneas que los unen que se llaman "aristas o lados" del grafo).
El problema planteado se reduce a dibujar la figura, partiendo de un punto, de un trazo, es decir, sin levantar el lápiz del papel y sin recorrer una misma líneados veces, A un recorrido de estas características se le llama camino Euleriano.
En la actualidad, la teoría de los grafos se utiliza en el estudio de circuitos eléctricos, en problemas de transporte, programación por computadora, planificación de proyectos, etc.
 
Conceptos fundamentales de Redes.
Una red es un conjunto de nodos (vértices o puntos) conectados por un conjunto de arcos(líneas, ramas, bordes). Existen arcos dirigidos de un nodo a otro y existen arcos que no tienen dirección. A las redes cuyos arcos no tienen dirección se les llama adireccionales.
Un grafo queda determinado por los conjuntos:
V={1,2,3,4,5} Nodos
A={(1,2)(1,3)(2,3)(2,4)(2,5)(3,5)(4,5)} Arcos o Aristas
Este grafo es un grafo no dirigido porque todos sus arcos son simétricos, es decir, el arco (1,2}...