Método Simplex en R
Función lp() del package lpSolve
Se trara de una 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.
- 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 1
\[\text{Minimizar } 0.3 P_1+0.9P_2\]
Sujeto a:
\[\begin{align*} P_1+P_2&\geq800\\ 0.21P_1-0.3P_2&\leq 0\\ 0.03P_1-0.01P_2&\geq0\\ P_1,P_2&\geq0 \end{align*}\]
Para empezar a resolver el problema debemos de installar y habilitar los siguientes paquetes
lpSolve lpSolveAPI ggplot2
library(lpSolve)
library(lpSolveAPI)
library(ggplot2)Una vez habilitados se procede a elaborar las gráficas
Empezando por definr las funciones que representan a cada una de las restricciones
# Obseve que todas las funciones fueron modificadas para poder ser empresadas como $ P_2(P_1) $
P_2R1 <- function(P_1) 0.03/0.01*P_1
P_2R2 <- function(P_1) 0.21/0.3*P_1
P_2R3 <- function(P_1) 800 -1*P_1Posteriormente se procede a elaborar las gráficas cada una de las restricciones
Empezamos por el dominio
x1 = seq(0,800,by=0.1)Posteriormente empezamos a graficar
mydf = data.frame(x1, P_21=P_2R1(x1), P_22=P_2R2(x1),P_23= P_2R3(x1))
mydf <- transform(mydf, z = pmax(P_21,pmin(P_22, P_23)))
ggplot(mydf, aes(x = x1)) +
geom_line(aes(y = P_21), colour = 'blue') +
geom_line(aes(y = P_22), colour = 'green') +
geom_line(aes(y = P_23), colour = 'red') 
Como se puede observar en el gráfico, la curva de la restricción 3 (línea roja) se intersecciona con las otras dos, por lo que se procede a encontrar los puntos de intersección
Interseccion entre R_3 y R_2
Se resuelve de manera matricial como ;
\[\left(\begin{matrix} P_1+P_2 &=800\\ 0.21P_1-0.3P_2 & =0 \end{matrix}\right)\] entonces las matrices \(A\) y \(B\) quedan como:
\[A=\left(\begin{matrix} 1&1\\0.21&-0.3 \end{matrix}\right)\]
\[B=\left(\begin{matrix} 800&0 \end{matrix}\right)\]
Definiendo matricialmente las funciones dentro de R, quedaría como
A<-matrix(c(1,1,0.21, -0.30 ), nrow=2, ncol = 2, byrow = T)
A [,1] [,2]
[1,] 1.00 1.0
[2,] 0.21 -0.3B<-matrix(c(800,0 ), nrow=2, ncol = 1, byrow = F)
B [,1]
[1,] 800
[2,] 0Resolviendo nos queda como
r<-solve(t(A)%*%A)%*%t(A)%*%B
r [,1]
[1,] 470.5882
[2,] 329.4118Interseccion entre R_3 y R_1
Se resuelve de manera matricial como ;
\[\left(\begin{matrix} P_1+P_2 &=800\\ 0.03P_1-0.01P_2 & =0 \end{matrix}\right)\] entonces las matrices \(A\) y \(B\) quedan como:
\[A=\left(\begin{matrix} 1&1\\0.03&-0.01 \end{matrix}\right)\]
\[B=\left(\begin{matrix} 800&0 \end{matrix}\right)\]
Definiendo matricialmente las funciones dentro de R, quedaría como
A<-matrix(c(1,1,0.03, -0.01 ), nrow=2, ncol = 2, byrow = T)
A [,1] [,2]
[1,] 1.00 1.00
[2,] 0.03 -0.01B<-matrix(c(800,0 ), nrow=2, ncol = 1, byrow = F)
B [,1]
[1,] 800
[2,] 0Posteriormente se resuelve como
r<-solve(t(A)%*%A)%*%t(A)%*%B
r [,1]
[1,] 200
[2,] 600Por último se busca determinar los puntos donde la función se minimice; por lo que simplemente se evalua en la función objetivo cada uno de los puntos encontrados
Definiendo la función objetivo
Para ello escribe el código como
val<-matrix(c(470.5882, 329.4118, 200,600), nrow=2, ncol = 2, byrow=T)
val [,1] [,2]
[1,] 470.5882 329.4118
[2,] 200.0000 600.0000FO<-matrix(c(0.3,0.9), nrow=2, ncol=1)
FO [,1]
[1,] 0.3
[2,] 0.9r=val%*%FO
r [,1]
[1,] 437.6471
[2,] 600.0000como se observa la solución óptima del sistema es 437.647 con las variables \(P_1=470.6\) y \(P_2=329.4\)
Método simplex
Programación lineal en R
Para llevar a cabo un análisis simplex de un modelo de programación, primero se realiza el siguiente planteamiento
Sea FO la función objetivo tal que
Ejemplo 1 usando la función lp
\[\text{Minimizar } 0.3 P_1+0.9P_2\]
Sujeto a:
\[\begin{align*} P_1+P_2&\geq800\\ 0.21P_1-0.3P_2&\leq 0\\ 0.03P_1-0.01P_2&\geq0\\ P_1,P_2&\geq0 \end{align*}\]
Entonces elaboramos el planteamiento como
Objetivo<-c(0.3,0.9)Luego definimos la matriz de coeficientes \(A\)
Coef_Restricciones <-matrix(c(1,1,0.21,-0.3,0.03,-0.01),nrow = 3,ncol=2,byrow = T)
Coef_Restricciones [,1] [,2]
[1,] 1.00 1.00
[2,] 0.21 -0.30
[3,] 0.03 -0.01Luego definimos la matriz de coeficientes \(B\)
Sol_Restricciones <- c(800, 0,0)
Sol_Restricciones [1] 800 0 0Por último buscamos definir las restricciones, utilizando el siguiente código
Dir_Restricciones <- c(">=","<=", ">=")
Dir_Restricciones [1] ">=" "<=" ">="Ahora se instala el paquete que permite solucionar la matrices por medio del método simplex
Se puede utilizar la ruta de Tools/Install Packages o bien el comando
Solucion <- lp(direction = "min",
objective.in = Objetivo,
const.mat = Coef_Restricciones,
const.dir = Dir_Restricciones,
const.rhs = Sol_Restricciones)
Sol<-c(Solucion$objval, Solucion$solution)
Sol[1] 437.6471 470.5882 329.4118Entonces observamos que el valor mínimo está en 437.6471 para los valores de \(P_1=470.5882\) y \(P_2=329.4118\).
Ejemplo 2
Resolvamos el siguiente problema
\[\text{Min } F0=-x_1-3x_2\]
con las siguientes restricciones
\[\begin{align*} x_1+x_2&\leq 6\\ -x_1+2x_2&\leq 8\\ x_1,x_2&\geq0 \end{align*}\]
Entonces elaboramos el planteamiento como
Objetivo <- c(-1, -3)Luego definimos la matriz de coeficientes \(A\)
\[A=\left(\begin{matrix}1&1\\-1&2\end{matrix}\right)\]
Coef_Restricciones <-matrix(c(1, 1, -1, 2),
nrow = 2,
ncol = 2,
byrow = TRUE)
Coef_Restricciones [,1] [,2]
[1,] 1 1
[2,] -1 2Así como los valores del vector \(B\)
\[B^T=\left(\begin{matrix}6\\8\end{matrix}\right)\]
Sol_Restricciones <- c(6, 8)
Sol_Restricciones [1] 6 8Por último buscamos definir las restricciones, utilizando el siguiente código
Dir_Restricciones <- c("<=", "<=")
Dir_Restricciones [1] "<=" "<="Ahora se instala el paquete que permite solucionar la matrices por medio del método simplex
library(lpSolve)Ahora escribimos el código siguiente
Solucion <- lp(direction = "min",
objective.in = Objetivo,
const.mat = Coef_Restricciones,
const.dir = Dir_Restricciones,
const.rhs = Sol_Restricciones)
Sol<-c(Solucion$objval, Solucion$solution)
Sol[1] -15.333333 1.333333 4.666667Problemas
Asignación de espacios de anaquel. Una tienda de abarrotes debe decidir el espacio de anaquel que se asignará a cada uno de los cinco tipos de cereales para el desayuno. La demanda diaria máxima es de 100, 85, 140, 80 y 90 cajas, respectivamente. El espacio de anaquel en pulgadas cuadradas para las cajas es de 16, 24, 18, 22 y 20. El espacio de anaquel total disponible es de 5000 pulg\(^2\). La utilidad por unidad es de \(\$1.100, \$1.300, \$1.080, \$1.250\) y \(\$1.200\). Determine la asignación de espacio óptimo para los cinco cereales.
Votación. En cierto condado del estado de Arkansas, en la boleta se presentan cuatro op- ciones a elegir: Construir nuevas carreteras, incrementar el control de armas, aumentar subsidios a granjas y elevar el impuesto a la gasolina. El condado comprende 100,000 votantes urbanos, 250,000 votantes suburbanos, y 50,000 votantes rurales, todos con variables de apoyo y oposición a los temas de elección. Por ejemplo, los votantes rurales se oponen al control de armas y al impuesto a la gasolina, sin embargo están a favor de la construcción de carreteras y de los subsidios a granjas. El condado está planeando una campaña publicitaria de TV con un presupuesto de \(\$100,000\) a un costo de \(\$1500\) por anuncio. La siguiente tabla resume el impacto de un solo anuncio en función de la cantidad de votos a favor y en contra de las diferentes opciones en la boleta.
Cantidad esperada de votos a favor (+) y votos en contra (-) por anuncio
| Tema | Urbanos | Suburbanos | Rurales |
|---|---|---|---|
| Nuevas carreteras | -30000 | 60000 | 30000 |
| Control de armas | 80000 | 30000 | -45000 |
| Control de smog | 40000 | 10000 | 0 |
| Impuesto a la gasolina | 90000 | 0 | -25000 |
Una opción será ganadora si acumula el 51\(\%\) de los votos. ¿Qué opción será aprobada por los votantes, y cuántos anuncios deben asignarse?
Control de semáforos, Stark y Nichols (1972). El tránsito automotriz de tres carreteras, H1, H2 y H3, debe detenerse y esperar una luz verde antes de salir de una carretera de cuota. Las cuotas son de \(\$3, \$4\) y \(\$5\) para los autos que salen de H1, H2 y H3, respectivamente. Las proporciones de flujo de H1, H2 y H3 son de 500, 600 y 400 autos por hora. El ciclo de los semáforos no debe exceder de 2.2 minutos, y la luz verde en cualquier carretera debe permanecer encendida por lo menos durante 25 segundos. La luz amarilla permanece encendida durante 10 segundos. La caseta de cobro puede atender un máximo de 510 automóviles por hora. Suponiendo que los automóviles no se mueven con la luz amarilla, determine el intervalo óptimo para la luz verde en las tres carreteras que maximizará el ingreso de la caseta de cobro por ciclo de tránsito.
Una pequeña empresa vende dos productos, denominados producto 1 y producto 2. Cada tonelada de producto1 consume 30 horas de trabajo, y una del Producto 2 consume 20 horas de trabajo. La empresa tiene un máximo de 2.700 horas de trabajo para el período considerado. En cuanto a las horas de máquina, cada tonelada de productos 1 y 2 consume 5 y 10 horas de máquina, respectivamente. Hay 850 horas de máquina disponibles. Cada tonelada de producto 1 produce 20$ de beneficio, mientras que el producto 2 rinde 60 dólares por cada tonelada vendida. Por razones técnicas, la empresa debe producir un mínimo de 95 toneladas en total entre ambos productos. Necesitamos saber cuántas toneladas de producto 1 y 2 se deben producir para maximizar el beneficio total.