Quel est le moyen le plus simple d’apprendre la programmation linéaire?

La programmation linéaire n’est PAS un type de langage de programmation, ni même quelque chose que vous faites avec votre ordinateur. C’est une technique mathématique permettant de résoudre certains types de problèmes, comme le fait de rechercher des dérivées ou de transformer une matrice, entre autres types de techniques.

C’est ce qu’on appelle un “programme” parce que le concept a été inventé pendant la Seconde Guerre mondiale où les “programmes” n’étaient que des algorithmes permettant de résoudre des problèmes, et dans ce cas, le problème est un problème d’optimisation. Un programme linéaire comporte trois composantes principales: les variables, les contraintes et les objectifs (un seul objectif, généralement).

Je vais vous donner un exemple de programme linéaire, volé de mes notes de cours au collège. Il y a 168 heures dans une semaine de 7 jours. Je suis au collège et j’ai donc besoin d’étudier, de faire la fête et de manger (je vais à Carnegie Mellon, alors ce n’est pas comme si je dormais). Je veux manger 3 repas par jour (1 heure chacun) par jour, et je ne veux absolument pas étudier plus de 14 heures par jour (mais rien de moins que cela est tout à fait raisonnable). Si je n’étudie pas au moins 10 heures par jour, j’échouerai probablement dans mes cours (sérieusement, vous ne comprenez pas à quoi ressemble cette école!) Et mon temps est uniquement consacré à ces trois choses. Disons aussi que si je fais la fête, je dois étudier encore plus pour le rattraper (l’exemple sur lequel je base ceci utilise 2S + E-3P> = 150, c’est-à-dire, si je ne fais jamais la fête, alors ce n’est jamais un problème, mais si je fais la fête, la différence pondérée entre le temps que je consacre à étudier / manger et le temps que je consacre à faire la fête doit être assez importante).

Donc, 3 variables: S, P, E.

Nombreuses contraintes: S + P + E = 168, E> = 21, S> = 70, S = 150, P> = 0

Pouvez-vous me donner des valeurs pour S, P et E telles que toutes les contraintes soient valides? Je suis sûr que vous pouvez, il y a beaucoup de réponses. Mais quelle est la “meilleure” réponse?

Nous ferons de la troisième composante du programme linéaire notre * objectif *. Quel devrait être notre objectif? J’ai 21 ans, mon objectif sera donc de MAXIMISER la valeur de P. C’est-à-dire que je suis intéressé à connaître toutes les assignations valides de S, P et E, lesquelles ont la plus grande valeur de P sans aller sur mes règles.

Et c’est à peu près tout. Programmation linéaire en un mot. Cela n’a absolument rien à voir avec la programmation fonctionnelle, la programmation orientée objet, la programmation Web, etc. C’est juste un problème d’optimisation mathématique.

Si vous voulez * utiliser * des programmes linéaires pour résoudre des problèmes, j’ai entendu dire qu’Excel peut les résoudre (oui, Microsoft Excel, le tableur), mais je sais que vous pouvez également les utiliser dans Mathematica, Maple, MATLAB et SAS. L’avantage de le faire dans Mathematica est que vous pouvez probablement le saisir dans Wolfram Alpha et le résoudre dans votre navigateur.

Ce livre est idéal pour apprendre la programmation linéaire: Introduction à l’optimisation linéaire

Les cinq premiers chapitres développent de manière rigoureuse la géométrie et l’algèbre de la programmation linéaire, et les derniers chapitres appliquent LP aux problèmes de flux de réseau et aux problèmes de programmation d’entiers.

À mon avis, la seule faiblesse du texte est le manque de discussion sur les techniques de pointe et les progiciels utilisés dans la pratique.

Si vous êtes familiarisé avec la programmation fonctionnelle en Python, vous pouvez utiliser un package appelé “PULP” qui vous permet d’utiliser une syntaxe Python familière. Cela vous enlève un peu de la bizarre syntaxe (au début) dont vous aurez besoin si vous deviez programmer (par exemple) GLPK ou CPLEX

J’ai un article de blog avec un certain nombre de livres [1] plus ou moins rigoureux, puis un cours de Boyd. J’apprends en faisant. Je l’ai appliqué à un problème de recherche. Vous pouvez également essayer de répondre aux personnes en débordement de pile.

Notes de bas de page

[1] Recueil de livres sur la programmation linéaire / optimisation par Ryan Howe sur les ressources mathématiques