Las cajas van enteras o se dejan
La programación entera es programación lineal en la que las variables deben ser números enteros, como cajas, personas o furgonetas. Es más difícil, porque redondear la solución de un programa lineal puede dar un plan peor o imposible.
Una furgoneta de reparto carga 10 kg y hay tres cajas con pedidos. Cada caja se lleva entera o se deja.
Al final de esta lección
Nota
Puedo decir por qué los problemas con números enteros son más difíciles.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Programación entera | programación lineal con variables que deben ser enteras | |
| Problema de la mochila | elegir objetos que caben en una carga para ganar lo máximo | |
| Variable binaria | una variable que vale 0 o 1 | llevar o no una caja |
| Relajación lineal | el mismo problema permitiendo fracciones | |
| Programación dinámica | resolver guardando las respuestas de problemas más pequeños |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
En la mochila solo cabe lo que cabe
En el problema de la mochila eliges objetos para llenar una carga limitada y ganar lo máximo. Aquí la carga es la furgoneta, de 10 kg.
Cada caja es una variable binaria: vale 1 si se lleva y 0 si se deja. No existe media caja.
Ejemplo resuelto: las tres cajas
| Caja | Peso (kg) | Valor del pedido (€) |
|---|---|---|
| A | 6 | 30 |
| B | 5 | 22 |
| C | 5 | 21 |
| Furgoneta | 10 como máximo |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Con fracciones, el problema es fácil de resolver
Si se permiten fracciones de caja, linprog lo resuelve. Cada variable puede valer de 0 a 1. Esto se llama relajación lineal: quitar la regla de los enteros.
El resultado lleva la caja A entera y 0,8 de la caja B. Gana 47,6 €, pero eso no se puede cargar.
Resuelve la mochila permitiendo fracciones
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-30, -22, -21], A_ub=[[6, 5, 5]], b_ub=[10], bounds=(0, 1)); print(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.
Redondear la solución con fracciones no sirve
Tienes 0,8 de la caja B. Si lo redondeas hacia arriba llevas la caja B entera, y A más B pesan 11 kg: no caben. Si lo redondeas hacia abajo llevas solo la A y ganas 30 €.
El mejor plan entero es otro: dejar la A y llevar la B y la C. Pesan 10 kg y valen 43 €.
Prueba las ocho combinaciones de cajas
docker exec jupyter python3 -c "import itertools; v = [30, 22, 21]; w = [6, 5, 5]; print(max((sum(a * b for a, b in zip(v, p)), p) for p in itertools.product([0, 1], repeat=3) if sum(a * b for a, b in zip(w, p)) <= 10))"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 basta con resolver con fracciones y redondear. Redondear hacia arriba puede pasarse del límite, y hacia abajo puede perder mucho. Aquí queda en 30 € un plan que puede llegar a 43 €.
Con muchas cajas hay demasiadas combinaciones
Cada caja se lleva o se deja: dos opciones. Con n cajas hay 2 elevado a n combinaciones, y esa cifra se duplica con cada caja nueva.
Con 10 cajas son 1.024. Con 20 son más de un millón y con 30 son más de mil millones. Probarlas todas deja de ser razonable.
Combinaciones posibles con 10, 20 y 30 cajas
docker exec jupyter python3 -c "print(2 ** 10, 2 ** 20, 2 ** 30)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
La programación dinámica evita repetir cuentas
Hay un camino mejor. Guarda una lista best donde best[c] es el mejor valor con c kilos de carga. Añade las cajas de una en una.
Para cada caja, mira cada capacidad de mayor a menor: ¿sale mejor llevar la caja o dejarla? El tamaño del trabajo es cajas por kilos, no dos elevado a las cajas.
Ejemplo resuelto: la lista best para cada caja
| Paso | 0 kg | 5 kg | 6 kg | 10 kg |
|---|---|---|---|---|
| Al empezar | 0 | 0 | 0 | 0 |
| Con la caja A | 0 | 0 | 30 | 30 |
| Con A y B | 0 | 22 | 30 | 30 |
| Con A, B y C | 0 | 22 | 30 | 43 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Rellena la lista best con tres cajas
weights = [6, 5, 5]
values = [30, 22, 21]
capacity = 10
best = [0] * (capacity + 1) # best[c]: el mejor valor con c kilos de carga
for item in range(len(weights)):
# De mayor a menor, para no usar la misma caja dos veces
for c in range(capacity, weights[item] - 1, -1):
with_item = best[c - weights[item]] + values[item]
if with_item > best[c]:
best[c] = with_item
print("Tras la caja", item, best)
print("Mejor valor:", best[capacity])
# Cambia la capacidad a 11: ¿qué cajas caben y cuánto vale?
Un solucionador entero hace el trabajo difícil
Los problemas enteros más grandes se dejan a un solucionador. SciPy trae milp, que resuelve programas lineales con variables enteras.
Un solucionador suele resolver relajaciones lineales una y otra vez, descartando las ramas que no pueden ganar. Aun así, hay problemas enteros que tardan mucho.
Resuelve la mochila con enteros en SciPy
docker exec jupyter python3 -c "from scipy.optimize import milp, LinearConstraint, Bounds; r = milp([-30, -22, -21], constraints=LinearConstraint([[6, 5, 5]], ub=10), integrality=[1, 1, 1], bounds=Bounds(0, 1)); print(round(-r.fun, 2), [round(v) 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.
Para ir más lejos: la carga que sobra
Con capacidad 10, ¿qué peso sobra con las cajas B y C? Prueba capacidades de 0 a 16 en el código y anota el valor de best[capacidad] en cada una. ¿En qué capacidades sube el valor de golpe?