|
|
 
|
Análisis Cuantitativo con WINQSB
Víctor Manuel Quesada Ibarguen y Juan Carlos Vergara Schmalbach
Esta página puede carecer de formato, fórmulas, notas, gráficos o tablas. Puede bajarse el libro completo en formato PDF comprimido ZIP (156 páginas, 1342 Kb)
pulsando aquí
11. MODELO DE REDES
La opción Nuevo Problema (New Problem) generará la siguiente ventana:
Existen 7 modelos fundamentales 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:
* Flujo en redes o modelo de trasbordo (Network Flow)
* Problema de transporte (Transportation Problem)
* Problema de asignación (Assignment Problem)
* Problema de la ruta más corta (Shortest Path Problem)
* Problema de flujo máximo (Maximal Flow Problem)
* Árbol de mínima expansión (Minimal Spanning Tree)
* Problema del agente viajero (Traveling Salesman Problem)
11.1 FLUJO EN REDES O MODELO DE TRASBORDO
Ingresemos la información de un modelo de red que enlaza 2 fábricas con 4 almacenes y 3 grupos demandantes (9 nodos en total):
La tabla inicial para este modelo se muestra a continuación:
Para modificar los nombres de los nodos pulsamos sobre Node Name en el menú Editar (Edit). Modifiquemos dichos nombre como se muestra a continuación:
La tabla muestra dos fuentes (fábricas S1 y S2) que cuentan con capacidades de producción de 600 y 800 unidades para un período dado. Hay 4 almacenes intermedios, T1 a T4, de los cuales T2 y T3 poseen 350 y 200 unidades respectivamente. Las demandas son T1, 200 unidades; T4, 100 unidades; D1, 500 unidades; D2, 350 unidades y D3 900 unidades. Los costos de transportar una unidad de producto desde cada fuente y punto de trasbordo hasta cada sitio de demanda se encuentran en el cuerpo de la tabla.
Para ver el modelo en modo gráfico procedemos a marcar la opción
Una versión arreglada de nuestro modelo de redes se muestra a continuación:
Como paso previo a la solución debe escogerse el método mediante el cual se determina la solución básica inicial (recuérdese que los métodos asociados con el transporte sólo se diferencian en la forma como se obtiene la solución básica inicial).
En este caso se ha escogido el método de la esquina noroeste.
La manera de resolver el problema es idéntica a la del simplex, pudiéndose resolver directamente o por pasos. La tabla de resultados finales muestra cómo se da el flujo de productos desde a las fuentes iniciales (S) a los puntos de transbordo (T) y de estas a los destinos finales, con un costo total de 7900 u.m.
A continuación se muestran dos resúmenes de los que permite este módulo, para realizar análisis:
La primera tabla nos muestra, entre otros, el estado de las variables (básicas o no básicas); esto es, si la solución indica que un tramo (i,j) debe realizarse o no; también enseña los costos reducidos, que tienen igual interpretación que en programación lineal. Las dos últimas columnas señalan los máximos y mínimos costos permitidos en un tramo de transporte; esto equivale al análisis de coeficientes de costos de la programación lineal.
De la segunda tabla cabe destacar los precios sombra y los máximos y mínimos permitidos para las restricciones que se interpretan igual que en programación lineal.
11.2 MODELO DE TRANSPORTE
Como el anterior, se trata de encontrar el programa que minimiza los costos de envío de bienes desde unos orígenes hasta unos destinos. La diferencia radica en que aquí se despachan los bienes directamente sin pasar por puntos de trasbordo.
En la tabla siguiente se muestran las demandas, las ofertas y los costos de transporte entre los distintos orígenes y destinos:
La siguiente tabla recoge la solución:
11.3 EL PROBLEMA DE ASIGNACIÓN
Con este modelo se busca resolver de la manera más eficiente, la asignación de una serie de tareas a sendas máquinas u operarios. Veamos un ejemplo:
Se trata de una empresa de consultoría en mercadeo, que ha recibido solicitud de tres clientes para adelantar estudios de mercado. Los números en las celdas son las horas que cada consultor invertiría en llevar a cabo cada proyecto. La compañía desea minimizar el tiempo total dedicado a los proyectos. ¿Cómo asignar los clientes a los consultores?
La solución nos indica que al consultor Pedro se le asigna el cliente 2, al consultor Carlos se le asigna el cliente 3 y a Roberto el cliente 1, con un costo total de $26.
11.4 EL PROBLEMA DE LA RUTA MÁS CORTA
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. El problema se resuelve por el "algoritmo de etiquetado".
La tabla siguiente muestra cómo se ingresan los datos para la red de ejemplo.
El nodo 1 representa la central y el nodo 6 la ciudad a donde debe llevarse el cableado procedente de la central, pasando por algunos de los otros nodos que conectan la central con la ciudad. Los números sobre los arcos representan distancias en millas. Se trata de llevar a cabo la interconexión con el menor consumo de cable.
La solución final del problema sería:
11.5 EL PROBLEMA DE FLUJO MÁXIMO
Muchos problemas pueden ser modelados mediante una red en la cual se considera que los arcos tienen la capacidad de limitar la cantidad de un producto que se puede enviar a través del arco. En estas situaciones, frecuentemente se desea transportar la máxima cantidad de flujo desde un punto de partida llamado fuente hacia un punto final denominado pozo. La tabla siguiente muestra un ejemplo de este modelo:
Gráficamente tenemos:
La solución del problema es:
Obsérvese que este modelo tiene aplicación en la planificación de transporte vehicular, transporte de líquidos mediante tuberías y otros problemas de similar estructura.
11.6 EL ÁRBOL DE EXPANSIÓN MÍNIMA
Es un problema clásico de optimización combinatoria, formulado en 1926 por Boruvka quien lo planteó para resolver el problema de hallar la forma más económica de distribuir energía eléctrica en el sur de Moravia. La formulación de este problema ha sido útil para la realización de muchas investigaciones en varios campos como el transporte, electrónica, telecomunicaciones e investigación de operaciones.
El modelo contempla un conjunto de arcos que conectan todos los nodos de la red sin crear un solo ciclo o vuelta. El problema consiste en determinar el árbol que minimiza la distancia de conexión total; se resuelve por el Algoritmo de Etiquetado. En cuanto a la introducción de datos y el proceso de solución es similar a los modelos anteriores de este módulo.
La solución para la plantilla anterior es:
El modelo de la red del ejemplo es:
11.7 EL PROBLEMA DEL AGENTE VIAJERO
El problema del agente viajero, como los demás de redes, involucra un conjunto de nodos y arcos que conectan todos los nodos. El objetivo es encontrar la forma de realizar una gira completa que conecte todos los nodos visitando sólo una vez cada nodo y minimizar o maximizar la distancia de la gira total. Este modelo tiene múltiples aplicaciones en ingeniería.
La figura representa ciudades, en los nodos, y los valores en los arcos son las distancias que las separan. En la tabla se muestra la representación matricial del problema.
La solución del problema es:
La solución gráfica al problema quedaría:
Volver al índice de Análisis Cuantitativo con WINQSB
Volver a "Libros Gratis de Economía"
Volver a la "Enciclopedia y Biblioteca de Economía EMVI"
