Programación Lineal Entera

Un LP donde se requiere que todas las variables sean enteras se denomina un problema de programacio´n lineal entera pura. Por ejemplo:

m´ax z = 3x1 + 2x2 s.t. x1 + x2 ≤ 6 x1, x2 ∈ Z+

(1.1)

Un LP donde s´olo algunas variables deben ser enteras se denomina problema de programacio´n lineal entera mixta. Por ejemplo:

m´ax z = 3x1 + 2x2 s.t. x1 + x2 ≤ 6 x2 ≥ 0 x1 ∈ Z+

(1.2)

Un LP donde todas la variables deben ser igual a 1 ´o 0 se denomina problema de programacio´n lineal binaria. Por ejemplo:

m´ax z = x1 − x2 s.t. x1 + 2x2 ≤ 2 2x1 − x2 ≤ 1 x1, x2 = {0, 1}

(1.3)

El concepto de relajaci´on de un problema de programaci´on lineal entera (IP) juega un rol funda- mental en la resoluci´on de este tipo de problemas.

Definicio´n 1 El LP obtenido eliminando todas las condiciones de valores enteros o binarios para las variables se denomina Relajacio´n del LP.

Por ejemplo, la relajaci´on de (1.1) quedar´ıa:

m´ax z = 3x1 + 2x2 s.t. x1 + x2 ≤ 6 x1, x2 ≥ 0

(1.4)

De la misma forma, la relajaci´on de (1.3) queda:

1

Segundo Semestre 2003 Programacio´n Lineal Entera

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

(1.5)

Cualquier IP puede ser visto como el LP relajado m´as algunas restricciones adicionales. Por lo tanto, el LP relajado es un problema menos restringido, o m´as relajado, que el IP. En consecuencia la regio´n factible para cualquier IP debe estar contenida en la regio´n factible del correspondiente LP relajado. Luego, si el problema es de maximizaci´on:

El valor ´optimo de z del LP relajado ≥ El valor ´optimo de z del IP

...