#!/usr/bin/env python # coding: utf-8 # # 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 : # # - https://realpython.com/linear-programming-python/ # # Documentation de `scipy.optimize` : # # - https://docs.scipy.org/doc/scipy/reference/optimize.html # # D'autres tutoriels : # - https://scipy-lectures.org/advanced/mathematical_optimization/index.html # - https://medium.com/better-programming/how-to-solving-linear-programming-problems-with-examples-and-implementation-in-python-a7b7061bafc9 # - http://stackoverflow.com/questions/10697995/ddg#10705799 # - Auteur : [Lilian Besson](https://perso.crans.org/besson/) # - License : [MIT](https://lbesson.mit-license.org/) # - Date : 27/01/2021 # - Cours : [ALGO2](http://people.irisa.fr/Francois.Schwarzentruber/algo2/) @ [ENS Rennes](http://www.dit.ens-rennes.fr/) #

Table of Contents

#
# ## Pré-requis pour exécuter ce notebook # # - Soit vous le téléchargez et vous l'utilisez localement, dans ce cas il faut que vous ayez installé le module `scipy`. # + Utilisez votre gestionnaire de paquet système (`apt-get` par exemple) si Python installé par ce gestionnaire ; # + Utilisez `pip install scipy` ou pip3, ou avec `sudo pip` (Linux/Mac) ou pip.exe (Windows) si modules Python gérés avec [pip](https://pypi.org/) (recommandé) ; # + Utilisez `conda install scipy` si modules Python gérés avec conda (si installé avec [Anaconda](https://www.anaconda.com/products/individual). # # - Soit vous utilisez le lien fourni dans Discord pour exécuter ce notebook dans un environnement en ligne, avec [MyBinder](https://mybinder.org/) (gratuit libre et sans connexion). # In[21]: try: import scipy.optimize except ImportError: print("Vous avez lu le paragraphe précédent...?") print("Je t'envoie sur https://scipy.org/install.html et tu auras plus d'informations...") import webbrowser webbrowser.open_new_tab("https://scipy.org/install.html") # ---- # # Quelques petits problèmes linéaires # ## Premier problème linéaire # # Il vient du tutoriel [susmentionné](https://medium.com/better-programming/how-to-solving-linear-programming-problems-with-examples-and-implementation-in-python-a7b7061bafc9) : # In[44]: # Objective Function: 50x_1 + 80x_2 # Constraint 1: 5x_1 + 2x_2 <= 20 # Constraint 2: -10x_1 + -12x_2 <= -90 result = scipy.optimize.linprog( [50, 80], # Cost function: 50x_1 + 80x_2 A_ub=[[5, 2], [-10, -12]], # Coefficients for inequalities b_ub=[20, -90], # Constraints for inequalities: 20 and -90 bounds=(0, None), # Bounds on x, 0 <= x_i <= +oo by default ) # On utilise les fonctionnalités de scipy pour les problèmes linéaires ([doc](https://docs.scipy.org/doc/scipy/reference/optimize.html#linear-programming)), et pour commencer [la seule fonction `scipy.optimize.linprog`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html#scipy.optimize.linprog) : # In[45]: if result.success: print(f"X1: {round(result.x[0], 2)} hours") print(f"X2: {round(result.x[1], 2)} hours") else: print("No solution") # 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 : # # - la valeur de la solution, `result.x` ; # - le nombre d'itérations, `result.nit` ; # - l'état des slacks variables (cf cours sur le simplexe), `result.slack` ; # - évaluation de l'état de l'optimisation, `result.success`, et `result.message` ; # - et même la valeur de la fonction objectif à ce point solution (c'est utile pour gagner du temps, si cette fonction objectif est très couteuse, par exemple quand on apprend un gros réseau de neurone, avec d'autres solveurs). # In[26]: print(result) # ## 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é... # In[54]: # Objective Function: x_1 + 6*x_2 + 13*x_3 # Constraint 1: x_1 <= 200 # Constraint 2: x_2 <= 300 # Constraint 3: x_1 + x_2 + x_3 <= 400 # Constraint 4: x_2 + 3*x_3 <= 600 # les variables sont supposées positives par défaut # x_1 >= 0 # x_2 >= 0 # x_3 >= 0 result = scipy.optimize.linprog( [-1, -6, -13], # Cost function: -x_1 + -6*x_2 + -13*x_3 to MINIMIZE A_ub=[ # Coefficients for inequalities [1, 0, 0], # for C1: 1*x_1 + 0*x_2 + 0*x_3 <= 200 [0, 1, 0], # for C2: 0*x_1 + 1*x_2 + 0*x_3 <= 300 [1, 1, 1], # for C3: 1*x_1 + 1*x_2 + 1*x_3 <= 400 [0, 1, 3], # for C4: 0*x_1 + 1*x_2 + 3*x_3 <= 600 ], b_ub=[200, 300, 400, 600], # Constraints for inequalities: 200, 300, 400, 600 bounds=(0, None), # Bounds on x, 0 <= x_i <= +oo by default method="simplex", ) # In[55]: print(result) # In[56]: if result.success: print(f"X1: {round(result.x[0], 2)} chocolats simples") print(f"X2: {round(result.x[1], 2)} pyramides") print(f"X2: {round(result.x[2], 2)} pyramides de luxe") else: print("No solution") # 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. # In[ ]: # TODO print(result) print("Variables slack:") print(result.slack) # ### **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 : # In[33]: methods = [ "simplex", "interior-point", #"revised-simplex", #"highs-ipm", #"highs-ds", #"highs", ] # In[34]: def solve_problem_1(method): return scipy.optimize.linprog( [50, 80], # Cost function: 50x_1 + 80x_2 A_ub=[[5, 2], [-10, -12]], # Coefficients for inequalities b_ub=[20, -90], # Constraints for inequalities: 20 and -90 method=method ) # In[35]: for i, method in enumerate(methods): # solve problem with this method print(f"\n- Pour la méthode #{i}, {method}...") solution = solve_problem_1(method) print(f"La solution trouvée est {solution}") # ### **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à : # # - en terme de nombre d'étape ? # - valeurs de x* ? # - valeur de f(x*) ? # --- # ## 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 !