Programación entera

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). 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 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 enteros (o sea las condiciones de integralidad) sería 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 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

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 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.

Método de Ramificación y Acotación

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.

Max z = 5x1 + 4x2

S.a x1 + x2 <=5

10x1 + 6x2 <=45

X1, X2 >= 0 y entero

Se muestra el espacio de soluciones de la programación lineal entera representado por los puntos. El espacio de soluciones de programación lineal asociado, 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.

El procedimiento de Ramificar y Acotar se basa en tratar solo con el problema programación lineal. Como la solución óptima (X1=3,75, X2=1,25 y Z= 23,75) pero no satisface la necesidad de valores enteros, el algoritmo de R y A exige “modificar” el espacio de soluciones lineales de forma tal que nos permita identificar, finalmente, para conseguir la solución óptima entera.

Primero se selecciona una de las variables cuyo valor corriente en la solución óptima no cumple el requisito de valor entero. Seleccionando X1=3,75 arbitrariamente, observamos que la región ( 3 < X1 < 4 ) del espacio de soluciones lineales, no puede incluir ninguna espacio solución factible entera. Entonces podemos modificar el espacio de soluciones lineales eliminando esta región no prometedora, lo que, en realidad, es equivalente a reemplazar el espacio original por dos espacios los PL1 y PL2, definidos de la manera siguiente:

1. Espacio PL1 = espacio PLO + (X1 <= 3)

2. Espacio PL2 = espacio PLO + (X1>= 4)

Se muestra los espacios PL1 y PL2 en forma grafica. Los dos espacios contienen los mismos puntos enteros factibles del modelo PLE. Esto significa que, desde el punto de vista del problema original de PLE, tratar con PL1 y PL2 es igual que tratar con el original PLO. La diferencia principal es que la selección de las nuevas restricciones e acotamiento ( X1 >= 3 y X1 <= 4 ) mejoraran la oportunidad de forzar a los puntos extremos óptimos de PL1 y PL2 hacia la satisfacción del requisito de valor entero. Además el hecho que las restricciones de acotamiento están en la “vecindad inmediata” del optimo continuo del PLO, incrementara las posibilidades de producir “buenas” soluciones enteras. Las nuevas restricciones X1 >= 3 y X2 <= 4 son mutuamente excluyentes, PL1 y PL2 deben tratarse como dos programas lineales separados. Esta dicotomía da lugar al concepto de ramificación en el algoritmo de R y A. En efecto, ramificar significa subdividir un espacio de soluciones corrientes en subespacios mutuamente excluyentes.

Las ramas PL1 y PL2 y X1 llamada variable de ramificación.

Sabemos que la solución óptima entera debe encontrarse en PL1 o PL2. Sin embargo, en ausencia del espacio grafico de soluciones, no tenemos manera de determinar dónde puede encontrarse la solución óptima, por lo que nuestra única opción es investigar ambos problemas. Hacemos esto trabajando con un problema a la vez (PL1 o PL2). Supongamos que escogemos a PL1 asociado con X1 <= 3. En efecto, debemos resolver el siguiente problema:

Max z = 5x1 + 4x2

S.a x1 + x2 <=5

10x1+ 6x2 <=45

X1 <=3

X1, X2>= 0

Como se indica antes PL1 es el mismo que el PLO con la restricción adicional de acotamiento superior, X1 <= 3. Así podemos aplicar el algoritmo primal de acotamiento superior para resolver el problema. Esto da la nueva solución óptima.

X1 = 3, x2 = 2 y Z = 23

Como esta solución

...