programacion entenr


INTRODUCCION
Con el término Programación lineal entera, (PLE), nos referiremos al siguiente tipo de problemas: problemas que formalmente son problemas de programación lineal, máx. =mn Z = Ax = b; x 0 pero en los que algunas variables están restringidas a tomar
valores enteros.
Por ejemplo, x1 0; x2 0 y entera, X3 2 f0; 1g, x1 una variable como las que hemos manejado hasta ahora, x2 unavariable entera no negativa y x3 una variable binaria, que toma únicamente dos valores, 0 o 1.
Como veremos en los apartado siguientes los problemas de programaciónno lineal entera nos van a permitir modelar muchas mas situaciones que la programación lineal, pero a cambio la resolución de los problemas será mucho más costosa, presentaran, en general, un costo computacional mucho mas elevado que elde la programación lineal.
La causa de este incremento de costo computacional se debe a que se pierde la deseable propiedad existente en los problemas de programación lineal de que al menos una solución optima del problema se encuentra en un punto extremo. En estos problemas los conjuntos
ya no tienen que ser conexos (pueden estar de nidos a trozos) y mucho menos convexos con lo que la idea depunto extremo tal y como la hemos tenido desaparece. De todos modos, para su resolución aun podremos utilizar técnicas basadas en el simplex.
En el apartado 2 presentaremos diversas situaciones generales que pueden ser modeladas mediante PLE y después en el apartado 3 mostraremos dos técnicas de resolución, una para el caso en que todas las variables del problema son binarias (Problemas deprogramación lineal binaria) y otro para problemas con solo variables enteras (PLE puros) o con variables continuas y enteras (PLE mixto).




PROGRAMACIÓN ENTERA:
Programación Entera es un término 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). Yahemos 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 lasvariables 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. Dichos problemas se llaman binarios o programas lineales enteros 0–1. Son de particularinteré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étodode 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 cálculo serefiere 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.

METODO GOMORY
Algoritmo de los cortes de Gomoroy para un PPLE
A continuación se enumeran los pasos del algoritmo de los cortes de Gomoroy para un PPLE:
Paso 1: Iniciación
1.1 Se resuelve el problema original sin restricciones de integralidad....