REDES EN INVESTIGACIÓN DE OPERACIONES
La modelación de redes permite la resolución de múltiples
problemas de programación matemática mediante la implementación de algoritmos
especiales creados para tal fin, conocidos como Algoritmos de optimización
de redes.
Un modelo de red puede adoptar diversas formas, como el
modelo de la ruta más corta y el modelo del flujo máximo y mínimo, el
problema de árbol de alcance mínimo, método de camino crítico, entre otras aplicaciones
de la planeación financiera y de producción.
Cuando se trata de encontrar el
camino más corto entre un origen y un destino, la técnica, algoritmo o el
modelo adecuado es el de la ruta más corta; aunque existen otros modelos de
redes como el árbol de expansión mínima, flujo máximo y flujo de costo mínimo
cada uno abarca un problema en particular.
Terminología de redes
Una red se compone de un conjunto de nodos unidos por arcos
(o ramas). La notación para describir una red es (N, A), donde N es el conjunto
de nodos, y A es el conjunto de arcos.
N = {1, 2, 3, 4, 5}
A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2),
(4, 5)}
A continuación se presenta un diagrama de red y sus
principales componentes.
¿Qué es un Nodo?
Es usualmente llamado vértice, o punto. Es usualmente
representado por un círculo. En las redes de transporte, estos deberían ser las
localidades o las ciudades en un mapa.
¿Qué es un Arco?
Es usualmente llamado borde o flecha. Este podría ser
directo o indirecto. La cabeza es el destino, y la cola el origen. La cabeza y
la cola son nodos que pueden estar tanto al origen como al final. En las redes
de transporte, los arcos podrían ser los caminos, los canales de navegación en
un río, o los patrones de vuelo de un avión. Los arcos proporcionan la
conectividad entre los nodos.
MODELOS DE REDES
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 la 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 forme un árbol de expansión. Por lo
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 óptima. 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 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á dada 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.
Algoritmo de la trayectoria de aumento para el problema de
flujo máximo:
- Se identifica una trayectoria de aumento encontrando alguna trayectoria dirigida del origen al destino en la red residual, tal que cada arco sobre esta trayectoria tiene capacidad residual estrictamente positiva. (Si no existe una, los flujos netos asignados constituyen un patrón del flujo óptimo).
- Se identifica la capacidad residual c* de esta trayectoria de aumento encontrando el mínimo de las capacidades residuales de los arcos sobre esta trayectoria. Se aumenta en c* el flujo de esta trayectoria.
- 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 al paso 1.
Modelo de la ruta más corta
Considere una red conexa y no dirigida con dos nodos
especiales llamados origen y destino. A cada ligadura (arco no dirigido) se
asocia una distancia no negativa. El objetivo es encontrar la ruta más corta
(la trayectoria con la mínima distancia total) del origen al destino.
Se dispone de un algoritmo bastante sencillo para este
problema. La esencia del procedimiento es que analiza toda la red a
partir del origen; identifica de manera sucesiva la ruta más corta a cada uno
de los nodos en orden ascendente de sus distancias (más cortas), desde el
origen; el problema queda resuelto en el momento de llegar al nodo destino.
Algoritmo de la ruta más corta:
- Objetivo de la (N) iteración: encontrar el (N) nodo más cercano al origen. (Este paso se repetirá para n=1, 2, hasta que el (N) nodo más cercano sea el nodo destino.)
- Datos para la (N) iteración: n-1 nodos más cercanos al origen (encontrados en las iteraciones previas), incluida su ruta más corta y la distancia desde el origen. (Estos nodos y el origen se llaman nodos resueltos, el resto son nodos no resueltos.)
- Candidatos para el (N) nodo más cercano: Cada nodo resuelto que tiene conexión directa por una ligadura con uno o más nodos no resueltos proporciona un candidato, y éste es el nodo no resuelto que tiene la ligadura más corta. (Los empates proporcionan candidatos adicionales.)
- Cálculo del (N) nodo más cercano: para cada nodo resuelto y sus candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta desde el origen a este nodo resuelto. El candidato con la distancia total más pequeña es el (N) nodo más cercano (los empates proporcionan nodos resueltos adicionales), y su ruta más corta es la que genera esta distancia.
ÁRBOL DE DECISIÓN.
¿Qué es el árbol de decisiones?
Es una estructura ramificada, la cual permite estimar cuáles
son las opciones más viables para la solución del problema, a través de
sus consecuencias, costos y demás factores, ayuda a construir una imagen
balanceada de riesgos, recompensas asociadas y cada posible curso de
acción.
un árbol de decisión cuenta con las siguientes
características:
- Plantea el problema desde distintas perspectivas de acción.
- Permite analizar de manera completa todas las posibles soluciones.
- Provee de un esquema para cuantificar el costo del resultado y su probabilidad de uso.
- Ayuda a realizar las mejores decisiones con base a la información existente y a las mejores suposiciones.
Su estructura permite
analizar las alternativas, los eventos, las probabilidades y los resultados.
¿Cómo aplicar un árbol de decisión en la empresa?
Los árboles de decisiones sirven para resolver cualquier
problemática donde se necesite comparación de alternativas, para ello,
necesitas tomar en cuenta los siguientes puntos.
- Identifica el problema.
- Limita los criterios de decisión (personajes, operatividad, costos, entre otros).
- Identifica la importancia de los criterios. En esta etapa es necesario que analices cuáles son los criterios con mayor importancia, de esta forma, sabrás a qué darle peso en el análisis.
- Desarrolla las alternativas. Realiza una lluvia de ideas e identifica cualquier alternativa que se basa en el número 2.
- Analiza cada alternativa. Verifica fortalezas y debilidades de acuerdo a la importancia de criterios, trata de que tu análisis sea objetivo.
- Estructúralo. Es momento de trasladarlo al árbol de
decisiones. En este ejemplo se analiza el costo beneficio de proveedores.
7. Selecciona una alternativa. Analiza cuál es la opción
más conveniente de acuerdo al árbol de decisiones, siempre toma en cuenta el
punto 3.
8. Implementa la alternativa. Recuerda, realizar un
análisis es muy distinto a implementar soluciones, cuida que se siga paso a
paso cada detalle, una pequeña falla podría dar resultados no deseados.
9.Evalúa la efectividad de la decisión. Siempre es
bueno saber qué se hizo bien y qué se hizo mal, analiza con tu equipo cada paso
en la evaluación de alternativas, esto ayudará a mejorar tomas de decisiones a
futuro.
Fuente
Teoría de decisiones y sistemas de información”,
William T. Green Wood.
