lunes, 30 de junio de 2014



FLUJO MÁXIMO DE REDES

Definición y aplicaciones según  Ing. José Luis Albornoz Salazar. OPTIMIZACIÓN DE REDES. Páginas 23-24.
"  En términos generales, un problema de flujo máximo de red se puede describir como:

1)   Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado fuente, y termina en otro nodo llamado destino.
2)   Los nodos restantes son nodos de trasbordo.
3)   Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco (flecha). En la fuente, todos los arcos (flechas) señalan hacia afuera. En el destino, todos señalan hacia el nodo.
4)   El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta cantidad se mide en cualquiera de las dos maneras equivalentes, esto es, la cantidad que sale de la fuente o la cantidad que entra al destino.

Algunas aplicaciones
1)      Maximizar el flujo a través de la red de distribución de la compañía de sus fábricas a sus clientes.
2)      Maximizar el flujo a través de la red de suministros de la  compañía de los proveedores a las fábricas.
3)      Maximizar el flujo de petróleo por un sistema de tuberías.
4)      Maximizar el flujo de agua a través de un sistema de acueductos.
5)      Maximizar el flujo de vehículos por una red de transporte.

Para algunas de estas aplicaciones, el flujo a través de la red se puede originar en más de un nodo y también puede terminar en más de un nodo, aunque el problema de flujo máximo puede tener sólo un  origen y un destino.

Por ejemplo, una red de distribución de una compañía tiene varias fábricas y múltiples clientes. Se usa una reformulación ingeniosa para ajustar esta situación al problema de flujo  máximo. Se trata de aumentar la red original para que incluya una fuente ficticia, un destino ficticio y algunos arcos o flechas nuevos. La fuente ficticia se maneja como el nodo que da origen a todo el flujo que  en realidad se origina en algunos otros nodos. Para cada uno de estos otros nodos, se inserta un nuevo arco que va de la fuente ficticia a este  nodo, donde la capacidad del arco es igual al flujo máximo que se puede originar en este nodo. De manera similar, el destino ficticio se trata como el nodo que absorbe todo el flujo que, en realidad, termina en algún otro nodo. Por lo tanto, se coloca un nuevo arco desde cada uno de los otros nodos al destino ficticio con capacidad igual al flujo máximo que en realidad termina en este nodo. Debido a estos cambios, todos los nodos de la red original ahora son nodos de trasbordo para que la red aumentada tenga un solo origen (la fuente ficticia) y un solo destino (el destino ficticio) y se ajuste al problema del flujo máximo.   "

 

EJEMPLO:
El ejemplo que se presenta es similar al del Ing. José Luis Albornoz Salazar. OPTIMIZACIÓN DE REDES. Páginas 24-32.

La figura siguiente muestra el sistema de bombeo de aguas blancas desde el Origen “O” hasta el Destino “D”; los otros nodos representan las ciudades intermedias que poseen estaciones de bombeo; las flechas representan las tuberías que conducen el agua desde una ciudad hasta otra (en un solo sentido); y los números representan el flujo o caudal máximo (en litros/seg) que se puede trasladar por cada tubería.

Se desea determinar la cantidad máxima de agua (en litros/seg) que puede recibir el nodo “D” utilizando las tuberías y bombas existentes.





SOLUCIÓN:
A continuación se orienta sobre la utilización de la hoja de cálculo EXCEL para la solución de este tipo de problemas de Flujo Máximo con la herramienta Solver, que posee el software.

Para poder usar Solver, primero es necesario que se vacíen los datos en una hoja de cálculo de la siguiente forma:





En la columna Condición (I) coloque ceros al lado de las ciudades intermedias (condición de las estaciones de trasbordo). No se coloca ningún valor al lado del Origen “O” ni del Destino “D” porque esos valores son justamente los buscados (el máximo positivo que sale del origen y el máximo negativo que entra al destino final).

Cada cero en las estaciones de trasbordo se refiere al hecho de que en dichas ciudades no se puede almacenar agua, es decir, se tiene que enviar la misma cantidad que se reciba:

Flujo neto = Flujo de salida - Flujo de entrada
es decir, Flujo neto = cero


Todas las celdas están llenas con la información tal y cómo se muestra en la imagen anterior, excepto por la columna de Flujo Neto (L) y la celda correspondiente a Flujo Máximo (L16), las cuales contienen ecuaciones.
  
Las ecuaciones para los flujos netos de cada “nodo” o ciudad se incluirán en la columna L, en donde cada celda de esta columna (L) calcula el flujo neto real en ese nodo sumando el flujo que sale y restando el que entra.

Conociendo la ecuación que debemos incluir en las celdas “L4” hasta “L10” tomamos en cuenta las siguientes consideraciones, tomadas parcialmente del libro citado al principio de este artículo:

·      Como las celdas de la columna E reflejarán los resultados (Flujo que debe enviarse por esa ruta), serán éstas las que se tomen en cuenta para la elaboración de las ecuaciones.
·      Como el flujo neto generado en un nodo es el flujo que sale menos el flujo que entra, las ecuaciones se reducen a la suma y resta de los valores que debe reflejar SOLVER en las celdas de la columna E
·      Las celdas de la columna E que se colocarán en las ecuaciones serán aquellas que se encuentren en la misma “Fila” donde esté ubicado el “nodo” estudiado. Si la letra que identifica al nodo se encuentra en la columna C (DESDE) se sumará; cuando se encuentre en la columna D (HASTA) se restará.

En la celda L5 se incluirá la ecuación relacionada con el Origen (“O”).
Notamos que la letra “O” se encuentra ubicada en las filas 5, 6 y 7, por lo tanto debo utilizar en la ecuación las celdas E5, E6 y E7.

En las filas 5, 6 y 7, podemos ver que existen tres rutas que incluyen a “O”, a saber:
O→A (Fila 5)
O→B (Fila 6)
O→C (Fila 7)

Como en los tres casos el flujo sale de “O” (La flecha empieza después de “O” y termina en ”A”,”B” ó “C”), en la ecuación se sumarán los tres valores:

Celda L5 = E5 + E6+ E7

En el resto de las celdas correspondientes a Flujo Neto quedarían con las siguientes ecuaciones:
Celda L6 = -E5+E8-E9
Celda L7 = -E6+E9+E10+E11-E12
Celda L8 = -E7+E12+E13
Celda L9 = -E8-E10+E14
Celda L10 = E11-E13-E14


En estas celdas se reflejarán inicialmente ceros hasta que apliquemos Solver.

La celda donde queremos que se refleje el flujo máximo que debe llegar hasta el destino “D”, o lo que es lo mismo el flujo máximo que debe salir del origen “O”. Como la celda L5 debe reflejar el flujo que sale de “O”, ese mismo valor será el flujo máximo que representará la función objetivo. En este caso, la celda destinada como la celda objetivo es E16 y en ella debemos incluir:

Celda E16 = L5

Una vez vaciada toda la información que tenemos en la hoja de cálculo, procedemos a ejecutar Solver, cuyo botón se encuentra en la pestaña Datos del programa. Al hacer clic se mostrará un cuadro de diálogo “Parámetros de Solver”.




Antes de que Solver pueda resolver el problema, necesita conocer con exactitud, donde se localizan los componentes del modelo en la hoja de cálculo. Es posible escribir las direcciones de las celdas o hacer clic en ellas.

Donde se solicita “Establecer objetivo” indique la celda E16. Coloque: $E$16

Donde se solicita “Cambiando las celdas de variables” indique las celdas donde se propuso anteriormente que se mostrarán los resultados. En este caso son las celdas E5 hasta E14, coloque: $E$5:$E$14



Indique las restricciones o condiciones del problema, para lo cual haga clic en “Agregar”. En este momento aparecerá en la pantalla el cuadro de diálogo “Agregar Restricción”.

En este problema existen dos restricciones: 


La primera:
$E$5:$E$14 ≤ $G$G:$E$14

La segunda:
$J$6:$J$9 = $L$6:$L$9






Haga clic en “Aceptar”. Ahora el cuadro de diálogo resume el modelo completo.



Hacer clic en “Resolver” y después de unos segundos Solver indicará los resultados en las celdas E5 hasta E14, en la celda objetivo E16 aparecerá el FLUJO MAXIMO que sale del origen y llega al destino.

En el cuadro final “Resultados de Solver”, haga clic en “Aceptar”.




Y aparecerá la hoja de resultados:



La siguiente figura muestra el flujo que entra y sale de cada nodo para garantizar el FLUJO MÁXIMO de 8 litros/seg desde “O” hasta “D”.




Artículo Posteado por Nameless.
Ariel Milá de la Roca
Juan Ramírez
Universidad Simón Bolívar - Venezuela

 

Fuente:
Ing. José Luis Albornoz Salazar. OPTIMIZACION DE REDES. Páginas 23-32.
http://www.monografias.com/trabajos-pdf4/optimizacion-redes/optimizacion-redes.pdf





Simulacion de Procesos

El uso de métodos en  estudios científicos   para el análisis de procesos no es nuevo,  aunque se ha notado en los últimos años que  el estudio  en el campo de la  investigación de operaciones  ya sea para la toma de decisiones o cualquier otro aspecto, se está utilizando nuevas herramientas para la mejora de  técnicas adecuadas  en  base a la matemática, cuestión que es  bastante frecuente si queremos tener como  fin  el hecho de  estudiar problemas con una visión más gráfica que  algebraica (en el caso de la simulación ) y así poder exponer de una manera más sencilla las mejoras o los posibles problemas en una organización .

A través del tiempo una gran parte del crecimiento de aplicaciones científicas  se debe a la simulación de procesos,  donde  facilitan la visión para el estudio de problemas de gran complejidad y  la  Obtención de resultados   de manera inmediata gracias a dos aspectos que se deben requerir  para la busque da de un resultado óptimo o una visión clara de los procesos tales como la gran versatilidad   aspectos muy  importantes  como , el conocimiento  sólido en re-ingeniería de procesos y  como segundo aspecto  la meticulosa percepción  en los errores de procesos  el sistema  y  formulación algebraicas de estos .

 Ahora bien a continuación se mostrara cual es la principal función y el concepto de la simulación para el buen desarrollo de una mejora continua en el análisis  e investigación de operaciones.

Simulación:

Según el Dtr.  Azarang M. en su libro sobre investigación de operaciones, menciona que  la simulación es “un modelo lógico-matemático de un sistema ” imitando de esta manera operaciones dentro de los procesos de un evento  ficticio ( por estudiar) o un evento real(posiblemente estudiado), haciendo notar características operacionales. cuando se construye el modelo, siendo la representación de elementos en el sistema reflejando de esta manera las actividades realizadas en el ciclo; Puede tomar una orientación gracias a ecuaciones lógicas que tienen relevancia en el sistema.

Tomando las ventajas de  los modelos de simulación, una vez construido  es fácil de analizar,  requiere de bajo presupuesto  ya que el personal no interviene en esta simulación puede utilizar para sistemas complejos y por ultimo en alguno de los casos puede ser la única manera de poder realizar el estudio de procesos en el sistema a estudiar.

Dentro del método de  simulación  usado  para una experiencia  en el campo de estudio,  existe  variaciones tales como los enfoques de estudio o el tipo de área a estudiar, tales como:

Teorico:
Es la visión supuesta para el resultado optimo para un sistema o proceso, utilizando modelos matemáticos, elementos que participan en la realización del proceso e hipótesis de resultados a través de antecedentes históricos y  estudios estadisticos.

Sistemico

 se realiza a traves de una realizacion del modelo de un sistema actual en contraste con un modelo otmimo y posterior a eso una comparacion del como podria realizarce el sistema optimo, utilizando tambien un enfoque a la dinamica de sistemas, analisando como interactuan cada proceso con el otro en el mismo sistema y tomar la desciendo de juntar, separar o unir un proceso con otro.

Ahora gracias a muchas herramientas a nivel de software se puede simular un sistema completo de prestas ion de servicio o generar un producto en base a varios procesos de fabricación(en este caso por estaciones)
por fienes educativos se tomo como ejemplo un software llamado SIMIO, el cual puede simular la trayectoria de un producto por cada estasion asi como tambie la simulacion de la atencion de servicio en un local especifico tomando un ejemplo se puede mostras en la imagen un flujo de pcoresos de tres estaciones, como se ve a continuacion  para contemplar la eficasia de este software.

viernes, 27 de junio de 2014

Árbol Mínimo Expandido

Autores: Andres Henriquez, Deilimar Pajaro y Genesis Ponce

Cuando hablamos de Árbol Mínimo Expandido nos referimos a la unión de nodos dentro de una red, esta red debe estar unida de tal manera que no se creen ciclos y los nodos se unan por distancias mínimas o costos mínimos.

Este método es utilizado para la planificación y diseño de cualquier tipo de red, si quisiéramos utilizarlo en una carrera como Organización Empresarial seguramente lo podríamos aplicar en el diseño de un proceso como ensamblaje de un producto cualquiera, donde tengamos que transportar piezas de un lado a otro; podemos utilizarlo también para establecer prioridades en el diseño de alguna estrategia guiada a cumplir los objetivos de una Organización.

¿Que debemos tomar en cuenta?


1) No deben haber ciclos ¡Nunca!, si llegara a existir aunque sea un pequeño ciclo dentro de nuestra red entonces créeme que no se trata de un árbol mínimo expandido.

2) Debemos unir cada nodo con el que esta más cercano o tiene un mínimo costo.

3) Debe haber una ligadura o arco uniendo cada par de nodos con el fin de que se unan todos los nodos que necesitamos y sean factibles para cumplir nuestro principal objetivo, reducir los costos y distancias o los tiempos.

4) La red siempre tendrá una cantidad de arcos igual a n nodos menos 1, la idea es que no haya un numero exagerado e innecesario de arcos (caminos, ligaduras) entre nuestros nodos, así evitamos también la formación de ciclos que repito, no deben existir dentro de nuestra red!


¿Para que se utiliza?


Principalmente se utiliza para planificar y diseñar redes de cualquier tipo, es una buena forma de establecer planes eficientes dentro de una empresa, en una comunidad, en la planificación de servicios públicos como las tuberías de agua que abastecen a toda una ciudad, el servicio de alumbrado en una comunidad, el servicio de transporte también podría ser planificado con este método, entre otros.

¿Cómo se usa?


Paso 1. Teniendo un conjunto de nodos debemos tomar cualquiera y conectarlo con el más cercano o tiene un bajo costo.

Paso 2. Conectar los siguientes nodos con la misma regla del paso 1.

Problema

Un cyber ubicado en la ciudad de Caracas tiene el proyecto de unir 6 computadoras representadas en la siguiente red, los números en cada arco representan la longitud en metros del cable necesario para conectar las computadoras.


Siguiendo los pasos 1 y 2 deberíamos lograr tener algo como esto:


Logrando así reducir la longitud del cable que debemos utilizar para la conexión de las computadoras que sería igual a 16 metros de cable.

¿Como resolverlo con WinqSB?


1) Se llena el método tabular, este se ira auto-llenando de manera que parecerá una matriz simétrica.


2) Pido la Solución del problema en la barra de tareas.


Análisis
·         Se debe conectar el nodo 1 con el nodo 2 a una distancia de 1 metro.
·         Se debe conectar el nodo 1 con el nodo 3 a una distancia de 5 metros.
·         Se debe conectar el nodo 2 con el nodo 4 a una distancia de 4 metros.
·         Se debe conectar el nodo 2 con el nodo 5 a una distancia de 3 metros.
·         Se debe conectar el nodo 4 con el nodo 6 a una distancia de 3 metros.

Distancia total: 16 metros

3) Interacciones






Paso a paso para resolver el problema en WinqSB

Mark Silva, Arbol de expansión minima WinqSB


Bibliografia


  • Teoría de redes, www.Ingenierosindustriales.JIMDO.com
  • BUSTOS EDUARDO, Modelos de redes: Árbol de expansión mínima.
  • SARMIENTO y ALOMOTO, Redes (Árbol de expansión mínima)







jueves, 26 de junio de 2014

Sistemas Expertos


Se puede considerar la historia de la civilización humana como la historia de la cooperación entre diversos grupos de personas trabajando de manera coordinada para lograr objetivos específicos a corto, mediano y largo plazo. Hoy día, con un mundo cada vez más interconectado, resulta aún más importante el apoyo y armonía entre individuos con capacidades, habilidades, conocimientos y perspectivas diferentes.

En el ámbito empresarial, o de manera más general, en todas aquellas organizaciones que buscan alcanzar altos grados de eficiencia, resulta de especial importancia la toma de decisiones, específicamente en lo relativo a la organización de los recursos. En este sentido, se ha ido implementando paulatinamente un conjunto de herramientas informáticas que permiten aumentar la eficacia de las decisiones dentro de las organizaciones: son los llamados Sistemas Expertos (SE).

Un SE es un programa o aplicación informática que reúne conocimiento de diversas áreas o de un área específica (llamada “dominio”), y lo utiliza para la resolución de problemas de ésa área (matemática, leyes, química, arquitectura, física, medicina, etc.) con altos grados de eficiencia y efectividad, siempre y cuando se le “alimente” con situaciones y consecuencias ya constatadas en el mundo real. Esto significa que toman datos de un problema actual, los comparan con otros problemas presentados anteriormente (almacenados previamente), y emiten una respuesta o solución propuesta que se basa en la efectividad de esa solución para superar el problema. El o los programadores humanos se deben ocupar de desarrollar las reglas lógicas que permitan resolver los problemas y a la vez introducir nueva situaciones, datos y condiciones para futuros problemas, de tal manera que el SE pueda “aprender” a medida que pase el tiempo. A grandes rasgos, los SE imitan el procedimiento de razonamiento de los humanos para la resolución de problemas de manera más eficiente, por lo que son una suerte de especialistas virtuales todo-en-uno.

El principal problema que solventa un SE es la paradoja acerca de los campos de actividad: Existen más problemas que personas capacitadas o disponibles para resolverlos. Para subsanar esta diferencia, se acuden a estas herramientas.
      Ventajas y Desventajas
Los SE tienen una serie de ventajas frente a las redes humanas de expertos y consultores: Su capacidad analítica no se reduce con el paso del tiempo, son fáciles de reproducir o difundir en el resto de la organización, resistentes a condiciones laborales y ambientales perjudiciales para los humanos, tienen gran capacidad de almacenamiento y “memorización”, y su costo de implementación rápidamente es superado por su efectividad a largo plazo. La principal ventaja es que le permite a personas que no poseen conocimientos especializados en un área, obtener respuestas claras y objetivas para la resolución de problemas en ese dominio, por lo que no es necesario consultar a otros expertos si se cuenta con un SE correctamente programado y actualizado; al menos, no si el problema se ha presentado, resuelto y registrado anteriormente, como es el caso de fallas regulares o casos que se presentan frecuentemente. Y en última instancia, también constituyen herramientas de enseñanza gracias a sus módulos de justificación (como se verá más adelante), ya que un individuo que no sea especialista en un dominio, puede eventualmente aumentar sus conocimientos al aprender empíricamente las posibles implicaciones, dinámica y soluciones que puede tener un problema ya estudiado.

Pero a diferencia de una persona, los SE carecen de capacidad de innovación o “razonamiento” de manera independiente; al fin y al cabo sus funciones se limitan a las de cualquier programa, el cual no puede hacer nada diferente a lo que está “programado” para hacer. Por esto mismo, su programación a menudo se limita a procesar  secuencias de datos estructurados y presentados de una manera muy específica, por lo que no puede “interpretar” el lenguaje coloquial que emplea una persona (sólo admite lenguaje de programación), ni las sugerencias “difusas” que empleamos como “mucho de X”, “poco de X”, “agregar/reducir un poco”, “aumentar unas cuantas unidades más”, etc. Más aún, los SE no pueden “percibir” o “intuir” las consecuencias a largo plazo de sus acciones y situación del entorno, y por ello no pueden modificar sus respuestas en función de los cambios que sufren los factores que impactan directa o indirectamente en el proceso de estudio (adaptación o flexibilidad). En conclusión, pueden “repetir” razonamientos hechos por otros humanos o SE, pero no pueden tener “ideas” sobre como resolver un problema completamente nuevo, con restricciones diferentes a las que conoce o factores ocultos que influyan en él de la manera como una persona con suficiente experiencia e intuición sí podría.
      Componentes
Los SE tienen una estructura básica común sin importar su grado o área de especialización, ya que deben contar de una manera u otra con:
Programadores y especialistas humanos en gestión de conocimientos y en las áreas que va a tocar el SE.

1.      Bases de Conocimientos, que contendrán los datos, situaciones y respuestas que emitieron los especialistas humanos frente a problemas similares. Es por esto que a veces de dice que los SE son Sistemas Basados en Conocimientos.
2.      Bases de hechos: Contiene los datos relativos a la situación o caso de estudio, de tal manera que exista un punto de comparación entre los conocimientos que posee el sistema y las condiciones del problema que quiere resolver la organización.
3.      Motor de inferencia, que realiza las labores de “pensamiento” del SE, imitando el razonamiento humano para la toma de decisiones, sólo que a velocidades muy superiores. Compara el contenido de las bases de hechos con las bases de conocimientos para encontrar respuestas a las interrogantes.
4.      Módulos de justificación: Para sustentar su razonamiento, se apoya en el subsistema de explicación, que almacena las respuestas, casos o factores que le llevaron a tomar una decisión, así como también pueden hacer que el SE solicite información específica al usuario para obtener mejores respuestas.
5.      Interfaz, que le permite a un usuario ajeno a la nomenclatura de programación “comunicarse” efectivamente con el programa, introduciendo datos y recibiendo respuestas de manera coherente.

Usos/Funciones de SE
Cuando hablamos del uso que tienen los sistemas expertos, aparece entre sus principales aplicaciones la gestión empresarial, específicamente en la toma de decisiones, tanto en el bajo como en el alto nivel. Esto se debe a que el objetivo de un sistema experto es igualar el comportamiento de los especialistas humanos. Algunos de los beneficios de aplicar este sistema en el proceso de toma de decisiones son:
1.    Resuelven problemas que requieren un conocimiento formal especializado.
2.  Obtienen conclusiones de forma más rápida que los humanos, ya que las mismas se obtienen de la información con la que se cuenta.
3.   Razonan en base al conocimiento (información) y no tienen lugar para la subjetividad (Puede convertirse en una desventaja, debido a que se pudiesen tomar decisiones muy arriesgadas).

Algunas de las áreas de aplicación más importantes se mencionan a continuación, sin embargo este tipo de sistemas es aplicable a prácticamente todas las áreas en las cuales sea necesario tomar decisiones para lograr objetivos.
     Militar. (ej. “Twirl”, utilizado para crear simulaciones de guerras completas y guía de mejores acciones posibles a realizar).
     Informática. (ej. “Programmers apprentice”, sistema que ayuda a la escritura de programas).
     Medicina. (Con sistemas como “MYCIN”, utilizado para diagnosticar infecciones en la sangre y meningitis).
     Industria. (ej. “Delta” utilizado para la reparación de motores Diesel y eléctricos).
     Finanzas y Gestión empresarial. (ej. “Consolidex”, Es un prototipo de sistema experto para la interpretación de las cuentas anuales consolidadas).
 Tipos de Sistemas Expertos

A Continuación se identificarán los tipos de SE y se dirá cómo solucionan problemas que se le planteen

● Basados en Reglas: Aplicando reglas heurísticas apoyadas en lógica difusa para su evaluación y aplicación.

●  Basados en Casos CBR (Case Based Reasoning): Aplicando el razonamiento en este tipo de SE, donde la solución a un problema parecido que se haya planteado anteriormente se pueda adaptar al nuevo problema.

  Basados en Redes: Aplicando redes, basadas en estadística

Ejemplos (software) de SE

El Sistema Experto (SE) que explicaremos a continuación se llama Forecast, utilizado para predecir  el comportamiento de una variable en el tiempo ya teniendo claro los datos históricos. Este sistema identifica una tendencia y de acuerdo a ella elabora mediante métodos estadísticos el pronóstico del comportamiento de la misma (Figura 1)   .

      Es utilizado en las empresas para predecir el comportamiento de los mercados, por ejemplo, si una empresa que fabrica juguetes tiende a aumentar sus ventas en un 20% en el último trimestre de cada año, lo más probable es que el software Forecast arroje como predicción que en el proximo año tambien aumente en un 20% o cerca de ese resultado. De esta forma, Forecast le dice a la empresa que fabrica juguetes que en el último trimestre del año deben aumentar su producción en un 20% para satisfacer esa demanda futura.
Figura 1
Al software se le pueden añadir o cambiar datos directamente desde la gráfica o en la hoja de cálculo para ajustarlo al resultado real que se desea obtener. Usted puede ajustar puntos, rangos o totales, utilizando porcentajes, incrementos o simplemente introduciendo nuevos valores.


            Se pueden crear presentaciones de excelente calidad y de fácil entendimiento para los usuarios mediante 4 formatos estandarizados que se pueden configurar para lograr un mejor efecto. Puede graficar sus resultados en series de tiempo o en base de año sobre año. Los formatos incluyen líneas y columnas 3D (Figura 2).
2).

Figura 2
Forecast posee una gran flexibilidad, que le permite importar y exportar datos de una gran variedad de formatos, incluyendo, uno de los más usados como lo son las hojas de cálculo de Excel. 

Videos extra de interés:



Referencias

Sistemas expertos, Wikipedia
Sistemas expertos, Monografías
Informática Integral Inteligente
Red Científica
Forecast, sistemas y pronostico


Elaborado por:

Lopez, Armando

Rivero, Luis

Sarmiento, Luis

Agente Viajero

Concepto

  Es un método que es utilizado cuando existe un problema donde se debe realizar varios viajes a diferentes  lugares una sola vez  y se debe llegar al mismo lugar de donde se originó dicho viaje. Es por ello que los principales objetivos son minimizar distancias, tiempos y costos, es decir, que al realizar una secuencia entre varios nodos estos pueden ser estaciones, ciudades, puntos de referencia entre otros.

Para realizar un problema de agente viajero, es necesario tomar en cuenta donde están dadas las n ciudades y el costos Cij que se genera al viajar de una ciudad a otra.

Tomando como finalidad al realizar el ejercicio lo siguiente:


  •   Conseguir el recorrido más corto en n ciudades.
  •   Cada ciudad solo puede ser visitada una sola vez antes de llegar de nuevo al punto de partida.
  •   Minimizar tiempo, y costos.

Siguiendo con la definición del Agente Viajero (PAV) o bien traveling salesman problem (TSP) Nombre de referencia a nivel mundial.

Este tipo de problema es estudiado en la Investigación de Operaciones y  en la optimización combinatoria tomado como uno de los problemas principales de gran importancia. Estos de problemas son utilizados como base para resolver una gran cantidad de problemas que ocurren en la vida cotidiana. Por otro lado también es utilizado en otra área tal como la teoría de la complejidad computacional para aprobar algoritmos que se van descubriendo día a  día. 

Sumado a esto otra de las áreas en las que se puede observar el problema del agente viajero es en la teoría de gráficas. En la siguiente grafica se puede observar las tres grandes áreas o enfoques que ha tomado el problema del Agente Viajero para su estudio, véase el siguiente gráfico. http://www.scribd.com/doc/104889745/Agente-Viajero-análisis

Ilustración 1. Imagen diseñada a partir de las definiciones asociadas al problema del Agente Viajero





Si como objetivo se quiere minimizar el tiempo usado para la configuración de  una máquina que es usada para producir n cantidad de artículos, se le llama TSP, y cada nodo corresponde a cada uno de los diferentes artículos y la distancia  al ir a modificar la maquina es el tiempo usado en la modificación de una maquina a la otra.

Cuando el objetivo no es reducir el tiempo o el recorrido en distancia al realizar el viaje, es necesario medir el costo que se obtiene al realizar dicho recorrido. Este en algunos casos suele ser más importante que los otros dos factores ya mencionados.


Ahora bien para tener una referencia que muestre de manera práctica y conceptual la definición del Agente Viajero, se ha utilizado el libro de Investigación de Operaciones Hamdy Taha. Séptima edición. Año 2004. En la sección 5.4 y 9.2 para los algoritmos. Donde se hace referencia de que dicho problema tiene que ver con la determinación del viaje más corto en un caso, con n ciudades a visitar, en el cual cada ciudad se visita exactamente solo una vez. Es por ello que el problema del Agente Viajero es un modelo de asignación con limitaciones adicionales que aseguran la exclusión de sub-viajes en la solución óptima. Entonces se debe tomar en cuenta de forma específica en el caso del problema del Agente Viajero con n ciudades, lo siguiente:


Si dij es la distancia de la ciudad i a la ciudad j, el modelo del agente viajero es el siguiente:





·     Las restricciones (1),(2),(3) definen un modelo regular de asignación.

En general, el problema de asignación producirá soluciones de subcircuito, más que un circuito completo que abarque todas la n ciudades.

A continuación se presenta un modelo con 5 ciudades. Los arcos representan las rutas en dos sentidos. Por otro lado se puede observar que la solución del circuito y dl subcircuito del modelo de asignación asociado. Si las asignaciones forman una solución  del circuito, el circuito es óptimo. En caso contrario se agregan más restricciones al modelo de asignación para eliminar los sub-circuitos. Las siguientes imágenes son tomadas del libro de Investigación de Operaciones de  Hamdy Taha. Séptima edición. Año 2004. En la sección 5.4 y 9.2 para los algoritmos.





Ahora bien los métodos disponibles para resolver el problema del agente viajero tienen su base en las ideas de los algoritmos generales de ramificación y acotamiento o del plano de corte.

Para tener una idea más clara acerca del método de asignación es importante leer del libro Investigación de Operaciones de Hamdy Taha. Séptima edición. Año 2004. En la sección 5.4 y 9.2 para los algoritmos.

Definiciones y ejemplos tomados del libro Investigación de Operaciones. Hamdy A Taha Séptima edición. Año 2004. Pág. 390, 391.


Como parte del aprendizaje del tema Agente Viajero, en el siguiente video se explica de manera sencilla como realizar dicho problema.

Áreas en las que al  aplicar el problema del agente viajero y resulta muy  útil

El problema del Agente Viajero se puede emplear en cualquier situación que requiera seleccionar nodos en cierto orden que reduzca los costos en las áreas de:


  • ·         Reparto de productos: Con la finalidad de mejorar una ruta de entrega para así conseguir la más corta.
  • ·         Transporte: Ya que permite realizar la mejor selección del recorrido de caminos buscando la menor distancia.
  • ·         Robótica: Utilizado con el objetivo de resolver problemas de fabricación de equipos o productos para así minimizar el número de desplazamientos al realizar una serie de perforaciones en un circuito impreso.
  • ·         Horarios de transportes laborales y/o escolares: Permitiendo de este modo estandarizar los horarios en los transportes, ya que  es una de sus aplicaciones principales, tanto  así que actualmente existen empresas que se especializan en ayudar a las escuelas a programar el tiempo y recorrido  para optimizarlos en base a una solución del TSP.
  • ·         Inspecciones a sitios remotos: En esta área es utilizado ya que permite ordenar los lugares que deberá visitar un inspector en el menor tiempo posible.
·         Secuencias: Aquí su uso consiste hacer referencia al orden en el cual n trabajos tienen que ser procesados de tal forma que se minimice el costo total de producción.

http://www.posgradoeinvestigacion.uadec.mx/CienciaCierta/CC30/3.html

Visto de esta manera el problema del Agente Viajero es de gran utilidad. Es aplicado para reducir los costos al realizar un recorrido por varias áreas una sola vez partiendo desde un punto y terminado en el mismo lugar, de manera que se quiere logra reducir los costos al realizar dicha actividad y recortar en términos de tiempo o distancia el viaje.
En el Problema del Agente Viajero, la solución al problema es una permutación de las n ciudades dadas, y este es dividido en dos tipos:
Ø  TSP simétrico (STSP): Al realizar este método la matriz de costos Cij es simétrica, es decir, que, el costo que se genera viajar de la ciudad i a la ciudad j es el igual al   que se tiene al viajar de la ciudad j a la ciudad i.

Ø  TSP asimétrico (ATSP): En este caso, la matriz de costos Cij no es simétrica, es decir, que, el costo que se genera de viajar de la ciudad i a la ciudad j, en general, no es el i que igual que se obtiene al viajar de la ciudad j a la ciudad i
Para ambos casos la formulación matemática es la igual, con la diferencia de que la matriz de costos para el primero es simétrica, y para el segundo no es igual. De manera que se han desarrollado formulaciones matemáticas específicas para el segundo caso. En las aplicaciones, tanto el caso simétrico como el asimétrico son de gran importancia.
El Problema del Agente Viajero en su forma asimétrica tiene (n-1)! rutas disponibles, esto es, (n-1)! posible soluciones. La forma simétrica tiene recorridos, porque al modificar la dirección de la ruta ésta no cambia y sigue siendo la misma.

Ahora bien, la parte simétrica ha sido más explorada en la investigación y desarrollo de algoritmos para resolver el TSP.
Al resolver un problema del agente viajero sebe tomar en cuenta todos los métodos que pueden aplicarse. El Problema del Agente Viajero puede resolverse de diferentes maneras:
Ø  Enumeración de todas las soluciones factibles: Es decir, se debe enlistar todas las posibles soluciones del problema, calcular los costos asociados, identificar por comparación, cuál es la solución con el costo más acorde, más bajo.
Ø  Métodos exactos: Son llamados algoritmos óptimos, con estos se intenta descartar familias de las posibles soluciones, tratando siempre de acelerar la búsqueda y llegar a una solución óptima. Los métodos que más se usan para resolver el TSP son Ramificación y Acotamiento, Ramificación y Corte.
Ø  Heurísticas: Estos son métodos  que obtienen buenas soluciones en tiempos de cómputo muy cortos, sin embargo no se puede garantizar el punto óptimo de la solución.

Existen diferentes tipos de heurísticas (Glover, Gutin, Yeo y Zverovich, 2001):
Ø  Heurísticas constructivas: Son procedimientos que se encargan de obtener una solución a partir de un criterio inicial, consiste en construir una solución factible.
Ø  Heurísticas de búsqueda local: Aquí son aplicados los procedimientos para mejorar soluciones ya encontradas. Es decir, que tratan de optimizar localmente alrededor de una solución, ubicando mínimos locales.
Ø  Heurísticas combinadas: Utilizado como procedimiento que constan de una heurística constructiva y una heurística de búsqueda local.
Heurística para el Problema del Agente Viajero (Cirasella, Lyle, McGeoch y Zhang, 2000):
El vecino más cercano (heurística constructiva)

Este tipo de heurística consiste en la idea de moverse de una ciudad a la siguiente, de tal manera que, de todas las opciones, la ciudad elegida sea la más cercana a donde se haya ubicado el agente viajero. Es considerada como una heurística miope, ya que en una iteración 3 escoge entre ellas la mejor opción que tiene disponible, sin ver que esto puede forzar a tomar malas decisiones posteriormente (Johnson et al., 2002).
Ilustración 2. El vecino más cercano, heurística constructiva.   http://www.posgradoeinvestigacion.uadec.mx/CienciaCierta/CC30/3.html

El Problema del Agente Viajero o TSP es un problema calificado como difícil de resolver, propiamente dicho como NP-Completo. Es decir, es un problema para el cual no podemos garantizar que se encontrará la mejor solución en un tiempo de cómputo razonable, por esto, cuando una instancia de grandes dimensiones se resuelve con algún método exacto, toma un extenso periodo de tiempo de estudio. Con el uso de heurísticas se tienen soluciones de muy buena calidad en tiempos de cómputo mucho más pequeños.


Ejemplo de utilidad en un problema de un viajero

            Un viajero tiene que visitar cada una de las cuatro ciudades y lo quiere hacer de tal manera que visite una sola vez partiendo de la ciudad A y regresando al final del recorrido, viajando el menor tiempo posible, la siguiente tabla muestra los tiempos entre ciudades (horas):


Formulación

Variables Xij: Horas de viaje desde la ciudad i hasta la ciudad j. Siendo i=A,B,C,D{1,2,3,4} y j=A,B,C,D{1,2,3,4}

  





         
Solución

Para poder darle solución a este problema se realizan cambios en el nombre de las variables se acomodan de acuerdo a su posición del 1 al 12.



Para la interpretación de resultados regresamos al nombre original de las variables obteniendo lo siguiente:
X1=X12
X6=X24
X7=X31
X12=X43

Por lo tanto se dice que el recorrido será de siguiente manera:
Pasa de la ciudad A a la B
Pasa de la ciudad B a la D
Pasa de la ciudad D a la 4
Pasa de la ciudad C a la A terminando donde se inició el recorrido.

El tiempo mínimo usado haciendo este recorrido será de 9 horas.



Elaborado por:

Fontiveros Alejandro
González Emeli
López Javier