programacion entera

Fundamentos de Investigaci´n de Operaciones
o
Investigaci´n de Operaciones 1
o
Programaci´n Lineal Entera
o
11 de septiembre de 2003

1.

Introducci´n
o

Un LP donde se requiere que todas las variables sean enteras se denomina un problema de
programaci´n lineal entera pura. Por ejemplo:
o
m´x z = 3x1 + 2x2
a
s.t. x1 + x2 ≤ 6
x1 , x2 ∈ Z +

(1.1)

Un LP donde s´lo algunasvariables deben ser enteras se denomina problema de programaci´n
o
o
lineal entera mixta. Por ejemplo:
m´x z = 3x1 + 2x2
a
s.t. x1 + x2 ≤ 6
x2 ≥ 0
x1 ∈ Z +

(1.2)

Un LP donde todas la variables deben ser igual a 1 ´ 0 se denomina problema de programaci´n
o
o
lineal binaria. Por ejemplo:
m´x z = x1 − x2
a
s.t. x1 + 2x2 ≤ 2
2x1 − x2 ≤ 1
x1 , x2 = {0, 1}

(1.3)

El concepto derelajaci´n de un problema de programaci´n lineal entera (IP) juega un rol fundao
o
mental en la resoluci´n de este tipo de problemas.
o
Definici´n 1 El LP obtenido eliminando todas las condiciones de valores enteros o binarios para las
o
variables se denomina Relajaci´n del LP.
o
Por ejemplo, la relajaci´n de (1.1) quedar´
o
ıa:
m´x z = 3x1 + 2x2
a
s.t. x1 + x2 ≤ 6
x1 , x2 ≥ 0
De lamisma forma, la relajaci´n de (1.3) queda:
o

1

(1.4)

Segundo Semestre 2003

Programaci´n Lineal Entera
o

m´x z = x1 − x2
a
s.t. x1 + 2x2 ≤ 2
2x1 − x2 ≤ 1
x1 , x2 ≥ 0

(1.5)

Cualquier IP puede ser visto como el LP relajado m´s algunas restricciones adicionales. Por lo
a
tanto, el LP relajado es un problema menos restringido, o m´s relajado, que el IP. En consecuencia
ala regi´n factible para cualquier IP debe estar contenida en la regi´n factible del correspondiente LP
o
o
relajado. Luego, si el problema es de maximizaci´n:
o
El valor ´ptimo de z del LP relajado ≥ El valor ´ptimo de z del IP
o
o
Consideremos el siguiente ejemplo:
m´x z = 21x1 + 11x2
a
s.t. 7x1 + 4x2 ≤ 13
x1 , x2 ∈ Z +

(1.6)

La regi´n factible del problema relajado se presentaen la figura 1.1. En este caso, la regi´n factible
o
o
del IP lo conforma el siguiente conjunto de puntos: S = {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1)}. En
este caso, mediante la evaluaci´n y comparaci´n de los valores de z en los seis puntos factibles es
o
o
posible determinar el ´ptimo. Luego, la soluci´n ´ptima de (1.6) es z = 33, x 1 = 0, x2 = 3.
o
o o

x2
3,0

= punto enla regi´n factible
o

2,5
7x 1
x2
+4

2,0

=

1,5

13

1,0
0,5
0

0

0,5 1,0 1,5 2,0 2,5 3,0

x1

Figura 1.1: Regi´n Factible del ejemplo 1.6
o
Si la regi´n factible de la relajaci´n de un IP puro est´ acotada, la regi´n factible del IP consistir´ en
o
o
a
o
a
un n´mero finito de puntos. En teor´ mediante la enumeraci´n y la evaluaci´n de z en cada uno de
u
ıa,o
o
los puntos es posible encontrar el mejor valor de z. El problema es que si la regi´n factible contiene
o
miles de puntos factibles, la enumeraci´n completa no es viable desde un punto de vista computacional.
o
Una segunda opci´n para resolver el IP ser´ mediante la aproximaci´n de la soluci´n obtenida de
o
ıa
o
o
13
la relajaci´n. Por ejemplo si se resolviera la relajaci´n de(1.6) se obtendr´ x 1 = 7 , x2 = 0. Redono
o
ıa:
deando esta soluci´n se obtendr´ x1 = 2, x2 = 0 como posible soluci´n ´ptima. Sin embargo este
o
ıa:
o o
punto est´ fuera de la regi´n factible por lo que no puede ser ´ptimo. Otro candidato a ´ptimo se
a
o
o
o
2

Segundo Semestre 2003

Programaci´n Lineal Entera
o

puede obtener redondeando el valor obtenido de la relajaci´n haciaabajo: x 1 = 1, x2 = 0, valor que
o
tampoco corresponde al ´ptimo real del problema.
o
Como se ve en este ejemplo, no existen garant´ de que la aproximaci´n de soluciones del probıas
o
lema relajado corresponda a la soluci´n ´ptima real del IP. Por lo tanto, no es un enfoque v´lido
o o
a
para resolver el problema. Como se estudi´ previamente, el algoritmo Simplex resuelve un LP a partir...