Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

INTRODUCTION A LA PROGRAMMATION MATHÉMATIQUE Selon une opinion assez largement

INTRODUCTION A LA PROGRAMMATION MATHÉMATIQUE Selon une opinion assez largement répandue, la programmation mathématique constituerait une technique toute récente et sa partie la mieux connue, la programmation linéaire, représenterait l'essentiel de la recherche opérationnelle. En réalité, il y a bien longtemps que des problèmes de programmation mathématique se sont posés à nos ancêtres, dans les termes mêmes où nous les exprimons aujourd'hui. D'autre part, pour importante que soit la programmation linéaire, elle n'est que le sous-ensemble le plus mathématisé, mais non le modèle le plus utile à la pratique de l'aide à la décision. Origines de la programmation mathématique. - Lorsque François Quesnay (1694-1774) publie en 1758 son Tableau économique de la France, il inaugure l'application de l'algèbre linéaire à un nouveau domaine : le calcul économique. Mieux compris de Karl Marx que d'Augustin Cournot, ses vrais continuateurs n'apparaîtront qu'au début du XX° siècle, avec V. K. Dimitriev (1904) et Vassily Léontieff, qui, en 1925, expose dans la revue Planification socialiste sa méthode du tableau intersectoriel. Mais, dans l'intervalle, d'autres applications de la programmation mathématique sont nées. En 1776, s'illustre Gaspard Monge (1744-1818) réalise l'optimisation du coût des transports dans le problème de déblai et remblai. Bien que cette communication ait subi plusieurs remaniements avant d'être publiée sous sa forme définitive aux Comptes rendus de l'Académie dont Monge était devenu membre. Elle ne cessa de susciter une vive curiosité. Plusieurs géomètres de talent s'y intéressèrent, tels Charles Dupin (Histoire de rAcadémie, 18 décembre 1815), Albert de SaintGermain en 1884 (Acad. Caen, 1826), Paul Appell en 1884, 1926 et 1928 (Mémorial des sciences mathématiques, XXVII, 1928) et, enfin, Ferdinand Pottier (CR Acad. des Sciences, t. 31, 1950, p. 11. 22-1124). Il est vrai que Monge inventa la belle théorie des congruences de normales pour venir à bout d'un problème qu'il formulait « en continu >> et dans l’espace, alors qu'aujourd'hui on le considère comme « plan et < discret et le résout directement au moyen d'algorithmes déduits de la théorie des graphes. Un autre mathématicien de renom, le baron JeanBaptiste Fourier (1768-1830), contemporain du premier essor de l'industrie, se trouve confronté à certains problèmes d'inéquations simultanées. Il fit connaitre, en 1824, pour les résoudre, une méthode directe qui suscite encore l'admiration. Enfin, en 1938, le célèbre mathématicien Léonid Kantorovitch, prix Nobel 1975, formulait dans toute leur amplitude les problèmes de programmation linéaire et fournissait une méthode de résolution, adaptée au système économique soviétique et apparentée à celle des multiplicateurs de Lagrange. Dès lors, A. Tolstoi (1939), F. L. Hitchcock (1941) et L. Kantorovitch lui- même (1942) pouvaient bien revenir sur les problèmes de transport. Le pas essentiel était franchi. Entre la publication de la méthode de Kantorovitch et l'annonce de l'algorithme du simplexe par G. B. Dantzig (1948), près de dix ans s'étaient écoulés ; il fallut encore attendre huit ans avant que des codes convenant aux premiers ordinateurs civils, commercialisés vers 1955-1956, autorisent les économistes d'entreprise et les chercheurs des sociétés de conseil à envisager l'utilisation réelle de programmes linéaires dans la pratique quotidienne. Il est d'ailleurs très curieux de constater que les théorèmes et résultats auxquels fait appel la théorie de la programmation mathématique datent souvent de nombreuses années. En dehors des références déjà citées et de l'apport fondamental de H. J. S. Smith, remontant à 1861, les théorèmes essentiels sont dus à P. Gordan (1873), J. Farkaš (1901), I. Fredholm (1903), 0. Perron (1907), H. Minkowski (1911), G. Frobenius (1912), E. Steinitz (1914), E. Stiemke (1915), E. Borel (1921-1924), J. v. Neumann (1928), G. Ascoli (1932) et S. Mazur (1933), L. Kantorovitch (1935), H. Weyl (1935), T. S. Motzkin (1936), M. Krein (1937), J. Ville (1938), M. Krein et D. Milman (1940), sans compter C. Caratheodory (1911-1918) ni E. Helly (1921-1923). C'est donc sur un riche terreau que des spécialistes bien connus : G. B. Dantzig, C. E. Lemke, A. Charnes, R. Frisch, E. M. L. Beale, H. V. Kuhn et A. W. Tucker, ont fait fleurir, de 1948 à 1958, les méthodes classiques de résolution des programmes linéaires. L'apport de George B. Dantzig, après sa mise au point, sur une indication de Janos von Neumann, de l'algorithme du simplexe, de 1947 à 1958), demeure considérable : démonstration de l'équivalence entre programmes linéaires et jeux (1951), méthode révisée du simplexe (1953); en collaboration avec Alex Orden et Philip Wolfe, méthode lexicographique (1955); en collaboration avec Lester R. Ford et Delbert R. Fulkerson, méthode primale- duale (1956); en collaboration de nouveau avec Philip Wolfe, principe de décomposition applicable aux grands programmes (1958). De son côté, Carlton E. Lemke, dans sa thèse, exposait, dès 1952, la méthode duale du simplexe, étudiée aussi, avec quelques variantes, par E.M. L. Beale (1954). A. Charnes, en 1952, indiquait le procédé du petit epsilon pour mettre fin aux difficultés provoquées par l'apparition de certaines solutions dégénérées au cours d'un calcul itératif et, la même année, A. Orden donnait la méthode du grand M ou de la base artificielle. Dans une tout autre direction, le Suédois Regnar A. K. Frisch, qui fut prix Nobel d'économie, proposait une méthode utilisant le « potentiel logarithmique », puis une technique « multiplexe », qui semblent un peu oubliées (1955-1957). Pendant ce temps, des chercheurs de plus en plus nombreux s'intéressaient, au développement de la programmation linéaire Objet de la programmation mathématique. - En dehors de quelques applications aux mathématiques elles-mêmes ou à des systèmes physiques, la programmation mathématique intéresse essentiellement l'économie. Nombreux sont les problèmes de l'entreprise auxquels elle convient. Ils concernent, en général, la planification d'activités diverses, et notamment : 1) l'optimisation d'un résultat (ou d'un rendement) en présence de ressources limitées : par exemple, plan d'utilisation optimale de moyens de production ou d'action en agriculture (force de travail, sol, eau, engrais...), dans l'industrie (force de travail, machines, matières premières...), le commerce (employés et représentants, engins de transport et de distribution, supports publicitaires, etc.) ; 2) l'obtention du coût minimal de mélanges de spécifications déterminées à partir de constituants différents (problèmes relevant de la physique, de la chimie industrielles ou de la diététique). La programmation mathématique peut aussi s'appliquer à la macroéconomie et c'est même de là qu'elle tire, nous l'avons vu plus haut, son origine. Beaucoup de problèmes de planification régionale ou nationale se présentent en effet comme des optimisations sous contraintes. Les traits communs qui caractérisent les problèmes se formulant en termes de programmation linéaire sont les suivants : a) Les variables, évidemment réelles, sont aussi non négatives : en effet, les niveaux d'activité atteints ou les quantités de moyens employées sont nécessairement positifs ou nuls. b) Les relations qui lient les variables sont linéaires : les effets sont proportionnels aux « causes (par exemple, les quantités fabriquées aux quantités de matière première utilisées) et additifs (par exemple, les productions de deux ateliers fabriquant le même article s'ajoutent). Les relations qui expriment la limitation des ressources ou les conditions de mise en cuivre de divers moyens ou activités sont soit des inéquations, soit des équations ; elles se nomment les contraintes du problème. c) Il existe une fonctionnelle linéaire des variables dont on recherche l'optimum : c'est la fonction économique. Ainsi tout problème de programmation linéaire revient à optimiser une fonctionnelle de variables non négatives sur un domaine défini par des contraintes d'égalité ou d'inégalité. La programmation mathématique est plus générale que la programmation linéaire : 1) Dans certains problèmes la fonction économique ou les contraintes, et souvent les deux, ne peuvent être décrites par des relations linéaires. Cette situation comporte de nombreux cas différents : a) contraintes linéaires et fonction économique non linéaire concave (en particulier quadratique) ; b) contraintes non linéaires mais domaine convexe et fonction économique concave ; c) domaine discret ; contraintes linéaires ou non ; fonction économique concave. Le fait que le domaine d'optimisation de la fonction économique soit discret (ou partiellement discret) est dû, assez souvent, à la nature même du problème : chargement optimal d'un sac à dos, d'un bateau... avec des colis de poids et d'encombrement déterminés, compte tenu des contraintes de masse et de volume disponibles ; optimisation d'activités dépendant de moyens dont les quantités sont entières : effectif du personnel présent, nombre de machines de puissances différentes, effectif et répartition d'un cheptel...; choix d'investissements indivisibles, etc. Dans d'autres cas, des variables discrètes, généralement bivalentes, ont été introduites dans la formulation du problème pour ramener certaines expressions non linéaires à des fonctionnelles <<linéaires >> entières. 2) Dans certaines situations, il est impossible d'exprimer la fonction économique ou les contraintes du problème, ou les deux, sans faire appel à des variables aléatoires. On envisage, en particulier, la programmation linéaire stochastique. 3) La programmation linéaire s'occupe d'optimisation <<statique>> ; elle s'applique à des problèmes dont on recherche la meilleure solution dans des conditions déterminées, à une date donnée ; elle ne permet pas, notamment, de trouver les stratégies qui conviennent à une situation qui évolue dans le temps. L'optimisation de décisions séquentielles n'est donc pas l'objet de ce modèle ; elle relève d'autres techniques, comme la programmation dynamique, uploads/Industriel/ temp.pdf