Modelo De Redes

Facultad de Ingeniería y Arquitectura Escuela de Ingeniería Industrial Asignatura: Investigación Operativa I Titulo:

Modelo de Redes

Profesor: José Villanueva Sección : 34G Integrantes: Araoz Porras Enrique Chau Guerrero José Gonzales Gaspar Juan Jiménez Valle Dennis

La Molina, 2008

Introducción La familia de redes de los problemas de optimización incluye los siguientes prototipos de modelos: Problemas de asignación, camino crítico, flujo máximo, camino más corto, transporte y costo mínimo de flujos. Los problemas son establecidos fácilmente mediante el uso de arcos de redes y de los nodos. ¿Que 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. ¿Que 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. Una calle de una sola dirección podría ser representada por un arco, mientras que una calle de dos direcciones podría representada por un arco sin dirección o por dos arcos que apuntan a direcciones opuestas. Una red con n nodos podría tener tantos arcos como n! /[(n-2)! 2!] = n(n-1)/2. Si están dirigidos, este número pudiese ser doble. Este enorme número de arcos posibles es una de las razones del porque existen soluciones de algoritmos especiales para problemas de redes particulares.

Tipos de Modelo de Redes Problemas de Transporte Los modelos de transporten juegan un papel importante en la gerencia logística y en la cadena de insumos para reducir costos y mejorar servicios. Por lo tanto, el objetivo es encontrar la manera más efectiva en termino de costos para transportar bienes. Un distribuidor que tiene m depósitos con un abastecimiento de productos ai ith en ellos, debe enviar dichos productos a n centros minoristas geográficamente dispersos, cada uno con una demanda de clientes dada ej, la cual debe ser cubierta. El objetivo es determinar el mínimo costo posible de transporte dados los costos por unidad de transportar entre el ith depósito y el jth centro minorista, el cual es Cij. Problemas de Asignación Normalmente, se tienen un grupo n de “concursantes” aplicando para n “empleos”, y el costo no-negativo Cij de asignar el iésimo concursante al jésimo empleo es conocido. El objetivo es asignar un empleo a cada concursante de tal forma de alcanzar el costo total mínimo posible. Defina las variables binarias Xij con un valor de 0 o 1. Cuando Xij = 1, significa que deberíamos asignar al concursante i el empleo j. De lo contrario, (Xij = 0), no deberíamos asignar al concursante i el empleo j. El problema de asignación es un caso especial del problema de transporte, el cual ocurre cuando cada oferta es 1 y cada demanda es 1. En este caso, la integración implica que cada oferente asignará un destino y cada destino tendrá un oferente. Los costos proporcionan las bases para la asignación correspondiente a un oferente y un destino. Problemas del Camino Más Corto El problema es determinar la mejor manera de cruzar una red para encontrar la forma mas económica posible desde un origen a un destino dado. Suponga que en una red dada existen m nodos y n arcos (bordes) y un costo Cij asociado con cada arco (i a j) en la red. Formalmente, el problema del camino mas corto (CC) es encontrar el camino mas corto (menor costo) desde el nodo de comienzo 1 hasta el nodo final m. El costo del camino es la suma de los costo de cada arco recorrido. Defina las variables binarias Xij, donde Xij =1 si el arco (i a j)es sobre el CC y Xij = 0 de lo contrario. Existen dos nodos especiales llamados origen y destino. El objetivo es encontrar el camino mas corto entre el origen y el destino. Camino Crítico en la Planificación de Proyectos de Redes La gerencia exitosa de un proyecto ambicioso, ya sea de construcción, de transporte o financiero, descansan en una coordinación y planificación minuciosa de varias tareas. El Método de Camino (o trayectoria) Crítico (MCC) intenta analizar la planificación de proyectos. Esto posibilita un mejor control y evaluación del proyecto. Por ejemplo, queremos saber ¿Cuanto tiempo durará

el proyecto?, ¿Cuándo se estará listo para comenzar una tarea en particular?, si la tarea no es completada a tiempo, ¿El resto del proyecto se retrasará?, ¿Qué tareas deben ser aceleradas (efectivo) de forma tal de terminar el proyecto antes? Problema de Flujo de Costo Mínimo 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. Análisis de Sensibilidad para los Modelos de Redes La familia de un clásico problema de optimización de redes incluye los siguientes prototipos de modelos: asignación, camino crítico, flujo máximo, camino más corto, y transporte. A pesar de que es bien conocido que este tipo de problemas se pueden modelar como programación lineal, normalmente nunca se hace. Debido a la ineficiencia y complejidad relativa del método simplex (primal, dual y otras variaciones) para modelos de redes, este problema es tratado por uno de mas de 400 algoritmos especiales. Esto conlleva a muchas dificultades. Las soluciones de los algoritmos no están unificadas y cada algoritmo usa una estrategia diferente para explorar la estructura especial de un problema específico. Adicionalmente, pequeñas variaciones en el problema tales como la adición de una restricción aparte, o índices múltiples, destruye la estructura especial y obliga a re comenzar el algoritmo. Además, estos algoritmos obtienen soluciones eficientes al costo de la astucia gerencial, como la solución final de estos algoritmos que no tienen la información suficiente para realizar un análisis de sensibilidad. El Problema de Viaje del Vendedor Un vendedor debe visitar las ciudades 1, 2,..n, y su viaje comienza y debe finalizar en Ciudad Hogar. Dejemos que Cij sea el costo de viajar de la ciudad i a la ciudad j, el cual es dado. El problema es determinar una orden óptima para viajar las ciudades de tal forma que el costo sea mínimo.

En el presente trabajo se explicara el Modelo de Redes aplicado específicamente a problemas de trasporte y la maximización de flujos mediante el mismo. La maximización de flujos es un problema típico de la Investigación de Operaciones, el cual tiene muchas aplicaciones, por ejemplo el flujo vial en una ciudad, una red de aguas negras, una red informática, etc. Si nosotros sobrecargamos una calle, una tubería o un canal que obviamente tiene un limite de capacidad, nos enfrentaremos a un problema, posiblemente un flujo mas lento o una tubería con demasiada presión, ahí es donde el Modelo de Redes es un método o secuencia el cual nos ayuda a tomar una decisión acertada que podría ser mejorar o dar mayor aprovechamiento a los flujos a vías donde que tengan mas capacidad, creando nuevas vías o eliminando algunas antiguas. También nos ayuda a maximizar este flujo de manera eficiente de forma tal que se aprovechen al máximo los recursos. Conceptos •

Red: Es un grafo dirigido formado por una fuente, un sumidero, aristas y nodos.

•

Arista: Segmento de recta dirigido de un punto a otro.

•

Nodo: Es el punto de intersección de dos o más aristas.

•

Capacidad: En una red, es la capacidad máxima de una arista cualquiera.

•

Sumidero (z): Es el punto de llegada del flujo total de una red.

•

Fuente (a): Punto de partida del flujo total de la red

Problema de Flujo Básico 1. En una ciudad se va a construir una obra civil que inutilizara las vías primarias durante una temporada. Los ingenieros proponen una red alterna formada por calles más pequeñas para distribuir el transito. Red Alterna en miles de vehículos por hora

Actualmente hay un flujo de 10 mil autos por hora en las horas pico. ¿La red propuesta tendrá la capacidad para canalizar este flujo? Solución en winqsb

La red alternativa tendrá la capacidad de canalizar 11 mil vehículos por hora.

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. 2. Tres refinerías envían gasolina a dos terminales de distribución a través de la siguiente red de oleoductos. La gasolina fluye en la dirección marcada por los arcos. La capacidad de cada segmento del oleoducto en miles de barriles diarios se indica en el arco. Determinar el número máximo de barriles que pueden distribuirse diariamente y cómo se llevaría a cabo la distribución. Restricciones: Las capacidades de las refinerías son de 200000, 250000, 300000 barriles por día respectivamente; la demanda de los terminales son de 400000 y 450000 barriles por día. La demanda que no se puede satisfacer se obtiene de otras fuentes.

Se pueden distribuir 71,5 millones de barriles al día.

Conclusiones Los modelos de redes son aplicables a una extensa variedad de problemas de decisión, los cuales pueden ser modelados como problemas de optimización de redes que pueden ser eficiente y efectivamente resueltos. Algunos de estos problemas de decisión son realmente problemas físicos, tales como el transporte o flujo de bienes materiales. Sin embargo, muchos problemas de redes son más que una representación abstracta de procesos o actividades, tales como el camino crítico en las actividades entre las redes de un proyecto gerencial. El modelo de redes posee una gran aplicabilidad en muchos problemas de la vida cotidiana, en nuestra sociedad moderna es casi imprescindible para lograr una mayor eficiencia en casi cualquier tipo de flujo. En general puede observarse la importancia de los modelos matemáticos para encontrar la solución de infinidad de problemas.

Bibliografia: 1- Investigacion de Operaciones Autor: Taha Hamdy A. Editorial: Prentice Hall Codigo de Biblioteca: 658.4034/T15/2004 2- Investigacion de Operaciones Autor: Raffo Lecca Eduardo Editorial: Raffo Lecca Editores Codigo de Biblioteca: 658.4034/T16