Problemas de programación lineal con Python

En algún momento de tu vida, ¿has llegado a verte en la obligación de tomar decisiones difíciles donde debes conseguir el mejor resultado, pero teniendo recursos limitados? Creo que la mayoría de las personas llegamos a estar en esa situación por lo menos un par de veces en nuestras vidas. Ya sea que tengamos que planificar horarios, optimizar presupuestos o maximizar los beneficios de un negocio, aprender qué son los problemas de programación lineal puede ayudarnos a encontrar la solución más eficiente.

En este artículo, voy a explicarte de manera bastante sencilla en qué consisten estos problemas, cuáles son sus componentes principales y cómo puedes resolverlos paso a paso utilizando Python. 

¿Qué son los problemas de programación lineal?

Los problemas de programación lineal son un tipo de problema matemático en el que debes maximizar o minimizar una función objetivo, como las ganancias o costos de un negocio, obedeciendo a un conjunto de restricciones lineales. Estas restricciones son inequaciones o ecuaciones que describen las limitaciones del problema, como los presupuestos, el tiempo o los recursos.

Para entenderlo mejor, supongamos que tienes una panadería y quieres producir panes y tartas con el objetivo de maximizar las ganancias, pero estás limitado por la cantidad de harina y azúcar que tienes. En esencia, esto es un problema clásico de programación lineal.

Elementos clave de los problemas de programación lineal

Para entender cuáles son los principales componentes de un problema de programación lineal, tomemos el siguiente ejemplo. Tienes un taller de carpintería donde fabricas mesas y sillas, así que tus ganancias están limitadas a la cantidad de materiales disponibles. En este caso:

• La función objetivo sería calcular las ganancias totales.
• Las restricciones representarían la cantidad de madera y el tiempo disponible.

Resolver este problema implica encontrar la combinación exacta de mesas y sillas que maximice las ganancias, sin exceder los recursos que dispones. Ahora sí, veamos los componentes del problema:

Función objetivo

Representa lo que queremos optimizar. Por ejemplo:

Z= 50x + 40y

Aquí, X y Y son las cantidades de mesas y sillas que puedes producir, mientras que los coeficientes 50 y 40 representan las ganancias respectivas.

Restricciones

Son las limitaciones del problema, expresadas en forma de inequaciones lineales. Por ejemplo: 

2x+y ≤100 (madera disponible)

x+y ≤ 70 (horas de trabajo)

Restricciones de no negatividad

Por practicidad, las cantidades no pueden ser negativas, pues de lo contrario no serían posibles en el mundo real. No puedes hacer una mesa si no tienes madera, ¿verdad?

x ≥ 0, y ≥ 0

¿Cómo resolver problemas de programación lineal en Python?

Resolver estos problemas manualmente puede ser bastante complejo. Afortunadamente, la tecnología ha avanzado para solucionarnos la vida, y hacerlo con herramientas como Python es mucho más sencillo. A continuación, te mostraré dos métodos: PuLP y SciPy.

Instalar las bibliotecas necesarias

Antes de comenzar, debes instalar las bibliotecas que usaremos:

pip install pulp scipy

Resolver un problema de programación lineal con PuLP

Supongamos que queremos maximizar la función objetivo:

Z=50x+40y

Con las siguientes restricciones:

• 2x+y ≤ 100 (madera disponible)
• x+y ≤ 70x (horas disponibles)
• x,y ≥ 0

Este sería el código que tendríamos que utilizar:

from pulp import LpMaximize, LpProblem, LpVariable

# Crear el problema de optimización
problema = LpProblem(name="problema-lineal", sense=LpMaximize)

# Definir las variables de decisión
x = LpVariable(name="x", lowBound=0)
y = LpVariable(name="y", lowBound=0)

# Definir la función objetivo
problema += 50 * x + 40 * y, "Ganancia total"

# Añadir las restricciones
problema += (2 * x + y <= 100, "Restricción de madera")
problema += (x + y <= 70, "Restricción de horas")

# Resolver el problema
status = problema.solve()

# Imprimir los resultados
print(f"Estado del problema: {problema.status}")
print(f"x (mesas) = {x.varValue}")
print(f"y (sillas) = {y.varValue}")
print(f"Ganancia máxima: {problema.objective.value()}")

En este caso, los resultados esperados serían: 

• x=30 (mesas)
• y=40y (sillas)
• Ganancia máxima: 3000

Resolver un problema de programación lineal con SciPy

SciPy utiliza un enfoque basado en matrices, lo que resulta ideal para resolver problemas más grandes. Recuerda que esta librería minimiza la función objetivo, así que debes invertir los signos de los coeficientes.

Este sería el código:

from scipy.optimize import linprog

# Coeficientes de la función objetivo (negativos para maximizar)
c = [-50, -40]

# Coeficientes de las restricciones
A = [[2, 1], [1, 1]]
b = [100, 70]

# Límites de las variables
bounds = [(0, None), (0, None)]

# Resolver el problema
resultado = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method="highs")

# Imprimir los resultados
if resultado.success:
    print(f"x (mesas) = {resultado.x[0]:.2f}")
    print(f"y (sillas) = {resultado.x[1]:.2f}")
    print(f"Ganancia máxima: {-resultado.fun:.2f}")
else:
    print("No se encontró solución.")

Los resultados que esperaríamos son los siguientes:

• x=30 (mesas)
• y=40 (sillas)
• Ganancia máxima: 3000

Ventajas de resolver problemas de programación lineal con Python

Sin duda alguna, utilizar Python para resolver problemas de programación lineal es una ayuda enorme. En primer lugar, por su rapidez, ya que puedes resolver problemas en cuestión de segundos. Luego, tenemos su escalabilidad, ya que funciona perfectamente para modelos con muchas variables y restricciones. Por último, tenemos una gran flexibilidad, pues es adaptable a una amplia variedad de escenarios.

¿Tú qué piensas? Vale la pena aprender a usar Python para resolver estos problemas, ¿no? Si la respuesta ha sido positiva y quieres aprender a programar desde cero, quiero decirte que este es el momento perfecto. En KeepCoding, hemos diseñado nuestro Bootcamp Aprende a Programar desde Cero para que, en tan solo 4 meses, puedas aprender sobre los mejores lenguajes de programación para el desarrollo Mobile, Web, Big Data, Videojuegos e IA. Encuentra aquí todo lo que necesitas para empezar tu carrera como programador profesional en uno de los sectores con mejores salarios y oportunidades laborales.

¡No aplaces más la oportunidad de empezar una nueva vida!