Remerciez-le!

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

PROGRAMMATION MATHEMATIQUE PRINCIPES ET APPLICATIONS Youssef BENADADA ENSIAS, U

PROGRAMMATION MATHEMATIQUE PRINCIPES ET APPLICATIONS Youssef BENADADA ENSIAS, Université Mohammed V – Souissi Rabat Ahmed ALAOUI EL HILALI FSTF, Université Sidi Mohammed Ben Abdellah Fès Edition Kawtar Print -‐ Rabat 2012 ii Avant Propos Après le succès remarquable qu’a eu la Recherche Opérationnelle dans le domaine militaire lors de la deuxième guerre mondiale, c’était au tour des milieux industriels de s’intéresser à cette nouvelle science. Depuis, la recherche opérationnelle est de plus en plus présente dans le quotidien des gestionnaires : planification de la production, affectation du personnel, gestion des stocks, problèmes de transport (routier, ferroviaire, aérien…), élaboration d’horaires… Tous ces problèmes font appel explicitement ou implicitement à des techniques de recherche opérationnelle. Cet intérêt à cette science, qui a été freiné au début par la complexité des calculs et la lenteur des ordinateurs de la première génération, a eu un essor considérable au cours des dernières décennies avec la puissance remarquable des ordinateurs. Mieux encore, les décideurs et les gestionnaires disposent désormais de plusieurs logiciels de recherche opérationnelle et d’aide à la prise de décision, disponibles sur des ordinateurs personnels de plus en plus rapides. Cependant, ces logiciels ne peuvent profiter vraiment qu’à ceux qui en comprennent les fondements et les hypothèses avec lesquels ils ont été conçus. En effet, pour être en mesure d’utiliser efficacement un logiciel de recherche opérationnelle, il faut bien respecter les conditions d’utilisation et rester dans les limites permises pour que l’interprétation des résultats reste valide. Les utilisateurs de ces logiciels doivent en plus s’assurer que les modèles mathématiques proposés reflètent bien la réalité des problèmes à résoudre. L’une des disciplines les plus exploitées de la recherche opérationnelle est celle de la programmation mathématique qui a comme objet l’étude théorique des problèmes d’optimisation ainsi que la conception et l’utilisation d’algorithme de résolution. La programmation mathématique regroupe plusieurs classes de problèmes dont : -‐ Programmation linéaire, (G.B. Dantzig 1949, [1]), pour l’étude des problèmes d’optimisation de fonctions linéaires sous contraintes linéaires. -‐ Programmation non linéaire, (H.W. Kuhn et A.W. Tucker 1951, [2]), pour l’étude des problèmes d’optimisation non linéaires avec ou sans contraintes. -‐ Programmation en nombres entiers, (R.E. Gomory, 1958 [3]), pour l’étude des problèmes d’optimisation où les variables sont astreindre à ne prendre que des valeurs entières -‐ Programmation dynamique, (R. Bellman, 1957, [4]), qui est une approche générale d’optimisation de problèmes dynamiques… Ce manuel regroupe les principales parties de ces classes de problèmes enseignées dans les grandes écoles d’ingénieurs et les facultés des sciences et techniques au Maroc. La matière de cet ouvrage provient en grande partie des différents cours dispensés par les auteurs, pendant une vingtaine d’années, dans certains établissements universitaires marocains et particulièrement à l’Ecole Nationale Supérieure d’Informatique et d’Analyse des Systèmes (ENSIAS) de Rabat, à la faculté des sciences de Tétouan ou la faculté des sciences et techniques de Fès. Certains exemples ou exercices de ce livre sont des exemples classiques et peuvent se trouver dans d’autres ouvrages, mais la plupart sont des exemples ou exercices originaux. iii L’objectif de ce manuel « Programmation Mathématique, Principes et Applications » est donc de développer chez l’étudiant, certaines habiletés de formulation de modèles mathématiques, d'application de quelques techniques de recherche opérationnelle, d’utilisation de certains logiciels d’aide à la décision et d’interprétation des résultats obtenus. Ce manuel peut servir de support de cours à la fois aux élèves-‐ingénieurs des grandes écoles, aux étudiants des licences sciences et techniques, des licences professionnelles, mais aussi étudiants des écoles privés spécialisés en gestion (Cycle normal ou MBA). Il peut aussi servir d’un guide aux enseignants de la recherche opérationnelle. Les notions de mathématiques requises pour la compréhension des notions présentées dans ce document est tout simplement celles d’algèbre linéaire du niveau baccalauréat. Une grande partie de ce manuel est dédiée à la modélisation mathématique et la résolution de modèles linéaires soit graphiquement soit par la méthode primale ou duale du Simplexe. Vue l’importance de l’analyse de sensibilité un chapitre lui a été consacré. Une grande attention a été donnée à la résolution des problèmes d’optimisation en nombres entiers. Comme applications, on a choisit deux problèmes classiques : les problèmes de transport et les problèmes d’affectation. Enfin, le dernier chapitre a été réservé à l’initiation à la programmation non linéaire. Les critiques et les propositions des utilisateurs de cet ouvrage seront les bienvenues et serviront, certainement, à l’améliorer pour les prochaines éditions. Nous tenons à remercier tous les collègues et particulièrement ceux avec qui j’ai eu des discussions fructueuses à propos de cet ouvrage et qui nous ont fortement encouragé à le réaliser. Qu’ils trouvent tous dans ce travail nos sentiments de respect et de considérations. Les auteurs Chapitre. 1 : Programmation mathématique et modélisation 5 CHAPITRE 1 PROGRAMMATION MATHEMATIQUE ET MODELISATION 1.1 Introduction La programmation mathématique est actuellement une branche particulièrement active des mathématiques appliquées, et cela, pour de nombreuses raisons. La première est peut-‐être le nombre, la variété, et l’importance de ses applications que ce soit dans les sciences de l’ingénieur, ou dans d’autres domaines des mathématiques appliquées. Mais, l’importance de la programmation mathématique vient aussi du fait qu’elle fournit un cadre conceptuel adéquat pour l’analyse et la résolution de nombreux problèmes de mathématiques appliquées, tels que, la théorie des jeux, l’analyse numérique et la programmation combinatoire. Sans prétendre être exhaustif, on peut citer quelques domaines d’application : -‐ Recherche opérationnelle : l’optimisation des systèmes technico-‐économiques (planification, économétrie,…), les problèmes de transport, les problèmes d’ordonnancement, les problèmes de gestion de stockes, …etc. -‐ Analyse numérique : l’approximation, la régression, la résolution de systèmes linéaires et non linéaires, les méthodes numériques liées à la mise en œuvre des méthodes d’éléments finis, …etc. -‐ Automatique : l’identification des systèmes, la commande optimale des systèmes, le filtrage, l’ordonnancement d’atelier, la commande de robots, …etc. -‐ Ingénierie : le dimensionnement et l’optimisation des structures et la conception optimale de systèmes techniques complexes tels que, les systèmes informatiques, les réseaux d’ordinateurs, les réseaux de transport, les réseaux de télécommunication, …etc. -‐ Economie mathématique : la résolution de grands modèles macro-‐économiques, des modèles micro-‐économiques ou modèles d’entreprise, la théorie de la décision et la théorie des jeux. La programmation mathématique vise l’étude théorique des problèmes d’optimisation ainsi que la conception et la mise en œuvre des algorithmes de résolution. Historiquement, l’existence du terme « programmation » dans le nom proposé à cette discipline peut s’expliquer par le fait que les premières recherches et les premières applications se sont développées dans le contexte de l’économie et de la recherche opérationnelle. Très naturellement, la terminologie adoptée Chapitre. 1 : Programmation mathématique et modélisation 6 reflète bien l’étroite relation existante entre l’activité d’analyse mathématique d’un problème et son interprétation économique. L’élaboration des concepts fondamentaux et la tendance à l’unification ont été constamment au centre des préoccupations, et c’est ainsi que l’histoire de cette discipline se trouve jalonnée par un certain nombre de travaux de synthèse remarquables, qui ont souvent été à l’origine de courants de recherche nouveaux et féconds. Mais, avant de résoudre un problème du monde de la gestion, il faut bien commencer par sa traduction par des relations mathématiques. Or, selon les situations, cette traduction reflète plus ou moins la réalité. Souvent nous sommes obligés d’accepter des compromis. Les relations mathématiques que nous proposons ne constituent en général que des modèles des problèmes considérés. Mais les résultats de ces modèles permettent souvent aux gestionnaires de prendre des décisions souvent efficaces pour mener à bien leurs projets. Nous parlons alors de modélisation mathématique pour caractériser cette traduction d’informations. C’est un processus qui relève à la fois de l’art, de l’expérience, de la culture générale et des connaissances mathématiques. Dans ce chapitre, avant de présenter plusieurs exemples pédagogiques ainsi que leurs modèles mathématiques, nous allons présenter quelques notions générales de programmation mathématique. Certains de ces exemples sont des problèmes classiques que l’on retrouve dans la littérature scientifique. C’est le cas du problème de transport, du problème d’affectation ou le problème du voyageur du commerce. 1.2 Préliminaires Les problèmes de la programmation mathématique se posent lorsqu’on cherche à maximiser (ou minimiser) une fonction à plusieurs variables, appelées fonction objectif. Ces variables sont soumises à des inéquations, appelées contraintes. Notons par X un sous ensemble de . Dans toute la suite signifie que le minimum de f est atteint, c'est-‐à-‐dire : et il existe tel que Si f est non bornée inférieurement, c'est-‐à-‐dire si , nous adoptons la convention : Dans ce cas, on dit que f n’a pas de minimum de valeur finie sur X ou que le problème est non-‐ borné inférieurement. Chapitre. 1 : Programmation mathématique et modélisation 7 De même, signifie que le maximum de f est atteint c'est-‐à-‐dire : et il existe tel que Si f est non bornée supérieurement, c'est-‐à-‐dire si , nous adoptons la convention : Dans ce cas, on dit que f n’a pas de maximum de valeur finie sur X ou que le problème est non-‐ borné supérieurement. 1.3 Programme Mathématique 1.3.1 Définitions Soient (i=1,2,…m) et un sous-‐ensemble de . Définition 1.1 Un programme mathématique est uploads/Science et Technologie/ modelisation-matematiqe.pdf