Techniques d'optimisation - Tome 2

Max Cerf

Description

Cet ouvrage en deux tomes propose un panorama des techniques d’optimisation continue, discrète et fonctionnelle. Ce deuxième tome est consacré à l’optimisation discrète (problèmes à variables entières) et à l’optimisation fonctionnelle (problèmes dont l’inconnue est une fonction). Les thèmes abordés sont :
• la programmation linéaire mixte : méthodes de coupes et méthodes arborescentes ;
• l’optimisation combinatoire basée sur les graphes : problèmes de chemin, de flot, d’affectation … ;
• le calcul des variations basé sur les conditions d’Euler-Lagrange et leurs extensions ;
• la commande optimale basée sur le principe du maximum de Pontryaguin et ses extensions ;
• les méthodes numériques : équations différentielles, méthodes directes et indirectes.
L’accent est mis sur la compréhension des principes plutôt que sur la rigueur mathématique. Chaque notion ou algorithme est accompagné d’un exemple détaillé aidant à s’approprier les idées principales. Cet ouvrage issu de 30 années d’expérience s’adresse aux étudiants, chercheurs et ingénieurs désireux d’acquérir une culture générale dans le domaine de l’optimisation.

Ce livre fait partie de la sélection finale du « Prix Roberval 2023 » dans la catégorie «Enseignement supérieur ».

1. Programmation linéaire mixte 1

1.1 Formulation 2

1.1.1 Problème linéaire en variables mixtes 2

1.1.2 Techniques de linéarisation 4

1.1.3 Techniques de réduction 10

1.2 Méthodes de coupes 12

1.2.1 Coupe sur une variable 12

1.2.2 Coupe sur le coût 14

1.2.3 Méthode de Gomory 15

1.2.4 Coupe intégrale 21

1.2.5 Coupe mixte 23

1.3 Méthodes arborescentes 31

1.3.1 Énumération implicite 31

1.3.2 Séparation 31

1.3.3 Évaluation 33

1.3.4 Stratégie d’exploration 51

1.4 Applications 58

1.4.1 Problème du voyageur de commerce 58

1.4.2 Problème d’affectation 62

1.4.3 Problème de coloration 66

1.4.4 Problème de flot 68

1.4.5 Problème du sac à dos 71

1.5 Problème quadratique 73

1.5.1 Méthode arborescente 73

1.5.2 Convexification 75

1.5.3 Problème d’affectation quadratique 80

1.6 Conclusion 81

1.6.1 Les points essentiels 81

1.6.2 Pour aller plus loin 82

2. Optimisation discrète 83

2.1 Problème combinatoire 84

2.1.1 Graphe 84

2.1.2 Parcours d’un graphe 87

2.1.3 Complexité 91

2.2 Problème de chemin 95

2.2.1 Algorithme de Ford 95

2.2.2 Algorithme de Bellman 98

2.2.3 Algorithme de Dijkstra 107

2.2.4 Algorithme A* 110

2.2.5 Algorithme de Demoucron et Floyd 124

2.3 Problème d’ordonnancement 128

2.3.1 Méthode PERT 129

2.3.2 Méthode MPM 132

2.3.3 Marges 136

2.4 Problème de flot 138

2.4.1 Algorithme de Ford-Fulkerson 138

2.4.2 Algorithmede Roy-Busacker-Gowen 144

2.5 Problème d’affectation 149

2.5.1 Problème de flot équivalent 149

2.5.2 Méthode hongroise 152

2.5.3 Justification théorique 159

2.6 Heuristiques 163

2.6.1 Problème d’empilement 164

2.6.2 Problème d’emboîtement 165

2.6.3 Problème de recouvrement 166

2.6.4 Problème de coloration 168

2.6.5 Problème du voyageur de commerce 172

2.7 Conclusion 175

2.7.1 Les points essentiels 175

2.7.2 Pour aller plus loin 175

3. Optimisation fonctionnelle 177

3.1 Formulation 178

3.1.1 Fonctionnelle 178

3.1.2 Voisinage 178

3.1.3 Variation 179

3.1.4 Minimum 180

3.1.5 Problème standard 181

3.2 Conditions d’optimalité 184

3.2.1 Conditions nécessaires de minimum faible 184

3.2.2 Conditions suffisantes de minimum faible 196

3.2.3 Conditions nécessaires de coin 205

3.2.4 Conditions nécessaires de minimum fort 214

3.2.5 Récapitulatif 218

3.3 Contraintes 219

3.3.1 Contrainte finale 219

3.3.2 Contrainte intégrale 226

3.3.3 Contrainte courante 232

3.4 Forme canonique 234

3.4.1 Changements de variables 234

3.4.2 Variables canoniques 237

3.4.3 Équation de Hamilton-Jacobi-Bellman 241

3.4.4 Application à la mécanique 244

3.5 Système dynamique 248

3.5.1 Formulation d’état 248

3.5.2 Stabilité 250

3.5.3 Système linéaire 256

3.5.4 Problème aux deux bouts 264

3.6 Conclusion 267

3.6.1 Les points essentiels 267

3.6.2 Pour aller plus loin 267

4. Contrôle optimal 269

4.1 Conditions d’optimalité 270

4.1.1 Problème de contrôle 270

4.1.2 Principe du minimum 272

4.1.3 Méthode variationnelle 281

4.1.4 Problème aux deux bouts 292

4.2 Contraintes 304

4.2.1 Contraintes terminales 304

4.2.2 Contraintes intérieures 311

4.2.3 Contraintes courantes 315

4.2.4 Problème linéaire quadratique 323

4.2.5 Contrôle robuste 333

4.3 Extrémales 337

4.3.1 Définitions 337

4.3.2 Extrémale anormale 338

4.3.3 Extrémale singulière 341

4.3.4 Extrémale voisine 346

4.3.5 Commande en retour d’état 352

4.3.6 Équation de Hamilton-Jacobi-Bellman 356

4.4 Conditions d’optimalité d’ordre 2 362

4.4.1 Problème de minimum auxiliaire 362

4.4.2 Conditions suffisantes de minimum 368

4.4.3 Arcs singuliers 372

4.5 Conclusion 389

4.5.1 Les points essentiels 389

4.5.2 Pour aller plus loin 390

5. Méthodes numériques encontrôle optimal 391

5.1 Transcription 392

5.1.1 Équations différentielles 393

5.1.2 Méthodes directes et indirectes 396

5.2 Méthodes de Runge-Kutta 398

5.2.1 Formules de quadrature 398

5.2.2 Analyse d’erreur 405

5.2.3 Conditions d’ordre 411

5.2.4 Méthodes emboîtées 415

5.3 Méthodes d’Adams 418

5.3.1 Méthodes d’Adams-Bashford 419

5.3.2 Méthodes d’Adams-Moulton 420

5.4 Méthodes de collocation 423

5.4.1 Conditions de collocation 423

5.4.2 Points de collocation 424

5.4.3 Collocation de degré 3 426

5.4.4 Collocation de degré 5 429

5.5 Méthodes directes 431

5.5.1 Discrétisation 431

5.5.2 Approche variationnelle 433

5.6 Méthodes indirectes 440

5.6.1 Méthode de tir 440

5.6.2 Approche variationnelle 450

5.7 Conclusion 455

5.7.1 Les points essentiels 455

5.7.2 Pour aller plus loin 455

Index

Bibliographie

Sujets

• Sciences formelles
• Mathématiques appliquées
• Mathématiques appliquées
• Applied
• Sciences et techniques
• mathématiques
• Mathematics
• Mathématiques
• Informatique
• Mathématiques pures
• Mathématiques générales
• Mathématiques fondamentales

Informations

• Publié par: EDP Sciences
• Date de parution: 01 décembre 2022
• Nombre de lectures: 9
• EAN13: 9782759827749
• Langue: Français
• Poids de l'ouvrage: 11 Mo

Extrait

- Max CERF
PROfl
Techniques d’optimisation Tome II
PROfl
Techniques d’optimisation Tome II
Optimisation discrète et fonctionnelle
Max CERF
PROfl
C et ouvrage en deux tomes propose un panorama des techniques d’optimisation continue,
discrète et fonctionnelle. Ce deuxième tome est consacré à l’optimisation discrète (problèmes
à variables entières) et à l’optimisation fonctionnelle (problèmes dont l’inconnue est une
fonction). Les thèmes abordés sont :
• la programmation linéaire mixte : méthodes de coupes et méthodes arborescentes ;
• l’optimisation combinatoire basée sur les graphes : problèmes de chemin, de fot, d’affectation … ;
• le calcul des variations basé sur les conditions d’Euler-Lagrange et leurs extensions ; Techniques d’optimisation
• la commande optimale basée sur le principe du maximum de Pontryaguin et ses extensions ;
• les méthodes numériques : équations différentielles, méthodes directes et indirectes.
Tome IIL’accent est mis sur la compréhension des principes plutôt que sur la rigueur mathématique.
Chaque notion ou algorithme est accompagné d’un exemple détaillé aidant à s’approprier
les idées principales. Cet ouvrage issu de 30 années d’expérience s’adresse aux étudiants, Optimisation discrète et fonctionnelle
chercheurs et ingénieurs désireux d’acquérir une culture générale dans le domaine de
l’optimisation.
Max Cerf est ingénieur expert en analyse de mission à ArianeGroup. Ses activités
portent sur l’optimisation des véhicules spatiaux et de leurs trajectoires. Il Max CERF
exerce également des fonctions d’enseignement en écoles d’ingénieurs et à
l’université.
Les ouvrages de la collection PROfl ont 978-2-7598-2773-2
pour vocation la transmission des savoirs
professionnels dans différentes disciplines. Ils
sont rédigés par des experts reconnus dans
leurs domaines et contribuent à la formation
9 782759 827732 www.edpsciences.org et l’information des professionnels.49 €
9782759827732-COUV_TechOptimi_T2.indd 1 21/10/2022 12:2521/10/2022 12:25 - Max CERF
PROfl
Techniques d’optimisation Tome II
PROfl
Techniques d’optimisation Tome II
Optimisation discrète et fonctionnelle
Max CERF
PROfl
C et ouvrage en deux tomes propose un panorama des techniques d’optimisation continue,
discrète et fonctionnelle. Ce deuxième tome est consacré à l’optimisation discrète (problèmes
à variables entières) et à l’optimisation fonctionnelle (problèmes dont l’inconnue est une
fonction). Les thèmes abordés sont :
• la programmation linéaire mixte : méthodes de coupes et méthodes arborescentes ;
• l’optimisation combinatoire basée sur les graphes : problèmes de chemin, de fot, d’affectation … ;
• le calcul des variations basé sur les conditions d’Euler-Lagrange et leurs extensions ; Techniques d’optimisation
• la commande optimale basée sur le principe du maximum de Pontryaguin et ses extensions ;
• les méthodes numériques : équations différentielles, méthodes directes et indirectes.
Tome IIL’accent est mis sur la compréhension des principes plutôt que sur la rigueur mathématique.
Chaque notion ou algorithme est accompagné d’un exemple détaillé aidant à s’approprier
les idées principales. Cet ouvrage issu de 30 années d’expérience s’adresse aux étudiants, Optimisation discrète et fonctionnelle
chercheurs et ingénieurs désireux d’acquérir une culture générale dans le domaine de
l’optimisation.
Max Cerf est ingénieur expert en analyse de mission à ArianeGroup. Ses activités
portent sur l’optimisation des véhicules spatiaux et de leurs trajectoires. Il Max CERF
exerce également des fonctions d’enseignement en écoles d’ingénieurs et à
l’université.
Les ouvrages de la collection PROfl ont 978-2-7598-2773-2
pour vocation la transmission des savoirs
professionnels dans différentes disciplines. Ils
sont rédigés par des experts reconnus dans
leurs domaines et contribuent à la formation
9 782759 827732 www.edpsciences.org et l’information des professionnels.
9782759827732-COUV_TechOptimi_T2.indd 1 21/10/2022 12:2521/10/2022 12:25Techniques
d’optimisation
Tome 2
Optimisation discrète
et fonctionnelle
Max CERF Imprimé en France
ISBN (papier) : 978-2-7598-2773-2 – ISBN (ebook) : 978-2-7598-2774-9
Tous droits de traduction, d’adaptation et de reproduction par tous procédés, réservés pour tous
pays. La loi du 11 mars 1957 n’autorisant, aux termes des alinéas 2 et 3 de l’article 41, d’une part,
que les « copies ou reproductions strictement réservées à l’usage prive du copiste et non destinées
à une utilisation collective », et d’autre part, que les analyses et les courtes citations dans un but
d’exemple et d’illustration, « toute représentation intégrale, ou partielle, faite sans le
consenteerment de l’auteur ou de ses ayants droit ou ayants cause est illicite » (alinéa 1 de l’article 40).
Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc une
contrefaçon sanctionnée par les articles 425 et suivants du code pénal.
© EDP Sciences, 2022










J’adresse mes plus sincères remerciements aux personnes qui m’ont aidé à réaliser
ce livre, en particulier :

France Citrini pour en avoir accepté la publication aux éditions EDP ;
Nathalie Legros pour sa relecture du texte et l’amélioration de la présentation ;
Sophie Hosotte et Magalie Jolivet pour leur assistance au processus éditorial ;
Thomas Haberkorn pour sa vérification minutieuse du contenu scientifique, et
pour les innombrables astuces numériques qu’il m’a partagées ;
Emmanuel Trélat pour sa préface, sa relecture et ses conseils d’exposé, mais
aussi pour notre collaboration de longue date et la compétence que j’ai acquise
à ses côtés ;
Claude Blouvac† mon professeur de lycée qui m’a mis en 1982 sur la voie des
mathématiques et qui aurait été très heureux de voir cet ouvrage.



Préface


Les algorithmes sont omniprésents dans notre monde moderne. Ils nous indiquent
les trajets optimaux, préviennent et évaluent les risques, fournissent des
prévisions, anticipent ou assistent nos décisions. Ils sont devenus des éléments
essentiels de notre quotidien. Ces algorithmes reposent la plupart du temps sur des
processus d'optimisation et consistent à minimiser ou maximiser un critère sous
certaines contraintes, nous indiquant ainsi des solutions faisables et plus
intelligentes que d'autres, permettant de planifier au mieux un processus à
exécuter.
Il existe de très nombreuses méthodes d'optimisation, basées sur des heuristiques
diverses et variées, parfois simples et intuitives, parfois plus élaborées et
nécessitant des développements mathématiques fins.
C'est à travers cette jungle d'algorithmes, résultant de dizaines d'années de
recherches et développements, que Max Cerf nous guide avec toute son expertise,
son intuition et son pragmatisme.
Max Cerf est ingénieur senior à ArianeGroup depuis 30 ans. Spécialiste reconnu
de trajectographie, il élabore et optimise les trajets des engins spatiaux, sous de
multiples contraintes. Il a ainsi acquis et développé une connaissance très
complète des meilleurs algorithmes en optimisation continue, en optimisation
discrète (sur des graphes), en contrôle optimal. C'est de plus un pédagogue
exceptionnel, avec un véritable talent à expliquer de manière limpide et intuitive
des concepts parfois compliqués.
Avec ce double ouvrage, il offre un guide inestimable au lecteur non spécialiste
qui souhaite comprendre ou résoudre des problèmes d'optimisation de la manière
la plus efficace possible.

Emmanuel Trélat, Sorbonne Université, Paris



Introduction


L’optimisation mathématique est en développement constant depuis les années
1950 et l’apparition des premiers ordinateurs. Devant la variété des algorithmes
et des logiciels disponibles, il est parfois difficile pour un non spécialiste de s’y
retrouver. L’objectif de ce livre en deux tomes est de donner un aperçu d’ensemble
du domaine. Il s’adresse aux étudiants, enseignants, ingénieurs et chercheurs
désireux d’acquérir une connaissance générale sur les techniques d’optimisation
mathématique.
L’optimisation vise à contrôler les entrées (variables) d’un système, d’un
processus ou d’un modèle pour obtenir les sorties souhaitées (contraintes) au
meilleur coût. Selon la nature des entrées à contrôler, on distingue l’optimisation
continue, discrète ou fonctionnelle.
L’optimisation continue (chapitres 1 à 5 du tome I) traite des problèmes à
variables réelles. Le chapitre 1 expose les conditions d’optimalité dans le cas de
fonctions différentiables ainsi que le calcul numérique de dérivées. Les chapitres
2, 3 et 4 donnent un panorama des méthodes d’optimisation sans gradient, sans
contraintes et avec contraintes. Le chapitre 5 est consacré à la programmation
linéaire continue, avec les méthodes du simplexe et de point intérieur.
L’optimisation discrète (chapitres 1 et 2 du tome II) traite des problèmes à
variables entières. Le chapitre 1 concerne la programmation linéaire en variables
mixtes par les méthodes de coupes ou les méthodes arborescentes. Le chapitre 2
présente un panorama des problèmes combinatoires, leur modélisation par des
graphes et les algorithmes spécialisés aux problèmes de chemin, de flot ou
d’affectation.
L’optimisation fonctionnelle (chapitres 3 à 5 du tome II) traite des problèmes en
dimension infinie. L’entrée à contrôler est une fonction et non plus un nombre fini
de variables. Le chapitre 3 introduit les notions de fonctionnelle et de calcul des
variations. Le chapitre 4 présente les problèmes de contrôle optimal et les
conditions d’optimalité. Le chapitre 5 est consacré aux méthodes numériques
(intégration d’équations différentielles, méthodes directes et indirectes).
Dans chaque chapitre, les développements théoriques et démonstrations se
limitent à l’essentiel. Les algorithmes sont accompagnés d’exemples détaillés en
vue de faciliter leur compréhension.
Table des matières

1. Programmation lin