Programación lineal entera

En algunos problemas de programación lineal las variables toman valores en un conjunto finito o infinito numerable (un caso particular es cuando las variables son binarias; es decir, toman valores entre cero y uno).

En este caso, el problema se convierte en un problema de Programación Lineal Entera (PLE). Aunque a simple vista el problema parece ser más simple, lo cierto es que las dificultades se incrementan, existiendo diferentes algoritmos para su resolución.

Problemas de programación lineal entera

Para resolver este tipo de probelmas en R, se puede usar el paquete lpsolve. Se trata de un software centrado en la solución de problemas de programación lineal, entera y mixta (cuando algunas variables deben ser enteras y otras no).

En concreto, para resolver problemas de PLE, se debe utilizar la función lp. Veamos un ejemplo a continuación.

Ejemplo I

Resolver el siguiente problema de programación lineal entera:

Max $$ \begin{aligned} \operatorname{Max} Z=5 x_{1}+7 x_{2} \\ 8 x_{1}+14 x_{2} \leq 63 \\ 10 x_{1}+4 x_{2} \leq 45 \\ x_{1}, x_{2} \geq 0 \text { y enteras } \end{aligned} $$

# install.packages('lpSolve')
library(lpSolve)

# Coeficientes de la función objetivo:
# Z = 5x1 + 7x2
coeficientes.objetivo <- c(5, 7)
coeficientes.objetivo

[1] 5 7

# Coeficientes de las restricciones del lado izquierdo (sin importar el tipo):
# 8x1 + 14x2 
# 10x1 + 4x2
coeficientes.lado.izquierdo <- c(8, 14,
                                 10, 4)
coeficientes.lado.izquierdo

[1]  8 14 10  4

# Matriz de coeficientes menores o iguales de 4 filas y ordenado por filas:
const.mat <- matrix(coeficientes.lado.izquierdo, nrow = 2, byrow = T)
const.mat

     [,1] [,2]
[1,]    8   14
[2,]   10    4

# Vector con la dirección de todas las desigualdades:
direccion.restricciones <- c("<=", "<=")
direccion.restricciones

[1] "<=" "<="

# Coeficientes de las restricciones del lado derecho (sin importar el tipo):
# ≤ 63
# ≤ 45
coeficientes.lado.derecho <- c(63, 45)
coeficientes.lado.derecho

[1] 63 45

# Se ejecuta la función para maximizar la función objetivo:
# - El argumento `int.vec = c(1,2)` indica las variables enteras.
#   En este caso, se interpreta como el vector (x1 y x2).
# - El argumento `all.int = T` señala que todas las variables deben ser enteras.
#   En este caso, no se hace uso de la programación lineal entera mixta. 
lp(direction = "max", 
   objective.in = coeficientes.objetivo, 
   const.mat = const.mat, 
   const.dir = direccion.restricciones,
   const.rhs = coeficientes.lado.derecho,
   int.vec = c(1, 2),
   all.int = T)

Success: the objective function is 31 

# Método para conocer los valores de las variables en el óptimo igual a 31:
lp(direction = "max",
   objective.in = coeficientes.objetivo,
   const.mat = const.mat, 
   const.dir = direccion.restricciones,
   const.rhs = coeficientes.lado.derecho,
   int.vec = c(1, 2),
   all.int = T)$solution

[1] 2 3

La salida se interpreta del siguiente modo: los valores óptimos de las variables son, respectivamente, \(2\) y \(3\). El óptimo de la función objetivo es \(31\). En otros términos, la solución al problema es \(x_{1}=2\), \(x_{2}=3\) y \(Z_{\text {óptimo }} = 31\).

Conclusión

Al ser R un software de programación estadística sumamente versatil, existe una gran variedad de opciones alternativas, entre las que destacan:

• Utilizar la función solveLP del paquete linprog.
• Cargar el paquete glpk que proporciona una interface para el programa GLPK (GNU Linear Programming Package), que es un software libre para resolver problemas de programación lineal y de programación lineal entera mixta de gran escala, así como problemas relacionados.
• Utilizar el paquete rcdd para resolver problemas PL con aritmética exacta mediante la función lpcdd.

Referencias

• Sallan, J. M., Lordan, O., & Fernandez, V. (2015). Modeling and solving linear programming with R. OmniaScience.
• Murthy, G. S. R. (2015). Applications of operations research and management science: Case Studies. International Series in Operations Research and Management Science. Springer New York.
• Murthy, G. S. R. (2015). Case Studies in Operations Research: Applications of Optimal Decision Making. International Series in Operations Research and Management Science. Springer New York.