Todos los nodos han
quedado conectados, por lo que esta es la solución (optima) que se buscaba. La
longitud total de las ramas es 14 millas.
Aunque con este
procedimiento a primera vista puede parecer que la elección del nodo inicial
afectaría la solución final ( y la longitud total de las ligaduras), en
realidad no es así. Se sugiere que se verifique este hecho para el ejemplo,
aplicando de nuevo el algoritmo, pero con un nodo inicial distinto de 0.
Se considera que
dentro de este capitulo el problema del árbol de expansión mínima es el que cae
dentro de la amplia categoría de diseño de redes. En esta categoría, el
objetivo es diseñar la red más apropiada para el problema dado (con frecuencia
se trata de sistemas de transporte) y no de analizar una red ya diseñada. La
referencia 8 proporciona una investigación en esta importante área.
5.4 Problema de flujo máximo
En una red con flujo de capacidades en los arcos, el
problema es determinar el flujo máximo posible proveniente de los orígenes de
forma tal de ahogar las capacidades de flujos de los arcos. Considere una red
con m nodos y n arcos con un flujo simple de bienes. Denote el arco de flujo (i
a j) como Xij. Asociamos cada arco a una capacidad de flujo, kij. En esta red,
deseamos encontrar el flujo total máximo en la red, F, del nodo 1 al nodo m.
En
la formulación de la programación lineal, el objetivo es maximizar F. El monto
que parte del origen por varias rutas. Para cada nodo intermedio, lo que entra
debe ser igual a lo sale. En algunas rutas los flujos pueden tomar ambas
direcciones. La capacidad que puede ser enviada a una dirección en particular
también es mostrada en cada ruta. Hamdy A. Taha(1991)1
1Hamdy A. Taha. Investigación De Operaciones.
Ediciones Alfaomega. Cuarta Edición. 1991
5.5 Problema de flujo de costo mínimo
El
problema de flujo de costo mínimo tiene una posición medular entre los
problemas de optimización de redes; primero, abarca una clase amplia de
aplicaciones y segundo, su solución es muy eficiente.
Todos los
problemas de red anteriores son casos especiales del problema de flujo de
costos mínimo. Al igual que el problema de flujo máximo, este considera flujos
en las redes con capacidades. Al igual que el problema del camino mas corto,
este considera un costo por flujo hacia un arco. Al igual que el problema de
transporte, este permite múltiples orígenes y destinos. Por lo tanto, todos
estos problemas pueden ser vistos como casos especiales del problema de flujo
de costos mínimo.
El problema es
minimizar el costo total sujeto a la disponibilidad y la demanda de algunos
nodos, y de la conexión superior de flujo a través de cada arco
La solución óptima es: X12 = 12, X13 = 8, X23 = 8, X24
= 4, X34 = 11, X35 = 5, X45 = 10, todos los demás Xij = 0. El costo óptimo es
$150
5.6 PROGRAMACIÓN LINEAL EN TEORÍA DE REDES
La programación lineal es actualmente la técnica matemática
utilizada más actualmente gracias a que el algoritmo simplex es muy eficiente y
al desarrollo de la computación. Lo que se busca con la aplicación de la
programación lineal es resolver problemas comunes y a la vez muy variados de la
empresa en donde en general se tienen necesidades por satisfacer con cierto
número de recursos limitados o escasos y con el objetivo de lograrlo en forma
óptima.
Ejemplo
Una empresa ha dejado de fabricar ciertos productos, liberando de
esta forma las cargas de producción que tenían sus equipos en los departamentos
de maquinado. Ahora se tienen horas máquina que se pueden utilizar en los
productos denominados 1,2,3 de la siguiente manera:
Máquina Horas por pieza de producto Horas
Maq. Disponibles
1 2 3 por semana
Fresadora 9 3 5 500
Torno 5 4 - 350
Rectificadora 3 - 2 150
Utilidad
$/ pieza 50 20 25
Recomendación del Mínimo Mínimo Mínimo
Depto. Vtas a Prod. 30 15 20
Formular un modelo de
Programación Lineal para este problema
·
Definición de variables a utilizar en el método de programación
lineal
Sea: Xj = número de piezas de producto
j(j=1,2,3) a fabricar para maximizar la utilidad.
·
Función económica y objetivo:
MAX Z= 50X1 + 20X2 + 25X3 [ (Dls/Unidad)
(Unidad/Sem)] = [Dls/Sem.]
Sujeta a restricciones de
horas máquina disponibles por semana
Fresadora: 9X1 + 3X2 + 5X3 * 500 horas
máquina fresadora
Torno: 5X1 + 4X2 * 350 horas máquina torno
Rectificadora: 3X1 + 2X3 * 150 horas maquina
rectificadora
Condiciones de signos pare las variables:
X1 * 30 piezas
X2 * 15 piezas
X3 * 20 piezas
CONCLUSIÓN
Los modelos de
optimización de redes constituyen una herramienta muy sencilla para la
encontrar la solución óptima a los problemas de flujo de redes, porque
proporcionan algoritmos fáciles de comprender y aplicar que comparados con el
método simplex disminuyen el número de iteraciones que resuelven el problema.
Si se aplicara el método simplex en un problema de distribución o de redes,
tendríamos muchas variables y restricciones en el modelo y se tendría que
utilizar herramientas computacionales para encontrar la solución optima de una
forma rápida, ahora con los modelos de redes solo habría que aplicar las
iteraciones al grafo que origina la representación de la red del problema y
luego aplicar el algoritmo que corresponde, que puede ser el algoritmo de la ruta
más corta, algoritmo para encontrar el árbol de expansión mínima, algoritmo de
la trayectoria de aumento o el algoritmo de flujo máximo.
Aunque los problemas
de flujo de costo mínimo y el de la ruta más corta pueden formularse como
modelos de programación lineal para luego aplicar el método simplex, no es
conveniente su utilización. Por otro lado solucionar el problema utilizando
redes mejora la eficiencia de los cálculos.
BIBLIOGRAFÍA
Frederick S. Hiller y Gerald J. Liberman. Investigación De Operaciones . McGraw-Hill. Séptima
Edición. 2002.
Hamdy
A. Taha. Investigación De Operaciones. Ediciones Alfaomega. Cuarta Edición.
1991
No hay comentarios:
Publicar un comentario