Optimisation combinatoire 1 , livre ebook

Optimisation combinatoire 1© LAVOISIER, 2005
LAVOISIER
11, rue Lavoisier
75008 Paris
www.hermes-science.com
ISBN 2-7462-1038-X
Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une
part, que les "copies ou reproductions strictement réservées à l'usage privé 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 ou reproduction intégrale, ou
partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce
soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.
Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins
d’identification et sont des marques de leurs détenteurs respectifs.Optimisation
combinatoire 1
concepts fondamentaux
sous la direction de
Vangelis Th. PaschosIl a été tiré de cet ouvrage
30 exemplaires hors commerce réservés
aux membres du comité scientifique,
aux auteurs et à l’éditeur
numérotés de 1 à 30Optimisation combinatoire 1
sous la direction de Vangelis Th. Paschos
fait partie de la série INFORMATIQUE ET SYSTÈMES D’INFORMATION
dirigée par Jean-Charles Pomerol
TRAITÉ IC2 INFORMATION – COMMANDE – COMMUNICATION
sous la direction scientifique de Bernard Dubuisson
Le traité Information, Commande, Communication répond au besoin
de disposer d'un ensemble complet des connaissances et méthodes
nécessaires à la maîtrise des systèmes technologiques.
Conçu volontairement dans un esprit d'échange disciplinaire, le traité IC2
est l'état de l'art dans les domaines suivants retenus par le comité
scientifique :
Réseaux et télécoms
Traitement du signal et de l'image
Informatique et systèmes d'information
Systèmes automatisés et productique
Management et gestion des STICS
Cognition et traitement de l’information
Chaque ouvrage présente aussi bien les aspects fondamentaux
qu'expérimentaux. Une classification des différents articles contenus
dans chacun, une bibliographie et un index détaillé orientent le lecteur
vers ses points d'intérêt immédiats : celui-ci dispose ainsi d'un guide pour
ses réflexions ou pour ses choix.
Les savoirs, théories et méthodes rassemblés dans chaque ouvrage ont
été choisis pour leur pertinence dans l'avancée des connaissances ou pour
la qualité des résultats obtenus dans le cas d'expérimentations réelles.Liste des auteurs
Jeremy BARBAY
Department of Computer Science
University of British Columbia
Canada
Alain BILLONNET
CEDRIC - CNAM
Paris
Alberto CESELLI
Dipartimento di Tecnologie dell’Informazione
Università degli Studi di Milano
Italie
Irène CHARON
Département informatique et réseaux
ENST
Paris
Fédérico DELLA CROCE
Dipartimento di Automatica e Informatica
Politecnico di Torino
Italie
Bruno ESCOFFIER
LAMSADE
Université Paris-Dauphine
Olivier HUDRY
Département informatique et réseaux
ENST
Paris
Claude LE PAPE
ILOG
ParisIrene LOISEAU
Departamento de Computación
Facultad de Ciencias Exactas y Naturales
Universidad de Buenos Aires
Argentine
Nelson MACULAN
Programa de Engenharia de Sistemas e Computação
COPPE
Universidade Federal do Rio de Janeiro
Brésil
Ali RIDHA MAHJOUB
LIMOS
Université Blaise-Pascal Clermont II
Vangelis TH. PASCHOS
LAMSADE
Université Paris-Dauphine
Matteo SALANI
Dipartimento di Tecnologie dell’Informazione
Università degli Studi di Milano
Italie
Olivier SPANJAARD
LIP6
Université Pierre et Marie Curie
Paris
Pierre TOLLA
LAMSADE
Université Paris-Dauphine ’
Table des matiŁres
Avant-propos ....................................... 17
Vangelis Th. PASCHOS
PREMI¨RE PARTIE. SUR LA COMPLEXIT DES PROBL¨MES
D’OPTIMISATION COMBINATOIRE ........................... 21
Chapitre 1. Concepts de base de l algorithmique et de la thØorie
de la complexitØ ..................................... 23
Vangelis Th. PASCHOS
1.1. La complexitØ des algorithmes ........................ 23
1.2. La complexitØ des problŁmes ......................... 24
1.3. Les classes P, NP et NPO ........................... 27
1.4. Les rØductions de Karp et de Turing ..................... 29
1.5. La NP-complØtude ............................... 31
1.6. Deux exemples de problŁmes NP-complets ................ 34
1.6.1. MIN G-TRANSVERSAL ........................... 34
1.6.2. MAX STABLE ................................ 36
1.7. Quelques mots sur la NP-complØtude aux sens fort et faible....... 37
1.8. Quelques autres classes de complexitØ notoires .............. 38
1.9. Bibliographie ................................... 40
Chapitre 2. ComplexitØ probabiliste......................... 43
JØrØmy BARBAY
2.1. Algorithmes dØterministes et probabilistes ................. 44
2.1.1. ComplexitØ dun algorithme de Las Vegas ............. 46
2.1.2. ComplexitØ probabiliste d un problŁme ................ 48
2.2. Technique de borne infØrieure 50
2.2.1. DØfinitions et notations 51








’
’
’
’
’
’
’
10 Optimisation combinatoire
2.2.2. ThØorŁme du Minimax ......................... 52
2.2.3. Lemme de Loomis et principe de Yao ................ 55
2.3. ProblŁme ØlØmentaire dintersection ..................... 57
2.3.1. Borne supØrieure ............................. 57
2.3.2. Borne infØrieure 58
2.3.3. ComplexitØ probabiliste 59
2.4. Conclusion .................................... 59
2.5. Bibliographie ................................... 59
DEUXI¨ME PARTIE. QUELQUES M THODES CLASSIQUES DE R SOLUTION .. 61
Chapitre 3. MØthodes arborescentes par sØparation et Øvaluation
(Branch and bound) 63
IrŁne CHARON, Olivier HUDRY
3.1. Introduction 63
3.2. Principes des mØthodes arborescentes .................... 65
3.2.1. Principe de sØparation .......................... 66
3.2.2. Principes dØlagage ........................... 68
3.2.2.1. Borne ................................ 68
3.2.2.2. Fonction dØvaluation ....................... 69
3.2.2.3. Utilisation de la borne et de la fonction dØvaluation
pour Ølaguer ................................. 72
3.2.2.4. Autres principes dØlagage .................... 72
3.2.2.5. Ordre des Ølagages ........................ 73
3.2.3. DØveloppement de larborescence ................... 74
3.2.3.1. Description des stratØgies de dØveloppement ......... 74
3.2.3.2. PropriØtØs comparØes des stratØgies en profondeur
et de la meilleure feuille .......................... 75
3.3. Un exemple dØtaillØ : le problŁme du sac dos binaire .......... 77
3.3.1. Calcul de la borne initiale 78
3.3.2. Premier principe de sØparation ..................... 80
3.3.3. Elagage sans Øvaluation ......................... 81
3.3.4. Evaluation ................................. 83
3.3.5. DØroulement complet de la mØthode arborescente
pour la recherche dune seule solution optimale .............. 84
3.3.6. PremiŁre variante : recherche de toutes les solutions optimales . . 86
3.3.7. DeuxiŁme variante : stratØgie de dØveloppement
de type « meilleure feuille » .......................... 87
3.3.8. TroisiŁme variante : second principe de sØparation ......... 88
3.4. Conclusion .................................... 90
3.5. Bibliographie .................................. 91






















à
’
É
É
’
’
Table des matiŁres 11
Chapitre 4. Programmation dynamique ...................... 95
Bruno ESCOFFIER, Olivier SPANJAARD
4.1. Introduction ................................... 95
4.2. Un premier exemple : le franchissement du pont ............. 96
4.3. Formalisation .................................. 100
4.3.1. Espace dØtats, ensemble des dØcisions, fonction de transition . . 100
4.3.2. Politiques rØalisables, relation de comparaison et objectif ..... 101
4.4. Quelques autres exemples ........................... 103
4.4.1. Gestion de stocks ............................. 103
4.4.2. Plus court chemin bottleneck dans un graphe ............ 105
4.4.3. ProblŁme du sac dos .......................... 107
4.5. RØsolution .................................... 108
4.5.1. ProcØdure avant .............................. 108
4.5.2. ProcØdure arriŁre 110
4.5.3. Principe d optimalitØ et monotonie .................. 111
4.6. RØsolution des exemples ............................ 113
4.6.1. Gestion de stocks ............................. 113
4.6.2. Plus court chemin bottleneck ...................... 113
4.6.3. Sac dos .................................. 114
4.7. Quelques extensions 114
4.7.1. Ordre partiel et optimisation multicritŁre ............... 115
4.7.1.1. Nouvelle formulation du problŁme 115
4.7.1.2. RØsolution 117
4.7.1.3. Exemples .............................. 117
4.7.2. Programmation dynamique dans lincertain ............. 118
4.7.2.1. Processus dØcision-hasard .................... 119
4.7.2.2. RØsolution ............................. 119
4.7.2.3. Exemple ............................... 120
4.7.3. Programmation dynamique gØnØralisØe ............... 120
4.8. Conclusion .................................... 123
4.9. Bibliographie .................................. 123
TROISI¨ME PARTIE. ELMENTS DE LA PROGRAMMATION MATHMATIQUE .. 125
Chapitre 5. ModØlisation de problŁmes d optimisati on combinatoire
laide de la programmation linØaire mixte entiŁre ............... 127
Federico DELLA CROCE (traduit en fran ais par Dominique Q UADRI)
5.1. Introduction ................................... 127
5.1.1. PrØliminaires ............................... 128
5.1.2. Le problŁme du sac dos ........................ 129
5.1.3. Le problŁme du remplissage des bo tes ( bin packing) ....... 129


























’
’
’
’
’
’
’
12 Optimisation combinatoire
5.1.4. Le problŁme de couverture et de partition d ensemble ....... 130
5.1.5. Le problŁme de flot de coßt minimum ................ 131
5.1.6. Le problŁme du flot maximum .................... 132
5.1.7. Le prob