¿Qué es la Programación Lineal?

La Programación Lineal, es un subconjunto de programación matemática que, a su vez, forma parte de la Investigación de Operaciones. La Investigación de Operaciones es una disciplina que se ocupa de la optimización y el control de los sistemas. Por lo tanto, el término “programación” se utiliza como sinónimo de optimización.

Los problemas de optimización son simplemente versiones formalizadas del principio económico fundamental: o maximizan las salidas (outputs) para una determinada entrada (input) o minimizan las entradas (inputs) para una cierta salida (output) requerida. Cuál de las dos versiones se aplica a cualquier problema depende del escenario específico o del punto de vista del tomador de decisiones. El ejemplo más común de esto es un proceso en el que se quiere maximizar el ingreso (en dinero) o minimizar el gasto (también en dinero).

Los problemas de programación matemática son modelos matemáticos que intentan modelar una situación de la vida real. Lo hacen mediante el uso de variables y parámetros. Ambos representan números, pero si bien los parámetros son números conocidos por el tomador de decisiones y deben tomarse como un dato fijo, las variables son números cuyos valores se determinarán en el proceso. En general, los parámetros no están bajo el control del decisor, mientras que las variables sí.

Además, todos los problemas de programación matemática consisten en dos componentes: Restricciones y objetivos. El sistema impone restricciones, lo que significa que no están bajo el control del tomador de decisiones, quien solamente puede darse cuenta de su existencia y respetarlas. Los ejemplos típicos son restricciones que limitan los recursos (por ejemplo, restricciones presupuestarias), acuerdos contractuales existentes que requieren que se entreguen ciertas cantidades de productos, límites físicos y/o químicos, etc. Cabe señalar que las restricciones en la programación matemática no pueden ser violadas.

La mayoría de los modelos de optimización emplean una única función objetivo (función matemática que modela la situación o proceso que se quiere mejorar) y restricciones (expresadas generalmente como desigualdades).

Finalmente, la Programación Lineal requiere que todas las funciones (funciones objetivo y restricciones), sean lineales. Muy a menudo, aunque no siempre, la linealidad es una aproximación razonable de la realidad.

En resumen se puede decir que la Programación Lineal es una herramienta para analizar y elegir la mejor entre muchas alternativas, determinando la mejor manera de distribuir una cantidad de recursos limitados en procura de lograr un objetivo expresable en maximizar o minimizar una determinada cantidad.

El método tradicional y más conocido y estándar para la solución de problemas de Programación Lineal es el Método Simplex. Este método se basa en operaciones de álgebra lineal con matrices, por lo que el sistema R, que tiene muchas funciones y operaciones que facilitan los cálculos con matrices, es una herramienta muy adecuada para solucionar problemas de Programación Lineal.

Resolución de problemas de Programación Lineal

Un problema típico (el más sencillo) de Programación Lineal es el siguiente:

Un agricultor dispone de 110 Ha donde realizar su cultivo con o sin riego. Estima que conseguirá un beneficio de 50 unidades monetarias por Ha sin riego y 80 unidades monetarias por Ha con riego. La cosecha supone 4 horas de trabajo por Ha sin riego y 8 horas por Ha con riego, pero el agricultor sólo dispone de 720 horas de trabajo. También existe una limitación en el terreno donde cultivar sin riego: sólo 80 Ha tienen las características adecuadas. El agricultor nos pide definir un modelo de programación líneal que maximice sus beneficios.

Los pasos para resolver este tipo de problemas son los siguientes:

  1. Identificación de Variables.
  2. Planteamiento de la “Función Objetivo” que se quiere optimizar (maximizar o minimizar).
  3. Planteamiento de las restricciones como desigualdades.
  4. Graficación de la “Función Objetivo” y de las restricciones (posible solamente cuando existen 2 variables).
  5. Resolución del problema.
  6. Análisis de Sensibilidad

Para la resolución de estos problemas se utilizará la función lp() del paquete lpSolve, por lo que se deberá instalar este paquete. Una vez instalado, se lo deberá cargar tecleando:

library(lpSolve)

Variables:

\(x_{1} =\) Hectáreas sin riego

\(x_{2} =\) Hectáreas con riego

Función objetivo:

\((max) z = 50 x_1 + 80 x_2\)

Restricciones:

Área: \(x_1+x_2 \leq 110\)

Horas de trabajo: \(4 x_1 + 8 x_2 \leq 720\)

Cuota: \(x_1 \leq 80\)

Graficación:

La graficación se realiza con las funciones makeFun() y plotFun() del paquete mosaic, que se carga tecleando lo siguiente:

library(mosaic)
# función objetivo para graficar
fun.obj <- makeFun(50*x1 + 80*x2 ~ x1 & x2)

# restricciones para graficar
rest.area <- makeFun(x1 + x2 ~ x1 & x2)
rest.horas <- makeFun(4*x1 + 8*x2 ~ x1 & x2)
rest.cuota <- makeFun(x1 + 0*x2~ x1 & x2)

# gráfico de la función objetivo
plotFun(fun.obj(x1,x2)~x1&x2,
        xlim=range(0,100),
        ylim=range(0,100),
        filled=FALSE)

# gráfico de la primera restricción
plotFun(rest.area(x1,x2)~x1&x2,
        levels=110,
        col = c("green","blue"),
        filled=FALSE,
        add=TRUE)

# gráfico de la segunda restricción
plotFun(rest.horas(x1,x2)~x1&x2,
        levels=720,
        filled=FALSE,
        add=TRUE)

# gráfico de la tercera restricción
plotFun(rest.cuota(x1,x2)~x1&x2,
        levels=80,
        filled=FALSE,
        add=TRUE)

Código para la resolución:

objetivo<-c(50, 80) # coeficientes de la función objetivo
mat.rest<-matrix(c(1,4,1,1,8,0), ncol=2) # matriz con los coeficientes de las restricciones
vec.rest<-c(110, 720, 80) # vector de restricciones
dir<-rep('<=',3) # vector de signos de las restricciones

resultado <- lp(direction = "max", # indica si se maximiza o minimiza la función objetivo
                objective.in = objetivo, # nombre del vector de coeficientes de la función objetivo
                const.mat = mat.rest, # nombre de la matriz de coeficientes de las restricciones
                const.dir = dir, # nombre del vector de signos de las restricciones
                const.rhs = vec.rest, # nombre del vector de restricciones
                all.int=FALSE, # indica si todas la variables deberían ser números enteros
                compute.sens = FALSE # indica si se debe hacer análisis de sensibilidad
                )
resultado
## Success: the objective function is 7600
resultado$solution
## [1] 40 70
# gráfico de la solución
plotFun(fun.obj(x1,x2)~x1&x2,
       levels = 7600,
       xlim=range(0,100),
       ylim=range(0,100),
       filled=FALSE,
       add = TRUE)

Solución:

Tanto la solución calculada como la solución gráfica muestran que se deben sembrar 40 Ha sin riego y 70 Ha con riego para tener un beneficio máximo de 7 600 unidades monetarias.

Análisis de sensibilidad

Para el análisis de sensibilidad simplemente se debe añadir la opción compute.sens = TRUE a la función lp():

resultado<-lp(direction = "max",
              objective.in = objetivo,
              const.mat = mat.rest,
              const.dir = dir,
              const.rhs = vec.rest,
              all.int=FALSE,
              compute.sens = TRUE # esta linea indica que se realice el análisis de sensibilidad
              )
resultado
## Success: the objective function is 7600
resultado$solution
## [1] 40 70

Como puede verse, la solución no ha cambiado: \(x_1= 40\) y \(x_2 = 70\)

resultado$sens.coef.from
## [1] 40 50
resultado$sens.coef.to
## [1]  80 100

Los valores dados por los comandos resultado2$sens.coef.from y resultado2$sens.coef.to indican los límites entre los que el valor resultante para cada variable puede variar sin que cambie la solución.

En el ejemplo, la variable “Hectáreas sin riego” (\(x_1\)) tiene un coeficiente objetivo (solución) de 40, un valor de límite inferior de 40 y un valor de límite superior de 80. Esto significa que mientras este coeficiente varíe entre 40 y 80, la solución no cambiará. Cuando el coeficiente objetivo de la variable “Ha sin riego” (\(x_1\)) esté por encima de 80, la solución cambiará. Por su lado, la variable “Ha con riego” (\(x_2\)) tiene un coeficiente objetivo (solución) de 70, un valor de límite inferior de 50 y un valor de límite superior de 100. Mientras este coeficiente varíe entre 50 y 100, la solución no cambiará.

Otro dato de información son los valores duales y sus límites inferior y superior, dados por los comandos resultado$duals, resultado$duals.from y resultado$duals.to, respectivamente. Estos valores se proporcionan tanto para las restricciones como para las variables (mostrando primero los valores para las restricciones). La información se interpreta de la misma manera tanto para restricciones como para variables.

resultado$duals
## [1] 20.0  7.5  0.0  0.0  0.0
resultado$duals.from
## [1]  9.0e+01  5.6e+02 -1.0e+30 -1.0e+30 -1.0e+30
resultado$duals.to
## [1] 1.3e+02 8.8e+02 1.0e+30 1.0e+30 1.0e+30

El valor dual especifica cuánto variará la función objetivo si el valor de la restricción o de la variable se incrementa en una unidad. El valor dual da una muy buena indicación de cuánto cuesta esta restricción o esta variable. Si el valor dual es muy alto, entonces esta restricción o variable es muy influyente en la función objetivo y si se puede cambiarla un poco, la solución será mucho mejor.

Para explicar el ejemplo es necesario tener siempre en mente los valores de la solución (\(x_1=40\) y \(x_2=70\)). El valor de la la primera restricción (Área) es 110 (\(x_1+x_2\)). Esta primera restricción (Área) tiene un valor dual de 20, con un límite inferior de 90 y un límite superior de 130. El peso de esta restricción (20), comparado con los de las otras restricciones, significa que esta restricción es la que más influye en la función objetivo. Específicamente, si la restricción se incrementa en una unidad (en este caso de 110 a 111), el valor de la solución se incrementará en 20, pero solamente entre los límites inferior y superior de 90 y 130. Fuera de estos límites, el valor dual cambiará.

El valor de la segunda restricción (Horas de trabajo) es 720 (\(4 x_1 + 8 x_2\)). Esta segunda restricción (Horas de trabajo) tiene un valor dual de 7.5 con un límite inferior de 560 y un límite superior de 880. El valor dual de esta restricción indica que es menos influyente que la primera. Además, si la restricción se incrementa en una unidad (en este caso de 720 a 721), el valor de la solución se incrementará en 7.5, y esto ocurrirá entre los límites de la restricción (560 y 880). Fuera de estos límites, el valor dual ya no será el mismo.

La tercera restricción y las variables tienen valores duales de cero (0), por lo que están inactivas. No tienen una rango en el que el cambio de valores mantenga la solución final.

El signo del valor dual también tiene un significado. Un valor positivo significa que a medida que la restricción o la variable se hace más grande, el valor de la función objetivo será más grande, y al hacerse más pequeño, el valor de la función objetivo será más pequeño. Si el valor dual es negativo, esta relación es inversa.