Programación lineal

R es un software de código abierto centrado en la programación estadística con una multitud de aportaciones en diversos ámbitos. Entre dichas aportaciones, existe un importante contacto con la investigación operativa; es decir, es posible utilizar R para resolver problemas relacionados con la investigación de operaciones.

La investigación de operaciones puede considerarse como una especie de miscelánea de diversas materias que, en ocasiones, no tienen mucho en común. El núcleo básico lo constituye la Programación Lineal (PL), aspecto que se abordará a continuación de forma somera.

Problemas de programación lineal

En los problemas de programación lineal (PL) se trata de optimizar una función objetivo lineal de \(n\) variables de la forma

$$ c_{1} x_{1}+c_{2} x_{2}+\ldots+c_{n} x_{n} $$

Sujeta a un conjunto de restricciones también lineales:

$$ \sum_{j=1}^{m} a 1_{i j} x_{j} \leq b 1_{j} $$ $$ \sum_{j=1}^{r} a 2_{i j} x_{j} \leq b 2_{j} $$ $$ \sum_{j=1}^{s} a 3_{i j} x_{j}=b 3_{j} $$ $$ x_{i} \geq 0, \forall i $$

Método simplex en R

Para empezar se necesita carga el paquete boot. En realidad se trata de un paquete que contiene funciones y datos para técnicas de estadística robusta, pero que contiene así mismo la función simplex para resolver problemas de PL. Los argumentos de esta función son, en este orden:

• a: Vector formado por los coeficientes de la función objetivo.
• A1: Matriz de coeficientes del lado izquierdo de las restricciones del tipo \(\leq\).
• b1: Vector de coeficientes del lado derecho de las restricciones del tipo \(\leq\).
• A2: Matriz de coeficientes del lado izquierdo de las restricciones del tipo \(\geq\).
• b2: Vector de coeficientes del lado derecho de las restricciones del tipo \(\geq\).
• A3: Matriz de coeficientes del lado izquierdo de las restricciones del tipo \(=\).
• b3: Vector de coeficientes del lado derecho de las restricciones del tipo \(=\).
• maxi: FALSE (argumento por defecto) si se trata de un problema de minimización y TRUE si se trata de un problema de maximización.

Ejemplo I

Resolver el siguiente problema de programación lineal:

$$ \begin{aligned} \operatorname{Max} Z=60 x_{1}+35 x_{2}+& 20 x_{3} \\ 8 x_{1}+6 x_{2}+x_{3} & \leq 48 \\ 4 x_{1}+2 x_{2}+1.5 x_{3} & \leq 20 \\ 2 x_{1}+1.5 x_{2}+0.5 x_{3} & \leq 8 \\ x_{2} & \leq 5 \\ x_{1}, x_{2}, x_{3} & \geq 0 \end{aligned} $$

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

# Coeficientes de la función objetivo:
# Z = 60x1 + 35x2 + 20x3
a <- c(60, 35, 20) 
a

[1] 60 35 20

# Coeficientes de las restricciones:
# 8x1 + 6x2 + x3
# 4x1 + 2x2 + 1.5x3
# 2x1 + 1.5x2 + 0.5x3
# 0x1 + 1x2 + 0x3
coeficientes.menor.igual <- c(8, 6, 1,
                              4, 2, 1.5,
                              2, 1.5, 0.5,
                              0, 1, 0) 
coeficientes.menor.igual

 [1] 8.0 6.0 1.0 4.0 2.0 1.5 2.0 1.5 0.5 0.0 1.0 0.0

# Matriz de coeficientes menores o iguales de 4 filas y ordenado por filas:
A1 <- matrix(coeficientes.menor.igual, nrow = 4, byrow = T) 
A1

     [,1] [,2] [,3]
[1,]    8  6.0  1.0
[2,]    4  2.0  1.5
[3,]    2  1.5  0.5
[4,]    0  1.0  0.0

# Coeficientes del lado derecho al menor o igual:
# ≤ 48
# ≤ 20
# ≤ 8
# ≤ 5
b1 <- c(48, 20, 8, 5) 
b1

[1] 48 20  8  5

# Se ejecuta la función para maximizar la función objetivo:
simplex(a, A1, b1, maxi = T) 

Linear Programming Results

Call : simplex(a = a, A1 = A1, b1 = b1, maxi = T)

Maximization Problem with Objective Function Coefficients
x1 x2 x3 
60 35 20 


Optimal solution has the following values
x1 x2 x3 
 2  0  8 
The optimal value of the objective  function is 280.

La salida se interpreta del siguiente modo: los valores óptimos de las variables son, respectivamente, \(2\), \(0\) y \(8\). El óptimo de la función objetivo es \(280\).

Ahora bien, resulta importante mencionar que el problema admite infinitas soluciones, por ejemplo: \(x_{1}=0\), \(x_{2}=1.6\), \(x_{3}=11.2\). Sin embargo, no hay información sobre este aspecto en la salida de la función.

Ejemplo II

Resolver el siguiente problema de programación lineal:

$$ \begin{aligned} \operatorname{Min} Z=800 x_{1}+400 x_{2}+600 x_{3} &+500 x_{4} \\ 10 x_{1}+3 x_{2}+8 x_{3}+2 x_{4} & \geq 5 \\ 90 x_{1}+150 x_{2}+75 x_{3}+175 x_{4} & \geq 100 \\ 45 x_{1}+25 x_{2}+20 x_{3}+37 x_{4} & \geq 30 \\ x_{1}+x_{2}+x_{3}+x_{4} &=1 \\ x_{1}, x_{2}, x_{3}, x_{4} & \geq 0 \end{aligned} $$

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

# Coeficientes de la función objetivo:
# Z = 800x1 + 400x2 + 600x3 + 500x4
a <- c(800, 400, 600, 500)
a

[1] 800 400 600 500

# Coeficientes de las restricciones:
# 10x1 + 3x2 + 8x3 + 2x4
# 90x1 + 150x2 + 75x3 + 175x4
# 45x1 + 25x2 + 20x3 + 37x4
coeficientes.mayor.igual <- c(10, 3, 8, 2,
                              90, 150, 75, 175,
                              45, 25, 20, 37)
coeficientes.mayor.igual

 [1]  10   3   8   2  90 150  75 175  45  25  20  37

# 1x1 + 1x2 + 1x3 + 1x4
coeficientes.igual <- c(1, 1, 1, 1)
coeficientes.igual

[1] 1 1 1 1

# Matriz de coeficientes menores o iguales de 4 filas y ordenado por filas:
A1 <- c(rep(0, 4))
A1

[1] 0 0 0 0

# Coeficientes del lado derecho al menor o igual:
b1 <- c(0)
b1

[1] 0

# Matriz de coeficientes mayores o iguales de 3 filas y ordenado por filas:
A2 <- matrix(coeficientes.mayor.igual, nrow = 3, byrow = T)
A2

     [,1] [,2] [,3] [,4]
[1,]   10    3    8    2
[2,]   90  150   75  175
[3,]   45   25   20   37

# Coeficientes del lado derecho al mayor o igual:
# ≥ 5
# ≥ 100
# ≥ 30
b2 <- c(5, 100, 30)
b2

[1]   5 100  30

# Matriz de coeficientes iguales de 1 fila y ordenado por fila:
A3 <- matrix(coeficientes.igual, nrow = 1, byrow = T)
A3

     [,1] [,2] [,3] [,4]
[1,]    1    1    1    1

# Coeficientes del lado derecho al mayor o igual:
# = 1
b3 <- c(1)
b3

[1] 1

# Se ejecuta la función para maximizar la función objetivo:
simplex(a, A1, b1, A2, b2, A3, b3, maxi = F) 

Linear Programming Results

Call : simplex(a = a, A1 = A1, b1 = b1, A2 = A2, b2 = b2, A3 = A3, b3 = b3, 
    maxi = F)

Minimization Problem with Objective Function Coefficients
 x1  x2  x3  x4 
800 400 600 500 


Optimal solution has the following values
        x1         x2         x3         x4 
0.25925926 0.70370370 0.03703704 0.00000000 
The optimal value of the objective  function is 511.111111111111.

Resulta necesario mencionar que, al no haber restricciones del tipo menor o igual, se ha tenido que generar una restricción ficticia formada por una matriz de ceros A1 y un vector nulo b1.

El método de cómputo que emplea R al utilizar la función simplex es adecuado sólo para problemas de relativamente pequeño tamaño. Si es posible, el número de restricciones debería ser reducido al mínimo posible, ya que el tiempo de ejecución es aproximadamente proporcional al cubo del número de restricciones.

En particular, si hubiera restricciones del tipo \(x_{i}≥b2_{i}\) deberían ser omitidas haciendo \(x_{i}=x_{i}-b2_{i}\), cambiando todas las restricciones y la función objetivo como corresponda (haciendo la transformación inversa una vez obtenida la solución).

Alternativas para resolver problemas de programación lineal en R

Una forma alternativa de abordar el problema de programación lineal en R es utilizando la función linp del paquete limsolve.

Ejemplo I

Resolver el siguiente problema de programación lineal con la función linp:

$$ \begin{aligned} \operatorname{Max} Z=60 x_{1}+35 x_{2}+& 20 x_{3} \\ 8 x_{1}+6 x_{2}+x_{3} & \leq 48 \\ 4 x_{1}+2 x_{2}+1.5 x_{3} & \leq 20 \\ 2 x_{1}+1.5 x_{2}+0.5 x_{3} & \leq 8 \\ x_{2} & \leq 5 \\ x_{1}, x_{2}, x_{3} & \geq 0 \end{aligned} $$

# install.packages("limSolve")
library(limSolve)

# Coeficientes de la función objetivo:
# Z = 60x1 + 35x2 + 20x3
a <- c(60, 35, 20)
a

[1] 60 35 20

# Se multiplican por –1 los coeficientes de la función objetivo.
# Dado que la función ´linp´ se aplica sólo a casos de minimización.
a <- a*(-1)
a

[1] -60 -35 -20

# Coeficientes de las restricciones:
# 8x1 + 6x2 + x3
# 4x1 + 2x2 + 1.5x3
# 2x1 + 1.5x2 + 0.5x3
# 0x1 + 1x2 + 0x3
coeficientes.menor.igual <- c(8, 6, 1,
                              4, 2, 1.5,
                              2, 1.5, 0.5,
                              0, 1, 0)
coeficientes.menor.igual

 [1] 8.0 6.0 1.0 4.0 2.0 1.5 2.0 1.5 0.5 0.0 1.0 0.0

# Se multiplican por –1 los coeficientes de las restricciones del tipo ≤.
# Dado que la función ´linp´ exige que todas las restricciones sean ≥.
coeficientes.mayor.igual <- coeficientes.menor.igual*(-1)
coeficientes.mayor.igual

 [1] -8.0 -6.0 -1.0 -4.0 -2.0 -1.5 -2.0 -1.5 -0.5  0.0 -1.0  0.0

# Matriz de coeficientes mayores o iguales de 4 filas y ordenado por filas:
A1 <- matrix(coeficientes.mayor.igual, nrow = 4, byrow = T) 
A1

     [,1] [,2] [,3]
[1,]   -8 -6.0 -1.0
[2,]   -4 -2.0 -1.5
[3,]   -2 -1.5 -0.5
[4,]    0 -1.0  0.0

# Coeficientes del lado derecho al menor o igual:
# ≤ 48
# ≤ 20
# ≤ 8
# ≤ 5
b1 <- c(48, 20, 8, 5) 
b1

[1] 48 20  8  5

# Se multiplican por –1 los coeficientes de las restricciones (lado derecho).
# Dado que la función ´linp´ exige que todas las restricciones sean ≥.
b1 <- b1*(-1)
b1

[1] -48 -20  -8  -5

# Se ejecuta la función para maximizar la función objetivo:
# E es el lado izquierdo de las restricciones de igualdad (que no hay). 
# F es el lado derecho de las restricciones de igualdad (que no hay). 
linp(E = NULL, F = NULL, G = A1, H = b1, Cost = a)

$X
[1]  0.0  1.6 11.2

$residualNorm
[1] 0

$solutionNorm
[1] -280

$IsError
[1] FALSE

$type
[1] "linp"

Conclusión

Al ser R un software de programación estadística sumamente versátil, 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.