Chapitre 3 - Methodes Exacte

Méthodes exactes
Plan
 Introduction
 Recherche exhaustives
 Programmation linéaire en nombres entiers
 Programmation dynamique
 Algorithme de séparation et évaluation (branch

and bound)
Introduction
 Les méthodes exactes sont des méthodes qui garantissent
l’obtention de la solution optimale pour un problème
d’optimisation.
 Consiste généralement à énumérer, souvent de manière
implicite, l’ensemble des combinaisons de l’espace de
recherche.
 Utile pour des instances de petite taille.
 Inefficace lorsque la taille du problème (l’espace de

recherche) est grande.
Plan
 Introduction

and bound)
Recherche exhaustive
Principe: consiste principalement à générer et évaluer

toutes les solutions possibles pour trouver la meilleure
(optimal) .
Avantage:
Certitude de trouver la meilleure solution;
Inconvénients:
Temps d’exécution prohibitif: 64 entités sur 2
processeurs (à 1 GHz): 292 ans!!!
Recherche exhaustive
Exemple: Le plus court chemin entre A et E
3 B 8
A 2 2 E
4
5
C 4
Solution: 1
D
• Énumération et évaluation de tous les chemins possibles
ABE : 11
ABCDE: 10
ABDE: 8
ACE: 9 6 Chemins possible
ACDE: 10
ABCE: 9
 Le meilleur chemin est ABDE, Longueur = 8

Plan
 Introduction

and bound)
Programmation linéaire en nombres entiers
Programmation linéaire:
 Un problème de programmation linéaire (PL) demande de
minimiser une fonction linéaire.
 La fonction que l'on minimise ainsi que
les contraintes sont décrites par des fonctions linéaires.
Exemple:
Exemple de méthodes de résolution: Algorithme de

simplexe
Problème de programmation linéaire en nombres entiers
(PLNE)
 UN PLNE est un problème de programmation linéaire (PL)
avec tout ou une partie des variables qui doivent être entières.
PL PLNE
 On dit que les variables sont soumises à des contraintes

d’intégrité.
 Un problème de programmation linéaire classique (PL) sera, a
contrarie, dit "en variables continues".
Méthodes de résolution
 Branch-and-Bound
 Branch-and cut
 La méthode de coupes (Cutting planes method)
Plan
 Introduction
and bound)
Programmation dynamique
Exemple illustratif
 La suite de fibonacci
u0 =1 , u1 =1, un = un-1 + un-2 si n>1.
 Résolution par récusions (Déviser pour rigner / de Haut au bas)
Fonction U (n: entier):entier
Si n<2 alors retourner 1
Sinon retourner U (n-1) + U(n-2)
Fin
 Problème:
 Nombre d’appels récursifs effectué
 La redondance
 La programmation dynamique est une

méthode algorithmique pour résoudre des problèmes
d'optimisation.
 S'appuie sur le principe d'optimalité de Bellman :
Une solution optimale d'un problème s'obtient en combinant des

solutions optimales à des sous-problèmes.
 Consiste à résoudre un problème en le décomposant en sous-
problèmes, puis à résoudre les sous-problèmes, des plus petits
aux plus grands en stockant les résultats intermédiaires.
 De nombreuses problème économiques de l’industrie peuvent
être résolus par cette technique.
Méthodes ascendant: Commence par calculer des solutions pour les sous-
problèmes les plus petits puis, de proche en proche, on calcule les solutions des
problèmes en utilisant le principe d'optimalité et on mémorise les résultats dans
un tableau.
fonction fibonacci(n) : entier
0 1
F[0] = 0
1 1
F[1] = 1
2 2
Pour i de 2 à n faire
3 3
F[i] := F[i-1] + F[i-2] 4 5
Fin pour 5 8
Retourner F[n] 6 13
Fin 7 21
F
Méthode descendant:
 On écrit un algorithme récursif mais on utilise la mémorisation pour
ne pas résoudre plusieurs fois le même problème.
 On stocke dans un tableau les résultats des appels récursifs :
fonction fibonacci(n: entier)
Si F[n]=-1 alors // F[n] n'est pas défini
Si n = 0 ou n = 1 alors
F[n] := n
Sinon
F[n] := fibonacci(n-1) + fibonacci(n-2)
Finsi
Fin si
retourner F[n];
Fin
Plan
 Introduction
 Algorithme de séparation et évaluation
(branch and bound)
Algorithme branch and bound
 L’algorithme de Séparation et Évaluation est plus connu sous son
appellation anglaise Branch and Bound (B&B).
 Plutôt qu’énumérer, on peut tenter d’utiliser le paradigme informatique
classique du diviser pour régner (divide&conqueer) consistant à diviser
le problème en sous problème plus simple à résoudre.
 Repose sur une méthode arborescente de recherche d’une solution
optimale par séparations et évaluations, en représentant les états
solutions par un arbre d’états, avec des nœuds, et des feuilles.
 La procédure de séparation et d'évaluation (branch and bound) se base
sur les axes suivants :
 La construction d'une solution initiale (heuristique),
 L'évaluation,
 La séparation
 L'exploration.
1) La construction d'une solution heuristique
 Une solution heuristique peut être calculé en utilisant

une heuristique.
 La méthode peut théoriquement fonctionner avec
toute solution réalisable pour le problème étudié.
 La bonne d’une telle solution conditionne souvent le
succès de cette méthode.
 Avec une solution initiale de bonne qualité, il est plus
facile d'augmenter l’efficacité de l’exploration et de
diminuer le temps de calcul.
2) Séparation
 Consiste à décomposer l'univers des solutions en plusieurs sous-
ensembles généralement disjoints.
 L’union de ces sous-ensembles couvre toutes les solutions
possibles de l’ensemble séparé (ou bien de la branche séparée).
 Le principe de la séparation est récursif.
 Conduisant ainsi à un arbre de recherche dont l’évolution,

pendant le déroulement de l’algorithme, est liée aux sous-
ensembles des solutions explorés.
2) Séparation
Exemple:
 La séparation de l’ensemble de solutions S en deux sous ensemble
S1, S2.
S ={s1, s2, …, sn}
x1=0 x1=1
S1 ={s1, s2, …sk} S2 ={sk +1, sk +2, …sk}
 La séparation est effectué selon la valeur de variable de décision x1.

 S1 contient les solutions dont x1=0.
 S2 contient les solutions dont x2=0.
3) Evaluation
 L’évaluation consiste à associer une borne B au problème
étudié que l’on calcule pour chaque branche explorée.
 On parle d'une borne inférieure (respectivement d'une borne
supérieure) dans le cas d'une minimisation (respectivement
dans le cas d'une maximisation).
 Cette borne permet d’estimer la performance de la branche
évaluée dans le meilleur des cas.
 La borne B d’un problème peut être calculé en utilisant la
relaxation.
4) Exploration
 L'exploration consiste à fixer un protocole donnant l'ordre
de visite des différentes branches.
 On distingue trois stratégies d’exploration (parcours):
 Parcours en largeur
 Parcours en profondeur
 Le meilleur d’abord
4) Exploration
1) Parcours en largeur:
 Parcours par niveau en favorisant les sommets les plus proches de la
racine
 Moins efficace que les deux autres stratégies présentées.
2) Parcours en profondeur :
 Favorise les sommets les plus éloignés de la racine (de profondeur la
plus élevée).
 Mène rapidement à une solution optimale en économisant la mémoire.
3) Le meilleur d’abord (Best-first):

 Nous commençons par explorer les branches les plus prometteuses.
 Le choix d’une branche se base sur la valeur de la borne inférieure (resp

la borne supérieure) dans le cas d'une minimisation (resp dans le cas de
maximisation )
4) Exploration
Au cours de l'exploration et dans un problème de minimisation par
exemple, on peut distinguer les cas suivants :
Cas 1:
⁻ La branche courante Si est évaluée par B(Si)≥b₀, avec b₀ la
borne supérieure initiale.
⁻ Dans ce cas, il est inutile d'explorer la branche car dans le
meilleur des cas, on va trouver une solution équivalente à la
solution heuristique.
Cas 2:
⁻ La branche courante Si est évaluée par B(Si)<b₀,
⁻ Dans ce cas, la branche sera séparée et ensuite explorée.
Cas 3:
⁻ La branche est terminale : c'est à dire, elle correspond à une
solution réalisable et par la suite, elle ne peut être séparée.
⁻ Dans ce cas, si cette solution représente une valeur du critère
b₁≥b₀, alors elle sera rejetée. Si b₁<b₀, la solution sera
temporairement mémorisée comme étant la meilleure
solution et elle remplacera la solution heuristique initiale.
⁻ Dans ce cas, la valeur de b₀ sera remplacée par b₁. La
procédure est résumée dans la figure suivante.
Principe de la méthode (Branch and Bond)
Relaxation
 Une relaxation d’un problème (P) est un nouveau problème
(R) construit à partir de (P) et auquel on a retiré au moins
une contrainte.
 Toutes les solutions de P sont des solutions de (R).
Attention ! La réciproque est fausse.
Relaxation
 Une borne supérieure d’un problème de maximisation
(Borne inferieur dans le cas minimisation) P peut être
calculée en résolvant une relaxation de (P).
 On a :
 Cas maximisation: v(P) ≤ v(R).
 Cas minimisation: v(P) ≥ v(R).
 v(P) valeur optimale de (P)
 v(R) valeur optimale de (R)
Relaxation
Exemple:
P R
o Solution optimale de (R) : x1 = 0; x2 = 1.25 de valeur 3.75 .

o 3.75 est une borne supérieure pour P.
o v(P) ≤3.75

Chapitre 3 - Methodes Exacte

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 3 - Methodes Exacte

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chapitre 3 - Methodes Exacte

Transféré par

Droits d'auteur :

Formats disponibles

Méthodes exactes

 Programmation linéaire en nombres entiers

 Algorithme de séparation et évaluation (branch

 Inefficace lorsque la taille du problème (l’espace de

 Algorithme de séparation et évaluation (branch

Principe: consiste principalement à générer et évaluer

 Le meilleur chemin est ABDE, Longueur = 8

 Programmation linéaire en nombres entiers

 Algorithme de séparation et évaluation (branch

Exemple de méthodes de résolution: Algorithme de

 On dit que les variables sont soumises à des contraintes

 Programmation linéaire en nombres entiers

 La programmation dynamique est une

Une solution optimale d'un problème s'obtient en combinant des

 Programmation linéaire en nombres entiers

 Une solution heuristique peut être calculé en utilisant

 Conduisant ainsi à un arbre de recherche dont l’évolution,

 La séparation est effectué selon la valeur de variable de décision x1.

3) Le meilleur d’abord (Best-first):

 Le choix d’une branche se base sur la valeur de la borne inférieure (resp

o Solution optimale de (R) : x1 = 0; x2 = 1.25 de valeur 3.75 .

Vous aimerez peut-être aussi