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.
- Quel est le meilleur moyen d'éduquer le monde? Peut-il y avoir un système éducatif universel gratuit?
- Quelles compétences techniques peut-on enseigner aux personnes sans éducation formelle sur une période de quelques mois, afin de les préparer à de bonnes idées de démarrage?
- Quelles sont les bases à apprendre sur les réseaux sans fil?
- J'ai la capacité d'apprendre très facilement des langues étrangères, quelles carrières peuvent convenir à ce talent?
- Qu'est-ce qui vous a motivé à apprendre une langue étrangère qui n'a aucune utilité pratique dans votre vie de tous les jours?
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.
