Mini tutoriel pour la résolution de programmes linéaires avec Python - ENS Rennes 2021

Références si vous êtes curieux-ses

Un très bon tutoriel :

Documentation de scipy.optimize :

D'autres tutoriels :

Table of Contents

Pré-requis pour exécuter ce notebook


Quelques petits problèmes linéaires

Premier problème linéaire

Il vient du tutoriel susmentionné :

On utilise les fonctionnalités de scipy pour les problèmes linéaires (doc), et pour commencer la seule fonction scipy.optimize.linprog :

Et voilà, pas plus compliqué !

Vous pourrez observer que le résultat de l'appel à cette fonction (si tout marche bien) est un objet qui encapsule plusieurs choses :

Problème exemple du cours sur le simplexe

Attention, généralement les solveurs cherchent à minimiser la fonction de coût, pas à la maximiser !

C'est un piège classique, on rentre le problème, le solveur répond [0,0,..,0] comme solution, et on ne sait pas ce qui n'a pas marché...

On trouve donc la solution commerciale optimale pour Charlie le chocolatier : 300 pyramides, et 100 pyramides de luxe.

Exercice 1 : sur ce problème, cherchez quelles contraintes (inégalités) sont saturées (devenues des égalités)

Indice : lire le tableau result.slack et l'interpréter.

Exercice 2 : résoudre un autre problème vu en cours

Bonus : réfléchir à une situation de votre vie personnelle qui pourrait être mis en forme comme un problème linéaire

Un exemple que j'ai beaucoup est le suivant, qui généralise l'idée de « régime diététique optimal » : https://jeremykun.com/2014/06/02/linear-programming-and-the-most-affordable-healthy-diet-part-1/ (très bon blogue à suivre si ça vous plaît).

Comparer différentes méthodes :

Comme le dit la documentation :

The linprog function supports the following methods:

linprog(method=’simplex’)
linprog(method=’interior-point’)
linprog(method=’revised simplex’)
linprog(method=’highs-ipm’)
linprog(method=’highs-ds’)
linprog(method=’highs’)

Certaines méthodes peuvent ne pas être disponible sur votre installation, mais normalement "simplex" et "interior-point" sont disponibles partout.

Exercice 3 : sur un problème de votre choix, testez au moins deux méthodes.

Ce petit morceau de code peut vous aider :

Exercice 4 : Chercher un problème qui donne une réponse différente sur deux méthodes différentes.

Avec le code ci-dessous, cherchez un problème plus compliqué qui donne une solution différente. Même si la différence est faible, commentez là :


Conclusion

Si vous êtes très curieux, regardez un peu les références données en haut de ce document.

N'hésitez pas à nous contacter si vous avez des questions !