Remerciez-le!

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

Épreuves non corrigées Fondements de recherche opérationnelle Notes de cours Fa

Épreuves non corrigées Fondements de recherche opérationnelle Notes de cours Fausto Errico Virginie Destuynder Août 2020 Épreuves non corrigées Table des matières Préface v Introduction vi 1 Modélisation 1 1.1 Le concept de modèle décisionnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Processus d’aide à la décision à partir de la modélisation . . . . . . . . . . . 2 1.1.2 Limitations de la modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 La programmation mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 La programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.1 Un exemple prototype : la compagnie Windor . . . . . . . . . . . . . . . . . . 6 1.3.2 Autres exemples de programmation linéaire . . . . . . . . . . . . . . . . . . . 10 1.3.3 Modèle linéaire général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 Autres problèmes-types de modélisation linéaire 16 2.1 Les standardistes : Problèmes d’emplois du temps - Workﬂow scheduling problems . 16 2.1.1 Modèle algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 SAVE-IT : Problèmes de composition - Blending and mixing problems . . . . . . . . 17 2.2.1 Modèle algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 PASTISSIMO : Problèmes multi-périodes - Multi-period production problems . . . . 20 2.3.1 Modèle algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 Programmation linéaire en nombres entiers 27 3.1 Programmation en nombres entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Programmation en nombres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2.1 Le problème du sac-à-dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2.2 Les franchises - problèmes de recouvrement minimal . . . . . . . . . . . . . . 29 3.2.3 Les sergents - problèmes d’aﬀectation . . . . . . . . . . . . . . . . . . . . . . . 30 3.2.4 L’équipe - Problème avec contraintes de compatibilité . . . . . . . . . . . . . . 31 3.2.5 La verrerie - Facility location problems . . . . . . . . . . . . . . . . . . . . . . 34 3.2.6 Les chaises - Utilisation de lots . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2.7 Problème d’entreposage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 i Épreuves non corrigées TABLE DES MATIÈRES ii 3.2.8 La diète - Contraintes optionnelles . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2.9 Le meunier - Linéarisation de la fonction-objectif * . . . . . . . . . . . . . . . 39 3.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4 Résolution de la Programmation linéaire : le simplexe 46 4.1 Rappels d’Algèbre Linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.1.1 Matrices et vecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.1.2 Matrices particulières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.1.3 Opérations sur les matrices et vecteurs . . . . . . . . . . . . . . . . . . . . . . 48 4.1.4 Opérations élémentaires sur des lignes . . . . . . . . . . . . . . . . . . . . . . 50 4.1.5 Matrices ligne-équivalentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.1.6 Systèmes d’équations linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.1.7 Systèmes d’équations lignes-équivalents . . . . . . . . . . . . . . . . . . . . . 53 4.1.8 Systèmes d’équations linéaires en forme canonique et solutions de base . . . . 54 4.1.9 Méthode de Gauss-Jordan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.1.10 Calcul de la matrice inverse par Gauss-Jordan . . . . . . . . . . . . . . . . . 57 4.2 Forme standard d’un problème linéaire et solutions de base . . . . . . . . . . . . . . 58 4.2.1 Déﬁnition du problème linéaire en forme standard . . . . . . . . . . . . . . . 58 4.2.2 Forme canonique du problème linéaire en forme standard et solutions de base 59 4.2.3 Lien entre problème original et solution de base . . . . . . . . . . . . . . . . . 61 4.3 Transformation d’un problème de PL en problème de forme standard . . . . . . . . . 61 4.3.1 Transformation d’un problème de PL de type ≤en problème de forme standard 61 4.3.2 Cas des inégalités de type ≥. . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.3.3 Cas des variables libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4 Géométrie de la programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . 64 uploads/Voyage/ gpa430-notesdecours.pdf