Programación Lineal y Método Simplex: Teoría y práctica

¿Qué es la Programación Lineal?

El concepto de Programación Lineal u Optimización Lineal hace referencia a aquella rama de las matemáticas que se dedica a optimizar (maximizar o minimizar) una función objetivo lineal sujeta a unas restricciones en forma de ecuaciones y/o inecuaciones.

Aunque se trate de una rama avanzada de las matemáticas, su uso es ampliamente extendido en la vida cotidiana. Por ejemplo, en la gestión de la compra del mes al intentar gastar el mínimo dinero posible cumpliendo una serie de requisitos.

En este post, definiremos las nociones básicas de la Programación Lineal y los diferentes tipos existentes. Además, introduciremos el método Simplex, un algoritmo muy utilizado para resolver problemas de optimización lineal.

Fundamentos básicos de la Programación Lineal

Como bien indica en su nombre, en la programación lineal las funciones y las restricciones son lineales. Por tanto, función objetivo es una función de n variables lineal y las restricciones deben ser ecuaciones o inecuaciones lineales.

Definición del problema de optimización

Una definición general de un problema de optimización de programación lineal es la siguiente:

¿Cuál es la solución que realmente queremos obtener? La solución es un vector n dimensional en el que se cumplen todas las restricciones del problema y optimice la función objetivo. Pueden existir muchos vectores que cumplan las restricciones, los cuales se denominan solución factible. Veamos un ejemplo para poder ilustrar de forma más clara los dos conceptos:

La región de las soluciones factibles en este caso sería:

{${(x,y)R²:5 x-2y<=6, x-3y>=-5, 2x+9y=12, (x,y)>=(0,0)}$}.

Como vemos, las restricciones que aparecen pueden ser de tipo desigualdad y de igualdad. No obstante, para emplear el algoritmo Simplex, necesitamos que las restricciones sean todas de igualdad (aunque la implementación que veremos después es flexible y no exige tal condición). Además de que se cumplan otras condiciones que mencionaremos en breve.

Problema estándar de optimización de Programación Lineal

Para ello, vamos a introducir otra forma de expresar un problema de optimización y es la Forma estándar de un Problema de Optimización de Programación Lineal:

El objetivo es poder transformar cualquier tipo de problema de optimización a su forma estándar. Para ello necesitamos una manera de realizar esta transformación y la metodología que permite esto consiste en los siguientes pasos:

1. Si el problema es de maximizar la función objetivo 𝑐̄x̄, debemos cambiar a minimizar -𝑐̄x̄.
2. Si existe algún término independiente de las restricciones de igualdad negativo, cambiamos el signo a toda la restricción.
3. Las restricciones de desigualdad pueden convertirse en restricciones de igualdad introduciendo las denominadas variables de holgura:
   • Si tenemos a_i1x₁ +...+ a_inx_n <= b_i, podemos transformarla utilizando una variable x_hi >= 0 así: a_i1x₁ +...+ a_inx_n + x_hi = b_i.
   • Si tenemos a_i1x₁ +...+ a_inx_n >= b_i, podemos transformarla utilizando una variable x_hi >=0 así: a_i1x₁ +...+ a_inx_n - x_hi = b_i.
4. Si alguna variable de decisión x_i no cumple con la condición de no negatividad no se cumple, entonces la sustituimos por 2 nuevas variables y_i, z_i tal que x_i = y_i + z_i.

Veamos un ejemplo de cómo pasar un problema de optimización a su forma estándar:

Fundamentos del Método o Algoritmo Simplex

En este caso, consideraremos solamente los problemas en su forma estándar para el método Simplex. Para ello, hay un concepto importante que es el de solución factible básica.

Qué es la Solución Factible Básica

Consideremos un problema de optimización en su forma estándar. Vamos a fijar algunos conceptos que son necesarios para definir una solución factible básica, siendo A la matriz de coeficientes de las restricciones de igualdad de dimensión mxn:

1. Matriz Básica. Una submatriz B cuadrada (mismo número de filas y columnas) no singular (existe su inversa) de A de dimensión m, se denomina matriz básica. Además, B es una matriz básica factible si B^-1b̅ >=0.
2. Llamaremos N a la submatriz de A con dimensión mx(n-m), que tiene como columnas las de A que no están en B.
3. Sea ^x̄_B el vector de variables de decisión asociadas a las columnas de la matriz A necesarias para construir B. Se denominan variables básicas.
4. Sea ^x̄_N el vector de variables de decisión asociadas a las columnas de la matriz A necesarias para construir N. Se denominan variables no básicas.
5. Si exigimos que ^x̄_N = 0̄, tendríamos:

Ax̄ = b̅$⟹$Bx̄_B + Nx̄_N = b̅ $⟹$Bx̄_B + N0̄ = b̅ $⟹$Bx̄_B = b̅ $⟹$x̄_B = B^-1b̅

Teniendo en cuenta lo expuesto, la solución x̄ = (B^-1b̅, 0̄) del sistema de ecuaciones Ax̄ = b̅ se le denomina solución factible básica si B^-1b̅ >= 0.

Procedimiento del Método o Algoritmo Simplex

Primero, procedemos a fijar la notación necesaria para explicar el procedimiento.

• Sea B una submatriz cuadrada no singular de dimensión m de A. Entonces, denotaremos por I y J los conjuntos con los índices asociados a las columnas de B y N, respectivamente.
• Sea $j∈j$ y ā_j la columna j-ésima de A, denotamos el vector B^-1ā_j por ȳ_j.
• Sea $j∈j$ y 𝑐̄_B es el vector formado por los coeficientes de la función objetivo asociados a las columnas de la submatriz B, denotamos por z_j el valor 𝑐̄_Bȳ_j = 𝑐̄_BB^-1ā_j.

El método Simplex se dedica a buscar todas las soluciones factibles básicas una a una y verificar si son óptimas o no. Lo hace de forma iterativa hasta encontrar la solución factible básica óptima o hasta verificar que el problema no tiene solución. 

Supongamos que x̄_B es una solución factible básica, entonces se realizan los siguientes pasos:

1. Si existe $j∈j$ tal que z_j - c_j > 0 e ȳ_j < = 0̄, entonces el problema de optimización en su forma estándar no admite solución óptima.
2. Si z_j - c_j <= 0, ∀j ∈ J, entonces x̄ = (B^-1b̅, 0̄) es una solución factible óptima ↔ z_j - c_j <= 0, ∀j ∈ J. Si se cumple que max{z_j - c_j: j ∈ J} = 0 , entonces el problema es factible pero la solución óptima no es única.
3. Si el Simplex no ha podido determinar ninguna decisión, se calcula una nueva solución factible básica y se vuelven a aplicar los pasos anteriores.

Método Simplex en Python con SciPy

Una vez que hemos explicado los entresijos del método Simplex, veamos cómo emplearlo en Python. El módulo optimize de la librería SciPy contiene un método llamado linprog() para resolver problemas de optimización de programación lineal (visita la documentación oficial para más información). Cabe recordar que este método no nos exige que todas las restricciones sean de igualdad, también incluye la opción de incorporar restricciones de menor o igual.

Consideremos el siguiente problema de optimización:

En total hay 6 restricciones (2 de cada tipo) y 4 variables de decisión, resultando su resolución a mano un proceso muy costoso. La implementación en Python es la siguiente:

from scipy.optimize import linprog
import numpy as np

A_ub = np.array([[7, -23, 5, 9], [-5, 3, 1, 0], [-4, 8, -12, -4], [-3, -2, -9, -10], 
     [-1, 0, 0, 0], [0, -1, 0, 0], [0, 0, -1, 0], [0, 0, 0, -1]])
A_eq = np.array([[-16, 28, 5, 8], [0, -5, 3, 2]])
b_ub = np.array([56, 7, -1, -6, 0, 0, 0, 0])
b_eq = np.array([5, 8])
c = np.array([-4, 9, -1, 3])

linprog(c=c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, method="simplex")

El resultado que obtenemos es:

       con: array([ 5.68434189e-13, -2.84217094e-14])
       fun: -60.305084745761874
message: 'Optimization terminated successfully.'
       nit: 9
    slack: array([5.68434189e-13, 2.19237288e+02, 7.02389831e+02,           
               7.75508475e+02, 7.26101695e+01, 3.17457627e+01,   
               5.55762712e+01, 0.00000000e+00])
    status: 0
    success: True
          x: array([72.61016949, 31.74576271, 55.57627119,  0.        ])

El método ha finalizado con éxito en su búsqueda de la solución factible óptima en 9 iteraciones. La solución óptima que obtenemos es x̄ = (72.61, 31.75, 55.58, 0.0) y el valor mínimo de la función objetivo  es -60.31.

Hasta aquí nuestro post de hoy. Si te ha parecido interesante, te animamos a visitar la categoría Algoritmos para ver todos los posts relacionados y a compartirlo en redes con tus contactos. ¡Hasta pronto!