Existen muchas situaciones en Investigación de Operaciones, que pueden modelarse y resolverse como redes. Un 70% de los problemas de programación matemática en el mundo real se pueden representar como modelos relacionados con redes.
La solución de las situaciones para optimización de redes se logra con una variedad de algoritmos de optimización como:
• Árbol de expansión mínima
• Algoritmo de la ruta mas corta
• Algoritmo del flujo máximo
• Algoritmo de red capacitada con costo mínimo
• Algoritmo de la ruta critica.
Las situaciones en las que se pueden aplicar estos algoritmos también se pueden formular y resolver en forma de programas lineales explícitos. Sin embargo, los algoritmos propuestos, basados en redes, son más frecuentes y más eficientes que el método simplex.
Una red consiste en una serie de nodos enlazados con arcos. Cada red se asocia con un algún tipo de flujo.
En general, el flujo en una red esta limitado por la capacidad de sus arcos, que pueden ser finitos o infinitos.
Una ruta es una sucesión de arcos distintos que unen dos nodos pasando por otros nodos, independientemente de la dirección de flujo en cada arco. Una ruta forma un ciclo si se conecta un nodo con si mismo.
Un árbol es una red conectada que puede consistir en un subconjunto de todos los nodos en ella, donde no se permiten ciclos.
Algoritmo de la ruta más corta.
Este caso de problema determina la ruta más corta, entre una fuente y un destino, en una red de transporte. De entre todas las rutas posibles se selecciona como su nombre lo indica, la ruta más corta.
El algoritmo de la ruta más corta se presenta en dos algoritmos para resolver tanto redes cíclicas, como aciclicas:
1.El algoritmo de Dijkastra
El algoritmo de Dijkastra tiene por objeto determinar la ruta mas corta entre el nodo fuente y todos los demás nodos de la red, permitiendo determinar la ruta más corta entre dos nodos cualquiera en la red.
2.El algoritmo de Floyd.
El algoritmo de Floyd es más general que el de Dijkastra, porque determina la ruta más corta entre dos nodos cualquiera de la red. Este se hace por medio de una red con n nodos como matriz cuadrada con n renglones y n columnas por lo que este concepto es directo.
Árbol de mínima expansión.
El algoritmo de expansión mínima enlaza los nodos de una red, en forma directa o indirecta, con la mínima longitud de ramas entrelazadas. Es decir que se busca el diseño mas económico de caminos que indique que se minimice la distancia recorrida
Algoritmo de red capacitada con costo mínimo.
Este tipo de problema se basa en las hipótesis siguientes:
• A cada arco se le asocia un costo de flujo unitario
• Los arcos pueden tener límites inferiores positivos de capacidad
• Todo nodo en la red puede funcionar como fuente o como sumidero.
El modelo en si determina los flujos en cada uno de los distintos arcos, que minimizan el costo total y a la vez satisfacen las restricciones de flujo y las cantidades de oferta y demanda en los nodos.
Esta formulación es la base del desarrollo de un algoritmo simplex capacitado especial, para resolver el modelo de flujo en la red. La selección termina con una presentación de una plantilla de hoja de cálculo de la red capacitada con costo mínimo.
Uso de programación lineal en teoría de redes
Para las redes capacitadas con costo mínimo la programación lineal es base del desarrollo de algoritmos como el simplex que se utiliza en cada notación, se acomodan por renglones y columnas los datos y por nodos y por medio de formulas se puede concluir a transformaciones de las actividades en las redes.
En la ruta mas corta la programación lineal es general, en el sentido de que se puede usar para determinar la ruta mas corta entre dos nodos cualquiera de la red.
Si suponemos que la red de la ruta mas corta tiene n nodo, y que se desea determinar la ruta mas corta entre dos nodos cualesquiera s y t de la red se realizan las siguientes formulaciones
1- Esta formulación supone que entrara a la red una unidad externa de flujo en el nodo s, y sale en el nodo t, siendo s y t dos nodos entre los que se busca determinar la ruta mas corta y se definen asi:
Xij= cantidad de flujo en el arco (i,j) para toda i y j factibles
Cij= Longitud de arco (i,j) para toda i y j factibles
2- Esta formulación es en realidad el problema dual del programa lineal en la formulación 1. Como la cantidad de restricciones es la formulación 1 es igual a la cantidad de nodos, el problema dual tendrá tantas variables como cantidad de nodos haya en la red. Tambien, las variables duales no deben estar restringidas, porque todas las restricciones de la formulación 1 son ecuaciones.
Como s y t son los nodos inicial y terminal de la red, el problema dual se define como se muestra:
Maximizar Z= Yt-Ys
Sujeto a Yj-Yi≤Cij para toda i y j factibles.
Programas de computación
• SENDA AF
• WinQSB
• EXCEL
• Microsoft Project
• Gantt projet
• Open Workbench
• Ms Proyect
Ejemplo
Se va a instalar una red de comunicaciones entre 12 ciudades, los costos de los posibles enlaces directos entre pares permisibles es el que se muestra en la figura. Cada unidad de costo representa$10000dlls . Determine las redes de comunicación mas económicas.
No hay comentarios:
Publicar un comentario