Programacion entera

Programación entera
un modelo de programación entera es un modelo que contiene restricciones y una función objetivo idénticas a las formuladas por la programación lineal. La única diferencia esque una o más de las variables de decisión tiene que tener un valor entero en la solución final.
Definición y modelos de programación entera
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 >= 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. Dichosproblemas 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 deasignació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 lasolució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 partesdel 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. Noobstante 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 elprocedimiento de ramificar y acotar.

Método de planos cortantes
El concepto de plano de corte lo ilustraremos primero con un ejemplo. Considere el problema de programación lineal entera:
Maximizar...