Mathematics">
Lectura - 01 - Programacion Entera
Lectura - 01 - Programacion Entera
Lectura - 01 - Programacion Entera
Definición
Un modelo de Programación Entera es aquel cuya solución óptima tiene sentido solamente si una
parte o todas las variables de decisión toman valores restringidos a números enteros, permitiendo
incorporar en el modelamiento matemático algunos aspectos que quedan fuera del alcance de los
modelos de Programación Lineal.
En este sentido los algoritmos de resolución de los modelos de Programación Entera difieren a los
utilizados en los modelos de Programación Lineal, destacándose entre ellos el Algoritmo de
Ramificación y Acotamiento o más conocido como Branch & Bound.
• Problema de Asignación
• Problema de Corte de Rollos
• Selección de Invitados a una Boda
• Programación de la Explotación Forestal
• Problema de la Mochila
Notar que en los problemas anteriores (PEP) el conjunto de las soluciones factibles (o dominio de
soluciones factibles) es finito. Esto ocurrirá generalmente con los problemas de Programación
Entera (puros).
Los algoritmos de programación lineal entera se basan en el aprovechamiento del gran éxito
computacional de la programación lineal. En la estrategia de esos algoritmos intervienen tres
pasos.
Paso 1. Relajar el espacio de soluciones del programa lineal entero omitiendo la restricción entera
en todas las variables enteras, y sustituyéndola con cualquier variable binaria y que tenga el
intervalo continuo 0 ≤ 𝑦 ≤ 1. El resultado del relajamiento es un programa lineal normal.
Paso 3. Iniciar en el punto óptimo continuo e ir agregando restricciones especiales que modifiquen
en forma iterativa el espacio de soluciones del programa lineal, en una forma que al final produzca
un punto extremo que satisfaga los requisitos enteros.
Se han desarrollado dos métodos generales para obtener las restricciones especiales del paso 3.
El primer algoritmo B&B fue desarrollado por A. Land y G. Doig en 1960, para el problema general
de programación lineal entera mixta y pura. Después, en 1965, E. Balas desarrolló el algoritmo
aditivo para resolver problemas de programa lineal entero con variables binarias (cero o uno)
puras. Los cálculos del algoritmo aditivo eran tan sencillos (principalmente suma y resta) que se le
aclamó como un gran avance en la solución del programa lineal entero. Desafortunadamente, el
algoritmo no pudo materializar las ventajas computacionales. Además se demostró que el
algoritmo, que al principio pareció no estar relacionado con la técnica B&B, no es más que un caso
especial del algoritmo general de Land y Doig. En esta sección se presentará sólo el algoritmo
general B&B de Land y Doig. Para explicar sus detalles usaremos un ejemplo numérico.
Los puntos de red de la figura 1 definen el espacio de soluciones del programa lineal entero. El
problema lineal asociado, el “0”, se define eliminando las restricciones enteras. Su solución óptima
es 𝑥1 = 3.75, 𝑥2 = 1.25 𝑦 𝑧 = 23.75
Como la solución óptima del programa lineal 0 no satisface los requisitos enteros, el algoritmo de
ramificación y acotamiento modifica el espacio de soluciones de tal manera que al final se
identifica el programa lineal entero óptimo.
Figura 1: Espacio de soluciones de programa lineal entero
Primero se selecciona una de las variables enteras, cuyo valor óptimo en el programa 0 no sea
entero. Si se selecciona 𝑥1 (= 3.75) en forma arbitraria, la región 3 < 𝑥1 < 4 del espacio de
soluciones del programa 0 no contiene valores enteros de x1 y se puede eliminar como poco
prometedor. Eso equivale a reemplazar el programa lineal 0 original con dos nuevos programas
lineales, el 1 y el 2 (PL1 y PL2), que se definen como sigue:
La figura 2 muestra los espacios PL1 y PL2. Los dos contienen los mismos puntos enteros factibles
del programa lineal entero original, lo que significa que, desde el punto de vista de la solución
entera, manejar PL1 y PL2 es lo mismo que manejar el PL0 original.
Si se continúa en forma inteligente eliminando las regiones que no incluyan a soluciones enteras,
imponiendo las restricciones adecuadas (como 3 < 𝑥1 < 4 en PL0), al final se producirán
programas lineales cuyos puntos extremos óptimos satisfacen las restricciones enteras.
De hecho, se resolverá el programa lineal entero manejando una sucesión de programas lineales
continuos. Las nuevas restricciones, 𝑥1 ≤ 3 𝑦 𝑥1 ≥ 4, son mutuamente excluyentes, por lo que
PL1 y PL2 se deben manejar como programas lineales separados, como se ve en la figura 3. Esta
dicotomización da lugar al concepto de ramificación en el algoritmo de ramificación y
acotamiento, y x1 es la variable de ramificación.
El programa lineal entero óptimo está en PL1 o en PL2. Por consiguiente, se deben examinar
ambos subproblemas. En forma arbitraria se examinará primero PL1 (asociado con 𝑥1 ≤ 3).
𝑀𝑎𝑥 𝑍 = 5𝑥1 + 4𝑥2
𝑠. 𝑎 𝑥1 + 𝑥2 ≤ 5
10𝑥1 + 6𝑥2 ≤ 45
𝑥1 ≤ 3
𝑥1 , 𝑥2 𝑒𝑠 𝑒𝑛𝑡𝑒𝑟𝑜𝑠 𝑛𝑜 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑜𝑠
𝑥1 = 3, 𝑥2 = 2 𝑦 𝑧 = 23
Esta solución satisface los requisitos de ser entero para 𝑥1 𝑦 𝑥2 . Por consiguiente, se dice que PL1
está agotado. Eso quiere decir que ya no se necesita investigar más el PL1, porque no puede
producir una solución mejor del programa lineal entero.
En este punto no se puede decir que la solución entera obtenida con el programa 1 sea la óptima
para el problema original, porque el programa 2 puede tener una solución entera mejor (con
mayor valor de z). Todo lo que se puede decir es que z = 23 es una cota inferior del valor objetivo
óptimo (máximo) del programa lineal entero original. Eso quiere decir que todo subproblema que
no se haya examinado que no pueda dar un valor objetivo mejor que la cota inferior debe
descartarse como no prometedor. Si un subproblema no examinado produce una solución entera
mejor, se debe actualizar la cota inferior en consecuencia.
Dada la cota inferior z = 23, se examina el programa lineal 2 (el único subproblema que queda no
examinado). Como la z óptima es 23.75 en el programa 0 y sucede que todos los coeficientes de la
función objetivo son enteros, es imposible que el PL2 (que es más restrictivo que el programa 0)
produzca una mejor solución entera. En consecuencia, se descarta al PL2 y se llega a la conclusión
que se ha agotado.
a) El valor de z óptimo del PLi no puede producir un valor objetivo mejor que la cota inferior
actual.
b) PLi produce una solución entera factible mejor, que la cota inferior actual.
c) PLi no tiene solución factible.
• Si PLi está agotado y se encuentra una solución mejor, actualizar la cota inferior. Si todos
los subproblemas se han agotado, detenerse; el programa lineal entero óptimo
corresponde a la cota inferior actual, si la hay. En caso contrario, igualar i + 1 y repetir el
paso 1.
• Si PLi no está agotado, seguir en el paso 2, para ramificar.
Paso 2: (Ramificación.) Seleccionar uno de los valores enteros, xj , cuyo valor óptimo en la solución
del PLi no sea entero. Eliminar la región
(en la que [v] define el mayor entero ≤ v) creando dos subproblemas lineales que corresponden a
𝑥𝑗 ≤ [𝑥𝑗∗ ] 𝑦 𝑥𝑗 ≥ [𝑥𝑗∗ ] + 1
Igualar i = i +1 e ir al paso 1