Programacion entera

Introducción

En este trabajo sobre la quinta unidad se habla sobre Programación entera así mismo se menciona que sus pioneros fueron Wagner (1950) y Manne (1959). Tradicionalmente estos modelos se han conside¬rado como subclases de la programación lineal, sin embargo, las variables de de¬cisión que aparecen en ellos sólo toman valores enteros, por lo que realmente deben considerarse como problemas de programación entera. El número de mo-delos lineales enteros y sus métodos de solución es en la actualidad bastante ex¬tenso, lo que nos ha llevado a hacer una selección considerando aquellos que creemos más interesantes y que aparecen con mayor frecuencia en la realidad. Si se requiere que todas las variables sean enteras, se dice que se habla de Programación Lineal Entera Pura; si se necesita que algunas de las variables de decisión sean números enteros, se tiene un problema de Programación Lineal Entera Mixta. Ampliando mas el tema se mencionan los temas con un claro ejemplo;

• Definición y modelo de P.E.

• Método de Ramificar y Acotar.

• Método de plano Cortante.

• Algoritmo Activo de Bolas.

• Programación Dinámica.

Desarrollo

Definición Y Modelos De Programación Entera

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. Los modelos de programación lineal entera se pueden clasificar en:

Ejemplo; PROBLEMA 1

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 construyó de tal forma de parecerse al interior de un conteiner, 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.

Un Modelo Matemático sería: ________________________________________

Máx 1200 X1 + 2000 X2

s.a. 2 X1 + 6 X2 <= 27

X2 >=2

3 X1 + X2 <= 19

X1, X2 >= 0, enteros

________________________________________

La solución real del problema es: X1 = 87/16, X2 = 43/16, Z = US$ 11.900

- Método de ramificar y acotar.

Definición y ejemplo; 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 el siguiente 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 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 seleccionaremos 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

...