PROGRAMACION LINEAL EN R

Orientación básica

Para ejecutar los códigos aquí expuestos y crear nuevos, puedes indistintamente:

Utilizar tu entorno RStudio, si lo tienes descargado en tu PC
Trabajar en RCloud (recuerda crear un usuario)
Utilizar Google Colaboratory (Video de ayuda para utilizar código R allí).

Entre otras posibilidades (Jupyter Notebooks, etc.).

Función `simplex()` del package `boot`

Sirve para problemas de tamaño no muy grande (leer Nota en la ayuda).

Instalar y cargar package previamente. [Fuente]

Función: simplex(a, A1, b1, A2, b2, A3, b3, maxi, n.iter, eps)

Argumentos:

a: coeficientes de la función objetivo
A1: matriz de restricciones de tipo ≤ (sólo la parte de coeficientes)
b1: vector de términos independientes de las restricciones de tipo ≤ (correspondientes a la matriz A1)
A2: idem con restricciones de tipo ≥
b2: idem correspondientes a la matriz A2
A3: idem con restricciones de tipo =
b3: idem correspondientes a la matriz A3
maxi: Poner a TRUE si se desea maximizar la función objetivo
n.iter: número máximo de iteraciones en cada fase (usa método de dos fases)
eps: tolerancia de coma flotante

Devuelve: un objeto de la clase simplex, que es una lista con componentes (entre otros):

$soln: solución óptima, si se alcanza
$solved: código de terminación:
- 1 indica solución óptima encontrada
- 0 indica que se ha alcanzado el número máximo de iteraciones sin acabar
- -1 indica que no existe solución factible
$value: valor de la función objetivo en la solución $soln

etc.

Ejemplos

[Fuente enunciados]

Maximice: $z=5x_1+6x_2$ sujeta a: \[\begin{eqnarray} 3x_1 + 2x_2 \leq 120 \\ 4x_1 + 6x_2 \leq 260 \\ x_1, x_2 \geq 0 \end{eqnarray}\]

library(boot)
#a coef. función objetivo
a=c(5,6)
#A1 matriz de coef. desigualdades <=
A1=matrix(c(3,2,4,6),2,2,byrow=TRUE)
#b1 términos indep. de desigualdades <=
b1=c(120,260)
simplex1<- simplex(a, A1, b1, maxi=TRUE )
simplex1

## 
## Linear Programming Results
## 
## Call : simplex(a = a, A1 = A1, b1 = b1, maxi = TRUE)
## 
## Maximization Problem with Objective Function Coefficients
## x1 x2 
##  5  6 
## 
## 
## Optimal solution has the following values
## x1 x2 
## 20 30 
## The optimal value of the objective  function is 280.

Minimice: $z=3x_1+6x_2$ sujeta a: \[\begin{eqnarray} 4x_1 + x_2 \geq 20 \\ x_1 + x_2 \leq 20 \\ x_1 + x_2 \geq 10 \\ x_1, x_2 \geq 0 \end{eqnarray}\]

library(boot)
#a coef. función objetivo
a=c(3,6)
#A1 matriz de coef. desigualdades <=
A1=matrix(c(1,1),1,2,byrow=TRUE)
#b1 términos indep. de desigualdades <=
b1=20
#A2 matriz de coef. desigualdades >=
A2=matrix(c(4,1,1,1),2,2,byrow=TRUE)
#b2 términos indep. de desigualdades <=
b2=c(20,10)
simplex2<- simplex(a, A1, b1, A2, b2, maxi=FALSE )
simplex2

## 
## Linear Programming Results
## 
## Call : simplex(a = a, A1 = A1, b1 = b1, A2 = A2, b2 = b2, maxi = FALSE)
## 
## Minimization Problem with Objective Function Coefficients
## x1 x2 
##  3  6 
## 
## 
## Optimal solution has the following values
## x1 x2 
## 10  0 
## The optimal value of the objective  function is 30.

Maximice: $z=3x_1-2x_2+2x_3$ sujeta a: \[\begin{eqnarray} x_1 + x_2+ x_3 \leq 15 \\ 2x_1 + x_2 +2x_3\leq 26 \\ 5x_1 + 2x_2 +3x_3\leq 43 \\ x_1, x_2, x_3 \geq 0 \end{eqnarray}\]

library(boot)
#a coef. función objetivo
a=c(3,-2, 2)
#A1 matriz de coef. desigualdades <=
A1=matrix(c(1,1,1,2,1,2,5,2,3),3,3,byrow=TRUE)
#b1 términos indep. de desigualdades <=
b1=c(15,26,43)
simplex3<- simplex(a, A1, b1, maxi=TRUE )
simplex3

## 
## Linear Programming Results
## 
## Call : simplex(a = a, A1 = A1, b1 = b1, maxi = TRUE)
## 
## Maximization Problem with Objective Function Coefficients
## x1 x2 x3 
##  3 -2  2 
## 
## 
## Optimal solution has the following values
## x1 x2 x3 
##  2  0 11 
## The optimal value of the objective  function is 28.

Minimice: $z=1.5x_1+x_2+2.5x_3$ sujeta a: \[\begin{eqnarray} 0.5x_1 + 0.6x_2+0.4x_3 \geq 6 \\ 0.2x_1 + 0.1x_2 +0.3x_3\geq 3.1 \\ x_1, x_2, x_3 \geq 0 \end{eqnarray}\]

library(boot)
#a coef. función objetivo
a=c(1.5,1,2.5)
A1=0
b1=0
#A2 matriz de coef. desigualdades >=
A2=matrix(c(0.5,0.6,0.4,0.2,0.1,0.3),2,3,byrow=TRUE)
#b2 términos indep. de desigualdades >=
b2=c(6,3.1)
simplex4<- simplex(a, A1, b1, A2, b2, maxi=FALSE )
simplex4

## 
## Linear Programming Results
## 
## Call : simplex(a = a, A1 = A1, b1 = b1, A2 = A2, b2 = b2, maxi = FALSE)
## 
## Minimization Problem with Objective Function Coefficients
##  x1  x2  x3 
## 1.5 1.0 2.5 
## 
## 
## Optimal solution has the following values
##   x1   x2   x3 
## 15.5  0.0  0.0 
## The optimal value of the objective  function is 23.25.

Función `lp()` del package `lpSolve`

Se trara de otra función para resolver PPLs, pero más completa pues admite variables enteras (programación entera) y variables binarias (programación 0-1).

Para usarla hay que instalar y cargar el package previamente. [Fuente]

Función: lp (direction, objective.in, const.mat, const.dir, const.rhs, int.vec, binary.vec)

Argumentos:

direction: poner 'max' si se quiere maximizar la función objetivo
objective.in: vector con coeficientes de la función objetivo
const.mat: matriz de coeficientes de las restricciones
const.dir: vector de cadenas de texto indicando la dirección de cada restricción ("<=", "=," o ">=")
const.rhs: vector de términos independientes de las restricciones
int.vec: Vector indicando qué variables son enteras
binary.vec: Vector indicando qué variables son 0-1

Devuelve: un objeto de la clase lp, que es una lista con componentes (entre otras):

$objval: valor de la función objetivo en el óptimo
$solution: solución óptima
$status: indicador numérico:
- 0: éxito
- 2: no hay solución factible

Ejemplo

lpSolveasume que todas las variables son no negativas.

Si queremos tener una variable libre, es necesario hacer la siguiente transformación: Xn = XnA - XnB, donde XnA y XnB son no negativas. [Fuente]

Maximice: $z=x_1+9x_2+3x_3$ sujeta a: \[\begin{eqnarray} x_1 + 2x_2+3x_3 \geq 1 \\ 3x_1 + 2x_2 +2x_3\leq 15 \\ x_1\in \{0;1\},\hspace{0.3cm} x_2\land x_3 \in \ Z \end{eqnarray}\]

library(lpSolve)
objective.in <- c(1, 9, 3) 
const.mat <-  matrix (c(1, 2, 3, 3, 2, 2), nrow=2, 
                               byrow=TRUE)
const.dir <- c(">=", "<=") 
const.rhs <- c(1, 15)
lpmax <- lp ("max", objective.in, const.mat, 
            const.dir, const.rhs, compute.sens=TRUE, 
            int.vec=c(2:3), binary.vec=c(1))
#ver si hubo éxito y valor hallado:
lpmax

## Success: the objective function is 63

#ver donde se alcanza el óptimo:
lpmax$solution

## [1] 0 7 0

El mismo problema anterior, sin pedir variables enteras ni binarias:

library(lpSolve)
objective.in <- c(1, 9, 3) 
const.mat <-  matrix (c(1, 2, 3, 3, 2, 2), nrow=2, 
                               byrow=TRUE)
const.dir <- c(">=", "<=") 
const.rhs <- c(1, 15)
lpmax2 <- lp ("max", objective.in, const.mat, 
            const.dir, const.rhs, compute.sens=TRUE)
#ver si hubo éxito y valor hallado:
lpmax2

## Success: the objective function is 67.5

#ver donde se alcanza el óptimo:
lpmax2$solution

## [1] 0.0 7.5 0.0

Ahora un ejemplo sin solución (Región disjunta, fuente: Grossman):

Minimice: $z=3x_1+6x_2$ sujeta a:

\[\begin{eqnarray} 2x_1 + 2x_2 \geq 6 \\ x_1 + x_2 \leq 1 \\ \end{eqnarray}\]

library(lpSolve)
problem.coef.obj <- c(3, 6) 
problem.coef.restr <-  matrix (c(2, 2, 1, 1), nrow=2, 
                               byrow=TRUE)
problem.dir.restr <- c(">=", "<=") 
problem.term.restr <- c(6, 1)
lpnul <- lp ("max", problem.coef.obj, problem.coef.restr, 
            problem.dir.restr, problem.term.restr, compute.sens=TRUE, 
            int.vec=c(2:3), binary.vec=c(1))
#ver si hubo éxito y valor hallado:
lpnul

## Error: no feasible solution found

#ver donde se alcanza el óptimo:
lpnul$solution

## [1] 0 0

Funcionalidad específica para el transporte:

Función `lp.transport()` del package `lpSolve`

Debemos construir la Matriz de costo.

En esta matriz cada elemento [i,j]nos dice cuál es costo unitario de transporte desde "i" a "j".

Ejemplo:

La empresa “España” dedicada al tratamiento, recuperación y transformación de RAEE dispone de 2 plantas de operación (ubicadas en Madrid y Zaragoza) y 8 almacenes en los cuales se depositan los residuos hasta agotar su capacidad de acopio (situados en Madrid, Zaragoza, Bilbao, Barcelona, Valencia, Alicante, Albacete y Pamplona).

Los almacenes, solicitan a las plantas les envíe un transporte para trasladar los residuos para su tratamiento. El objetivo de la empresa es siempre minimizar los costos de transporte considerando las siguientes restricciones:

1-Satisfacer la mayor cantidad de demanda de vaciado de los almacenes.

2-No sobrepasar la capacidad de operación disponible=ofrecida por las plantas.

Se solicita: Determinar cuántas toneladas se trasladarán por cada vía almacén-planta y cuál es el costo total mínimo hallado, utilizando la siguiente tabla de datos:

-Plantas de tratamiento (filas).

-Almacenes de acopio (columnas).

-Límite de acopio de cada almacén (total de residuos que se demanda recoger = total de la columna “almacén #”).

-Límite de capacidad de tratamiento de cada planta (total de capacidad ofrecida disponible= total de la fila “planta #”).

-Costos unitarios (ton) de traslado por la vía que une cada planta-almacén.

Datos:

Modelización Matemática:

En este problema se interpreta a las plantas de tratamiento como proveedoras de servicios y a los almacenes como demanda (o clientes) del servicio de tratamiento.

Código:

La salida mostrará el valor de la función objetivo y en $solution se mostrará una matriz que reflejará cuántas toneladas RAEE se trasladarán desde el almacén columna "j" hasta la planta fila "i"

library(lpSolve)
# especificamos la matriz de costos
cost.mat <- matrix(nrow=2,ncol=8)
cost.mat[1,] <- c(14,24,21,20,21.5,19,17,30)
cost.mat[2,] <- c(24,15,28,20,18.5,19.5,24,28)

# no se puede exceder la capacidad de las plantas
row.signs <- rep("<=",2)
row.rhs <- c(100,45)

# la demanda de los almacenes debe ser satisfecha
col.signs <- rep(">=",8)
col.rhs <- c(22,14,18,17,15,13,15,20)

# problema de minimización
direction = "min"

distribucion <- lp.transport(cost.mat,direction,
                         row.signs,row.rhs,
                         col.signs, col.rhs)

#ver el costo mínimo total alcanzado:
distribucion

## Success: the objective function is 2583.5

#ver distribución matricial planta-almacén (proveedor-cliente):
distribucion$solution

##      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [1,]   22    0   18   17    0   13   15    4
## [2,]    0   14    0    0   15    0    0   16

Aquí otro, Ejemplo sencillo

Para conocer más:

Visita las fuentes linkeadas en este escrito.
https://cran.r-project.org/web/packages/linprog/
Investiga programación lineal con R. (Por ejemplo en rpubs: https://rpubs.com/Jaime90/335146 )
Anímate a LaTeX

PROGRAMACION LINEAL EN R

Irma Noemí No

1/9/2021

Orientación básica

Función `simplex()` del package `boot`

Ejemplos

Función `lp()` del package `lpSolve`

Ejemplo

Funcionalidad específica para el transporte:

Función `lp.transport()` del package `lpSolve`

Ejemplo:

Datos:

Modelización Matemática:

Código:

Para conocer más:

PROGRAMACION LINEAL EN R

Irma Noemí No

1/9/2021

Orientación básica

Función simplex() del package boot

Ejemplos

Función lp() del package lpSolve

Ejemplo

Funcionalidad específica para el transporte:

Función lp.transport() del package lpSolve

Ejemplo:

Datos:

Modelización Matemática:

Código:

Para conocer más:

Función `simplex()` del package `boot`

Función `lp()` del package `lpSolve`

Función `lp.transport()` del package `lpSolve`