Remerciez-le!

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

Recherche opérationnelle Aspects mathématiques et applications Frédéric Bonnans

Recherche opérationnelle Aspects mathématiques et applications Frédéric Bonnans Stéphane Gaubert Recherche Opérationnelle : aspects mathématiques et applications J. Frédéric Bonnans & Stéphane Gaubert Septembre 2018 INRIA Saclay - Île-de-France & Centre de Mathématiques Appliquées (CMAP), École Polytechnique, CNRS. e-mail : Frederic.Bonnans@inria.fr, Stephane.Gaubert@inria.fr ii Table des matières 1 Premiers pas en recherche opérationnelle 1 1.1 Quelques problèmes d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Rudiments de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Convexité, polyédralité et dualité 11 2.1 Séparation d’ensembles convexes en dimension ﬁnie . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Quelques résultats sur les polyèdres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Intégrité des points extrêmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.5 Calcul sous-diﬀérentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3 Problèmes de ﬂots 37 3.1 Flots dans un graphe : premières propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Algorithmes de ﬂots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4 Programmation dynamique déterministe 53 4.1 Cadre général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2 Problème en horizon ﬁni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.3 Quelques applications du problème en horizon ﬁni . . . . . . . . . . . . . . . . . . . . . . . . 57 4.4 Problème arrêté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.5 Problème actualisé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.6 Problème ergodique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5 Séparation, évaluation, relaxation 67 5.1 Séparation et évaluation (branch and bound) . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.2 Relaxation de problèmes combinatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.3 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6 Algorithme du simplexe 83 6.1 Méthodes de gradient réduit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.2 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.3 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 7 Coupes d’intégrité 97 7.1 Principe des coupes d’intégrité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7.2 Coupes mixtes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 7.3 Coupes spéciﬁques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7.4 Coupes d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 iii 7.5 Compléments sur la théorie des coupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 8 Décomposition 115 8.1 Principe de décomposition de Benders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 8.2 Génération de colonnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 8.3 Optimisation avec recours multiples . uploads/Science et Technologie/ recherche-operationnelle-aspects-mathematiques-et-applications-j-frederic-bonnans-stephane-gaubert.pdf