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 : 2022/2023 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 1.4.2 Tableaux Simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.4.3 Détérmination d’une solution de base admissible . . . . . . . . . 35 1.4.4 Utilisation de la méthode du simplexe dans un problème de mini- misation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.5 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 1.5.1 Déﬁnition et exemples . . . . . . . . . . . . . . . . . . . . . . . 40 1.5.2 Propriétés de la dualité . . . . . . . . . . . . . . . . . . . . . . . 42 1.5.3 Correspondances entre les tableaux simplexes optimaux Dual et Primal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 1.5.4 Interprétation économique de la dualité . . . . . . . . . . . . . . 44 1.6 Analyse de sensitivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 1.6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 1.6.2 Paramétrisation de la fonction économique . . . . . . . . . . . . 46 1.6.3 Paramétrisation du second membre des contraintes . . . . . . . . 47 1.7 Mises-en oeuvre sur un solveur . . . . . . . . . . . . . . . . . . . . . . . 49 2 Programmation en nombres entiers 53 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2 La méthode de séparation et d’évaluation (Branch and Bound) . . . . . . 54 2.2.1 Relaxation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.2.2 Démarche de résolution . . . . . . . . . . . . . . . . . . . . . . 54 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 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 1.12 Problème à région réalisable ne contenant pas l’origine. . . . . . . . . . . 35 1.13 Intervalles de stabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.1 Arbre d’un programme linéaire à variables entières. . . . . . . . . . . . . 55 2.2 Branchement du PL à variables entières . . . . . . . . . . . . . . . . . . 57 2.3 Arbre associée à un PL à variables entières . . . . . . . . . . . . . . . . . 57 2.4 Branchement d’un PL à variables entières . . . . . . . . . . . . . . . . . 58 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 uploads/Science et Technologie/ polycopie-pl-gme22-23.pdf