Programacion entera

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 a conjuntocontinuo. 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 con dicotom´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 que permite comprobarexplicita 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 2. Aplicaciones de la programaci´n lineal entera (PLE) o 3 3

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

2

Prog. Lineal

Dualidad

A. Post-optimal

Prog. Entera

1.

Introducci´n o

Con el t´rmino Programaci´n lineal entera, (PLE), nos referiremos al siguiente tipo e o de problemas: problemas que formalmente 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 Como veremos en los apartado siguientes los problemas de programaci´nlineal 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 computacional se debe a que se pierde la deseable propiedad existente en los problemas deprogramaci´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 todos modos, para su resoluci´n a´n podremos utilizar t´cnicas basadas en el simplex. o u e Enel 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 problemas con 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 de este tipo de variables es el problema de inversiones, a continuaci´n se o o muestra una de sus...