Casos especiales de programación lineal

Vista previa del material en texto

Casos especiales de programación lineal 
La Programación Lineal (PL) tiene varios casos especiales que presentan 
características particulares y requieren enfoques específicos para su resolución. A 
continuación, se mencionan algunos casos especiales comunes en la PL: 
1. Programación Lineal Entera (PLE): En la PLE, todas las variables de 
decisión deben tomar valores enteros en lugar de valores continuos. La PLE 
es NP-duro, lo que significa que no existe un algoritmo eficiente que pueda 
resolver todos los problemas de PLE en tiempo polinómico. Sin embargo, se 
han desarrollado técnicas heurísticas y métodos de ramificación y 
acotamiento para encontrar soluciones aproximadas. 
2. Programación Lineal Binaria (PLB): En la PLB, las variables de decisión 
solo pueden tomar valores binarios, es decir, 0 o 1. La PLB es ampliamente 
utilizada en problemas de optimización combinatoria, como la asignación de 
recursos limitados, la programación de actividades y la planificación de rutas. 
Al igual que la PLE, la PLB puede requerir métodos de resolución 
especializados, como algoritmos de búsqueda exhaustiva o métodos 
basados en heurísticas. 
3. Programación Lineal Mixta-Entera (PLME): En la PLME, el modelo de PL 
contiene una combinación de variables continuas y variables enteras o 
binarias. Esto permite una mayor flexibilidad en la representación de 
problemas y su resolución. La PLME también es un problema NP-duro, y los 
métodos de resolución incluyen algoritmos de ramificación y acotamiento, 
métodos de descomposición y enfoques basados en relajación y cortes. 
4. Programación Lineal Degenerada: La PL degenerada se produce cuando 
hay más de una solución óptima con el mismo valor objetivo. Esto puede 
ocurrir cuando existen múltiples combinaciones linealmente independientes 
de variables básicas en una solución óptima. La degeneración puede causar 
problemas en los algoritmos de resolución, ya que pueden caer en ciclos 
infinitos o no converger. Se requieren técnicas especiales, como las reglas 
de Bland o el método de dos fases revisado, para evitar la degeneración y 
garantizar la convergencia. 
5. Programación Lineal de Dos Fases: La programación lineal de dos fases 
se utiliza cuando hay restricciones de igualdad en el modelo y se necesita 
encontrar una solución inicial factible para aplicar el método simplex. En la 
primera fase, se resuelve un problema auxiliar para obtener una solución 
factible básica inicial. En la segunda fase, se resuelve el problema original 
utilizando el método simplex a partir de la solución inicial obtenida en la fase 
1. Esto es útil cuando no hay una solución factible inicial clara o cuando las 
restricciones no están bien definidas. 
Estos son solo algunos de los casos especiales comunes en la Programación Lineal. 
Cada caso presenta desafíos únicos y requiere enfoques específicos para su 
resolución. La elección del método y la técnica adecuados depende de las 
características particulares del problema y los objetivos de optimización.