Programación Lineal Entera

Actividad: Programación Lineal Entera

Modelos de Optimización

INTRODUCCION

Sus pioneros fueron Wagner (1950) y Manne (1959). Tradicionalmente estos modelos se han conside¬rado como subclases de la programación lineal, sin embargo, las variables de de¬cisión que aparecen en ellos sólo toman valores enteros, por lo que realmente deben considerarse como problemas de programación entera. El número de mo¬delos lineales enteros y sus métodos de solución es en la actualidad bastante ex-tenso, lo que nos ha llevado a hacer una selección considerando aquellos que creemos más interesantes y que aparecen con mayor frecuencia en la realidad.

La programación entera trata de optimizar aquellos problemas que en algunas o todas las variables de decisión se restringen a un conjunto de valores discretos. Es a partir de la publicación del primer algoritmo de programación lineal entera de Gomory en 1958, cuando se sientan las bases para su desarrollo, aunque ya en la década de los cuarenta se resolvió el problema del transporte (Hitchcock, 1941). Algunas aplicaciones de la programación entera solventan problemas clásicos como el de la mochila, el del viajante, la programación proyectos, la localización de recursos, etc. (Yepes, 2002).

El requerimiento entero sobre las variables a menudo significa que aun cuando la función objetivo y las restricciones sean lineales, el problema no pueda ser resuelto por un algoritmo de programación lineal. La razón es que no existe garantía de que los valores de las variables en la solución más favorable sean enteros.

Una forma de conseguir una solución entera óptima es redondear los valores de las variables de decisión obtenidas por la programación lineal. En algunos casos, este método brinda como resultado una solución entera óptima. Sin embargo, el redondeo puede ofrecer una opción viable con un valor de función objetivo significativamente peor que el óptimo. Peor aún, puede aparecer una solución infactible. Por ello, se han desarrollado algoritmos especializados que alcanzan resultados óptimos cuando algunas variables de decisión presentan valores enteros.

La programación entera trata de optimizar aquellos problemas que en algunas o todas las variables de decisión se restringen a un conjunto de valores discretos. Es a partir de la publicación del primer algoritmo de programación lineal entera de Gomory en 1958, cuando se sientan las bases para su desarrollo, aunque ya en la década de los cuarenta se resolvió el problema del transporte (Hitchcock, 1941). Algunas aplicaciones de la programación entera solventan problemas clásicos como el de la mochila, el del viajante, la programación proyectos, la localización de recursos, etc. (Yepes, 2002).

El requerimiento entero sobre las variables a menudo significa que aún cuando la función objetivo y las restricciones sean lineales, el problema no pueda ser resuelto por un algoritmo de programación lineal. La razón es que no existe garantía de que los valores de las variables en la solución más favorable sean enteros. Una forma de conseguir una solución entera óptima es redondear los valores de las variables de decisión obtenidas por la programación lineal. En algunos casos, este método brinda como resultado una solución entera óptima. Sin embargo, el redondeo puede ofrecer una opción viable con un valor de función objetivo significativamente peor que el óptimo. Peor aún, puede aparecer una solución infactible. Por ello, se han desarrollado algoritmos especializados que alcanzan resultados óptimos cuando algunas variables de decisión presentan valores enteros.

Con el término Programación lineal entera, (PLE), nos referiremos al siguiente tipo de problemas: problemas que formalmente son problemas de programación lineal, máx. / mín. Z = Ax = b, x ≥ 0 pero en los que algunas variables están restringidas a tomar 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 ´únicamente dos valores, 0 ´o 1.

Como veremos en los apartado siguientes los problemas de programación lineal entera nos van a permitir modelar muchas más situaciones que la programación lineal, pero a cambio la resolución de los problemas será mucho más costosa, presentaran, en general, un costo computacional mucho más elevado que el de la programación lineal.

La causa de este incremento de costo computacional se debe a que se pierde la deseable propiedad existente en los problemas de programación lineal de que al menos una solución ´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 aun podremos utilizar técnicas basadas en el simplex.

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, 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 con variables continuas y enteras (PLE mixto).

APLICACIONES DE LA PROGRAMACIÓN LINEAL ENTERA (PLE)

Variables 0-1.2

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ípico de utilización de este tipo de variables es el problema de inversiones, a continuación se muestra una de sus versiones más simplificadas.

Ejemplo:

Un inversor dispone de una cantidad b para invertir en n posibles proyectos/acciones. Cada posible acción tiene un costo de aj unidades monetarias y un beneficio posterior de cj unidades monetarias. El inversor debe decidir que inversiones realizar con objeto de maximizar el beneficio total.

Para este problema se definen variables xj que toman valor 1 cuando se invierte en el proyecto j y valor 0 cuando no se invierte, con estas variables el problema queda en la forma siguiente:

Máx. Z = c1x1 + c2x2 +. . . + cnxn

S/A: a1x1 + a2x2 +. . . + anxn ≤ b

xj ∈ {0, 1}, j = 1, . . . , n

Este problema básico puede modificarse incorporando el hecho de que las inversiones no sean de un solo periodo de tiempo

...