Programación Lineal con Python: Guía Básica

La programación lineal es una de las técnicas de optimización matemática más utilizadas en el mundo real. Desde la logística hasta las finanzas, pasando por la ingeniería y la ciencia de datos, este método nos permite encontrar la mejor solución posible cuando tenemos recursos limitados. En este artículo aprenderás los fundamentos de la programación lineal y cómo resolverla con Python usando las librerías SciPy y PuLP.

¿Qué es la Programación Lineal?

La programación lineal (PL) es una técnica matemática para optimizar (maximizar o minimizar) una función objetivo lineal, sujeta a un conjunto de restricciones lineales. El término "lineal" se refiere a que tanto la función objetivo como las restricciones son relaciones lineales entre las variables.

Fue desarrollada formalmente por George Dantzig en 1947, quien también inventó el método simplex, el algoritmo más famoso para resolver estos problemas. Hoy en día, la programación lineal es la base de disciplinas como la investigación de operaciones, la optimización convexa y el aprendizaje automático.

Tip: La programación lineal es la puerta de entrada al mundo de la optimización matemática. Una vez que domines este concepto, entender la programación entera, cuadrática y no lineal será mucho más sencillo.

Componentes de un Problema de Programación Lineal

Todo problema de programación lineal tiene tres componentes esenciales:

1. Variables de Decisión

Son las incógnitas que queremos determinar. Representan las decisiones que tomamos. Por ejemplo, ¿cuántas unidades del producto A y del producto B debo fabricar?

Las denotamos típicamente como $ x_1, x_2, \ldots, x_n $.

2. Función Objetivo

Es la función matemática que queremos optimizar (maximizar ganancias o minimizar costos). Tiene la forma:

\[ z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \]

Donde $ c_i $ son los coeficientes (utilidades o costos) de cada variable de decisión.

3. Restricciones

Son las limitaciones del problema, expresadas como desigualdades o igualdades lineales:

\[ a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \leq b_1 \] \[ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \leq b_2 \] \[ x_1, x_2, \ldots, x_n \geq 0 \quad \text{(restricciones de no negatividad)} \]

El conjunto de todos los puntos que satisfacen las restricciones se llama región factible o espacio factible. La solución óptima siempre se encuentra en uno de los vértices (puntos extremos) de esta región.

Un Ejemplo Clásico: El Problema de la Fábrica

Imaginemos una pequeña fábrica que produce dos tipos de muebles: sillas y mesas. Tenemos los siguientes datos:

Recurso	Silla (por unidad)	Mesa (por unidad)	Disponible
Madera (kg)	2	5	40 kg
Mano de obra (hrs)	3	2	30 hrs
Ganancia (MXN)	$300	$500	—

Objetivo: Maximizar la ganancia total.

Formulando matemáticamente, si $ x_1 $ = número de sillas y $ x_2 $ = número de mesas:

\[ \text{Maximizar:} \quad z = 300x_1 + 500x_2 \] \[ \text{Sujeto a:} \quad 2x_1 + 5x_2 \leq 40 \quad \text{(madera)} \] \[ 3x_1 + 2x_2 \leq 30 \quad \text{(mano de obra)} \] \[ x_1, x_2 \geq 0 \]

Resolviendo Programación Lineal con SciPy

Python ofrece SciPy como una de las librerías científicas más completas. La función linprog del módulo scipy.optimize resuelve problemas de programación lineal de forma eficiente.

Tip: scipy.optimize.linprog minimiza por defecto. Para maximizar una función, debes multiplicar los coeficientes de la función objetivo por -1.

Instalación (si no la tienes):

pip install scipy numpy

Ahora resolvamos nuestro problema de la fábrica:

import numpy as np
from scipy.optimize import linprog

# =============================================
# Problema: Maximizar z = 300*x1 + 500*x2
# Equivalente a: Minimizar z = -300*x1 - 500*x2
# =============================================

# Coeficientes de la funcion objetivo (negados para maximizar)
c = [-300, -500]

# Coeficientes de las restricciones (lado izquierdo)
# 2*x1 + 5*x2 <= 40  (madera)
# 3*x1 + 2*x2 <= 30  (mano de obra)
A_ub = [
    [2, 5],   # restriccion de madera
    [3, 2]    # restriccion de mano de obra
]

# Lado derecho de las restricciones
b_ub = [40, 30]

# Limites de las variables (x1 >= 0, x2 >= 0)
x1_bounds = (0, None)
x2_bounds = (0, None)

# Resolver el problema
resultado = linprog(
    c,
    A_ub=A_ub,
    b_ub=b_ub,
    bounds=[x1_bounds, x2_bounds],
    method='highs'  # Metodo HiGHS: el mas eficiente en SciPy moderno
)

# Mostrar resultados
if resultado.success:
    print(f"Estado: {resultado.message}")
    print(f"Sillas a producir (x1): {resultado.x[0]:.2f}")
    print(f"Mesas a producir  (x2): {resultado.x[1]:.2f}")
    print(f"Ganancia maxima:  ${-resultado.fun:,.2f} MXN")
else:
    print("No se encontro solucion:", resultado.message)

Salida esperada:

Estado: Optimization terminated successfully.
Sillas a producir (x1): 10.00
Mesas a producir  (x2):  4.00
Ganancia maxima:  $5,000.00 MXN

La solución óptima es producir 10 sillas y 4 mesas para obtener una ganancia máxima de $5,000 MXN.

Resolviendo con PuLP: Modelado más Legible

PuLP es una librería de Python diseñada específicamente para la programación lineal y entera. Su sintaxis es mucho más cercana a la notación matemática, lo que facilita la lectura y el mantenimiento del código.

pip install pulp

Resolvamos el mismo problema con PuLP:

import pulp

# Crear el problema de optimizacion
problema = pulp.LpProblem("Fabrica_de_Muebles", pulp.LpMaximize)

# Definir las variables de decision
x1 = pulp.LpVariable("Sillas", lowBound=0, cat='Continuous')
x2 = pulp.LpVariable("Mesas",  lowBound=0, cat='Continuous')

# Funcion objetivo (maximizar ganancia)
problema += 300 * x1 + 500 * x2, "Ganancia_Total"

# Restricciones
problema += 2 * x1 + 5 * x2 <= 40, "Restriccion_Madera"
problema += 3 * x1 + 2 * x2 <= 30, "Restriccion_Mano_de_Obra"

# Resolver
problema.solve(pulp.PULP_CBC_CMD(msg=0))

# Mostrar resultados
print(f"Estado: {pulp.LpStatus[problema.status]}")
print(f"Sillas a producir: {x1.value():.0f}")
print(f"Mesas a producir:  {x2.value():.0f}")
print(f"Ganancia maxima:   ${pulp.value(problema.objective):,.2f} MXN")

# Verificar uso de recursos
print("\n--- Uso de Recursos ---")
print(f"Madera usada:        {2*x1.value() + 5*x2.value():.0f} / 40 kg")
print(f"Mano de obra usada:  {3*x1.value() + 2*x2.value():.0f} / 30 hrs")

Salida:

Estado: Optimal
Sillas a producir: 10
Mesas a producir:   4
Ganancia maxima:   $5,000.00 MXN

--- Uso de Recursos ---
Madera usada:        40 / 40 kg
Mano de obra usada:  38 / 30 hrs

Tip: PuLP es ideal para comenzar porque su sintaxis es intuitiva. SciPy es mejor cuando ya tienes tus datos en matrices NumPy y necesitas integrarlo en un pipeline de ciencia de datos.

Visualizando el Espacio Factible

Una de las formas más efectivas de entender la programación lineal es visualizar la región factible y los vértices donde se evalúa la función objetivo.

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches

fig, ax = plt.subplots(figsize=(9, 7))

# Rango de x1
x1 = np.linspace(0, 20, 400)

# Graficar restricciones como lineas de frontera
# Restriccion 1: 2*x1 + 5*x2 = 40  =>  x2 = (40 - 2*x1) / 5
x2_madera = (40 - 2 * x1) / 5

# Restriccion 2: 3*x1 + 2*x2 = 30  =>  x2 = (30 - 3*x1) / 2
x2_trabajo = (30 - 3 * x1) / 2

ax.plot(x1, x2_madera,  'b-', linewidth=2, label='Madera: 2x₁ + 5x₂ ≤ 40')
ax.plot(x1, x2_trabajo, 'r-', linewidth=2, label='Trabajo: 3x₁ + 2x₂ ≤ 30')

# Sombrear la region factible
x2_factible = np.minimum(
    np.maximum(x2_madera, 0),
    np.maximum(x2_trabajo, 0)
)
ax.fill_between(
    x1,
    0,
    np.minimum(x2_madera, x2_trabajo),
    where=(np.minimum(x2_madera, x2_trabajo) >= 0),
    alpha=0.25,
    color='green',
    label='Region Factible'
)

# Vertices de la region factible
vertices = [(0, 0), (10, 0), (10, 4), (0, 8)]
for vx, vy in vertices:
    ax.plot(vx, vy, 'ko', markersize=8)
    ganancia = 300*vx + 500*vy
    ax.annotate(
        f'({vx}, {vy})\nz={ganancia:,}',
        (vx, vy),
        textcoords="offset points",
        xytext=(10, 5),
        fontsize=9,
        bbox=dict(boxstyle='round,pad=0.3', facecolor='yellow', alpha=0.7)
    )

# Punto optimo
ax.plot(10, 4, 'g*', markersize=18, zorder=5, label='Óptimo (10, 4): z=5,000')

ax.set_xlim(0, 18)
ax.set_ylim(0, 14)
ax.set_xlabel('Sillas (x₁)', fontsize=12)
ax.set_ylabel('Mesas (x₂)', fontsize=12)
ax.set_title('Programación Lineal: Espacio Factible y Solución Óptima', fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('espacio_factible.png', dpi=150)
plt.show()
print("Gráfica guardada como 'espacio_factible.png'")

La gráfica muestra claramente cómo la solución óptima se encuentra en uno de los vértices de la región factible. Este es el principio fundamental del método simplex: solo necesita evaluar los vértices, no todos los puntos posibles.

¿SciPy o PuLP? Comparativa Rápida

Característica	SciPy (linprog)	PuLP
Sintaxis	Matricial (NumPy)	Algebraica (más legible)
Velocidad	Alta (integrada con NumPy)	Buena (usa CBC por defecto)
Variables enteras (MIP)	No	Sí
Integración con datos	Excelente con DataFrames	Requiere conversión
Recomendado para	Pipelines de ciencia de datos	Modelado de negocio

Aplicaciones Reales de la Programación Lineal

La programación lineal no es solo teoría: se usa a diario en problemas del mundo real:

Logística y transporte: Optimizar rutas de distribución y minimizar costos de envío.
Planeación de producción: Determinar cuánto producir de cada producto para maximizar utilidades.
Dietas y nutrición: Diseñar planes alimenticios que cumplan requerimientos nutricionales al menor costo.
Finanzas: Asignar capital entre inversiones maximizando rendimiento con riesgo controlado.
Telecomunicaciones: Asignar ancho de banda a diferentes servicios de forma óptima.
Machine Learning: Las Máquinas de Vectores de Soporte (SVM) se formulan como problemas de programación cuadrática, una extensión directa de la PL.

Conclusión

La programación lineal con Python es una herramienta poderosa y accesible para cualquier programador o científico de datos. En este artículo aprendiste:

Los fundamentos matemáticos de la programación lineal: función objetivo, variables de decisión y restricciones.
Cómo formular un problema de optimización lineal de forma matemática.
Cómo resolver problemas de programación lineal con SciPy usando linprog.
Cómo usar PuLP para un modelado más legible y expresivo.
Cómo visualizar el espacio factible y entender por qué la solución óptima está en los vértices.

En los próximos artículos de esta serie exploraremos temas intermedios como la programación entera mixta (MIP), el análisis de sensibilidad y el uso de solvers comerciales como Gurobi y CPLEX desde Python. Si este artículo te resultó útil, compártelo con tu comunidad y déjanos tus preguntas en los comentarios.

Programación Lineal con Python: Guía Básica de Teoría y Práctica

¿Qué es la Programación Lineal?

Componentes de un Problema de Programación Lineal

1. Variables de Decisión

2. Función Objetivo

3. Restricciones

Un Ejemplo Clásico: El Problema de la Fábrica

Resolviendo Programación Lineal con SciPy

Resolviendo con PuLP: Modelado más Legible

Visualizando el Espacio Factible

¿SciPy o PuLP? Comparativa Rápida

Aplicaciones Reales de la Programación Lineal

Conclusión

Tags

Artículos Relacionados

Programación Lineal Avanzada con Python: Branch & Bound, …

Programación Lineal Intermedia con Python: MIP, Transporte y …

Grafos Dirigidos y No Dirigidos: Una Visión Matemática …

Cómo Funciona Stable Diffusion: Guía Completa de Generación …

Tags