Programación entera


En muchos problemas reales las variables sólo pueden
tomar valores enteros
Ejemplos:



decisiones sobre inversiones, compras, arranques, etc.
Cantidades de productos no divisibles, personas, etc.
Problemas con el método Simplex:


soluciones no están en vértices
¿cómo saber si tenemos una solución?
1
Programación entera

Problema entero puro:
min c Tx
s.a Ax = b
x0
xi entera i

Problema entero mixto:
min c Tx
s.a Ax = b
x0
xi entera i  I
2
Programación entera



Por simplicidad: problema entero puro
Métodos también aplicables al problema mixto
Dificultad principal:


no podemos emplear aproximaciones basadas en la
continuidad de las funciones del problema
no podemos extraer conclusiones para puntos próximos
3
Programación entera

Métodos de solución:


Comparar todas las alternativas (no es eficiente)
Procedimientos eficientes para seleccionar o descartar
alternativas

Basados en la aproximación del problema mediante
problemas lineales (que sabemos resolver)
4
Programación entera

Procedimiento más simple:


ignorar la condición de que las variables sean enteras, y
redondear la solución
Inconvenientes:




¿tiene significado la solución no entera?
¿cómo se redondea la solución?
¿cómo se obtiene una solución redondeada factible?
¿cuándo es óptima una solución redondeada?
5
¿Es válida una solución aproximada?
¿Es válida una solución aproximada?
¿Es válida una solución aproximada?
¿Es válida una solución aproximada?
Algunos ejemplos. Formulación

Hoja de problemas: formulación de problemas
enteros

Modelización de condiciones lógicas
Programación entera

Método más sofisticado:



introducir restricciones adicionales que no eliminen
soluciones enteras (cubierta convexa)
Si las soluciones enteras son vértices, podemos
aplicar el método Simplex
Inconvenientes:


¿Cómo se calculan las restricciones necesarias?
¿Cuántas hacen falta?
11
Programación entera

Cubierta convexa
12
Programación entera

Métodos más eficientes:




Combinación de ideas
se añaden restricciones que aproximan la cubierta convexa
(planos de corte), o
se añaden restricciones que eliminan puntos que no pueden
ser solución (branch and bound)
se resuelven problemas lineales relajados
13
Programación entera

Método de “branch and bound”

Se trata de:



dividir la región factible, y
descartar aquellas partes en las que no puede encontrarse la
solución
Partes que no pueden descartarse:


se calcula la solución por el método Simplex, o
se subdividen en nuevas partes añadiendo restricciones
14
Programación entera

Procedimiento:

Dado el problema
min c Tx
s.a Ax = b
x0
xi entera i
se resuelve su versión relajada (P0)


Si la solución de (P0) es entera, se termina
Si no lo es, se subdivide el problema en varios
15
Programación entera

División del problema


Supongamos que la solución del problema relajado es
xk*, y que (xk*)i no es entera
En la solución (entera) se cumplirá una de las dos
condiciones siguientes:
xi   (xk*)i  , xi   (xk*)i  + 1
donde x  denota la parte entera de x
16
Programación entera

División del problema

Se generan los dos problemas siguientes:
P1 = P0  {xi  (xk*)i }, P2 = P0  {xi  (xk*)i +1}
 En general, se tiene una lista de problemas pendientes de
resolver

Se toman los problemas de la lista, y se resuelven hasta que
la lista queda vacía
17
Programación entera

Ejemplo gráfico
Solución P0
P4 no factible
Solución P1
Solución entera
Solución P2
Solución P3
18
Programación entera

¿Qué sucede al resolver subproblemas?

Subproblema no factible:


Subproblema con solución no entera:


nada
se generan nuevos subproblemas
Subproblema con solución entera:

se compara con la mejor solución entera hasta el momento
19
Programación entera

Eliminación de nodos

Método no eficiente si es necesario examinar todos los
subproblemas


Número de subproblemas:  2n
Eliminar subproblemas:

si la función objetivo óptima del problema relajado cumple
ciertas condiciones
20
Programación entera

Eliminación de subproblemas

Basada en mejor solución entera


Mejor valor de la función objetivo para una solución entera
(hasta el momento): z
Si para un subproblema se cumple


c Txk* > z
descartar el subproblema (y todos los subproblemas que se
generen de él)
Todas sus soluciones enteras son peores que z
21
Programación entera

Selección de subproblema

Análisis en profundidad del árbol de subproblemas



Se toma el último subproblema generado
Se obtienen rápidamente soluciones enteras
Alternativa: búsqueda en extensión

Se examinan primero todos los problemas de un nivel dado
22
Programación entera

Arbol de subproblemas
P0
P2
P5
P7
P9
P1
P6
P8
P10
P11
P12
P3
P4
- Búsqueda en profundidad:
P0, P1, P3, P4, P2, P5, P7
P9, P10, P11, P12, P8, P6
- Búsqueda en extensión:
P0, P1, P2, P3, P4, P5, P6,
P7, P8, P9, P10, P11, P12
23
Programación entera

Generación de nuevos subproblemas:

¿Qué variable no entera se escoge para generar los
subproblemas?


Aquella que permita obtener la solución más rápidamente
Aquella que dé un menor valor de la función objetivo (más
cerca de la solución)

Como el valor de la función objetivo relajada aumenta, variable
con menor aumento
24
Programación entera

Estimación de cambios en la f. objetivo:
xi  xi

La variable i es básica y pasa a ser no básica
Una variable no básica debe pasar a ser básica
xi + (B -1N )i xN = (B -1b )i
xi + (B -1N )i xN = (B -1b )i
c T (x - x )  (xi - xi ) mink (-ck /nik )
Se escoge la variable i con el menor cambio
25
Programación entera

Resolución de subproblemas



Dado un subproblema resuelto, añadimos una
restricción al subproblema
La última solución no cumple la restricción
Aplicamos el método dual del Simplex:



Ponemos la restricción en forma estándar
Añadimos la restricción a la tabla
Aplicamos el método dual
26
Programación entera

Ejemplo:
max 8x1 + 9x2
s.a 76 x1 + 68 x2  767
-38 x1 + 32 x2  29
2 x2  3
x  0 entera

Solución del problema relajado:
x1 = 9/2 , x2 = 25/4
3 = -299/2508 , 4 = -70/2508
27
Programación entera

Nuevas restricciones:
x1  4 , x1  5

Primer subproblema:
x1 + s4 = 4 , s4  0

Nueva solución del primer subproblema:
x1 = 4 , x2 = 181/32
4 = -9/32 , 4 = -299/16
28
Programación entera

Métodos de planos de corte

Alternativa a métodos branch and bound

Introducir nuevas restricciones



sin dividir el problema
sin eliminar soluciones enteras
Objetivo: solución del problema relajado = solución del
problema entero
29
Descargar

prog_entera1