Programacion entera

PROGRAMACION 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). Ya hemos apuntado que los modelos de programación lineal entera son modelos de programación lineal que tienen la característica adicional de quealgunas de las variables de decisión deben tener valores enteros. Existen diversas clasificaciones de esta categoría de modelos.
 
            Programas Enteros Puros (x Z+)
 
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     6x1 +  5x2 +   4x3
            s.a.108x1 + 92x2 + 58x3 >= 576
                      7x1 + 18x2 + 22x3 >= 83                        
           
            x1, x2, x3 ><0 y enteros
 
Es un modelo entero puro. Sin las restricciones adicionales de que x1, x2, x3 sean enteras (o sea las condiciones de integralidad) sería un problema de programación lineal.
 
            Programas Enteros Mixtos (x R+, y Z+)
 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     6x1 +   5x2 +   4x3            s.a. 108x1 + 92x2 +  58x3 >= 576
                      7x1 -  18x2 +  22x3 >= 83                                   
                       
            x1, x2, x3 >=0;       x1 y x2 enteros
 
            Programas Enteros 0-1 (x {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 departicular 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 óptimaentera 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 acotarson mucho mejores en cuanto al cálculo 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.
 
PROGRAMACION ENTERA Y METODO GRAFICO
 
En este momento será más conveniente explicar los fundamentos del algoritmo de ramificar y acotar (R y A), por medio de un ejemplo numérico: 
Consideremos elsiguiente problema de Programación lineal Entera:
 
Max z = 5x1 + 4x2 

Sujeto a    x1 +   x2 <=5
                        10x1 + 6x2 <=45
                       
                        x1, x2 >= 0 y entero
 
En la siguiente figura se muestra  el espacio de soluciones de la programación lineal entera representado por los puntos. El espacio de soluciones de programación linealasociado, programación lineal óptima, se define por cancelación de las restricciones enteras. La solución programación lineal óptima se da como x1 = 3,75, x2 = 1,25 y z = 23,75.

PROBLEMAS TÍPICOS
* Problema del transporte
* Problema de flujo con coste mínimo en red
* Problema de asignación
* Problema de la mochila (knapsack)
* Problema del emparejamiento (matching)...