1

Historia de las Redes

Lo ultimo

en Redes de

Optimización

Revista E-Book de Redes de Optimizacion

2

INDICERuta mas corta….

……………..4

Flujo máximo……………………9

Flujo a costo mínimo…………12

Redes de actividad………….….16

Conociendo a los creadores...22

Si de métodos hablamos.........25

Clasificando los problemas……28

Referencias………………...29

3

Los problemas de redes surgen en una gran variedad de situaciones. Las redes de transporte, eléctricas y de comunicaciones predominan en la vida diaria. La representación de redes se utiliza ampliamente en áreas tan diversas como producción, distribución, planeación de proyectos, localización de instalaciones, administración de recursos y planeación financiera, por nombrar sólo unos ejemplos.

Como ya se mencionó antes, la aplicación de la representación gráfica es muy variada y en este trabajo, intentaremos mostrar cuatro de las muchas aplicaciones de las redes de optimización.

Introducción

En muchas ocasiones es mucho más sencillo visualizar la solución de un problema a través de una gráfica. Una representación de este estilo proporciona un panorama general muy poderoso y  ayuda conceptualmente a  visualizar las relaciones entre los componentes de los sistemas, es por esto que sus aplicaciones son aun más variadas.Una gráfica es un conjunto de nodos y arcos. Ejemplo:

4

Introducción

El problema del camino más corto (o ruta más barata) consiste en encontrar una ruta o camino óptimo entre un nodo fuente y un nodo destino, los cuales están enlazados a través de una red con arcos que poseen un cierto atributo, el cual puede ser costo, distancia, tiempo, etc. La Programación Entera permite abordar de forma eficiente este tipo de problemas, en especial cuando la cantidad de nodos y rutas posibles es un número muy grande. Utilizar en estos casos un enfoque intuitivo de resolución es tedioso y de no ser exhaustivo no garantiza la identificación de la mejor alternativa o ruta.

5

Un corredor desea tomar el camino más corto entre el inicio de la carrera que se representa con el nodo 1 y el final de la misma, que está representado con el nodo 8. Puede pasar por cualesquiera puntos para hidratarse, en la siguiente tabla se muestra la distancia en km entre cada punto de hidratación.

Con los datos de la tabla podemos generar una red tomando en cuenta las conexiones entre cada uno de los puntos de hidratación, así como la distancia entre cada uno de ellos. Por ejemplo la tabla indica que el nodo 1 o punto de salida se conecta con 2 puntos de hidratación (2 y 3) pero para ir a 2 hay una distancia de 4km y para ir a 3 hay una distancia de 3 km. Siguiendo este ejemplo se plantea la red correspondiente

Planteamiento

Modelado

6

M.P.L

Función Objetivo: Minimizar la

distancia total en [km] dada por la

siguiente expresión:

Variables de Decisión

7

Restricciones:

La primera restricción (1) garantiza que sólo un nodo (entre el 2 y el 3) pueda ser el que se visita a continuación de comenzar en el nodo 1. La restricción (2) determina que si se visitó el nodo 2 después del nodo 1, entonces necesariamente el nodo 5 será visitado después del nodo 2. La restricción (3) permite verificar que si el nodo 3 fue visitado luego del nodo 1, entonces a continuación se visita el nodo 4 o el nodo 6 (sólo uno de ellos). La restricción (4) establece que si el nodo 5 fue visitado luego del nodo 2, entonces el nodo 7 debe ser visitado luego del nodo 5. La restricción(5) garantiza que si el nodo 4 fue visitado luego del nodo 3, entonces a continuación se visita uno de los siguientes nodo: 7, 8 o 6. La restricción (6)indica que si el nodo 6 fue visitado inmediatamente luego de estar en el nodo 3 o 4, a continuación se visita el nodo 8. La restricción (7) determina que si el nodo 7 fue visitado inmediatamente luego de estar en el nodo 4 o 5, a continuación se visita el nodo 8. Finalmente la restricción (8) asegura que ya sea el nodo 7, 4 o 6 sea el último en visitar previo a terminar la ruta en el nodo 8.

Xij>=0;Xij E Z

8

Utilizando un software podemos dar solución a las ecuaciones que forman parte de nuestras restricciones para encontrar los valores de nuestras variable incógnitas.

Las variables que valen uno serán las variables óptimas a tomar en cuenta para tener la ruta más corta, para obtener nuestra distancia tendremos que sumar cada ruta que si se haya recorrido en la ruta más corta. Nuestra Z=29 km así que la ruta más corta a recorrer es la siguiente y esta tiene una distancia de 29 km.

El corredor deberá pasar por los puntos de hidratación 3,6 y llegar a la meta.

Solución:

Hay problemas en donde lo importante es la cantidad de flujo que pasa a través de la red, como por ejemplo: en las líneas de gasoductos, redes eléctricas o de transmisión de datos. En dichos problemas, podría ser interesante determinar el flujo máximo que pasa a través de dicha red. Naturalmente, en este tipo de problemas, es necesario que existan restricciones para la capacidad de los arcos. Para esto nos sirve la aplicación de Flujo Máximo.

Pemex quiere enviar la cantidad máxima posible de petróleo (en miles de galones) por hora, vía tubería del nodo S al nodo t representado en la siguiente gráfica.

Planteamiento

9

Para resolver este problema aplicamos el algoritmo de Ford y Fulkerson al la propuesta dada por el mismo problema.

Modelado

10

¿SABIAS QUE?

El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. Es aplicable a los Flujos máximos. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino. Su nombre viene dado por sus creadores, L. R. Ford, Jr. y D. R. Fulkerson.

Solución:

La red anterior representa nuestra solución el primer dígito de cada arco representa las unidades de flujo a enviar por tanto el flujo máximo total será de 3 la suma de los flujos mandados de los arcos (2,4) y (3,4).Por lo consiguiente debe de enviar 3 mil galones por hora distribuyéndolos como se menciona. 11

12

Dada una red R[X, A, lij, Uij, Cij] el problema de flujo a costo mínimo tiene una posición medular entre los problemas de optimización de redes; primero, porque abarca una clase muy amplia de aplicaciones y segundo, porque su solución es en extremo eficiente.

Igual que el problema del flujo máximo, toma en cuenta un flujo en una red con capacidades limitadas en sus arcos. Igual que el problema de la ruta más corta, considera un costo (o distancia) para el flujo a través de un arco.

INTRODUCCIÓN

13

Nissan produce autos en San Francisco y Dallas. La planta de San Francisco puede producir 6500 autos y en la planta de Dallas puede producir 6000 autos. Producir un auto cuesta $2000 en San Francisco y $1800 en Dallas. Los autos se deben enviar a tres ciudades.

La ciudad 1 debe recibir 5000 autos, la ciudad 2 4000 y la 3, 3000. El costo de enviar auto de cada planta a cada unidad se da en la siguiente tabla. A lo sumo se debe enviar 5000 autos de una planta a una ciudad.

PLANTEAMIENTO

14

Modelado.La Red sería la siguiente tomando en cuenta los datos.

M.P.L.Xij= # de autos que se envían de i a j.Max z=

V=12

15

SoluciónUtilizando un Software solucionamos el modelo de programación lo que nos arroja los siguientes resultados.

Y nuestra z es: 27 900 lo que implica que este será el costo mínimo que se requiere para cumplir con las expectativas de mi flujo de autos.

16

Redes de actividadSabias que…..las

redes de actividad te sirven para hacer un proyecto mucho mas

organizado, como planear una fiesta, un

viaje, una receta y mas…

Se le llama ruta critica a la serie de actividades, a partir de la iniciación y hasta la terminación del proyecto que no tienen posibilidad de variación en su tiempo de ejecución, ya que si una de ellas retrasara el proyecto total sufrirá el mismo efecto.

La red de actividad es una parte de la fase administrativa de planeación que se encarga de la programación, ejecución y control de un proyecto que deba realizarse con aprovechamiento óptimo de tiempo y costos destinados al mismo.

17

A continuación te mostraremos un ejemplo de redes de actividad, para que conozcas una aplicación de las redes de actividad. Una compañía esta planeando fabricar un producto que consiste en tres partes (A, B, C). La compañía anticipa que toma 5 semanas diseñar las tres partes y determinar la forma en que se deben ensamblar estas partes para conformar el producto.

Entonces la compañía estima que tomara 4 semanas hacer la parte A, 5 semanas hacer la parte B y 3 semanas la parte C. la compañía debe probar la parte A después de su terminación (esto toma 2 semanas).así, el proceso de la línea de ensamblado procederá como sigue: ensamblar las partes A y B (dos semana) y luego añadir la parte C (una semana). Luego el producto final debe experimentar una semana de prueba.

PLANTAMIENTO

18

Lo primero que tenemos que hacer en un problema como este es establecer cuales son las actividades, y para un mejor entendimiento ponerlos en una tabla como la siguiente: Actividad Duración Actividad

precedente

A (fabricación de la parte A)

4 semanas -

B (fabricación de la parte B)

5 semanas -

C (fabricación de la parte C)

3 semanas -

D (revisión de la parte A)

2 semanas A

E (ensamble de la parte A y B)

2 semanas A,B,D

F (ensamble de la parte C)

1 semana E,C

G (revisión del producto final)

1 semana F

En esta tabla vemos las actividades a realizar , las duraciones de las mismas y las actividades que son precedentes.

19

A continuación les mostramos la red de actividad.

20

La siguiente es una representación muy grafica de la solución:

21

Una ruta critica es una cadena de actividades criticas, las cuales conectan el nodo inicial y el nodo termina, la duración de esta cadena define la duración del proyecto.En nuestro ejemplo,:Ruta critica: A,D,E,F,G.Actividades criticas: A,D,E,F,G.Actividades no criticas: C.BTiempos de holgura:Para C: 6 semanasPara B: 1 semanaLa duración del proyecto (dada por las actividades criticas es: 10 semanas.

La imagen anterior, representa todo el proyecto, cuando hay líneas verticales muy alejadas del tiempo final de la actividad representa un tiempo de holgura.Una actividad critica es una actividad en el proyecto que no tiene tiempo de holgura, es decir, si se tiene un retraso en esa actividad todo el proyecto se retrasa.El tiempo de holgura es cuando se tiene mucho mas tiempo del necesario para realizar esta actividad.

22

CONOCIENDO A LOS CREADORES….

Es claro para todos que cuando hablamos de métodos de solución alguien debió idear un algoritmo para resolver cierto tipo de problema, y de ellos hablaremos a continuación, sólo haciendo una pequeña referencia a sus éxitos y sus aportaciones.

23

Edsger W. Dijkstra

Otro concepto debido a Dijkstra, en el campo de la computación distribuida, es el de la auto-estabilización, una vía alternativa para garantizar la confiabilidad del sistema. Creó el primer sistema operativo con estructura jerárquica, de niveles o capas. Fue denominado THE (Technische Hogeschool, Eindhoven) que se utilizó con fines didácticos. Muchos de los últimos trabajos de Dijkstra tratan sobre las maneras de hacer fluida la argumentación matemática.Dijkstra murió el 6 de agosto de 2002 después de una larga lucha contra el cáncer.

Entre sus contribuciones a las ciencias de la computación está la solución del problema del camino más corto, también conocido como el algoritmo de Dijkstra, la notación polaca inversa y el relacionado algoritmo shunting yard, THE multiprogramming system, el algoritmo del banquero y la construcción del semáforo para coordinar múltiples procesadores y programas. Otro concepto debido a Dijkstra, en el campo de la computación distribuida, es el de la auto-estabilización, una vía alternativa para garantizar la confiabilidad del sistema.

Dijkstra estudió física teórica en la Universidad de Leiden. Trabajó como investigador para Burroughs Corporation. En la Universidad de Texas en Austin, Estados Unidos, ocupó el Schlumberger Centennial Chair in Computer Sciences. Se retiró en 2000.

24

Delbert Ray Fulkerson

El Premio Fulkerson es un premio otorgado por la Sociedad de Programación Matemática y la Sociedad Estadounidense de Matemática, para los autores de artículos científicos destacados en el área de la matemática discreta. Cada tres años, son premiados hasta tres artículos en el Simposium Internacional de la MPS.

Delbert Ray Fulkerson (*14 de agosto de 1924 – 10 de enero de 1976) fue un matemático estadounidense que desarrolló como co-autor, y junto con Lester Randolph Ford, Jr., el Algoritmo de Ford-Fulkerson, uno de los algoritmos más utilizados para computar el flujo máximo en una red de flujo.Fulkerson recibió su Ph.D. en la Universidad de Wisconsin-Madison en 1951. En 1956, su importante artículo científico fue publicado. Desde 1979, la Sociedad de Programación Matemática (MPS) y la American Mathematical Society (AMS) otorgan cada tres años el Premio Fulkerson, para aquellos matemáticos que hayan creado artículos importantes en el área de la matemática discreta.

25

Si de métodos hablamos….A continuación vamos a presentar un resumen de los métodos utilizados y de aquellos que pudieron utilizarse para resolver los modelos planteados.

Método Tipo de problema

Características Ventajas y desventajas

PRIM Ruta mas corta

-Obtiene el árbol de peso mínimo.-Tiene n-1 iteraciones.-Trabaja con nodos.-Trabaja en redes sin dirección.

Ventajas: fácil de usar.Desventaja: sólo resuelve problemas pequeños

Kruskal Ruta mas corta

-Obtiene el árbol de peso mínimo.-Trabaja con arcos.-Tiene por lo menos n-1 iteraciones.-Trabaja en redes sin dirección

Ventajas: Resuelve problemas grandes, es preciso para programar.Desventaja: Puede llevar muchas iteraciones

Dijkstra Ruta mas corta entre dos nodos

-Encuentra la arborescencia de rutas mas cortas.-Trabaja en redes dirigidas

Ventajas: fácil de implementar.Desventajas: etiqueta a destiempo y no acepta costos negativos

26

Método Tipo de problema

Características Ventajas y desventajas

Dijktra generalizado

Ruta mas corta entre dos nodos

-Equivale al M simplex.-Redes dirigidas con cualquier costo-Arborescencia de rutas mas cortas

Ventaja: acepta costos negativos.Desventaja: muchas iteraciones.

Floyd Ruta mas corta entre todo par de nodos.

-Trabaja con redes dirigidas con cualquier costo.-Se tienen n iteraciones

Ventaja: Encuentra cualquier ruta mas corta.Desventaja: Muchas combinaciones en los costos.

Algoritmo de Ford y Fulkerson

Flujo máximo

-Hace pasar flujo-Aumenta y disminuye flujo en los arcos

-Ventaja: Fácil de aplicar-Desventaja: muchas iteraciones

Método de eliminación de circuitos negativos

Flujo a costo mínimo

-Utiliza red marginal-Determina la distribución de la red

Ventaja: elimina circuitos negativosDesventaja: se hace complicado trabajar con la red marginal

27

Método Tipo de problema

Características Ventajas y desventajas

M Simplex Flujo a costo mínimo

-.Arborescencia con n-1 v básicas.-Tiene n multiplicadores

Ventaja: muy parecido al M simplex para transporte.Desventaja: muchas iteraciones.

CPM Redes de actividad

-Calcula la ruta critica -Hace revisión hacia adelante y hacia atrás

Ventaja: fácil de aplicarDesventaja: pueden cometerse errores

28

Tipo de proble

ma

Característica

Planteamiento

Métodos

Ruta mas corta

-Maneja arboles de peso mínimo y arborescencia de rutas mas cortas

-Ruta segura-Reemplazo-Planeación de producción-Tipo mochila

-PRIM, Kruskal-Dijkstra, Dijkstra generalizado-Floyd

Flujo máximo

-Tiene el concepto de corte.-Flujo mínimo-Tiene capacidades en los nodos

-Casamentero-Típicos

-Ford y Fulkerson

Flujo a costo mínimo

-Maneja concepto de red marginal-Es el modelo mas general, tiene capacidades y costos, nodos origen y destino

-Planeación de producción -Asignación de empleados

-M. de eliminación de circuitos negativos-M. basado en rutas mas cortas.-M. Simplex

Redes de actividad

-PERT-Supuestos-Manejo de probabilidades.

-Algún proyecto

-CPM

Clasificando problemas

29

REFERENCIAS BIBLIOGRAFICAS

(Sin fecha) [Imagen] [Sin titulo] http://catalog.devir.es/juegos/tablero/guerra_del_anillo/docs/images/rutas_sm.jpg (Sin fecha) [Imagen] [Sin titulo] http://u.jimdo.com/www11/o/s075f076504dfea8d/img/i6d47c3a24291bf80/1312354764/std/bryan-antonio-salazar-lopez.jpg(Sin fecha) [Imagen] [Sin titulo] https://encrypted-tbn2.gstatic.com/images?q=tbn:ANd9GcQ4xLwa9V4OKgzp3qxMZdbbsUJ5Rk-rEmlzhBaB3uAzmUMkRs3e(Sin fecha) [Imagen] [Sin titulo] http://www.gas.pemex.com/NR/rdonlyres/75435B6F-44DD-40CA-B2A0-8A3EE6AC078F/0/cardenas_ok.jpg

Recuperado de apuntes de clase Guadalupe del Carmen Rodríguez Moreno(Sin fecha) [Imagen][Sin titulo]http://www.sct.gob.mx/transporte-y-medicina-preventiva/transporte-ferroviario-y-multimodal/(Sin fecha) [Imagen][Logo MAC] http://gauss.acatlan.unam.mx/course/view.php?id=2(Sin fecha) [Documento] [Sin titulo] http://www.monografias.com/trabajos-pdf4/optimizacion-redes/optimizacion-redes.shtml(Sin fecha) [Imagen][Grafica] http://mauortiz117.blogspot.mx/(Sin fecha) [Documento] [Sin titulo] http://equip4.files.wordpress.com/2010/12/unid-5-optimizacion-de-redes.docx

30

(Sin fecha) [Imagen] [Sin titulo] http://www.aprendeypiensa.com/2012_08_01_archive.html(Sin fecha) [Imagen] [Sin titulo] http://www.listadosybases.com/bases-de-datos/category/6(Sin fecha) [Imagen] [Sin titulo] http://nomienredes.com/blog/como-lanzar-un-producto-nuevo-al-mercado/(Sin fecha) [Documento] [Sin titulo] http://es.wikipedia.org/wiki/Algoritmo_de_Ford-Fulkerson(Sin fecha) [Imagen] [Sin titulo] https://sites.google.com/site/io4in4/(Sin fecha)[imagen][Edsger Dijkstra] http://es.wikipedia.org/wiki/Edsger_Dijkstra(Sin fecha)[Documento][Sin titulo] http://es.wikipedia.org/wiki/Edsger_Dijkstra

(Sin fecha) [Imagen] [Sin titulo] http://pixabay.com/static/uploads/photo/2013/03/30/00/09/notepad-97841_640.png(Sin fecha) [Imagen] [Sin titulo] http://clusterindustrial.com.mx/wp-content/uploads/2014/07/image.axd_236.jpeg(Sin fecha) [Imagen] [Sin titulo] http://s0.uvnimg.com/autos/nissan/fotos/photo/2012-02-07/fotos-nissan-370z-2013-2_590x395.jpg(Sin fecha)[Imagen][Delbert Ray Fulkerson]http://en.wikipedia.org/wiki/D._R._Fulkerson(Sin fecha) [Documento][Sin titulo]http://es.wikipedia.org/wiki/Delbert_Ray_Fulkerson

Martínez Ventura Analía

González Martínez

Diego Armando