Formulacion

5 Programación entera.

5.1.1 Introducción y casos de aplicación.

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.

No siempre es admisible que las variables de un PL tomen valores continuos, existen:

• Decisiones dicotómicas (si-no)

• Decisiones que deben tomarse en unidades discretas

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.

En algunas aplicaciones, sólo se permite que todas las variables tomen valores de cero o uno, hablamos en estos casos de Programación Lineal Entera Binaria (Digital); si se requiere que solamente algunas de las variables tomen valores de cero o uno, se tiene un problema de Programación Lineal Entera Binaria Mixta.

La PE tiene gran cantidad de aplicaciones en todos los campos.

Hay problemas que no pueden resolverse con las técnicas actuales por:

• Disponibilidad de tiempo de ordenador

• Capacidad de memoria

Para evitar esto parece sensato calcular la solución de un PE redondeando la solución continua.

Pero el redondeo no es aconsejable debido a:

• La solución redondeada no es necesariamente óptima. En muchos casos, ni siquiera estará cera del óptimo.

• La solución redondeada puede no ser factible.

5.2 Definición y Modelos de 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 6×1 + 5×2 + 4×3

s.a. 108×1 + 92×2 + 58×3 >= 5767

×1 + 18×2 + 22×3 >= 83

x1, x2, x3 ><0 y enteros

Es un modelo entero puro. Sin las restricciones adicionales de que x1, x2, x3 sean enteros (osea las condiciones de integralidad) seria 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 6×1 + 5×2 + 4×3

s.a. 108×1 + 92×2 + 58×3 >= 5767

×1 - 18×2 + 22×3 >= 83

x1, x2, x3 >=0; x1 y x2 entero.

Programas Enteros 0–1En 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

5.3 Método Ramificar y Acotar.

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 = 5×1 + 4×2

Sa: x1 + x2 <=510

×1 + 6×2 <=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 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)

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 original por dos espacios los PL1 y PL2, definidos de la manera

...