Unidad 3 Inv. de Operaciones

¿QUÉ ES LA PROGRAMACIÓN ENTERA?
Programación entera es programación lineal con la restricción adicional de que los valores de las variables de decisión sean enteros:
P.E pura: Todas las variables de decisión tienen valores enteros.
P.E mixta (PEM): Algunas de las variables de decisión tienen valores enteros. Las demás cumplen con la suposición de divisibilidad.
P.E. Binaria (PEB) : Utilizavariables binarias
Las Xj: son variables de decisión restringidas a tomar valores 0,1.
Xj=1 si la decisión j es si.
0 si la decisión j es no.
Sólo tiene 2 alternativas posibles.


En algunos casos se requiere que la solución óptima se componga de valores enteros para algunas de las variables. La resolución de este problema se obtiene analizando las posibles alternativas de valores enterosde esas variables en un entorno alrededor de la solución obtenida considerando las variables reales. Muchas veces la solución del programa lineal truncado esta lejos de ser el óptimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta solución de forma exacta. El más famoso es el método de 'Ramificar y Acotar' o Branch and Bound por su nombre en inglés. El método deRamificar y Acotar parte de la adición de nuevas restricciones para cada variable de decisión (acotar) que al ser evaluado independientemente (ramificar) lleva al óptimo entero


2.- ¿PARA QUÉ SIRVE?
Programación Entera
Un modelo de Programación Entera (PE) permite abordar aplicaciones donde la solución tiene sentido si una parte o todas las decisiones toman valores restringuidos a números enteros.Por ejemplo, consideremos que tenemos el siguiente problema de Programación Lineal:
 

 
 
 
 
Si todas las variables restringen sus valores a números enteros, entonces estamos frente a un modelo deProgramación Entera (puro). Por el contrario, si al menos algun conjunto de variables no esta acotada a adoptar valores o números enteros, se trata de un modelo de Programación Entera (mixta).Luego, si consideramos que estamos a un modelo de Programación Entera (puro o mixto) y resolvemos el modelo deProgramación Lineal asociado (esto es, admitiendo valores continuos para las variables), estarémosobtiendolasolución de la Relajación Contínua del modelo entero. Para un modelo de maximización, la relajación continua nos proporciona una cota superior del valor óptimodel modelo de Programación Entera asociado.
En el caso particular que la Relajación Contínua nos proporcione una solución entera, entonces ésta será también lasolución del modelo de Programación Entera asociado. En caso contrario deberemos utilizar alguna estrategia o algoritmo para obtener la solución del modelo de PE.
Una herramienta eficiente para abordar estos casos es el algoritmo de Branch &Bound. Utilizaremosun ejemplopara explicar este método:
Resuelva el siguiente modelo de Programación Entera utilizando el algoritmo de Branch &Bound:

 
 
 
 
 
 
Gráficamente corresponde a:

El dominio de puntos factibles para el modelo de Programación Lineal asociado es el área demarcada con verde. Dicho modelo tiene valor óptimo igual a 39, con X1=1,9 y X2=0. Esto corresponde a la relajación contínua delPLE y nos proporciona una cota superior del valor óptimo de dicho problema.
Además, claramente la solución de la relación contínua no satisface la condición de integralidad del modelo de PLE. Finalmente, en el gráfico anterior se han marcado con azul todas aquellas combinaciones que satisfacen las restricciones del modelo de PLE. Claramente esto corresponde a un subdominio del problema linealasociado lo que justifica que la relajación continua nos entrega una cota superior del valor óptimo del PLE.
Al aplicar el algoritmo de Branch &Bound, el nodo inicial corresponde a la relajación continua y se van agregando las ramas o nodos necesarios hasta alcanzar la(s) soluciones que satisfacen las condiciones de integralidad.

 

P0: Corresponde a la relajación continua del PLE.
P1: Po...