yghjg

Programaci´n Lineal Entera
o
P.M. Mateo y David Lahoz
2 de julio de 2009
En este tema se presenta un tipo de problemas formalmente similares a los
problemas de programaci´n lineal, ya que en su descripci´n s´lo se establecen
o
o o
expresiones lineales. Sin embargo no responden a problemas lineales ya que
algunas (o todas) las variables del problema toman valores que no est´n en un
aconjunto continuo. Por ejemplo, pueden ser variables que toman valores 0 o 1
(binarias), o variables que toman valores enteros no negativos (0,1,2,...), etc.
Tras introducir el tipo de problemas se dedica un importante apartado para
presentar las posibilidades de modelado que esta herramienta proporciona:
problemas binarios, problemas de carga fija, problemas con restricciones condicionales o condicotom´ etc. Tras dedicar una parte importante del tema
ıas,
a presentar estas herramientas de modelado y a plantear numerosos problemas con ellas se procede a mostrar dos m´todos de resoluci´n. Uno de ellos
e
o
dedicado a problemas en los que todas las variables son binarias y otro para
problemas generales. Ambos m´todos tienen en com´n que desarrollan un
e
u
proceso de enumeraci´n quepermite comprobar explicita o implicitamente
o
todas las soluciones del problema hasta encontrar la ´ptima, y entran dentro
o
del tipo de m´todos de ramificaci´n y acotaci´n.
e
o
o

1

Prog. Lineal

Dualidad

A. Post-optimal

Prog. Entera

´
Indice
1. Introducci´n
o

3

2. Aplicaciones de la programaci´n lineal entera (PLE)
o

3

3. Resoluci´n de problemas de PLE
o11
3.1. M´todo enumerativo sencillo para PLE’s binarios puros . . . . . . . . . . 12
e
3.2. M´todo de ramificaci´n y acotaci´n . . . . . . . . . . . . . . . . . . . . . 17
e
o
o

2

Prog. Lineal

1.

Dualidad

A. Post-optimal

Prog. Entera

Introducci´n
o

Con el t´rmino Programaci´n lineal entera, (PLE), nos referiremos al siguiente tipo
e
o
de problemas: problemas queformalmente son problemas de programaci´n lineal, m´x /
o
a
m´ Z = Ax = b, x ≥ 0 pero en los que algunas variables est´n restringidas a tomar
ın
a
valores enteros.
Por ejemplo, x1 ≥ 0, x2 ≥ 0 y entera, X3 ∈ {0, 1}, x1 una variable como las que hemos
manejado hasta ahora, x2 una variable entera no negativa y x3 una variable binaria, que
toma unicamente dos valores, 0 ´ 1.
´
o
Comoveremos en los apartado siguientes los problemas de programaci´n lineal entera
o
nos van a permitir modelar muchas m´s situaciones que la programaci´n lineal, pero a
a
o
cambio la resoluci´n de los problemas ser´ mucho m´s costosa, presenteran, en general,
o
a
a
un costo computacional mucho m´s elevado que el de la programaci´n lineal.
a
o
La causa de este incremento de costo computacionalse debe a que se pierde la deseable
propiedad existente en los problemas de programaci´n lineal de que al menos una soluci´n
o
o
optima del problema se encuentra en un punto extremo. En estos problemas los conjuntos
´
ya no tienen que ser conexos (pueden estar definidos a trozos) y mucho menos convexos
con lo que la idea de punto extremo tal y como la hemos definido desaparece. De todosmodos, para su resoluci´n a´n podremos utilizar t´cnicas basadas en el simplex.
o u
e
En el apartado 2 presentaremos diversas situaciones generales que pueden ser modeladas mediante PLE y despu´s en el apartado 3 mostraremos dos t´cnicas de resoluci´n,
e
e
o
una para el caso en que todas las variables del problema son binarias (Problemas de programaci´n lineal binaria) y otro para problemascon solo variables enteras (PLE puros)
o
o con variables continuas y enteras (PLE mixto).

2.

Aplicaciones de la programaci´n lineal entera (PLE)
o

Variables 0-1. Problema de inversiones
Las variables binarias xj ∈ {0, 1} pueden utilizarse para modelar situaciones en las
que se decide si una acci´n se realiza, xj = 1, o si no se realiza, xj = 0. Un ejemplo t´
o
ıpico
de utilizaci´n...