El mejor plan está en una esquina
La programación lineal busca el mejor valor de una cuenta cuando todos los límites son rectas. Con dos variables, el mejor plan está siempre en una esquina de la zona de planes posibles, así que basta mirar unas pocas esquinas.
La panadería de la lección anterior puede elegir entre infinitos planes, porque admite medias tandas. Aquí reducirás la búsqueda a cuatro planes.
Al final de esta lección
Nota
Puedo resolver un problema de dos variables mirando sus esquinas.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Programa lineal | un problema con objetivo y límites en línea recta |
| Región factible | todos los planes que cumplen los límites |
| Esquina | un punto donde se cruzan dos límites |
| Recta de límite | los puntos donde un límite se gasta justo |
| Óptimo | el mejor plan factible |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La región factible reúne los planes posibles
Dibuja x en horizontal e y en vertical. Cada restricción es una línea recta que corta el dibujo en dos: de un lado se cumple el límite y del otro no.
La región factible es la zona donde se cumplen todos los límites a la vez. Cada punto de esa zona es un plan que se puede hacer.
Ejemplo resuelto: dónde corta cada recta los ejes
| Límite | Recta | Corta el eje x en | Corta el eje y en |
|---|---|---|---|
| Horno | 2 * x + 3 * y = 24 | x = 12 | y = 8 |
| Harina | 4 * x + 2 * y = 32 | x = 8 | y = 16 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
El mejor plan siempre está en una esquina
Imagina que recorres un lado de la región en línea recta. El beneficio sube o baja siempre al mismo ritmo y nunca sube para luego bajar. Por eso el mejor punto de un lado está en uno de sus extremos, y los extremos son esquinas.
Así no hace falta probar infinitos planes: solo las esquinas.
Ejemplo resuelto: el beneficio de cada esquina
| Esquina (x, y) | Cómo sale | Beneficio (€) |
|---|---|---|
| (0, 0) | no se hace nada | 0 |
| (8, 0) | solo pan, hasta agotar la harina | 400 |
| (6, 4) | se cruzan el horno y la harina | 540 |
| (0, 8) | solo tartas, hasta agotar el horno | 480 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Elige la esquina de mayor beneficio
corners = [[0, 0], [8, 0], [6, 4], [0, 8]]
best = corners[0]
for corner in corners:
# El beneficio de una esquina: 50 por tanda de pan y 60 por tanda de tarta
if 50 * corner[0] + 60 * corner[1] > 50 * best[0] + 60 * best[1]:
best = corner
print("Mejor esquina:", best, "beneficio:", 50 * best[0] + 60 * best[1])
# Cambia el 60 por un 90 en las dos cuentas: ¿qué esquina gana ahora?
Cada cruce de rectas es una esquina posible
Para encontrar las esquinas, cruza cada pareja de rectas, ejes incluidos. Después comprueba cada cruce en todos los límites.
Con el horno, la harina y los dos ejes salen seis cruces. Solo cuatro cumplen todos los límites y son esquinas de la región.
Ejemplo resuelto: los seis cruces
| Cruce (x, y) | Horno usado | Harina usada | ¿Factible? |
|---|---|---|---|
| (0, 0) | 0 de 24 | 0 de 32 | Sí |
| (12, 0) | 24 de 24 | 48 de 32 | No |
| (8, 0) | 16 de 24 | 32 de 32 | Sí |
| (0, 16) | 48 de 24 | 32 de 32 | No |
| (0, 8) | 24 de 24 | 16 de 32 | Sí |
| (6, 4) | 24 de 24 | 32 de 32 | Sí |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Comprueba los seis cruces contra los dos límites
docker exec jupyter python3 -c "for p in [(0, 0), (12, 0), (8, 0), (0, 16), (0, 8), (6, 4)]: print(p, 2 * p[0] + 3 * p[1] <= 24 and 4 * p[0] + 2 * p[1] <= 32)"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 todo cruce de dos rectas es una esquina de la región. Dos rectas siempre se cruzan, pero el cruce puede romper otro límite. El punto (12, 0) agota el horno y necesita 48 kg de harina. Comprueba cada cruce contra todos los límites.
Para ir más lejos: un tercer límite
Añade un límite nuevo: el mostrador solo admite 10 tandas en total, es decir x + y <= 10. Cruza esa recta con las otras y con los ejes. ¿Cambia alguna esquina? ¿Cambia el mejor plan?