Programación Lineal y Programación Entera

Vista previa del material en texto

Programación Lineal y Programación Entera 
La programación lineal es una técnica de optimización 
ampliamente utilizada en la IO. En este enfoque, se busca 
maximizar o minimizar una función objetivo lineal sujeta a 
restricciones lineales. Esto se aplica a problemas en los 
que los recursos son limitados y se deben asignar de la 
manera más eficiente posible. 
Un ejemplo clásico de programación lineal es el problema 
de transporte, en el que se busca determinar la cantidad 
de productos que se deben enviar desde múltiples fuentes 
a múltiples destinos para minimizar los costos de envío. 
Otro ejemplo común es la asignación de recursos, donde 
se busca asignar trabajadores a tareas de manera que se 
maximice la productividad o se minimicen los costos 
laborales. 
La programación entera es una extensión de la 
programación lineal en la que se requiere que las variables 
de decisión tomen valores enteros en lugar de valores 
continuos. Esto es esencial en situaciones en las que las 
soluciones deben ser números enteros, como la 
asignación de trabajadores a turnos o la selección de 
proyectos para financiar. 
Los problemas de programación entera son conocidos por 
ser NP-duros, lo que significa que encontrar una solución 
óptima puede ser un proceso computacionalmente 
costoso. Para abordar estos problemas, se utilizan 
algoritmos de búsqueda exhaustiva, como la búsqueda por 
ramificación y acotamiento, que exploran de manera 
sistemática todas las posibles combinaciones de valores 
enteros para las variables de decisión.