Laisser un solveur chercher à ta place
Un menuisier peut fabriquer des tables et des chaises, mais le bois et les heures s’épuisent. Quel assortiment rapporte le plus ? On pourrait essayer des plans tout un après-midi. Ou bien on écrit les limites et on laisse un solveur trouver le meilleur plan, ou prouver qu’il n’y en a pas.
À la fin de cette leçon
Remarque
Je peux lancer un modèle d’optimisation et lire son statut, son plan et ses prix fantômes.
Mots-clés
- Modèle : les limites et l’objectif, écrits.
- Solveur : un programme qui trouve la meilleure réponse à un modèle.
- Marge : ce qui reste d’une limite.
- Prix fantôme : ce que vaut une unité de plus d’une limite.
- Entier : un nombre sans fraction.
Pour commencer : ce que tu sais déjà
Remarque
Réponds dans ta tête. 1. Qu’est-ce qu’une variable ? 2. Que veut dire maximiser quelque chose ? 3. Peut-on fabriquer 2,5 chaises ? Tu as besoin de la troisième réponse dans un instant.
Avant de commencer
Remarque
Appuie sur Démarrer le lab dans la barre en haut de cette leçon. Ce lab est une machine Ubuntu entière, rien que pour toi : elle met un peu plus de temps à démarrer qu’un conteneur, et elle installe ses solveurs la première fois. Chaque bouton Exécuter tape sa commande dans le terminal de la machine, l’une après l’autre, dans la même session. Si l’un d’eux dit que la machine démarre encore, attends quelques secondes et appuie de nouveau. Pour les regarder, ou pour taper les tiens, appuie sur Ouvrir le terminal dans la barre.
Un modèle, c’est un objectif et des limites
Tes fichiers sont dans le dossier optimisation. La première commande y entre. lp.py est un modèle écrit avec PuLP : des tables et des chaises, un gain à maximiser, et des limites de bois, d’heures et de stockage. opt lance un fichier Python avec les solveurs prêts. La première ligne dit Optimal, ce qui veut dire que le solveur a fini et que la réponse est fiable. Le plan est 20 tables et 60 chaises, pour un gain de 2800.
cd optimisationAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
opt lp.pyAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Vérifie
Astuce
Quelle limite a de la marge, et quel est son prix fantôme ? Réponse : le stockage a 60 de reste, donc une unité de stockage de plus ne vaut rien. Le bois et les heures sont épuisés, et leurs prix fantômes sont 20 et 10 : une planche de plus ajoute 20 au gain.
Une erreur fréquente
Attention
Beaucoup pensent qu’une limite épuisée est toujours celle qu’il faut accuser d’un gain faible. Ce n’est pas le cas. Lis le prix fantôme : une limite épuisée dont le prix est 20 vaut la peine d’être augmentée, et une limite qui a de la marge ne vaut rien de plus, même si elle est grande.
Les nombres entiers demandent un autre solveur
integer.py choisit des projets, et un projet se fait en entier ou pas du tout. Il résout le modèle deux fois. Avec des fractions permises, la valeur est 45,17 et le plan réalise 0,67 d’un projet. Arrondir ce plan à des projets entiers coûte 22 pour un budget de 19 : ce n’est pas un plan. En demandant des projets entiers seulement, on obtient une valeur de 42, avec trois projets : bridge, garden et theatre.
opt integer.pyAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Vérifie
Astuce
Pourquoi la réponse avec fractions vaut-elle plus que celle en nombres entiers ? Réponse : elle a moins de règles. Permettre des parties de projet ne peut qu’aider : c’est donc une limite supérieure de la réponse en nombres entiers.
Un solveur de contraintes construit un planning
shifts.py utilise OR-Tools CP-SAT. Trois infirmières se partagent trois services par jour pendant quatre jours, et chacune a des souhaits de ne pas travailler certains services. Personne ne travaille une nuit puis le matin suivant. Le solveur répond OPTIMAL et dit qu’un souhait doit être rompu, parce que deux infirmières ne peuvent pas éviter les mêmes services le premier jour. Un planning s’affiche pour chaque jour.
opt shifts.pyAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Vérification finale
Astuce
Réponds sans revenir en arrière. 1. Que fait un solveur ? 2. Que t’apprend un statut Optimal ? 3. Qu’est-ce qu’un prix fantôme ? 4. Pourquoi ne peut-on pas arrondir un plan fractionnaire ? Réponses : il trouve la meilleure réponse à un modèle ; que le solveur a fini et que la réponse est la meilleure ; ce que vaut une unité de plus d’une limite ; le plan arrondi peut enfreindre une limite. Ouvre maintenant le README.md de ton dossier personnel avec cat ~/README.md : tu écris deux modèles.
Pour les enseignants
Astuce
Cette leçon se déroule dans un lab VM : chaque élève a sa propre machine Ubuntu avec PuLP, CBC et OR-Tools installés, et un bouton Exécuter tape dans son terminal et montre ce qui s’est affiché. Points clés : 1. Un modèle est un objectif et des limites, et un solveur trouve la meilleure réponse. 2. Lire le statut avant les nombres. 3. La marge et le prix fantôme disent quelles limites comptent. 4. Les nombres entiers demandent un solveur entier, et arrondir peut enfreindre une limite. Erreur fréquente : accuser n’importe quelle limite épuisée sans lire son prix. Matériel : le lab et un navigateur. Conseil : avant la deuxième commande, demandez à la classe d’arrondir elle-même 0,67 d’un projet. Le lab lui-même a une vérification qui note deux modèles sur des instances cachées. Le module de recherche opérationnelle résout ses problèmes avec SciPy ; ce lab est l’endroit où une classe rencontre PuLP et OR-Tools.