Práctica 6: PROGRAMACIÓN LINEAL CON R

1. Introducción

Un problema de programación lineal (PPL) es una situación compleja en la que el responsable debe tomar decisiones del tipo:

• elegir cantidades de producción para maximizar beneficios,
• decidir la ruta de un viaje para minimizar costes,
• determinar un reparto de tareas para minimizar el tiempo de finalización,
• etc.

de modo que se cumpla con ciertas limitaciones, como:

• no superar la materia prima, el personal y el almacenaje disponibles,
• pasar necesariamente por una serie de puntos comprometidos,
• no exceder la capacidad de los encargados,
• etc.

y de manera que, tanto la función objetivo (a maximizar o minimizar), como las limitaciones se pueden escribir como ecuaciones lineales en las variables de decisión.

Una forma estándar en la que todo PPL puede escribirse es:

\[ \begin{array}{rrrrrrrrc} \text{max } z = &c_1 x_1 & + & c_2 x_2 & + & \cdots & + & c_n x_n & &\\ \text{s.a:} & & & & & & & & & \\ &a_{11} x_1 & + &a_{12} x_2 & + &\cdots & + &a_{1n} x_n & = &b_1 \\ &a_{21} x_1 & + & a_{22} x_2 & + & \cdots & + & a_{2n} x_n & = & b_2 \\ & \vdots & \vdots &\vdots & \vdots &\ddots & \vdots &\vdots & \vdots &\vdots \\ &a_{m1} x_1 & +& a_{m2} x_2 & + &\cdots & +& a_{mn} x_n & =& b_m \\ & x_1, & & x_2, & & \ldots, & & x_n & \geq & 0 \end{array} \]

donde:

• \(c_1, c_2, \ldots, c_n \in \mathbb{R}\) son constantes conocidas (llamadas “costes” de cada variable)
• \(b_1, b_2, \ldots, b_m \in [0,+\infty)\) son constantes conocidas (llamadas “topes” de las restricciones, o right-hand-side)
• \(a_{11}, a_{12}, \ldots, a_{mn} \in \mathbb{R}\) son constantes conocidas (y forman la matriz tecnológica, o de restricciones)
• “s.a:” es una abreviatura de “sujeto a:” (para indicar las restricciones del problema)

La resolución “manual” de un PPL pasa por:

• Modelizarlo (a partir de una descripción verbal del problema):
  • Identificando las variables de decisión,
  • Escribiendo la función objetivo,
  • Escribiendo las restricciones.
• Pasarlo a forma estándar:
  • Transformando las variables no restringidas (si las hay) como resta de dos no negativas,
  • Transformando las inecuaciones (si las hay) en ecuaciones:
    • Sumando variables de holgura,
    • Restando variables de exceso,
    • Cambiando signo de toda la ecuación si el término independiente \(b_j\) es negativo
• Aplicar el algoritmo SIMPLEX:
  • Añadir variables artificiales (si hace falta) para obtener la tabla simplex inicial (con una primera solución básica factible).
  • Aplicar sucesivamente el algoritmo hasta su detención.

2. El algoritmo SIMPLEX

Se llama región factible al conjunto de valores de todas las variables de decisión que cumplen las restricciones del PPL. Se denota con la letra \(F\)

• Si \(F\) es vacío, el PPL no tiene solución y se dice que es infactible.
• Si \(F\) no es vacío, sus elementos son candidatos a solución del problema, y se llaman soluciones factibles.
  • \(F\) es cerrado, y por eso:
    • Si \(F\) es acotado, entonces es seguro que la función objetivo alcanza su óptimo en un punto de \(F\).
    • Si \(F\) no es acotado, es posible que el óptimo sea \(+\infty\) (en ese caso sería un problema no acotado).
  • \(F\) es convexo, y por eso:
    • Tiene unos puntos especiales, llamados puntos extremos.
    • Si \(F\) es acotado, los puntos no extremos de \(F\) siempre se pueden ubicar “entre unos cuantos de los puntos extremos”.
    • Si se alcanza el óptimo en un punto de \(F\), es seguro que hay un punto extremo de \(F\) que también alcanza el óptimo.

El algoritmo Simplex (George B. Dantzig, 1947) se basa en esto último. Mediante sencillas operaciones:

1. Sale de un punto extremo de \(F\) (tabla simplex inicial).
2. Desde un punto extremo de \(F\) puede chequear si la función objetivo mejora en puntos extremos adyacentes, y se puede pasar a cualquiera de ellos (actualizar tabla simplex).
3. Se detiene si mingún punto extemo adyacente mejora la función objetivo, dando la solución óptima (o indicando la no existencia de solución).

Existen muchas implementaciones del algoritmo simplex, y algunos permiten tratar el PPL sin estar en forma estándar, lo cual quita trabajo al usuario.

Este algoritmo no está exento de inestabilidad numérica, ya que se calculan divisiones con valores que pueden ser muy pequeños en el denominador.

3. Función simplex() del package boot

Sirve para problemas de tamaño no muy grande (leer Nota en la ayuda help(simplex)). Instalar y cargar package previamente.

• Función: simplex(a, A1, b1, A2, b2, A3, b3, maxi, n.iter, eps)
• Argumentos:
  • a: vector de coeficientes de la función objetivo
  • A1: matriz de coeficientes de las restricciones de tipo \(\leq\) (sólo la parte de coeficientes)
  • b1: vector de términos independientes de las restricciones de tipo \(\leq\) (correspondientes a la matriz A1)
  • A2: idem con restricciones de tipo \(\geq\)
  • 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 (por defecto es FALSE)
  • 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 otras):
  • $soln: solución óptima, si se alcanza. Vector con los valores de las variables
  • $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
  • $val.aux: valor de las variables artificiales en el óptimo
  • etc.

4 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.

• Función: lp (direction, objective.in, const.mat, const.dir, const.rhs, int.vec, binary.vec)
• Argumentos:
  • direction: por defecto vale 'min'. Cambiar a '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"<=", "==" o ">=") indicando la dirección de cada restricción dada por las filas de la matriz const.mat
  • const.rhs: vector de términos independientes de las restricciones
  • int.vec: vector indicando la posición de las variables que deben ser de valores enteros
  • binary.vec: Vector indicando la posición de las variables que deben ser de valores binarios (0 o 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, si se alcanza. Vector con los valores de las variables
  • $status: indicador numérico:
    • 0: éxito
    • 2: no hay solución factible

4. Ejercicios evaluables

4.1. Un PPL queda modelizado como:

\[ \begin{array}{rl} \text{max} &x_1 + 5x_2 - x_3 \\ \text{s.a} & \\ & x_1 + x_2 + x_3 \geq 100 \\ & 5x_1 - x_2 + 8x_3 \leq 500 \\ & - x_1 + x_2 + 2x_3 = 0 \\ & 2x_1 + x_2 + 12x_3 \leq 800 \\ & x_1, x_2, x_3 \geq 0 \end{array} \] 4.1.1 Resuelve el PPL con las dos funciones de R: escribe el valor óptimo de la función objetivo y los valores de las variables de decisión que consiguen ese óptimo.

library(boot)
library(lpSolve)
# AQUÍ TU CÓDIGO

ESCRIBE LA SOLUCIÓN (VARIABLES Y SUS VALORES) Y EL VALOR ÓPTIMO ENCONTRADO, O BIEN SI NO SE ENCUENTRA, COMENTAR LO QUE HA PASADO

4.1.2 Resuelve el PPL con las dos funciones de R, SI EL OBJETIVO FUERA MINIMIZAR LA FUNCIÓN OBJETIVO (valga la redundancia)

# AQUÍ TU CÓDIGO

ESCRIBE LA SOLUCIÓN (VARIABLES Y SUS VALORES) Y EL VALOR ÓPTIMO ENCONTRADO, O BIEN SI NO SE ENCUENTRA, COMENTAR LO QUE HA PASADO

4.1.3 Resuelve (como sea posible) el PPL DE MINIMIZAR, SUPONIENDO ADEMÁS QUE LAS VARIABLES \(x_1\) Y \(x_2\) REPRESENTAN NÚMEROS DE PERSONAS, Y NO PUEDEN TOMAR VALORES NO ENTEROS.

# AQUÍ TU CÓDIGO

ESCRIBE LA SOLUCIÓN (VARIABLES Y SUS VALORES) Y EL VALOR ÓPTIMO ENCONTRADO, O BIEN SI NO SE ENCUENTRA, COMENTAR LO QUE HA PASADO

4.2. Un PPL queda modelizado como:

\[ \begin{array}{rl} \text{min} &15 x + 10y\\ \text{s.a} & \\ & y \leq 50 \\ & 1.5 x - y \geq 20 \\ & x_1, x_2 \geq 0 \end{array} \]

4.2.1 Resuelve el PPL con las dos funciones de R el PPL: escribe el valor óptimo de la función objetivo y los valores de las variables de decisión que consiguen ese óptimo.

# AQUÍ TU CÓDIGO

ESCRIBE LA SOLUCIÓN (VARIABLES Y SUS VALORES) Y EL VALOR ÓPTIMO ENCONTRADO, O BIEN SI NO SE ENCUENTRA, COMENTAR LO QUE HA PASADO

4.2.2 Resuelve el PPL con las dos funciones de R, SI EL OBJETIVO FUERA MAXIMIZAR LA FUNCIÓN OBJETIVO (valga la redundancia)

# AQUÍ TU CÓDIGO

ESCRIBE LA SOLUCIÓN (VARIABLES Y SUS VALORES) Y EL VALOR ÓPTIMO ENCONTRADO, O BIEN SI NO SE ENCUENTRA, COMENTAR LO QUE HA PASADO

4.2.3 Como se trata de tan solo dos variables, representa gráficamente la región factible y la curva de nivel \(z=0\) y comenta los resultados obtenidos en 4.2.1 y 4.2.2.

Ayuda: la función abline(a,b,h,v) añade rectas a un plot, que se pueden indicar con término independiente y pendiente (a, b) o bien con la ordenada en el origen, si es horizontal (h) o bien con la abcisa, si es vertical (v).

# AQUÍ TU CÓDIGO
plot(x=0, y=0, xlim=c(0,100), ylim=c(0,100))

# LA RECTA x=0
# LA RECTA y=0
# LA RECTA y=50
# LA RECTA 1.5x-y=20
# LA CURVA DE NIVEL z=0 PARA z=15x+10y

COMENTARIO DE LOS RESULTADOS DE 4.2.1 Y 4.2.2 A PARTIR DE LA FIGURA.