Comment trouver le meilleur plan sans tout essayer ?
Un programme linéaire est un problème où l’objectif et toutes les contraintes sont des sommes de variables multipliées par des nombres. À deux variables, on peut le résoudre en regardant les coins de la région des plans possibles.
Cette méthode graphique évite d’essayer une infinité de plans. Vous saurez trouver le meilleur plan de la boulangerie en quatre calculs.
À la fin de cette leçon
Remarque
Je peux résoudre un problème à deux variables en comparant le gain à chaque sommet.
Mots clés
| Mot | Ce que ça veut dire |
|---|---|
| Programme linéaire | un problème dont l’objectif et les contraintes sont de la forme a x + b y |
| Région réalisable | l’ensemble de tous les plans qui respectent les contraintes |
| Sommet | un coin de la région, où deux limites se croisent |
| Plan optimal | le plan réalisable qui rapporte le plus |
| Droite de contrainte | les points où une limite est atteinte exactement |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La région réalisable est l’ensemble des plans possibles
Chaque contrainte coupe l’ensemble des plans en deux : d’un côté de sa droite, les plans permis, de l’autre, les plans interdits. La région réalisable est ce qui reste après toutes les coupes.
Pour la boulangerie, c’est un quadrilatère. Ses quatre coins sont (0, 0), (5, 0), (4, 2) et (0, 4).
Exemple travaillé : d’où vient chaque sommet
| Sommet | Les deux limites qui se croisent | Gain 40 x + 50 y |
|---|---|---|
| (0, 0) | x = 0 et y = 0 | 0 |
| (5, 0) | farine 2 x + y = 10 et y = 0 | 200 |
| (4, 2) | farine 2 x + y = 10 et temps x + 2 y = 8 | 260 |
| (0, 4) | temps x + 2 y = 8 et x = 0 | 200 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Trouver où deux droites se croisent
docker exec jupyter python3 -c "import numpy as np; print(np.linalg.solve([[2, 1], [1, 2]], [10, 8]))"Affiché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.
Un sommet est la solution de deux équations
La commande résout deux équations à deux inconnues : 2 x + y = 10 et x + 2 y = 8. Elle affiche le point où les deux limites sont atteintes en même temps.
Elle affiche [4. 2.], soit x = 4 et y = 2. C’est le sommet du milieu du tableau, celui où la farine et le temps sont tous deux épuisés.
Le meilleur plan est toujours un sommet
Le gain 40 x + 50 y varie de façon régulière : quand on avance dans une direction, il monte ou descend sans jamais faire de creux. Il ne peut donc pas avoir son maximum au milieu de la région.
Le maximum est à un sommet. Il suffit de calculer le gain aux sommets et de garder le plus grand.
Comparer les sommets avec Python
# Le gain aux quatre sommets de la boulangerie.
sommets = [[0, 0], [5, 0], [4, 2], [0, 4]]
meilleur = sommets[0]
meilleur_gain = 40 * meilleur[0] + 50 * meilleur[1]
for s in sommets:
g = 40 * s[0] + 50 * s[1]
print("sommet", s, "gain", g)
if g > meilleur_gain:
meilleur = s
meilleur_gain = g
print("meilleur sommet", meilleur)
Afficher le gain à chaque sommet
docker exec jupyter python3 -c "[print(p, 40 * p[0] + 50 * p[1]) for p in [(0, 0), (5, 0), (4, 2), (0, 4)]]"Affiché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.
Une erreur fréquente
Attention
Beaucoup pensent que le meilleur plan est au milieu de la région, pour « équilibrer ». Prenez le plan (2, 2) : il rapporte 180 euros. Le gain suit une droite, donc il augmente jusqu’au bord, et le meilleur plan est un sommet.
Pour aller plus loin
Dans votre carnet, changez le gain du pain de 40 à 90 euros. Recalculez le gain aux quatre sommets et dites quel sommet gagne maintenant.
Dites ce que cela signifie pour la boulangerie : à partir de quel gain le pain prend-il la première place ?