Hasta ahora hemos visto los problemas de programación lineal en el dominio de los reales. Sin embargo, en muchos modelos algunas o todas las variables de decisión deben ser enteras. Estos modelos son conocidos como modelos de programación lineal entera (ILP).
A primera vista podría parecer más fácil resolver problemas con restricción de enteros, ya que transforman un problema continuo en un problema discreto. Sin embargo, los algoritmos que permiten resolver los problemas ILP son más complejos y requieren mucho más tiempo computacional.

Los modelos de programación lineal entera se pueden clasificar en:
 

Boxcar es una nueva cadena de restaurants de comida rápida (fast-food) que está planificando expandirse en Washington DC. Aún cuando la comida es de alta calidad, la principal atracción de esta cadena de restaurants es su diseño. En el centro de la ciudad el interior del local se contruyó de tal forma de parecerse al interior de un container, mientras que en los suburbios los restaurants se construyeron al interior de verdaderos containers.
La compañía dispone de US$2.7 millones para su expansión. Cada restaurant en los suburbios requiere US$200.000 en inversión, y cada local en el centro requiere de US$600.000. Se proyecta que luego de los gastos, la ganancia neta semanal en los locales de los suburbios (que estarán abiertos las 24 horas) será en promedio US$1200. Los restaurants del centro abrirán sólo 12 horas al día, pero debido a una gran cantidad de clientes durante las horas de trabajo las proyecciones indican que la ganancia neta semanal será de US$2000. La compañía desea abrir al menos 2 restaurants en el centro.
Boxcar actualmente tiene 19 administradores. Cada local en los suburbios requerirá tres administradores para su funcionamiento las 24 horas, y se cree que con sólo un administrador en el centro por restaurant sería suficiente.
Boxcar desea saber cuántos restaurants podría abrir para maximizar su ganancia neta semanal.

Solución.

Resumiendo el problema, se tiene

• Boxcar debe decidir cuántos restaurants debe abrir en los suburbios y en el centro de Washington DC
• Desean maximizar su ganancia total semanal promedio
• La inversión total no puede exceder US$2.7 millones
• Se deben abrir al menos 2 restaurants en el centro
• Sólo se cuenta con 19 administradores.

La solución real del problema es:

      X1 = 87/16 , X2 = 43/16, Z = US$ 11.900

Surgen naturalmente algunas interrogantes:

¿Por qué no redondear simplemente los valores la solución real?.

 

Posibles resultados del redondeo

Los puntos pueden ser no-factibles

Los puntos pueden ser factibles pero no-óptimos

Los puntos pueden ser factibles y óptimos

 

Nota: Imponer restricción de enteros agrega dos restricciones al problema: X1 entero y X2 entero. Asi es que tal como vimos antes el valor de la función objetivo NO puede mejorar. En un problema de maximización esto significa que el valor de la función objetivo disminuirá o en el mejor de los casos será el mismo que el valor óptimo del problema de programación lineal en el dominio de los reales.

La solución entera del problema es: X1 = 4, X2 = 3, Z = US$ 10.800

PROBLEMA 2.

Después de muchos años con bajos intereses en los bancos, la señorita Mednick ha decidido incursionar el la bolsa. Sin embargo, ella desea hacer una inversión cautelosa. Ella escuchó que las acciones de una compañía de telecomunicaciones se están vendiendo en US$55 c/u (incluyendo comisiones) y se proyecta su venta en US$68. También está considerando invertir en un fondo mutuo, el cuál según un diario especializado, daría un retorno de la inversión de un 9% el próximo año.
Para esta primera incursión en el mercado la srta. Mednick ha sido extremadamente "modesta" en sus objetivos. Ella desea invertir sólo lo suficiente para obtener un retorno de US$250.
Además ella confia más en el fondo mutuo que en la bolsa, por lo tanto se impuso la restricción que la máxima cantidad a invertir en la bolsa no excederá el 40% de su inversión total, y su inversión en acciones no será más de US$750.

Ella desea saber cómo debería invertir.

Solución.

Resumiendo tenemos:

• determinar el número de acciones y la cantidad de dinero invertido en el fondo mutuo
• Minimizar la cantidad de dólares invertidos
• Obtener un retorno de al menos US$250 al año
• Invertir a lo más 40% de su inversión total y no más de US$ 750 en acciones.

El óptimo se encuentra en X1 = 12 y X2 = 1044.44
 

Resolución de ILP´s.

Se han propuesto muchos métodos para poder resolver este tipo de problemas además de redondear y verificar y el de la simple enumeración de puntos. El método más conocido y eficaz hasta el momento es el Branch & Bound (Cota y Ramificación). Este método resuelve inicialmente el problema sin considerar las restricciones de números enteros. Luego se selecciona una de las variables que debe ser entera agregando dos nuevas restricciones:

• la primera impone una upper bound (cota superior) a la variable seleccionada restringiendo su valor de a lo más la parte entera de su valor actual
• la segunda impone una lower bound (cota inferior) a la variable seleccionada restringiendo su valor de al menos la parte entera de su valor actual más 1.

El algoritmo tiene dos conceptos fundamentales:

1. Si se encuentra una solución de un subproblema que satisface todas las restricciones de enteros y ya que esta es una solución factible del problema original, el valor de la función objetivo es una cota inferior para la solución entera óptima.
2. Si se encuentra una solución a un problema que no satisface una o más de las restricciones enteras y ya que agregar restricciones adicionales no puede mejorar el valor de la función objetivo, el valor de esta función objetivo es una cota superior para todos los problemas restantes.

L: La mejor (mas grande) cota inferior encontrada para el IPL o MILP
Z : El valor de la función objetivo del problema que se está considerando (la cota superior para todos los próximos sub-problemas)

Para comenzar el algoritmo se requiere una cota inferior. Si no hay una solución inmediatamente podemos considerar L como menos infinito. El valor inicial de Z es el valor de la función objetivo del problema relajado (es decir, sin restricción de enteros). Luego, si para un sub-problema dado el valor de Z es menor que o igual que la mejor cota inferior L (o si el subproblema es no-factible), se anula la rama.
 

El método Branch & Bound es el siguiente:

1. Resuelva el problema relajado. Si todas las variables tienen valores enteros esta es la solución óptima. Sino, asigne menos infinito a L.
2. Seleccione el siguiente subproblema a resolver con el mayor valor de Z. Seleccione la primera variable entera Xj que tiene actualmente un valor no entero. Cree un nuevo subproblema agregando la restricción Xj ³ I + 1. Si esta rama ya ha sido evaluada, cree un nuevo subproblema agregando una restricción Xj £  I.
3. Resuelva el nuevo subproblema:

Si	Entonces
El problema no es factible	anule la rama
El valor de Z £  L	anule la rama
El problema es una solución y Z > L	Anule la rama Cambie el valor de L por Z Anule las ramas con Z<L
El problema no es solución y Z>L	Este es un nuevo problema

Si quedan subproblemas, volver al paso 2. Si no hay subproblemas entonces la solución óptima es el valor de L.