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?

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
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

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
3
Programación entera

La solución no tiene que estar en un vértice,
ni contigua a un vértice
Solución relajada
Solución entera
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
4
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)
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
5
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?

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
6
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?

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
7
Programación entera

Cubierta convexa
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
8
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

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
9
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

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
10
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
11
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
12
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
13
Programación entera
Ejemplo gráfico
Solución P0
P4 no factible
Solución P1
Solución entera
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
Solución P2
Solución P3
14
Programación entera
P4: NF
P0: NE
P1: NE
P6: NF
P2: NE
P3: E
P8: E
P12: B
P10: NE
P5: NE
P11: E
P7: NE
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
P9: NF
15
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
16
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
17
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
18
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
19
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
20
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
21
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
22
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

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
23
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
24
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
25
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
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
26
Programación entera
Planos de corte

Condiciones sobre las nuevas restricciones
(cortes):
No eliminar soluciones enteras
 Eliminar la última solución


Forma de las restricciones:

Restricciones lineales generales
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
27
Programación entera
Planos de corte de Gomory
Nuevas restricciones se generan a partir de
solución del problema relajado
 Suponemos que todas las variables han de ser
enteras y no negativas
 Basados en estudiar la parte entera y la
fraccionaria de las restricciones

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
28
Programación entera
Planos de corte de Gomory
Supongamos una solución relajada no entera
 Variable básica i-ésima no entera
 Restricción correspondiente
xi + k nik xk = bi
 Lado derecho no entero (variable no entera)

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
29
Programación entera
Planos de corte de Gomory

Justificación de la expresión del corte

Por ser las x positivas,
xi + k nik xk = bi  xi + k nik xk = bi

Por ser las x enteras,
xi + k nik xk = bi  xi + k nik xk = bi
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
30
Programación entera
Planos de corte de Gomory

Combinando la restricción inicial con la nueva,
k (fn )ik  (fb )i
Nueva restricción a añadir al problema
 La cumplen todas las soluciones enteras
 No la cumple la última solución
 Resolución eficiente: método dual del Simplex

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
31
Programación entera
Ejemplo de planos de corte

Problema entero anterior. Solución:
x1 = 9/2 , x2 = 25/4
16/2508 -34/2508
N = 19/2508 38/2508
38/2508 76/2508

Nueva restricción
16/2508 s1 + 2474/2508 s2  1/2
16 s1 + 2474 s2 - 2508 s4  1254 , s4  0
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
32
Programación entera
Ejemplo
Corte 1 , x1
Corte 1 - x2
Corte 2 , x2
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
min -x1 - x2
s.a 4x1 - 2x2 - s1 = 3
4x1 + 2x2 + s2 = 9
x,s0
33
Programación entera
Limitaciones del procedimiento
La ecuación que define el corte es válida si
todas las variables son enteras
 Los datos del problema (A, b, c ) han de ser
enteros
 Las variables de holgura han de introducirse
sobre restricciones con coeficientes enteros

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
34
Programación entera
Convergencia

Al resolver un problema relajado

Problema no factible


Problema no acotado


el problema entero no está acotado (sólo para el primer
problema)
Problema óptimo con solución entera


el problema entero no es factible
es la solución del problema entero
Problema óptimo con solución no entera

introducir cortes
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
35
Programación entera
Convergencia finita

Si se siguen las reglas:
Se introducen cortes también sobre la función
objetivo
 Se selecciona la primera de las variables básicas
que toman valores no enteros
 La función objetivo se toma como la primera
variable

Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
36
Programación entera
Cortes sobre la función objetivo

Se introduce una nueva restricción
x0 - i ci xi = 0

Variable x0 siempre básica. Corte:
1 -c T
0
A=
, b=
0 A
b
B -1A =
1 0 -cnT + cbTB -1N
0 I
B -1N
, B=
1 -cbT
0 B
, B -1b =
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
cbTB -1b
B -1b
37
Programación entera
Cortes sobre la función objetivo

De los resultados anteriores, el corte
k (f- )k xk  fz
se obtiene de las partes fraccionales de
-cnT + cbTB -1N = -n , cbTB -1b = z
 Valores de los multiplicadores, cambiados de signo
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
38
Programación entera
Problemas enteros mixtos
 Si
algunas variables no son enteras,
kI fik xk + fi 0/(1-fi 0) kJ (1-fik)xk + kK nik xk
- fi 0/(1-fi 0) kL nik xk  fi 0
I = {i E : fik < fi 0 }, J = {i E : fik  fi 0 },
K = {i E : nk > 0 }, L = {i E : nk  0 }
 No
es posible introducir cortes sobre la
función objetivo (convergencia)
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
39
Programación entera
Método Simplex dual
V é r t ic e in ic ia l
M é t o d o s im p le x
F a c t ib le ( x  0 )
N o ó p t im o (  i < 0 )
M é t o d o s im p le x d u a l
O p t im o (   0 )
N o f a c t ib le ( x i < 0 )
D ir e c c ió n d e
m o v im ie n t o
pn =
B pb
b
n
L o n g it u d d e
paso
C o m p r o b a c ió n
m u lt ip lic a d o r e s
xb +  pb  0
ei
= - N ei
T
=
=
T
e i , B   = -  b
T
-N  
n +  n  0
-T
 n = cn – N B cb  0
Universidad Carlos III de Madrid – Ingeniería Informática
Investigación Operativa - Curso 2003/2004
xb = B
–1
b  0
40
Descargar

Transparencias de clase