SOLUCIÓN DE PROBLEMAS DE PROGRAMACION LINEAL CON R

SOLUCIÓN DE  PROBLEMAS DE PROGRAMACION LINEAL CON R

Ing. Luis Manfredo Reyes

La programación lineal es una técnica de optimización desarrollada por Dantzig alrededor de 1947.

Se tiene una función llamada función objetivo, que debe ser optimizada en dos posibles rutas:

Maximizándola o minimizándola.

El proceso manual de cálculo, aunque relativamente sencillo, es engorroso. Afortunadamente existen muchas opciones de software para resolverlo.

Una de las opciones gratuitas disponibles es el paquete R

R es un paquete estadístico producido  en el proyecto GNU , y se puede descargar en éste link:

http://www.r-project.org/

R no posee una función directa para resolver problemas de programación lineal, pero existe una librería adicional, llamada boot que posee una función para éste fin.

el uso de la función se detalla aquí: (fuente: http://www.ugr.es/~proman/PDF/PracticasIO1_R_simplex.pdf)

Método Simplex para problemas de Programación Lineal
Descripción: 
Esta function optimiza una función lineal ax sujeta a restricciones A1x<=b1, A2x>=b2, 
A3x=b3 y x >= 0. Tanto la maximización como la minimización son posibles, pero por 
defecto hace la minimización. 
Uso simplificado: 
 simplex(a, A1 = NULL, b1 = NULL, A2 = NULL, b2 = NULL, A3 = NULL, 
 b3 = NULL, maxi = FALSE) 

Argumentos: 
 a: Un vector de longitud n que contiene los coeficientes de la función objetivo 
A1: Una matriz de dimensiones m1 por n que contiene los coeficientes de las 
restricciones del tipo <=. 
b1: Un vector de longitud m1 con los coeficientes del lado derecho de las 
restricciones del tipo <=. Este argumento es necesario si está A1, sino se ignora. 
Todos los valores en b1 deben ser no negativos. 
A2: Una matriz de dimensiones m2 por n que contiene los coeficientes de las 
restricciones del tipo >=. 
b2: Un vector de longitud m1 con los coeficientes del lado derecho de las 
restricciones del tipo >=. Este argumento es necesario si está A2, sino se ignora. 
Todos los valores en b2 deben ser no negativos. Notemos que las restricciones x>=0 
se incluyen automáticamente y no se deben introducir aquí. 
A3: Una matriz de dimensiones m3 por n que contiene los coeficientes de las 
restricciones de igualdad 
b3: Un vector de longitud m1 con los coeficientes del lado derecho de las 
restricciones de igualdad. Este argumento es necesario si está A3, sino se ignora. 
Todos los valores en b3 deben ser no negativos. 
maxi: Un carácter lógico que especifica la minimización si es ‘FALSE’ (por defecto) 
y la maximización en caso contrario. Si ‘maxi’ es ‘TRUE’ entonces el problema de 
maximización se convierte en un problema de minimización cambiando los 

coeficientes de la función objetivo por sus negativos. 

Se asume que el lector tiene instalado el paquete y conoce el uso básico del mismo.

El proceso se ilustra con el siguiente ejemplo: 

Maximizar: 200x1+6000x2+3000x3-200x4

Sujeto a:

800x1+6000x2+1000x3+400x4<=13800

50x1+3x2+150x3+100x4>=600

10x1+10x2+75x3+100x4>=300

150x1+35x2+75x3+5x4>=550

INSTRUCCIONES EN R PARA DEFINIR EL PROBLEMA

 library(boot)
 enj <- c(200, 6000, 3000, -200)
 fat <- c(800, 6000, 1000, 400)
 vitx <- c(50, 3, 150, 100)
 vity <- c(10, 10, 75, 100)
 vitz <- c(150, 35, 75, 5)
> simplex(a = enj, A1 = fat, b1 = 13800, A2 = rbind(vitx, vity, vitz), b2 = c(600, 300, 550), maxi = TRUE)

Y el resultado que produce es el siguiente

Linear Programming Results

Call : simplex(a = enj, A1 = fat, b1 = 13800, A2 = rbind(vitx, vity, 
    vitz), b2 = c(600, 300, 550), maxi = TRUE)

Maximization Problem with Objective Function Coefficients
  x1   x2   x3   x4 
 200 6000 3000 -200 


Optimal solution has the following values
  x1   x2   x3   x4 
 0.0  0.0 13.8  0.0 
The optimal value of the objective  function is 41400.