Resolver un programa lineal con SciPy
La función linprog de SciPy resuelve un programa lineal sin dibujar nada. SciPy es una biblioteca de Python con herramientas de cálculo científico.
Con dos variables basta mirar esquinas. Con diez o con mil variables ya no se puede, y ahí linprog trabaja por ti.
Al final de esta lección
Nota
Puedo resolver un programa lineal con SciPy y leer su respuesta.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| SciPy | una biblioteca de Python para cálculo científico | |
| linprog | la función de SciPy que resuelve programas lineales | |
| A_ub | la tabla con un límite en cada fila | [[2, 3], [4, 2]] |
| b_ub | la lista con lo que hay de cada límite | [24, 32] |
| Estado | un número que dice si se encontró solución |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
linprog siempre minimiza
La función linprog busca el valor más pequeño de la función objetivo. Pero la panadería quiere el beneficio más grande.
El truco es cambiar el signo. Buscar el beneficio más grande es lo mismo que buscar el más pequeño de menos el beneficio. Das [-50, -60] como objetivo y, al final, cambias otra vez el signo del resultado.
Una llamada a linprog para la panadería
from scipy.optimize import linprog
limits = [[2, 3], [4, 2]] # una fila por límite: horno y harina
available = [24, 32] # lo que hay de cada uno
# linprog minimiza, así que damos el beneficio con el signo cambiado
result = linprog([-50, -60], A_ub=limits, b_ub=available)
print(result.status, round(-result.fun, 2), [round(v, 2) for v in result.x])
Cambia el signo del beneficio con un bucle
profits = [50, 60]
objective = [0, 0]
for i in range(len(profits)):
# Cambiar el signo convierte "el más grande" en "el más pequeño"
objective[i] = -profits[i]
print(objective)
# Cambia el beneficio de la tarta a 90 y vuelve a ejecutar.
Cada fila de A_ub es un límite
linprog recibe los límites en dos piezas. A_ub es una tabla con una fila por límite y una columna por variable. b_ub es la lista de lo que hay de cada límite.
Todo límite se escribe con «menor o igual». Si necesitas «mayor o igual», cambia todos los signos: x + y >= 1 se escribe como -x - y <= -1. Las variables ya valen 0 o más sin que lo pidas.
Ejemplo resuelto: del modelo a la llamada
| Pieza del modelo | En linprog | En la panadería |
|---|---|---|
| Objetivo, con el signo cambiado | el primer argumento | [-50, -60] |
| Los límites, uno por fila | A_ub | [[2, 3], [4, 2]] |
| Lo que hay de cada límite | b_ub | [24, 32] |
| Cantidades de 0 o más | no hace falta escribirlas | ya valen por defecto |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Resuelve la panadería con linprog
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-50, -60], A_ub=[[2, 3], [4, 2]], b_ub=[24, 32]); print(r.status, round(-r.fun, 2), [round(v, 2) for v in r.x])"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
El estado dice si hay solución
Antes de fiarte de un resultado, mira result.status. El valor 0 significa que linprog encontró el mejor plan.
El valor 2 significa que no hay ningún plan factible, porque los límites se contradicen. El valor 3 significa que no hay un mejor plan, porque el beneficio puede crecer sin fin.
Dos límites que se contradicen
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-50, -60], A_ub=[[1, 1], [-1, -1]], b_ub=[2, -5]); print(r.status, r.success)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un límite que no frena el beneficio
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-50, -60], A_ub=[[-1, -1]], b_ub=[-1]); print(r.status, r.success)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error muy común
Advertencia
Mucha gente cree que linprog maximiza si le das el beneficio. No lo hace: siempre minimiza. Con [50, 60] te devolvería el plan de no hacer nada, que cuesta 0 y es el menor valor posible.
Para ir más lejos: mínimo contra máximo
Escribe en una hoja un problema de coste mínimo, como mezclar dos piensos para alimentar animales al menor precio. ¿Hace falta cambiar el signo del objetivo? ¿Cómo escribirías el límite «al menos 20 kg de proteína» para linprog?