10
Recherche opérationnelle
Une première partie sera consacrée à la programmation linéaire. D’un point de vue
pédagogique, ce choix n’est pas optimal ; en effet les programmes linéaires, parmi les
outils que nous exposons ici, sont ceux qui font le plus appel aux mathématiques, alors
que les graphes, par exemple, sont très économes en concepts et connaissances
mathématiques, et sont donc plus à même de séduire des lecteurs intéressés par la
discipline mais moins par les équations. D'un autre côté, beaucoup de problèmes,
notamment résolus par des méthodes appuyées sur les graphes, pourraient l'être aussi par
un programme linéaire, l'inverse n'étant pas vrai. C’est cet aspect fédérateur qui jusitifie
que l’on débute ainsi l'exposé.
Après avoir relié la programmation linéaire à une problématique générale de
planification de production industrielle, on développera de façon complète la méthode de
résolution « phare », à savoir l'algorithme du simplexe. On soulignera qu'il ne s'agit pas
de la méthode de résolution a priori la plus rapide et on donnera quelques indications sur
d'autres méthodes logiquement plus performantes (sans que cela se vérifie
empiriquement).
On introduira dans cette partie la notion de dualité dans les programmes linéaires, notion
fondamentale d'abord d'un point de vue économique (fixation des prix d'acquisition de
ressources supplémentaires), ensuite d'un point de vue pratique (analyse de sensibilité).
Dans une seconde partie, nous passerons à la théorie des graphes, et nous montrerons
que cet objet, très simple dans son principe (des points et des flèches) permet de
résoudre un grand nombre de problèmes combinatoires concrets et ayant des
implications évidentes au niveau de l'organisation de la production et de la logistique.
C'est ainsi que l'on traitera de quelques algorithmes destinés à résoudre le problème du
chemin de valeur minimale dans un graphe. Nous montrerons que ces méthodes peuvent
s'appliquer sans difficultés à la question très importante de l'ordonnancement des tâches
dans un projet. Comme on l'a signalé plus haut, peu de projets industriels se privent à
l'heure actuelle d'une planification à base d'un PERT ou d'une méthode potentiels, qui
constituent les deux outils concurrents en la matière. Là aussi, l'exposé restera succinct,
dans la mesure où l'on ne fera qu'évoquer les complications introduites dans ces
techniques par la prise en compte de contraintes autres que celles portant sur la
succession des tâches (les contraintes disjonctives notamment, qui ouvrent l'immense et
difficile chapitre de l'ordonnancement d'atelier).
On traitera ensuite des problèmes liés à des graphes particuliers, nommés « arbres » ; on
montrera que cette notion permet de traiter simplement des questions de tracé de réseaux
(comment relier n points de la façon la plus économique ?). Le concept voisin
d'arborescence conduit moins, de son côté, à des outils d'optimisation de réseau qu’à
une classe particulière de méthodes visant à approcher des questions hautement
combinatoires et particulièrement difficiles. C'est dans ce cadre que nous aborderons le
fameux problème du voyageur de commerce (cf. supra).
Le dernier chapitre de cette partie abordera les problèmes de flots : il s'agit cette fois-ci
de faire circuler des flux dans des réseaux (flux divers : pièces, matières premières, mais
aussi individus ou voitures sur un réseau autoroutier) de façon soit à maximiser les
entrées totales sur le réseau (problème du flot maximal), soit à minimiser un coût global
de transport, à entrée totale donnée (programme de transport). On montrera également
Recherche opérationnelle
Une première partie sera consacrée à la programmation linéaire. D’un point de vue
pédagogique, ce choix n’est pas optimal ; en effet les programmes linéaires, parmi les
outils que nous exposons ici, sont ceux qui font le plus appel aux mathématiques, alors
que les graphes, par exemple, sont très économes en concepts et connaissances
mathématiques, et sont donc plus à même de séduire des lecteurs intéressés par la
discipline mais moins par les équations. D'un autre côté, beaucoup de problèmes,
notamment résolus par des méthodes appuyées sur les graphes, pourraient l'être aussi par
un programme linéaire, l'inverse n'étant pas vrai. C’est cet aspect fédérateur qui jusitifie
que l’on débute ainsi l'exposé.
Après avoir relié la programmation linéaire à une problématique générale de
planification de production industrielle, on développera de façon complète la méthode de
résolution « phare », à savoir l'algorithme du simplexe. On soulignera qu'il ne s'agit pas
de la méthode de résolution a priori la plus rapide et on donnera quelques indications sur
d'autres méthodes logiquement plus performantes (sans que cela se vérifie
empiriquement).
On introduira dans cette partie la notion de dualité dans les programmes linéaires, notion
fondamentale d'abord d'un point de vue économique (fixation des prix d'acquisition de
ressources supplémentaires), ensuite d'un point de vue pratique (analyse de sensibilité).
Dans une seconde partie, nous passerons à la théorie des graphes, et nous montrerons
que cet objet, très simple dans son principe (des points et des flèches) permet de
résoudre un grand nombre de problèmes combinatoires concrets et ayant des
implications évidentes au niveau de l'organisation de la production et de la logistique.
C'est ainsi que l'on traitera de quelques algorithmes destinés à résoudre le problème du
chemin de valeur minimale dans un graphe. Nous montrerons que ces méthodes peuvent
s'appliquer sans difficultés à la question très importante de l'ordonnancement des tâches
dans un projet. Comme on l'a signalé plus haut, peu de projets industriels se privent à
l'heure actuelle d'une planification à base d'un PERT ou d'une méthode potentiels, qui
constituent les deux outils concurrents en la matière. Là aussi, l'exposé restera succinct,
dans la mesure où l'on ne fera qu'évoquer les complications introduites dans ces
techniques par la prise en compte de contraintes autres que celles portant sur la
succession des tâches (les contraintes disjonctives notamment, qui ouvrent l'immense et
difficile chapitre de l'ordonnancement d'atelier).
On traitera ensuite des problèmes liés à des graphes particuliers, nommés « arbres » ; on
montrera que cette notion permet de traiter simplement des questions de tracé de réseaux
(comment relier n points de la façon la plus économique ?). Le concept voisin
d'arborescence conduit moins, de son côté, à des outils d'optimisation de réseau qu’à
une classe particulière de méthodes visant à approcher des questions hautement
combinatoires et particulièrement difficiles. C'est dans ce cadre que nous aborderons le
fameux problème du voyageur de commerce (cf. supra).
Le dernier chapitre de cette partie abordera les problèmes de flots : il s'agit cette fois-ci
de faire circuler des flux dans des réseaux (flux divers : pièces, matières premières, mais
aussi individus ou voitures sur un réseau autoroutier) de façon soit à maximiser les
entrées totales sur le réseau (problème du flot maximal), soit à minimiser un coût global
de transport, à entrée totale donnée (programme de transport). On montrera également