Para representar el flujo que entra y que sale lo expresamos mediante las siguientes ecuaciones
La ecuación matemática para hallar x que se maximiza es:
Mi ejemplo de flujo máximo seria:
El problema es:
Una compañía de petróleo quiere trasportar galones de petróleo a los puntos de almacenamiento desde su refinería (fuente) hacia el punto 7 que es el pozo, lo que la compañía quiere es saber cuál es el flujo máximo que se puede trasportar.
Para representar y así analizar pondré esta imagen que representa toda la red, esto quiere decir el inicio (refinería) y hacia donde debe de llegar que en este caso sería al almacén 7.
En la siguiente tabla les muestro las trayectorisas posibles y en seguida cada trayectoria con sus pasos.
----------------------------------------------------------------------------------------
La primer trayectoria ,que pasa por los puntos 1-2-5-7 y la capacidad de flujo seria 3, para que se entienda entran 3 galones entonces como hay 6 se le restan 3 y sobran 3, en el segundo almacén como hay 3 se le restan 3 y quedan 0, en el 5 almacén hay 5 galones se le restan los 3 que entran y quedan 2. Y para interpretar esto está la imagen así se entenderá mejor los números que están en rojo representan los galones que quedan de la primer trayectoria.
----------------------------------------------------------------------------------------
Para la segunda trayectoria que pasa por los puntos 1-4-7, la capacidad de flujo que debe entrar seria de 2.Entonses para el almacén 1 se tienen 6 galones si entrar2 pues quedarían 4 galones, en el amasen 4 hay 2 galones y entrar 2 entonces quedan o galones .Los números que están de verde representan los galones que quedan de esta segunda trayectoria.
----------------------------------------------------------------------------------------
Para la tercera trayectoria que pasa por los puntos 1-4-3-6-7, la capacidad de flujo que debe entrar seria de 2 galones. En el almacen 1 hay 4 que fueron los que quedaron de la segunda trayectoria se le estan los 2 galones que entrar y quedarian 2 galones, en el almacen 4 hay 3 galones se le restan los 2 que entrar entonses quedaria 1 galon , para el almacen 3 hay 2 galones se le restan 2 y quedarian 0 galones ,para el almacen 6 hay 5 galones y se le restan 2 quedarian 3 .Los numeros que estan de morado representan los galones que quedan de esta tercer trayectoria.
----------------------------------------------------------------------------------------
Para la cuarta trayectoria que pasa por los puntos 1-4-3-5-7 , la capacidad de flujo que debe entrar es de 1 galón .En el almacén 1 de los galones que quedaban de la trayectoria 2 se le restan 1 galón que es el que entra y quedan 1 galón, en el almacén 4 de 1 galón que quedaba de la trayectoria 4 se le resta 1 y quedan 0 galones , del almacén 3 de los 2 galones que hay se le restan 1 que son los que entran y quedan 1 galón, del almacén 5 como quedaron dos de la trayectoria 1 se le está 1 que es lo que entra en esta trayectoria y queda 1.Los números que están de morado representan los números que quedan de esa trayectoria.
----------------------------------------------------------------------------------------
Para la quinta trayectoria que pasa por los puntos 1-4-6-7 , la capacidad de galones que debe entrar es de 1 galón. En el almacén 1 como quedo 1 galón en la trayectoria 4 y entra 1 galón pues quedan 0 galones, en el almacén 4 como hay 1 galón y entra 1 quedan o galones, en el almacén 6 como en la trayectoria 4 quedaron 3 se le resta 1 que es el de esta trayectoria y quedan 2 galones. Los números que están de amarillo representan los galones que quedan de esta trayectoria.
----------------------------------------------------------------------------------------
Para la sexta trayectoria que pasa por los puntos 1-2-5-7, la capacidad de flujo que debe galones que debe entrar es de 1 galón .En el almacén 1 como quedaron 3 galones de la trayectoria 1 se le resta 1 y quedan 2 galones, en el almacén 2 como hay dos galones y entra 1 y queda 1 galón, en el almacén 5 como hay 1 galón de la trayectoria 5 se le resta el que entra y quedan 0 galones. Los números que están de celeste representan los galones que quedan de esta trayectoria.
----------------------------------------------------------------------------------------
Como se pueden dar cuenta esas son las trayectorias posibles ya que la fuente que es el inicio es el almacén 1 y hacia el almacén 2 si se puede trasportar un galón pero del almacén 2 hacia otro almacén no, y del almacén 1 que se dirige al almacén 4 no se puede ya que por así decirlo no hay espacio.
El flujo máximo seria de 10 ya que si suman los galones de cada trayectoria suman eso y ese el máximo flujo que se puede trasportar.
El problema de desión seria: Cual Cual es el camino que mas le convendria a la empresa de petroleo , es decir el camino mas corto y que trasporte la mayor cantidad de galones .
Pues como resolví el problema y analizando el camino para trasportar los galones sería el de la trayectoria primera que involucra a los caminos 1-2-5-7.Ya que es el camino mas corto y trasporta mayor cantidad de galones.
El algoritmo para el problema de decisión sería:
1. Inicio.
2. Analizar las trayectorias que resolví en el ejemplo de la compañía de petroleo.
3. Escoger la trayectoria que trasporta el máximo de galones.
4. Fin.
La complejidad de este algoritmo se haría en poco tiempo ya que solo son 12 almacenes, pero cuando la cantidad de almacenes es mucho mayor tardaríamos mucho tiempo en analizar cada camino para trasportar el máximo de galones.
Este problema es P ya que si existe método de solución, aunque dependiendo de los almacenes es el tiempo que nos vamos a tardar, pero eso no se quiere decir que no se pueda si no que cuando la cantidad de almacén es muy grande nos tardaríamos mucho tiempo , que podrían ser días, meses , años etc.
El problema no corresponde a NP-duro ya que no es NP no puede ser NP-duro.
Para el problema se debe considerar una red elegida, se tiene un inicio (fuente) y un fin (pozo), los nodos se utilizan para trasbordar y así llegar hacia donde queremos.
El algoritmo para el problema de optimización es:
1. Inicio.
2. Conocer los caminos posibles
3. Checar cuál camino tiene la capacidad que deseamos y debe ser mayor que 0.
4. Ya que checamos y elegimos el camino de mayor capacidad, elegir la rama de menor capacidad del camino que elegiste.
5. Reducuir la cantidad de capacidad de las ramas involucradas, pero aumentar la cantidad en el sentido contrario.
6. Seguir buscando caminos y se repite el mismo proceso de paso 4,5y6
7. Fin.
Este algoritmo funciona para saber el flujo máximo, pero depende los nodos que haiga es el tiempo que te tardarías, mas si se llega al resultado para saber el flujo máximo.
Puse este video ya que me fue muy útil para entender el concepto de flujo máximo
la pagina del video
http://www.youtube.com/watch?v=bu1BnW9H9V0
----------------------------------------------------------------------------------------
En las páginas en las que leí y estaba buscando información para así interpretar el concepto fue:
http://fc.uni.edu.pe/publicaciones/rev06-02/pdf/R%F3sulo%2ara
http://www.google.com.mx/#hl=es&source=hp&q=forumlar+un+problema+de+desicion+correspondiente&meta=&aq=f&oq=forumlar+un+problema+de+desicion+correspondiente%C3%A7&fp=d98d46c23d717632
http://www.virtual.unal.edu.co/cursos/sedes/manizales/4060015/Lecciones/Capitulo%20IV/problemas.htm
http://lear.inforg.uniovi.es/ioperativa/TutorialGrafos/flujomax/flujomax.htm
http://upcommons.upc.edu/revistes/bitstream/2099/4069/4/article.pdf
http://slirsredirect.search.aol.com/slirs_http/sredir?sredir=1692&query=el+problema+de+flujo+entero+m%C3%A1ximo+en+su+%C3%A7&invocationType=tb50hpcnnbie7-es-mx
">http://mit.ocw.universia.net/15.053/s02/pdf/s02-lec11.pdf
Hola Doris.
ResponderEliminarLeeré todas las entradas que has puesto, para entenderle bien a esta materia. Por lo que he visto, está muy bien toda esta información.
Gracias por tener un blog de este tipo.
Que te vaya bien. Nos vemos en el examen de matemáticas.