Deja que un solucionador haga la búsqueda
Un carpintero puede fabricar mesas y sillas, pero la madera y las horas se acaban. ¿Qué combinación gana más? Podrías probar planes toda una tarde. O puedes escribir los límites y dejar que un solucionador encuentre el mejor plan, o demuestre que no hay ninguno.
Al terminar esta lección
Nota
Puedo ejecutar un modelo de optimización y leer su estado, su plan y sus precios sombra.
Palabras clave
- Modelo: los límites y el objetivo, escritos.
- Solucionador: un programa que encuentra la mejor respuesta a un modelo.
- Holgura: lo que sobra de un límite.
- Precio sombra: lo que vale una unidad más de un límite.
- Entero: un número sin fracciones.
Para empezar: lo que ya sabes
Nota
Responde mentalmente. 1. ¿Qué es una variable? 2. ¿Qué significa maximizar algo? 3. ¿Se pueden fabricar 2,5 sillas? Necesitarás la tercera respuesta enseguida.
Antes de empezar
Nota
Pulsa Iniciar el laboratorio en la barra de arriba de esta lección. Este laboratorio es una máquina Ubuntu entera para ti, así que tarda un poco más en arrancar que un contenedor, e instala sus solucionadores la primera vez. Cada botón Ejecutar escribe su comando en el terminal de la máquina, uno tras otro, en la misma sesión. Si alguno dice que la máquina aún está arrancando, espera unos segundos y púlsalo de nuevo. Para verlos, o para escribir los tuyos, pulsa Abrir el terminal en la barra.
Un modelo es un objetivo y unos límites
Tus archivos están en la carpeta optimisation. El primer comando entra en ella. lp.py es un modelo escrito con PuLP: mesas y sillas, un beneficio que maximizar y límites de madera, horas y almacén. opt ejecuta un archivo de Python con los solucionadores preparados. La primera línea dice Optimal, que significa que el solucionador terminó y que la respuesta es fiable. El plan es 20 mesas y 60 sillas, con un beneficio de 2800.
cd optimisationSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
opt lp.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Comprueba
Consejo
¿Qué límite tiene holgura y cuál es su precio sombra? Respuesta: el almacén tiene 60 de sobra, así que una unidad más de almacén no vale nada. La madera y las horas están agotadas, y sus precios sombra son 20 y 10: un tablón más de madera añade 20 al beneficio.
Un error frecuente
Advertencia
Mucha gente cree que un límite agotado es siempre el culpable de un beneficio bajo. No es así. Lee el precio sombra: un límite agotado con un precio de 20 compensa ampliarlo, y un límite con holgura no vale nada más, aunque sea grande.
Los números enteros necesitan otro solucionador
integer.py elige proyectos, y un proyecto se hace entero o no se hace. Resuelve el modelo dos veces. Con fracciones permitidas el valor es 45,17 y el plan hace 0,67 de un proyecto. Redondear ese plan a proyectos enteros cuesta 22 con un presupuesto de 19, así que no es un plan. Pedir solo proyectos enteros da un valor de 42, con tres proyectos: bridge, garden y theatre.
opt integer.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Comprueba
Consejo
¿Por qué la respuesta con fracciones vale más que la de números enteros? Respuesta: tiene menos reglas. Permitir partes de un proyecto solo puede ayudar, así que es un tope para la respuesta entera.
Un solucionador de restricciones hace un cuadrante de turnos
shifts.py usa OR-Tools CP-SAT. Tres enfermeras se reparten tres turnos al día durante cuatro días, y cada una tiene deseos de no trabajar algunos turnos. Nadie trabaja una noche y luego la mañana siguiente. El solucionador dice OPTIMAL y que hay que incumplir un deseo, porque dos enfermeras no pueden evitar los mismos turnos el primer día. Se imprime el cuadrante de cada día.
opt shifts.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Comprobación final
Consejo
Responde sin mirar atrás. 1. ¿Qué hace un solucionador? 2. ¿Qué te dice un estado Optimal? 3. ¿Qué es un precio sombra? 4. ¿Por qué no se puede redondear un plan fraccionario? Respuestas: encuentra la mejor respuesta a un modelo; que el solucionador terminó y que la respuesta es la mejor; lo que vale una unidad más de un límite; el plan redondeado puede incumplir un límite. Abre ahora el README.md de tu carpeta personal con cat ~/README.md: escribes dos modelos.
Para el profesorado
Consejo
Esta lección se da en un laboratorio VM: cada alumno tiene su propia máquina Ubuntu con PuLP, CBC y OR-Tools instalados, y un botón Ejecutar escribe en su terminal y muestra lo que se imprimió. Puntos clave: 1. Un modelo es un objetivo y unos límites, y un solucionador encuentra la mejor respuesta. 2. Lee el estado antes que los números. 3. La holgura y el precio sombra dicen qué límites importan. 4. Los enteros necesitan un solucionador entero, y redondear puede incumplir un límite. Error frecuente: culpar a cualquier límite agotado sin leer su precio. Material: el laboratorio y un navegador. Consejo: antes del segundo comando, pide a la clase que redondee ella misma 0,67 de un proyecto. El propio laboratorio tiene una comprobación que califica dos modelos con instancias ocultas. El módulo de investigación operativa resuelve sus problemas con SciPy; este laboratorio es donde una clase conoce PuLP y OR-Tools.