PROGRAMACION ENTERA (Resumen)

Programación Entera es un termino general para los modelos de programación matemática que presentan condiciones de integridad (condiciones que estipulan que algunas o todas las variables de decisión deben tener valores enteros). Ya hemos apuntado que los modelos de programación lineal entera son modelos de programación lineal que tienen la característica adicional de que algunas de las variables de decisión deben tener valores enteros. Existen diversas clasificaciones de esta categoría de modelos.

Programas Enteros Puros

Un modelo entero puro (PLE) es, como su nombre lo indica, un problema en el que se exige que todas las variables de decisión tengan valores enteros. Por ejemplo

Min 6×1 + 5×2 + 4×3

s.a. 108×1 + 92×2 + 58×3 >= 576

7×1 + 18×2 + 22×3 >= 83

x1, x2, x3 ><0 y enteros

Es un modelo entero puro. Sin las restricciones adicionales de que x1, x2, x3 sean enteros (o sea las condiciones de integralidad) seria un problema de programación lineal

Programas Enteros Mixtos

Un problema en el que solo se requieren que algunas variables tengan valores enteros mientras que otras pueden asumir cualquier numero no negativo (es decir, cualquier valor continuo) se llama programación lineal entera mixta (PLEM). Por ejemplo, supóngase que en el problema anterior solo x1 y x2 deben ser enteros y x3 no. El problema resultante es:

Min 6×1 + 5×2 + 4×3

s.a. 108×1 + 92×2 + 58×3 >= 576

7×1 - 18×2 + 22×3 >= 83

x1, x2, x3 >=0; x1 y x2 enteros

Programas Enteros 0–1

En algunos problemas se restringe el valor de las variables a 0 o 1. Dichos problemas se llaman binarios o programas lineales enteros 0–1. Son de particular interés debido a que se pueden usar las variables 0–1 para representar decisiones dicotómicas (sí o no). Diversos problemas de asignación, ubicación de plantas, planes de producción y elaboración de cartera, son de programación lineal entera 0–1.

Existen dos métodos para generar las restricciones especiales que fuercen la solución óptima del problema, hacia la solución óptima entera deseada:

- Método de ramificar y acotar.

- Método de planos de corte.

En ambos métodos las restricciones agregadas eliminan partes del espacio de soluciones, pero nunca alguno de los puntos enteros factibles. Desafortunadamente, ninguno de los dos métodos es efectivo en la solución de problemas de programación lineal entera. No obstante los métodos de ramificar y acotar son mucho mejores en cuanto al calculo se refiere que los métodos de plano de corte. Por esta razón, la mayoría de los códigos comerciales se basan en el procedimiento de ramificar y acotar.