REDES EN INVESTIGACIÓN DE OPERACIONES
"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 arco(o ligaduras, aristas o ramas). (Hillier Frederick, 1992)."
Las redes son rutas invisibles sobre las cuales se van a mover los "Recursos" o las "Entidades".• Para que una red cumpla con su función, debe estar unida a las "Locaciones" por medio de "Interfaces“.• Una red puede estar conformada por muchos tramos, los cuales están separados por "Nodos", y cada "Nodo" debe tener su respectiva "Interfaz".• Cuando la red cambia de dirección en un punto que no esté conectado a una "Locación", se habla de "Puntos de Quiebre".
Terminología y conceptos básicos:
- El Nodo es un círculo en un diagrama de redes que representan un aspecto importante de un problema,el nodo representa el origen y destino de bienes de un plan a realizar.
- El Arco es una línea que conecta dos nodos en un diagrama esquemático que representa una relación entre estos dos nodos,el arco es una curva que enlaza dos nodos, estableciendo así una conexión en cuanto a la representación gráfica en un sistema.
Los problemas de optimización de redes se pueden representar en términos generales a través de uno de estos cuatro modelos:
Modelo de minimización de redes (Problema del árbol de mínima expansión).
Modelo de la ruta más corta.
Modelo del flujo máximo.
Modelo del flujo del costo mínimo.
Modelo de minimización de redes.
El modelo de minimización de redes o problema del árbol de mínima expansión tiene que ver con la determinación de los ramales que pueden unir todos los nodos de una red, tal que minimice la suma de las longitudes de los ramales escogidos. No se deben incluir ciclos en al solución del problema.
Para crear el árbol de expansión mínima tiene las siguientes características:
Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras potenciales y la longitud positiva para cada una si se inserta en la red. (Las medidas alternativas para la longitud de una ligadura incluyen distancia, costo y tiempo.)
Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un camino entre cada par de nodos.
El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las ligaduras insertadas en la red.
Una red con n nodos requiere sólo (n-1) ligaduras para proporcionar una trayectoria entre cada par de nodos. Las (n-1) ligaduras deben elegirse de tal manera que la red resultante formen un árbol de expansión. Por tanto el problema es hallar el árbol de expansión con la longitud total mínima de sus ligaduras.
Algoritmo para construir el árbol de expansión mínima:
Se selecciona, de manera arbitraria, cualquier nodo y se conecta (es decir, se agrega una ligadura) al nodo distinto más cercano.
Se identifica el nodo no conectado más cercano a un nodo conectado y se conectan estos dos nodos (es decir, se agrega una ligadura entre ellos). Este paso se repite hasta que todos los nodos están conectados.
Empates: los empates para el nodo más cercano distinto (paso 1) o para el nodo no conectado más cercano (paso 2), se pueden romper en forma arbitraria y el algoritmo debe llegar a una solución optima. No obstante, estos empates son señal de que pueden existir (pero no necesariamente) soluciones optimas múltiples. Todas esas soluciones se pueden identificar si se trabaja con las demás formas de romper los empates hasta el final.
Modelo de la Ruta mas Corta.
El método de la ruta más corta es un método de programación lineal, que permite buscar la solución a un problema de optimización que resulte de una combinatoria y de diferentes aplicaciones, el objetivo de este método esta en encontrar rutas cortas o de menor costo, según sea el caso, que va desde un nodo especifico hasta cada uno de los demás nodos de la red.
importancia
Este método es muy importante ya que por medio de este modelo se pueden resolver de manera rápida, ya que pueden formularse como modelos de redes obteniendo soluciones enteras sin necesidad de restricciones (aunque en algunos casos pudieran tenerlas), asimismo se puede decir que no importa que tan grande sea el problema se puede resolver por pequeños algoritmos.
Aplicaciones:
• Transporte.
• Horarios de operadores telefónicos.
• Planeación de tráfico urbano.
• Trasbordo .
• En las redes eléctricas.
• Diseño de rutas de vehículos.
• Telecomunicaciones.
• Planeación de inventarios • Planeación de producción.
El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. el objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino. se trata de encontrar la ruta de menor distancia, o costo, entre el punto de partida o nodo inicial y el destino o nodo terminal
Modelo del Flujo de Costo Mínimo.
El flujo de costo mínimo se define como el envió de la oferta disponible ó flujo a través de los diferentes arcos ó la red,satisfaciendo al mismo tiempo las relaciones del flujo en los arcos y las cantidades de la oferta y demanda en los nodos, tal que el costo de envío sea mínimo. La aplicación más importante de este problema es la operación de cualquier red de distribución, otras que son también comunes se presentan a continuación:
- Aplicación Red de distribución ó suministros Fuentes
- Fuentes de bienes ó suministros
- Tipo de Nodos De trasbordo Bodegas ó almacenes intermedios
- Administración de flujo de efectivo Fuentes de efectivo en tiempos específicos
- Opciones de inversión a corto plazo
- Administración de desechos sólidos
- Coordinación de mezcla de productos en plantas
- Fuente de desechos sólidos Instalaciones de procesamiento
- Rellenos Plantas Producción de un artículo específico
- Distribuidor Demanda Clientes internos ó externos
- Necesidades de efectivo en tiempos específicos
Este problema es gran importancia en problemas de optimización de redes como problemas de flujo máximo, la ruta más corta, el problema del transporte y el de asignación ya que son casos especiales del problema de flujo de costo mínimo y abarca diversas aplicaciones, su solución es muy eficiente ya que se puede formular como un problema de programación lineal, y por lo tanto se puede resolver mediante una versión simplificada del método simplex llamada método simplex de redes.
Modelo de Flujo Máximo.
Se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad de flujo entre la fuente y el destino.
Características:
Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado fuente, y termina en otro nodo llamado destino.
Los nodos restantes son nodos de trasbordo.
Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dad por la capacidad del arco. En la fuente, todos los arcos señalan hacia fuera. En el destino, todos señalan hacia el nodo.
El objetivo es 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 o la cantidad que entra al destino.
El problema de flujo máximo se puede formular como un problema de programación lineal, se puede resolver con el método símplex y usar cualquier software. Sin embargo, se dispone de un algoritmo de trayectorias aumentadas mucho más eficientes. El algoritmo se basa en dos conceptos intuitivos, el de red residual y el de trayectoria aumentada.
Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de aumento. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. Se regresa la paso 1.
Existen al menos 7 modelos para el tratamiento de los problemas que involucran redes con el fin de optimizar el uso de algún recurso, generalmente tratándose de la minimización de costos, tiempo o la maximización del flujo a través de una red.
Estos modelos son:
• Network Flow
• Transportation Problem
• Assignment Problem
• Shortest Path Problem
• Maximal Flow Problem
• Minimal Spanning Tree
• Traveling Salesman Problem
Árbol de decisión.
Un árbol de decisión es un modelo de predicción utilizado en diversos ámbitos que van desde la inteligencia artificial hasta la Economía. Dado un conjunto de datos se fabrican diagramas de construcciones lógicas, muy similares a los sistemas de predicción basados en reglas, que sirven para representar y categorizar una serie de condiciones que ocurren de forma sucesiva, para la resolución de un problema.
Los árboles de decisión son muy utilizados a la hora de analizar la toma de decisiones de individuos, son muy diversas las materias donde son utilizados, desde la economía hasta la informática se sirven de su uso. Estos árboles son muy útiles para visualizar las diversas opciones que se tienen y como llegar a ellas, además se les pueden aplicar métodos de inducción, como por ejemplo la inducción hacia atrás, gracias a los cuales mediante sencillos razonamientos se ve cómo se llegaría a la solución final.
Construcción de un árbol de decisión.
Vamos a explicar cómo se construye un árbol de decisión, para ello vamos a hacer hincapié en varios aspectos.
Elementos de un Árbol de decisión.
Los árboles de decisión están formados por nodos, vectores de números, flechas y etiquetas.
• Cada nodo se puede definir como el momento en el que se ha de tomar una decisión de entre varias posibles, lo que va haciendo que a medida que aumenta el número de nodos aumente el número de posibles finales a los que puede llegar el individuo. Esto hace que un árbol con muchos nodos sea complicado de dibujar a mano y de analizar debido a la existencia de numerosos caminos que se pueden seguir.
• Los vectores de números serían la solución final a la que se llega en función de las diversas posibilidades que se tienen, dan las utilidades en esa solución.
• Las flechas son las uniones entre un nodo y otro y representan cada acción distinta.
• Las etiquetas se encuentran en cada nodo y cada flecha y dan nombre a cada acción.
En los árboles de decisión se tiene que cumplir una serie de reglas.
• Al comienzo del juego se da un nodo inicial que no es apuntado por ninguna flecha, es el único del juego con esta característica.
• El resto de nodos del juego son apuntados por una única flecha.
• De esto se deduce que hay un único camino para llegar del nodo inicial a cada uno de los nodos del juego. No hay varias formas de llegar a la misma solución final, las decisiones son excluyentes.
En los árboles de decisiones las decisiones que se eligen son lineales, a medida que vas seleccionando entre varias opciones se te van cerrando otras, lo que implica normalmente que no hay marcha atrás. En general se podría decir que las normas siguen una forma condicional:
Opción 1->opción 2->opción 3->Resultado Final X
Estas reglas suelen ir implícitas en el conjunto de datos a raíz del cual se construye el árbol de decisión.
En este árbol de decisión podemos observar como hay cuatro posibles soluciones finales. En él se cumplen las normas antes descritas (nodo inicial, una única flecha por nodo y un único camino para llegar a cada nodo final) y tiene todos los elementos antes descritos (nodos, vectores de números, flechas y etiquetas).
La imagen representa un árbol de decisión conformado por dos jugadores, en el se pueden observar las opciones que El juego cuenta con dos jugadoras.
La primera decisión la ha de tomar la jugadora 1, quien debe decidir entre O1 y O2, en este punto será la jugadora 2 quien decida. Si la Jugadora 1 ha elegido O1, tendrá que decidir entre A1 y R1, A1 le producirá una utilidad de 2, y R1 de 0, a su vez A1 le reportará una utilidad de 8 a la jugadora 1 y R1 de 0. En cambio, si la jugadora 1 elige O2, la jugadora 2 deberá elegir entre A2 y R2, la primera opción le reportará una utilidad de 5 a ella y a la otra jugadora, R2 reportará una utilidad de 0 a las dos. Con los adecuados métodos de inducción existentes se podría resolver este árbol de decisión sin mucha complicación.
FUENTE: Libro "Introduccion a la investigacion de operacion" - Frederick S. Hillier,1992
