Remerciez-le!

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

Université Pierre et Marie Curie Optimisation Combinatoire : Programmation Liné

Université Pierre et Marie Curie Optimisation Combinatoire : Programmation Linéaire et Algorithmes Pierre Fouilhoux pierre.fouilhoux@lip6.fr 29 septembre 2015 Avant-propos Table des matières I Modéliser 8 1 Programmation mathématique 9 1.1 Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Di culté de la PMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Programme linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Programme non-linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5 Un puissant outil de modélisation . . . . . . . . . . . . . . . . . . . . . 15 2 Convexi cation et linéarisation 17 2.1 Convexi cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Linéarisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Modélisation par un PLNE . . . . . . . . . . . . . . . . . . . . . . . . . 19 3 Optimisation Combinatoire et modélisations 21 3.1 Problèmes d'Optimisation Combinatoire . . . . . . . . . . . . . . . . . 21 3.2 Notations de théorie des graphes . . . . . . . . . . . . . . . . . . . . . . 22 3.3 Problèmes classiques en optimisation combinatoire . . . . . . . . . . . . 24 3.3.1 Le problème du sac-à-dos . . . . . . . . . . . . . . . . . . . . . . 24 3.3.2 Recouvrement, pavage et partition . . . . . . . . . . . . . . . . 24 3.3.3 Le problème du stable . . . . . . . . . . . . . . . . . . . . . . . 26 3.3.4 Le problème du voyageur de commerce . . . . . . . . . . . . . . 27 3.3.5 Le problème de coloration . . . . . . . . . . . . . . . . . . . . . 30 3.3.6 Le problème du ot max . . . . . . . . . . . . . . . . . . . . . . 32 3.3.7 Le problème du couplage biparti . . . . . . . . . . . . . . . . . . 33 4 Exercices 34 4.1 Modélisation de petits problèmes . . . . . . . . . . . . . . . . . . . . . 34 4.1.1 Problème de production (tiré d'un livre de 1ereS) . . . . . . . . 34 4.1.2 Problème de transport . . . . . . . . . . . . . . . . . . . . . . . 34 4.1.3 Combinaison optimale en vitamines (Diet Problem) . . . . . . . 35 4 TABLE DES MATIÈRES 4.1.4 Constitution d'un portefeuille optimal . . . . . . . . . . . . . . 35 4.1.5 Centres de loisir . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.1.6 Diététique avare . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.1.7 Problème d'aectation quadratique . . . . . . . . . . . . . . . . 37 4.2 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2.1 Linéarisation de la diérence entre variables . . . . . . . . . . . 37 4.2.2 Linéarisation d'un quotient . . . . . . . . . . . . . . . . . . . . . 37 4.2.3 Décision en production industrielle . . . . . . . . . . . . . . . . 38 4.3 Un peu plus dur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.3.1 Verre de spin et Max-Cut . . . . . . . . . . . . . . . . . . . . . 39 II Résoudre 42 5 Résolution approchée ou exacte 43 5.1 Enumération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.1.1 L'explosion combinatoire . . . . . . . . . . . . . . . . . . . . . . 43 5.1.2 Cas polynomiaux . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.2 Solutions approchées et garantie . . . . . . . . . . . . . . . . . . . . . . 44 5.2.1 Trouver des solutions réalisables . . . . . . . . . . . . . . . . . . 45 5.2.2 Solution à garantie théorique . . . . . . . . . . . . . . . . . . . 46 5.2.3 Solution approchée avec garantie expérimentale . . . . . . . . . 46 5.3 Résolution exacte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6 Algorithme de Branchement-Evaluation 48 6.1 Illustration par le problème du voyageur de commerce . . . . . . . . . . 48 6.2 Dé nitions et algorithme de Branch&Bound . . . . . . . . . . . . . . . 51 6.2.1 Sous-problèmes, évaluation et stérilité . . . . . . . . . . . . . . . 51 6.2.2 E cacité d'un algorithme de branchement . . . . . . . . . . . . 52 6.2.3 Schéma de l'algorithme . . . . . . . . . . . . . . . . . . . . . . . 52 6.3 Programmation dynamique et dominance . . . . . . . . . . . . . . . . . 54 6.4 Branchement pour les PMD et pré-traitement . . . . . . . . . . . . . . 55 6.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.5.1 Représentation graphique . . . . . . . . . . . . . . . . . . . . . 56 6.5.2 Arborescence à compléter . . . . . . . . . . . . . . . . . . . . . 56 6.5.3 Sac-à-dos binaire . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7 Evaluation par relaxation 58 7.1 Relaxation continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.2 Relaxation lagrangienne . . . . . . . . . . . . . . . . . . . . . . . uploads/Voyage/ optimisation-combinatoire-programmation-lineaire-et-algorithmes.pdf