Remerciez-le!

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

; ; Département de Mathématiques et Informatique École Nationale Supérieure d’A

; ; Département de Mathématiques et Informatique École Nationale Supérieure d’Arts et Métiers Université Moulay Ismaïl Meknès Cours et travaux dirigés de Mathématiques Intitulé de module : Programmation Linéaire & Statistiques Intitulé de l’élément de module : Programmation Linéaire Filière : Génie civil Volume horaire de l’élément de module : 20h Année universitaire : 2020/2021 Mohamed BENDAOUD Email : m.bendaoud@ensam-umi.ac.ma .......................................................................................................................... École Nationale Supérieure d’Arts et Métiers, Marjane II, B.P. 15290, Al Mansour, Meknès Tél : +212(0)535457160/61- +212(0)648313896 Fax : +212(0)535467163 Table des matières Introduction 4 1 Programmation linéaire 6 1.1 Introduction à la recherche opérationnelle . . . . . . . . . . . . . . . . . 6 1.1.1 Enjeux de la recherche opérationnelle . . . . . . . . . . . . . . . 8 1.1.2 Formulation d’un problème d’optimisation . . . . . . . . . . . . 8 1.1.3 Méthodes et outils de la recherche opérationnelle . . . . . . . . . 9 1.2 Modélisation d’un programme linéaire . . . . . . . . . . . . . . . . . . . 9 1.3 Méthode graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.4.1 Algorithme du Simplexe . . . . . . . . . . . . . . . . . . . . . . 24 2 Table des ﬁgures 1.1 La ville de Königsberg et ses 7 ponts. . . . . . . . . . . . . . . . . . . . 6 1.2 Graphe associé au problème des ponts de Königsberg . . . . . . . . . . . 7 1.3 Régionnement du plan par une contrainte. . . . . . . . . . . . . . . . . . 17 1.4 Région réalisable d’un problème. . . . . . . . . . . . . . . . . . . . . . . 17 1.5 Problème ayant une solution maximale unique. . . . . . . . . . . . . . . 18 1.6 Polyèdre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.7 Problème ayant une inﬁnité de solutions maximales. . . . . . . . . . . . . 20 1.8 Problème à solution minimale unique. . . . . . . . . . . . . . . . . . . . 21 1.9 Problème à solution minimale unique. . . . . . . . . . . . . . . . . . . . 22 1.10 Problème à solution impossible. . . . . . . . . . . . . . . . . . . . . . . 22 1.11 Problème à solution rejeté à l’inﬁni. . . . . . . . . . . . . . . . . . . . . 23 3 Introduction Introduction La recherche opérationnelle est une discipline qui a pour rôle d’assurer la compré- hension et la modélisation des systèmes industriels et du secteur public et de les traduire au monde théorique fondé principalement par des mathématiques, des statistiques et de l’informatique. L’employabilité de la recherche opérationnelle est composée de deux phases. La pre- mière consiste à formuler mathématiquement un problème qui demande une analyse dé- taillée et sufﬁsamment précise pour recueillir les caractéristiques essentielles du problème posé en plus d’un savoir-faire et d’une certaine expérience. La deuxième phase s’intéresse à la résolution du problème par l’utilisation d’algorithmes rigoureux et bien déterminés. Comme objectif de ce cours est de présenter l’un des méthodes de recherche opéra- tionnelle à savoir la programmation linéaire. Le premier objectif de ce cours est de ce concentrer sur la formulation et la modélisation des problèmes d’optimisation continue ou discrètes où les contraintes et le critère (ou la fonction objective) s’expriment linéai- rement. Dans cette partie, nous commencerons par la collecte des données et des infor- mations fournies par le problème traité. Ensuite nous présentons les différentes étapes à suivre pour donner une vision mathématique globale. Le deuxième objectif concerne la présentation des différentes techniques de résolution de ces problèmes dont le but est de trouver la meilleure solution (appelée solution optimale) ou pour le problème étudié. Le premier chapitre est est organisé en cinq sections. La première section est des- tiné à la présentation de la recherche opérationnelle, son utilisation et les domaines qui font appel à cette discipline. Les autres sections sont consacré à la formulation et la ré- solution d’une programmation linéaire, c’est-à-dire les problèmes où les contraintes et la fonction objective sont linéaires. Dans ce chapitre nous apprendrons comment translater et formuler des problèmes sous forme d’un programme linéaire, puis nous présenterons les méthodes de résolution d’un programme linéaire à savoir la résolution graphique et la résolution analytique, plus précisément l’algorithme du simplexe qui est la méthode prin- cipale pour la résolution de programmes linéaires en nombres réels. Nous conclurons en donnant un petit aperçu sur la dualité et ses principales applications dans les programmes linéaires. L’analyse de la sensibilité ainsi que et la mise en oeuvre un solveur libre et/ou professionnel sont aussi présentées. Le deuxième chapitre traitera des problèmes en nombres entiers. La résolution de ces problèmes fait appel à des techniques et des algorithmes de résolution. Parmi eux nous présenterons dans un premier temps l’approche par énumération, suivie par une présenta- tion de la méthode de branch and bound pour les valeurs entières. On parle de la résolution en nombres entiers lorsque les valeurs des variables doivent être entières, par rapport à la résolution en nombres réels. Les notes de ce cours se composent à la fois de cours magistraux et de séances de travaux dirigés. Mohamed BENDAOUD 4 Chapitre 1 1.1 Introduction à la recherche opérationnelle Ce cours de RO s’adresse aux étudiants de la troisième année de L’ENSAM-Meknès de la ﬁlière Génie Civil, à l’Université de Moulay Ismaïl. Bien évidemment, de nombreux aspects ne sont pas étudiés faute de temps et de volume horaire. Cependant, les notions de base choisies dans ce cours permettent aux étudiants d’acquérir des connaissances et un savoir-faire en Recherche Opérationnelle pour traiter divers problèmes. Ce support de cours comporte également une annexe consacrée à des rappels d’al- gèbre linéaire et quelques notions algorithmiques, qui constituent les pré-requis à une bonne compréhension des premières parties du cours. Ces notes de cours ne vous seront proﬁtables que si vous préparez régulièrement et sérieusement les T.D.s et ne vous dispensent bien évidement pas d’assister au cours. Mohamed BENDAOUD 5 Chapitre 1 Programmation linéaire 1.1 Introduction à la recherche opérationnelle La Recherche Opérationnelle (RO) est une discipline qui permet de formuler des pro- blèmes par des supports scientiﬁques, mathématiques et informatiques pour aider à mieux décider. La RO est donc un outil d’aide à la décision. Autrement déﬁnie, la RO traduit des énoncés ou des cahiers de charges liés à des problématiques spéciﬁques sous forme de méthodes et des démarches à base d’équation mathématique, des algorithmes et des outils statistiques. Comme premier exemple d’application de la RO, on cite le problème des ponts de Königsberg ci-dessous : Exemple 1.1.1 (Euler 1735) FIGURE 1.1 – La ville de Königsberg et ses 7 ponts. Deux îles de la ville de Königsberg sont reliées entre elles par 1 pont. D’autre part 6 autres ponts relient les îles à la ville. La question posée est la suivante : à partir d’un 6 Chapitre 1 1.1 Introduction à la recherche opérationnelle point de départ quelconque, existe-t-il un chemin passant une et une seule fois par chaque pont et qui revient au point de départ? La réponse (apportée par Euler) est non. La preuve utilise un graphe : les arêtes du graphe représentent les ponts et les sommets correspondent aux différents endroits de la ville (les rives gauche et droite et les deux îles; voir ﬁgure Figure 1.2 ci-dessous). Supposons qu’un tel chemin existe. Un tel chemin est appelé chemin eulérien. Alors né- cessairement en chacun des noeuds du graphe il y a toujours un nombre pair d’arêtes reliées au noeud : s’il y a une arête qui arrive au noeud, il y en a nécessairement une autre (différente) qui le quitte. Or, on constate que le graphe possède des noeuds (tous en fait!) reliés à un nombre impair d’arêtes. Par conséquent, il n’existe pas de chemin eulérien. FIGURE 1.2 – Graphe associé au problème uploads/Science et Technologie/ polycopie-pl-gme20-21-suite2.pdf