Proyecto de matheuristica


Introducción


En el lenguaje común las personas utilizan el término “optimizar” en el sentido de mejorar; pero, en el lenguaje de las matemáticas la optimización es el proceso de buscar la mejor solución posible para un determinado problema. En un problema de optimización existen diferentes soluciones, que conforman el conjunto de decisiones factibles, y una función que mide la calidad de cadauna de esas soluciones, denominada función objetivo o criterio, la cual nos permite discriminar entre ellas, obviamente la meta es encontrar la solución de mejor calidad, que se denomina la solución óptima del problema.
Algunos tipos de problemas de optimización son, desde un punto de vista matemático, relativamente fáciles de resolver, este es el caso, por ejemplo, de los problemas deprogramación lineal, en los que tanto la función objetivo como las restricciones son expresiones lineales y las variables pueden tomar valores dentro del conjunto de los números reales. Para estos problemas existen algoritmos que permiten resolverlos de una manera eficiente, como con el método Simplex, o los métodos de punto interior; sin embargo, la mayoría de problemas de optimización son muy difíciles deresolver. Es más, casi todos los problemas reales en la logística, la industria y la ciencia que podemos encontrar en la práctica entran dentro de esta categoría. A partir de ahí surge la necesidad de tener métodos aproximados, que a pesar que no permiten determinar la solución óptima de estos problemas, por lo menos nos proporcionan buenas soluciones, cercanas a la solución óptima.
El problema dela mochila (KP por sus siglas en inglés), es un problema de optimización combinatoria muy referenciado en la literatura de investigación de operaciones, tanto por sus aplicaciones como por su estructura, que lo hace ideal para la evaluación del desempeño de métodos de búsqueda inteligente en problemas de optimización combinatoria.










Problema de la Mochila
El problema KP es un problema deoptimización combinatoria de formulación sencilla, aunque su resolución es compleja, y que aparece, directamente, o como un subproblema, en una gran variedad de aplicaciones, incluyendo planificación de la producción, modelización financiera, muestreo estratificado, planificación de la capacidad de instalaciones, etc., como se observa en. Además de sus potenciales aplicaciones, el KP es departicular interés por sus características combinatorias y su estructura sencilla, que lo vuelve un problema ideal para el diseño de métodos de búsqueda inteligente. Con el tratamiento del problema KP se pueden evaluar las ventajas y desventajas de estos algoritmos, sobretodo su robustez, precisión y rapidez.






Se nos ha dado n objetos denotados por xi (i = 1, 2,. . ., n) cada uno con pesocorrespondiente wi. Podemos imaginar una persona que lleva una mochila que tenga acceso a cada uno de estos objetos. Por desgracia, esta persona sólo puede mantener un peso máximo W en su mochila. El problema e es el siguiente: ¿cuál es el surtido óptimo de los objetos de tal manera que la persona que maximiza el valor de los objetos en la mochila con la restricción de peso W?
Las aplicaciones de estesimple problema se pueden encontrar en muchos campos. En economía, el problema de la mochila es análogo a un modelo de consumo sencillo dado una restricción presupuestaria. En otras palabras, se elige de una lista de objetos para comprar, cada uno con una cierta utilidad, sujeto a la restricción presupuestaria. Debido a que el problema de la mochila es un problema muy general en la optimizacióncombinatoria.
Así, el KP puede ser representado sencillamente por la siguiente formulación de programación binaria:





Métodos Resolución Mediante Heurísticas
Métodos de Búsqueda Local
A diferencia de los métodos anteriores, los procedimientos de búsqueda o mejora local comienzan con una solución del problema y la mejoran progresivamente. El procedimiento realiza en cada paso un movimiento de una...