Técnicas de optimización: programación lineal entera, dinámica, binaria y algoritmos heurísticos

Resumen

El documento presenta varias técnicas de optimización matemática: la programación lineal entera, la programación dinámica, la programación binaria y los algoritmos heurísticos y metaheurísticos. Explica en qué consiste cada una, cómo se clasifican y algunos métodos de resolución como los cortes de Gomory o Ramificar y Podar. Sirve para entender cuándo conviene usar cada enfoque según el tipo de problema.

Puntos clave

La programación lineal entera es un modelo lineal en el que las variables de decisión deben ser enteras, con soluciones factibles discretas.
Métodos de resolución de la programación lineal entera: cortes de Gomory y Ramificar y Podar (Branch and Bound).
La programación dinámica resuelve problemas con decisiones secuenciales y se clasifica en determinística (estado siguiente determinado) y probabilística (distribución de probabilidad sobre el siguiente estado).
La programación binaria restringe las variables a los valores 0 o 1 y es un caso especial de la programación entera, útil para decisiones Sí/No.
El problema de la asignación es un caso particular de programación binaria para asignar recursos limitados a tareas de forma óptima.
Los algoritmos heurísticos sacrifican exactitud a cambio de un tiempo de respuesta corto; los metaheurísticos son procedimientos iterativos de propósito general.

Ponte a prueba

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)

Preguntas frecuentes

¿Qué es la programación lineal entera?

Es un modelo de programación lineal en el que las variables de decisión deben tomar valores enteros, lo que hace que el conjunto de soluciones factibles sea discreto.

¿Qué diferencia hay entre programación dinámica determinística y probabilística?

En la determinística el estado de la siguiente etapa queda completamente determinado por el estado y la decisión actual. En la probabilística existe una distribución de probabilidad sobre cuál puede ser el siguiente estado.

¿Qué es la programación binaria?

Es un caso especial de la programación entera en el que las soluciones solo pueden tomar los valores 1 o 0, y resulta útil para problemas de decisión Sí/No.

¿Qué sacrifican los algoritmos heurísticos?

Sacrifican la exactitud de la solución a cambio de un tiempo de respuesta corto o aceptable, buscando soluciones lo suficientemente buenas.