Comment résoudre un programme linéaire avec Python ?
SciPy est une bibliothèque Python de calcul scientifique, et sa fonction linprog résout un programme linéaire à n’importe quel nombre de variables. Vous lui donnez le modèle, elle rend le meilleur plan.
C’est la méthode de tous les jours dès que le dessin n’est plus possible. Vous saurez écrire l’appel et lire son résultat.
À la fin de cette leçon
Remarque
Je peux résoudre un programme linéaire avec linprog et lire son résultat.
Mots clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| linprog | la fonction de SciPy qui résout un programme linéaire | |
| Minimiser | chercher la plus petite valeur de l’objectif | |
| Statut | le code qui dit si le problème a été résolu | 0 |
| Problème non borné | un problème où l’objectif peut grandir sans fin | |
| Problème impossible | un problème dont aucun plan ne respecte les contraintes |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un appel à linprog donne trois choses
On donne à linprog les gains de l’objectif, une ligne par contrainte et les limites. Les variables sont déjà supposées positives ou nulles.
Attention : linprog minimise toujours. Pour maximiser un gain, on change son signe : 40 x + 50 y devient -40 x - 50 y. À la fin, on remet le signe.
Un appel complet à linprog
from scipy.optimize import linprog
# linprog minimise : pour maximiser le gain, on change les signes.
gains = [-40, -50]
# Une ligne par contrainte : farine, puis temps.
limites = [[2, 1], [1, 2]]
disponible = [10, 8]
res = linprog(gains, A_ub=limites, b_ub=disponible)
print(res.x) # le plan : les valeurs de x et de y
print(-res.fun) # le gain, avec son vrai signe
Résoudre la boulangerie avec SciPy
docker exec jupyter python3 -c "from scipy.optimize import linprog; res = linprog([-40, -50], A_ub=[[2, 1], [1, 2]], b_ub=[10, 8]); print(res.status, res.success); print([round(v, 2) for v in res.x]); print(round(-res.fun, 2))"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.
Lire le résultat de linprog
La commande affiche trois lignes. La première est le statut : 0 veut dire résolu, et True confirme le succès.
La deuxième est le plan, [4.0, 2.0] : quatre fournées de pain et deux de brioches. La troisième est le gain, 260 euros, le même que par les sommets.
Oublier le signe donne un plan absurde
Si l’on donne 40 et 50 au lieu de -40 et -50, linprog cherche le gain le plus petit. Le plus petit gain possible est zéro, en ne cuisant rien.
La commande suivante donne ce piège : le plan est [0.0, 0.0] et le gain 0. Rien ne signale l’erreur, il faut la reconnaître.
Voir ce que donne l’oubli du signe
docker exec jupyter python3 -c "from scipy.optimize import linprog; res = linprog([40, 50], A_ub=[[2, 1], [1, 2]], b_ub=[10, 8]); print([round(v, 2) for v in res.x], round(res.fun, 2))"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.
Le statut dit si un plan existe
Un problème n’a pas toujours un meilleur plan. Si on peut grandir sans fin, il est non borné : le statut vaut 3. Si aucun plan ne respecte les limites, il est impossible : le statut vaut 2.
Lisez toujours le statut avant le plan.
Un problème où le gain ne s’arrête pas
docker exec jupyter python3 -c "from scipy.optimize import linprog; res = linprog([-1, -1], A_ub=[[1, -1]], b_ub=[1]); print(res.status)"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 linprog maximise, parce que c’est ce que l’on veut. Il minimise toujours. Pour un gain, changez le signe des coefficients, puis changez le signe du résultat.
Pour aller plus loin
Dans votre carnet, changez la farine disponible de 10 à 20 kg et relancez l’appel. Lisez le plan et le gain.
Dites ce qui change et ce qui ne change pas : quelle contrainte limite désormais la boulangerie ?