viernes, 28 de octubre de 2011

Detección de Colisiones y Optimización de Trayectorias


En el mundo actual es bastante común ver diferentes objetos interactuando entre sí. A diario vemos a nuestro alrededor balones rebotando, autos moviéndose por las avenidas y aviones aterrizando en los aeropuertos, o, de vez en cuando, practicando alguna formación interesante para algún desfile que se aproxima. Ahora, de todos estos fenómenos con los que nos encontramos a diario, hay muchos, tal vez demasiados, sobre los cuales no tenemos ningún tipo de control. Por ejemplo, sería imposible predecir si un auto va a intentar cruzar mientras la luz está en rojo, o tratar de decidir, en un partido de basquetbol, exactamente hasta qué altura va a rebotar el balón después de que el jugador haya fallado un lanzamiento al aro. Pero, por otra parte, seguramente nunca hemos visto que dos aviones en una formación choquen entre sí, causando un trágico accidente, o que en un simulador de vuelo por computadora, cualquier novato logre realizar un aterrizaje exitoso.

Es justamente el área de interés de la investigación que llevamos a cabo todos esos hechos que implican la interacción entre objetos, y en particular las colisiones entre objetos, que pueden ser medidos, estudiados, e incluso predichos utilizando métodos de programación lineal. Y en este ámbito existen miles de aplicaciones en el mundo real, así como miles de personas haciendo estudios al respecto, para lograr una mejor comprensión de cómo se pueden predecir las trayectorias de los objetos en movimiento, y así lograr puntos de encuentro deseados para numerosas trayectorias.

Uno de los ejemplos más comunes en esta área, y que puede ser resuelto utilizando programación lineal, consiste, como ya se mencionó antes, en el mantenimiento y reorganización de formaciones de aeronaves. Problemas de este estilo toman en consideración las diferentes órbitas de todos los elementos que maniobran en el aire, y realizan cálculos sobre los movimientos de los mismos para evitar colisiones.

Otra rama en el estudio de las colisiones de órbitas, y una de las más populares, está centrada en el desarrollo de videojuegos. Aquí, los estudiosos buscan métodos para simular con la mayor precisión posible eventos que luego pueden ser utilizados para obtener beneficios en el mundo real. Así, se estudian casos como la colisión segura de dos órbitas, o el problema de un misil que persigue a una aeronave.

Claramente existen muchas otras aplicaciones para este tipo de estudios, pero tal vez más interesante que los problemas que se pueden plantear, son las diferentes soluciones que se han podido generar para dar respuesta a dichas preguntas. Así, se han desarrollado algoritmos de todo tipo, que involucran programación lineal, para calcular los puntos de colisión entre órbitas y las condiciones de dicha colisión. Así, se tienen algoritmos genéticos, algoritmos basados en figuras geométricas, entre otros.

Así pues, la detección de colisiones y el estudio de transferencias de órbitas puede ser considerada como una de las ramas de la programación lineal que tiene más aplicaciones en la realidad, y cuyo estudio puede ser utilizado para predecir hechos a los cuales estamos acostumbrados pero sobre los cuales, antes, no teníamos ningún control.

Referencias:

Evitar Colisiones en Trafico Aereo (Modelo de Optimizacion Lineal)

http://www.agifors.org/award/submissions2010/JavierMartinCampo_paper.pdf

Algortimos Círculo, Rectángulo, Polígono Convexo
http://black-byte.com/tutorial/algoritmos-basicos-de-colisiones-para-videojuegos/

Orbitas de Combate
http://www.springerlink.com/content/42w777gk8l435gxk/

Algoritmos Genéticos
ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4797362&abstractaccess=no&usertype=inst

Reconfiguración de Formaciones
trs-new.jpl.nasa.gov/dspace/handle/2014/40138

Trayectorias de Transferencia de Orbitas
http://www.jstor.org/pss/168814

"Plume Avoidance Maneuver Planning"
hohmann.mit.edu/papers/gnc01_milp.pdf

Mantenimiento de Formaciones de Aeronaves
http://acl.mit.edu/papers/ACC02_AIAA1059.pdf

Detección de Colisiones de Trayectorias
http://resources.metapress.com/pdf-preview.axd?code=206651664570657l&size=largest

Trayectorias de Colisión Seguras
acl.mit.edu/papers/gnc06?bregerhow_safety.pdf

Gilbert–Johnson–Keerthi distance algorithm
http://en.wikipedia.org/wiki/Gilbert-Johnson-Keerthi_distance_algorithm

Articulo de un problema en particular de colisiones

http://hal.archives-ouvertes.fr/docs/00/52/62/69/PDF/acc2011.pdf


Integrantes:

- Carlos Ledezma

- Vicente Santacoloma

- Charles Yuan




lunes, 24 de octubre de 2011

Optimización del diseño automotriz


Como respuesta a la sociedad y mercado globalizado en el que vivimos la industria automovilística, como todas las demás, ha tenido que adaptarse a demandas y necesidades siempre cambiantes. Es por esto que en la producción de automóviles entran en juego múltiples factores que al sumarse conforman una cadena de valor mucho más compleja que la que manejaron las industrias pioneras en esta rama.


El primero de estos factores es la Planificación Estratégica que toma en cuenta todos los elementos involucrados en proceso productivo; abarca desde las leyes, regulaciones y políticas que rigen la producción de vehículos automotores hasta los cambios en las tendencias de consumo y el insight de los consumidores. Es la base del proceso productivo que define el camino que seguirán las etapas subsiguientes.


Luego nos encontramos con El Diseño Automotriz, este es una disciplina que se ocupa de la creación y desarrollo de automóviles en su aspecto externo a nivel de las proporciones, la forma y las superficies del vehículo; e interno, a nivel de los accesorios y herramientas como el tablero, la bolsa de aire, los asientos, entre otros. Su finalidad es optimizar la aerodinámica del vehículo, que no le reste a su potencia ni perjudique sus funcionalidades básicas; y la ergometría y seguridad de los pasajeros, asegurándoles la máxima comodidad posible y conformidad con el producto. Adicionalmente, se cubren aspectos como el peso y resistencia de los distintos materiales de elaboración, el costo de ensamblaje, su aporte nocivo a la contaminación, entre otros.


Posteriormente tenemos la Producción Automotriz propiamente dicha, la fase del proceso productivo donde todos los planes y los diseños se ejecutan y se plasman en la elaboración de los diferentes componentes de un automóvil y en su ensamblaje para constituir el producto terminado, esta etapa también contiene las pruebas reglamentarias y el control de calidad, para dar como resultado automóviles completamente conformados.


Por último nos encontramos con el proceso de Downstream, que consiste en la fase final de la cadena de suministros. Es en esta etapa que el producto llega al mercado, por medio de las estrategas aplicadas a los canales de distribución.


Con esta investigación pretendemos estudiar la relación de todos los aspectos a la hora de la producir automóviles de desempeño óptimo, así como exponer nuevas revoluciones dentro del mercado automotriz y elevar el interés de nuestros lectores.



Paginas de interés:

Sobre las etapas de desarrollo automotriz (Ver video para cada proceso):

http://www.automation.siemens.com/mcms/automotive-manufacturing/es/process/pages/default.aspx


Sobre la velocidad:

martes, 18 de octubre de 2011

Programación Lineal



¿Cómo predecir el número de graduando en la USB en base al número de admitidos por cohorte? En el siguiente trabajo de investigación lograremos obtener una solución a esta incógnita mediante un modelo lineal que se ajuste a los datos que describen el problema.

La variable de predicción es el número de graduandos por cohorte, esta depende de otras variables que son independientes como son el número de horas dedicadas a sus estudios, carrera entre otras.




BIBLIOGRAFIA

http://es.wikipedia.org/wiki/Regresi%C3%B3n_lineal#Supuestos_del_modelo_de_regresi.C3.B3n_lineal

http://www.udc.es/dep/mate/estadistica2/sec8_7.html

http://www.bioestadistica.uma.es/libro/node43.htm

http://www.eumed.net/rev/ced/11/jtq.htm

http://www.jcyl.es/jcyl/cee/dgeae/congresos_ecoreg/CERCL/443.PDF





lunes, 17 de octubre de 2011

Optimización Ferroviaria

Acá les dejo un pequeño abreboca de mi trabajo.

Todos hemos pasado alguna vez por un retraso en el metro, por algún colapso en plaza Venezuela a las 5:00 pm. Bueno, eso inspira mi investigación. Analizar las variables que entran en juego, entre ellas la afluencia vs frecuencia de los trenes. Quiero explorar, en parte, ¿de dónde viene eso de frecuecias? y ¿cómo puede ser optimizado?. Todo esto tomando ejemplos históricos de los trabajos que se han hecho en países como Alemania, Inglaterra, entre otros.

Les dejo un link para que vean el mapa. Tiene unas cuantas notas imbuídas en los nodos, con alguna información interesante y con la bibliografía encontrada (por ahora).

Optimización Ferroviaria

Alejandro Tarazona
05-398978

sábado, 15 de octubre de 2011

Planificación de ubicación de antenas WLAN en la USB usando programación lineal



Todos los estudiantes de la Universidad Simón Bolívar desearían tener internet en todo el campus. Sin embargo, para lograr esto, es necesario tomar en cuenta la planificación de las antenas de manera de optimizar la señal, permitir la mayor cantidad de usuarios por área y reducir el costo en lo posible en la compra de antenas.

Es importante tomar en cuenta la serie de restricciones que vienen a la hora de enfrentar este problema. Una de las más importantes es la interferencia de señal entre las estaciones base. Para dicha restricción, se toma en cuenta el número de estaciones base y la cantidad de canales disponibles en dicha base(De hecho, se tomará en cuenta que cada estación base solo tendrá una frecuencia asignada). Otra restricción importante es la densidad de usuarios. La densidad de usuarios (concentración de muchos usuarios de la red en puntos acceso específicos), “degrada” el rendimiento de la red, afectando la velocidad de conexión.

Finalmente, las estrategias a utilizar en este problema será en primer lugar hacer uso de un planteamiento de programación lineal entera(Vista en el curso de Modelos 2). Para lograr aplicar programación lineal, se hará una “relajación” de dicho problema, haciendo uso del algoritmo de randomized rounding. La relajación significa que en lugar de tratar con variables booleanas, trataremos con probabilidades que oscilen de 0 a 1.

Referencias:
  1. Rodriguez, Ricardo, et al. “On the Design and Capacity Planning of a Wireless Local Area Network”. En http://www.forth.gr/ics/mobile/Bibliography/LoadBalancing/LB/Design_Capacity_Planning_WLAN.pdf
  2. Zhang, Yan, et al. “Wireless Mesh Networking: Arquitecture, protocols, standard”. Pag 312-317.
  3. “Linear Programming Relaxation”. En http://en.wikipedia.org/wiki/Linear_programming_relaxation
  4. “Randomized Rounding”. En http://en.wikipedia.org/wiki/Randomized_rounding

Programación Lineal para una óptima Dieta económica y saludable



Mapa conceptual para una óptima Dieta Diaria


Una dieta es una pauta que se sigue a la hora de consumir alimentos, es decir, es la combinación de alimentos que se elige en cada comida. Esta selección puede ser debido a diversos factores como la cantidad de nutrientes, calorías, precio de cada porción, preferencias personales, entre otros.

En una época en la que el precio de los productos es cada vez mayor, es de gran ayuda encontrar una dieta que entre dentro del presupuesto. Pero no debemos olvidar que lo mas importante es que la combinación de alimentos elegida cumpla con los requisitos de nutrientes mínimos para mantenernos saludables. De allí surge el Problema de la Dieta, un problema de optimización que trata de minimizar costos mientras se cumple con las restricciones nutricionales.

Debido a que todos necesitamos comer, este problema ha mantenido el interés de la población y es por eso que a través de los años sigue siendo un caso bastante estudiado en la programación lineal. También es importante que la formulación del problema sea flexible por lo que se pueden agregar nuevas restricciones y se puede adaptar a todo tipo de gustos.

En cuanto a la formulación del problema, las variables no tienen que ser enteras, debido a que se puede consumir menos de una ración de cualquier alimento. Las restricciones son todas del tipo A <= b.X <= C, en donde b es la cantidad de calorías, vitaminas, minerales, etc, que proporcione ese alimento y A, C son constantes conocidas basadas en estudios de nutrición que representan los valores mínimos y máximos de tal elemento que deben ser consumidos para mantener el bienestar.


Grupo:
OneMind

Integrantes:
Carla Nardone; 08-10792
Cristina Villalobos; 08-11186
Héctor Gomes; 08-11231

Fuentes:
Medline Plus (en Español)
Wikipedia: Stigler Diet
Excel Calculations (The Diet Problem)
Matthew Ford's Diet: An Application of the Diet Problem
Prof. Armbruster: Diet Optimization Problem
George J. Stigler: The Cost Of Subsistence


viernes, 14 de octubre de 2011

Programación Lineal de un Sistema de Tráfico Aéreo


El servicio de control del tráfico aéreo, también conocido por sus siglas en inglés ATC (Air Traffic Control) se presta por los países firmantes del tratado de Chicago que dieron origen a la creación de la OACI/ICAO en los términos especificados por las normas de esta organización internacional. Los 2 factores por los cuales en un aeropuerto se requiere el Control de Tráfico Aéreo ATC son la seguridad y eficiencia.

Este tema resulta interesante ya que se logra una coordinación efectiva de los vuelos para evitar complicaciones y accidentes, al igual que en cualquier emergencia que pueda suceder.

Un análisis más profundo del tema se observa en el siguiente link:

http://dl.dropbox.com/u/29546916/TEMA%204%20-%20Aplicacion%20de%20la%20Programacion%20Lineal%20al%20Transporte%20aereo.ppt

En el cual se puede observar un estudio realizado para la aplicación de la programación lineal al transporte aéreo, específicamente problemas de explotación y gestión.

En la presentación se observan distintos modelos lineales que surgen a partir del problema de la programación lineal para el transporte aéreo, las distintas variables que se toman en cuenta para el estudio e incluso las restricciones que se deben tomar en cuenta para los modelos, como por ejemplo:

FO1: minimizar el costo de la asignación de flota.

Variables:

Xij: cantidad de vuelos i realizados en el avión del tipo j.

Yij: Número de aviones del tipo j en el aeropuerto k

Restricciones:

Cobertura de Vuelo: cada vuelo debe ser realizado por algún tipo de avión : Xi1 +Xi2 = 1

Balance de Aviones: Una salida disminuye en uno el número de aviones de un tipo en un aeropuerto; una llegada lo aumenta en uno Yk,i = Yk-1,j + - Xfk,i

fk es el vuelo que llega o sale del aeropuerto k y el signo es + si dicho vuelo es de llegada y si es de salida


Asi como la anterior tambien se pueden tomar otras funciones objetivos y realizar diferentes modelos según sea el caso, estos los pueden observar en el link dado anteriormente.


entre otras funciones objetivo tenemos:


Maximizar las posibilidades de mantenimiento

Maximizar las conexiones que emplean un mismo avión(para que los pasajeros no deban cambiar de avión)

Minimizar costos, asignando para ello costos para penalizar rotaciones con bajas posibilidades de conexión o de empleo del avión.


Finalmente, podemos ver que es de suma importancia realizar un modelo de programación lineal para controlar un sistema de tráfico aéreo, ya que a través de las respectivas soluciones se podrá agilizar la entrada y salida de los aviones de cada aeropuerto, el mantenimiento de los aviones, las escalas, y más.

Grupo: O.V.N.

Integrantes:

Niuroska Filardi

Verónica Liñayo

Omar El Assaad

jueves, 13 de octubre de 2011

Programación Lineal de un sistema de diseminación de información: Gossiping

Forma de lectura: Inicialmente de arriba hacia abajo y luego de izquierda a derecha.

     El gossiping es una técnica de diseminación de información basado en que cada persona tiene una información relevante la cual tiene que transmitir a los demás. Fue introducido inicialmente en las matemáticas discretas como un problema combinatorio en la teoría de grafos. Tiene aplicaciones en las áreas de comunicación, sistemas de distribución de memorias en multiprocesadores y en paralelismo computacional.
        El poder del chisme reside en una sólida diseminación de información, para lo cual existe una variedad de protocolos que, en general, tratan de convertir un sistema de comunicación aleatorio entre personas en un modelo determinístico o cercano a ello.
       El interés en el gossiping reside en su capacidad de determinar maneras de cómo distribuir información basándose en el funcionamiento de los rumores o los chismes en las personas, en general buscando una diseminación de información eficiente, ya sea entre individuos, entre procesadores, entre procesos, etc.

Autores:
The Designers

Integrantes:
D'Apollo, José. 08-10272
Ramos, Melvin. 07-41408
Rosa, Ricardo. 08-11005

Fuentes usadas (bibliografía completa en el mapa conceptual):

Archivos para descarga:
Archivo RAR que contiene un archivo CMAP, un archivo imagen y un archivo HTML para que puedan acceder a los links.
Si tienen problemas con el link, notifíquenlo.

Link para WinRAR (por si acaso):

miércoles, 12 de octubre de 2011

Programación lineal para la compra de productos a proveedores para tiendas departamentales y la venta de los mismos a los consumidores


Andreina Loriente 07-41125
Fabiana Reggio 07-41420
María Valentina 08-10558

El tema elegido es de suma importancia dado que es significativo el uso de programación lineal para la gestión de compra y venta de productos en tiendas departamentales.

Actualmente, a nivel mundial, existen centenares de tiendas departamentales, las cuales ofrecen productos que abarcan todas las necesidades de las personas en genera o tiendas departamentales de un área en particular, por ejemplo en Venezuela, contamos con ferreterías como EPA y Ferretotal…

Del mismo modo, es importante considerar también los costos de todos los productos que se compran previamente a los proveedores, las ganancias que se obtendrán a futuro por la venta de los mismos y el nivel de satisfacción de los clientes y consumidores al comprar dichos productos.

Muchos elementos hay que considerar cuando se habla de un gran negocio, la idea consiste en maximizar las ganancias obtenidas a las tiendas departamentales, pero también minimizar los costos dentro de las mismas, es decir, hay que tomar en cuenta cuántos trabajadores están trabajando dentro de dichas tiendas, cuál es su horario y su salario, de forma que todo el departamento quede satisfecho logrando su objetivo final que es la venta de los productos a los clientes y consumidores. También es considerable el análisis de la frecuencia de los clientes a las tiendas, para calcular el nivel de satisfacción personal.


Bibliografía:

· http://maximizatusganancias.com/aumentar-ventas-en-tiempo-de-crisis/

· http://www.univalle.edu/publicaciones/journal/journal6/pag9.htm