Técnicas de Optimización: Programación Lineal, Dinámica, Binaria y Algoritmos

Programación Lineal Entera

Programación Lineal Entera es una técnica que permite modelar y resolver problemas cuya característica principal es que el conjunto de soluciones factibles es discreto. Es un Modelo Lineal (que vimos en P.L.) agregando que las variables de decisión deben ser enteras.

Existen métodos de resolución de la programación lineal entera, como el procedimiento de los cortes de Gomory o el Ramificar y Podar (Branch and Bound).

Programación Dinámica

La Programación Dinámica es una técnica matemática que se utiliza para la solución de problemas matemáticos seleccionados, en los cuales se toma una serie de decisiones en forma secuencial.

Clasificación de los problemas de Programación Dinámica:

• Programación Dinámica Determinística: Son problemas dinámicos donde el estado en la siguiente etapa está completamente determinado por el estado y la decisión actual.
• Programación Dinámica Probabilística: Existe una distribución de probabilidad sobre lo que puede ser el siguiente estado.

Programación Binaria

La Programación Binaria hace referencia a aquella cuyo conjunto de soluciones sólo puede tomar uno de dos posibles valores: 1 ó 0. Es un caso especial de la Programación Entera. Esta herramienta matemática es especialmente útil para enfrentar problemas de tipo de toma de decisiones Sí/No. El Problema de la Asignación es un caso particular de esta metodología, donde se deben asignar recursos limitados a tareas específicas de manera óptima.

Algoritmos Heurísticos

La palabra heurística viene del griego y significa algo así como 'relativo a la búsqueda' (recordad, 'eureka' significa 'lo he encontrado' y tiene el mismo origen etimológico). Estos algoritmos sacrifican la exactitud de la solución en favor del tiempo de respuesta, es decir, intentan obtener soluciones lo suficientemente buenas con un tiempo de respuesta corto o aceptable.

Algunos algoritmos heurísticos son:

• Algoritmo Heurística General (CONSTRUCTIVO)
• Hill Climbing (ITERATIVO: mejora la solución inicial)

Algoritmos Metaheurísticos

Los Algoritmos Metaheurísticos son algoritmos aproximados de optimización y búsqueda de propósito general. Son procedimientos iterativos que guían una heurística subordinada, combinando de forma inteligente distintos conceptos para explorar y explotar adecuadamente el espacio de búsqueda.

Algunas de las técnicas metaheurísticas son:

• Algoritmos basados en nubes de partículas
• La Búsqueda Tabú (BT)
• La Búsqueda Dispersa (BD)