I. introduction








télécharger 296.05 Kb.
titreI. introduction
page3/4
date de publication31.03.2018
taille296.05 Kb.
typeRecherche
p.21-bal.com > documents > Recherche
1   2   3   4

II.3. La Méthode Branch and Cut

L’algorithme des coupes de Gomory a montré ses limites dans beaucoup de cas, le temps d’exécution devenant très prohibitif. Pour palier à ce problème, l’algorithme des coupes de Gomory a été combiné avec la méthode Branch and Bound pour donner une méthode hybride appelée « Branch and Cut ».
Le principe de départ est le même que celui de la méthode de Gomory. « Branch and Cut » commence par résoudre la relaxation continue du PLNE à l'aide de l'algorithme du simplexe. Lorsqu'une solution optimale est trouvée, et que l'une des variables entières a une valeur non entière, une contrainte est ajoutée au programme linéaire de sorte que la résolution de ce programme donne une solution avec moins de valeurs non entières. Ce procédé est répété jusqu'à ce qu'une solution entière soit trouvée (qui est alors optimale) ou jusqu'à ce qu'aucune coupe ne puisse être trouvée.

À ce moment, la partie séparation et évaluation de l'algorithme commence. Le problème est scindé en deux sous problèmes, l'un en rajoutant la contrainte que la variable est plus grande ou égale à l'entier supérieur, et l'autre en rajoutant la contrainte que la variable est plus petite ou égale que l'entier inférieur. Le principe décrit est répété pour les deux nouveaux programmes linéaires ainsi obtenus jusqu’à obtention d’une solution optimale entière.

  • Exemple

Soit à résoudre le PLNE suivant : Min Z = –6x1 – 5x2

avec 3x1 + x2 ≤ 11

–x1 + 2x2 ≤ 5

x1 , x2  0 et entiers

La solution réelle (de la relaxation continue du PLNE) est avec Z* = -232/7

A ce niveau, deux choix sont possibles :

  • Soit générer une coupe de Gomory (par exemple x1+x≤ 5)

  • Soit partitionner le problème en deux sous problèmes suivant une variable trouvée réelle (x1 ou x2 dans ce cas). Dans le cas de x1 (égale à 17/7 2.43), le premier sous problème (P1) comprendra la contrainte x1≤2, le deuxième (P2) comprendra la contrainte x13. La solution optimale du PLNE sera la meilleure entre celles de P1 et P2.

Prenons le deuxième choix, la résolution de la relaxation de P1 conduit à une solution entière avec Z = -28, qui devient la meilleure solution trouvée jusqu’à maintenant. Quant à P2, sa résolution continue donne : avec Z = -29.5

Le problème P2 doit être exploré car une solution meilleure que Z=-28 peut être trouvée.
Le processus se répète et prenons cette fois-ci le choix d’ajouter au problème P2 une coupe de Gomory. Ceci donne le problème P3 suivant :

Min Z = –6x1 – 5x2

avec 3x1 + x2 ≤ 11

–x1 + 2x2 ≤ 5

x1 ≤ 2

2x1 + x2 ≤ 7

x1 , x2  0 et entiers

La relaxation de P3 conduit à la solution optimale réelle avec Z = -27.8 qui est supérieure à la meilleure solution trouvée jusqu’à maintenant. Le principe du Branch and Bound permet d’arrêter cette branche. Ceci termine la résolution du PLNE original avec une solution optimale avec Z = -28.
II.4. La Programmation dynamique

La Programmation Dynamique est une méthode exacte de résolution de problèmes d’optimisation, due essentiellement à R. Bellman (1957). Bien que très puissante, son cadre d’application est relativement restreint, dans la mesure où les problèmes qu’elle adresse doivent vérifier un principe dit principe d’optimalité qui stipule qu’une solution optimale d’un problème de taille n peut s’exprimer en fonction de la solution optimale de problèmes de taille inférieure à n. Bien que naturel, ce principe n'est pas toujours applicable ! Prenons l'exemple des chemins dans un graphe : le principe marche si on cherche le plus court chemin entre deux points : si le chemin le plus court entre A et B passe par C, le tronçon de A à C (resp. de C à B) est le chemin le plus court de A à C (resp. de C à B) ; par contre ça ne marche plus si on cherche le plus long chemin sans boucle d'un point à un autre !
L’idée de base est donc de décomposer le problème en une suite de sous problèmes emboîtés plus petits mais généralement de même nature que le problème principal. Résoudre ensuite les sous problèmes séquentiellement en partant du plus petit, les solutions des problèmes d’une étape donnée s’obtenant à partir de celles des problèmes de l’étape précédente (voir des étapes précédentes). Le principe est d’éviter de résoudre plusieurs fois le même sous problème.
On définit une table, à chaque élément correspondra la solution d'un et d'un seul problème intermédiaire. Il faut donc qu'on puisse définir chaque sous problème qui sera traité au cours du calcul... Ensuite il faut remplir cette table. Cet algorithme peut être exprimé de manière itérative ou récursive.
Le plus gros du travail réside dans l'expression d'une solution d'un problème en fonction de celles de problèmes "plus petits" (formule de récurrence). Si on se rend compte qu'on est amené à recalculer plusieurs fois la solution de mêmes problèmes, on est dans le cadre de la programmation dynamique. Attention, le nombre de sous problèmes peut être grand et l'algorithme obtenu n'est pas forcément polynomial.


  • Application au problème du voyageur de commerce (PVC/TSP)

Rappelons le problème du TSP : étant donné un graphe valué G(X,U,C), le TSP consiste, en partant d’un sommet donné, de trouver un cycle hamiltonien de poids minimum.
Pour obtenir l’équation de récurrence relative au TSP (expression du TSP initial en fonction de sous problèmes plus petits) procédons comme suit  (sommet de départ 1) :
Il est clair que tout cycle est constitué d’un arc (1,k) et d’un chemin simple (partant de k et passant une et une seule fois par tous les sommets de U-{1,k}. Soit donc D[i,S] la distance d’un plus court chemin partant de i, passant par tous les points de S, une et seule fois, et se terminant au sommet 1. La relation suivante n’est donc pas difficile à établir :



La solution optimale est donc donnée par D[1,U{1}].



Avec D[i,]=

Il reste à définir la table qui permettra de résoudre les sous problèmes du TSP à partir des plus simples jusqu’au problème initial en faisant varier l’ensemble S de l’ensemble vide jusqu'à .
Exemple :

Soit le graphe suivant :

0

2

5

8

2

0

3

4

5

3

0

1

8

4

1

0

Dans ce cas, la table est :




{}

{2}

{3}

{4}

{2,3}

{2,4}

{3,4}

2

2

-

8

12

-

-

10

3

5

5

-

9

-

7

-

4

8

6

6

-

6

-

-


D[2, ]=2, D[3, ]=5, D[4, ]=8

D[2,{3}] = c23 + D[3, ] = 3+5 = 8, D[2,{4}] = c24+ D[4, ] = 4+8 = 12

D[3,{2}] = c32 + D[2, ] = 3+2 = 5, D[3,{4}] = c34+ D[4, ] = 1+8 = 9

D[4,{2}] = c42 + D[2, ] = 4+2 = 6, D[4,{3}] = c43+ D[3, ] = 1+5 = 6

D[2,{3,4}]=min{c23 + D[3,{4}] , c24+ D[4,{3}]} = min{3+9 , 4+6} = 10

D[3,{2,4}]=min{c32 + D[2,{4}] , c34+ D[4,{2}]} = min{3+12 , 1+6} = 7

D[4,{2,3}]=min{c42 + D[2,{3}] , c43+ D[3,{2}]} = min{4+8 , 1+5} = 6
Et
Note : Le détail du cycle hamiltonien optimal peut être retrouvé en retenant l’indice j minimisant l’équation de récurrence détaillé précédemment.

II.4. La Relaxation lagrangienne

Avant d’être une méthode de résolution de problèmes difficiles, la relaxation lagrangienne est avant tout une technique de relaxation qui consiste à supprimer des contraintes difficiles en les intégrant dans la fonction objectif en la pénalisant si cette contrainte n’est pas respectée. La solution obtenue représente ainsi une borne de la solution optimale du problème initial.

Considérons un Programme Linéaire : Max (ou Min) CX

AX  (ou ) b (P)

X  S

On sépare les contraintes « difficiles » des contraintes « faciles », on obtient :

Max (ou Min) CX

A1 X  (ou ) b1 (1) : Contraintes « faciles »

A2 X  (ou ) b2 (2) : Contraintes « difficiles »

X  S
La relaxation lagrangienne est faite en introduisant les contraintes difficiles dans la fonction objectif de la manière suivante : Max ou Min CX +  (b2 – A2 X)

A1 X  (ou ) b1 (LR)

X  S

Où  est un vecteur de pénalités positives appelées « multiplicateurs de Lagrange ».

Ainsi, toute violation d’une contrainte (difficile) sera pénalisée dans la fonction objectif.
Exemple :

Soit le Programme Linéaire suivant : Max 7x1 + 2x2

avec –x1 + 2x2  4 (1)

5x1 + x2  20 (2)

–2x1 – 2x2  –7 (3)

–x1  –2 (4)

x2  4 (5)

x1 , x2  Z
La relaxation lagrangienne par rapport aux contraintes (1) et (3) conduit à (1 , 2  R+) :

Max 7x1 + 2x2 + 1 (4 + x1 – 2x2) + 2 (–7 + 2x1 + 2x2)

avec 5x1 + x2  20

–x1  –2

x2  4

x1 , x2  Z

On obtient ainsi :

Max (7 + 1 + 22) x1 + (2 – 21 +22) x2 + 41 –72

avec 5x1 + x2  20

–x1  –2

x2  4

x1 , x2  Z
Propriétés

  • La relaxation lagrangienne permet d’obtenir un programme linéaire plus simple dont la résolution fournit une borne inférieure pour le programme initial (cas Min).


z(P)






z(LR)


Le problème dual-lagrangien consiste à chercher la meilleure borne inférieure : Max z (LR)

La fonction z(LR) est appelée le Lagrangien et est notée L(x,). Le programme dual est obtenu en relaxant toutes les contraintes du primal puis poser : Max(0) L(x,)

x L(x,) = 0 (Points stationnaires).
III. METHODES APPROCHEES

Les méthodes approchées sont généralement des algorithmes polynomiaux qui donnent une solution quelquefois optimale, souvent bonne. Une méthode approchée peut être déterministe - pour une entrée donnée, elle donnera toujours la même solution - (heuristiques gloutonnes, optimum local) ou non déterministe (recuit simulé, algorithme génétique,...).

Elle peut être basée sur un critère propre au problème (heuristique gloutonne) ou sur une métaheuristique (avec une notion de voisinage adaptée au problème).
III.1. Heuristiques classiques

Ce sont des heuristiques conçues pour un problème particulier en s'appuyant sur sa structure propre. Cependant, on retrouve en général des principes de base utilisés dans ces heuristiques tels que :


  • Principe glouton : ce principe repose sur le choix définitif des valeurs de la solution, ce qui interdit toute modification ultérieure.

  • Principe de construction progressive : c’est une extension du principe glouton dans la mesure où l’on s’autorise, cette fois-ci, à modifier des valeurs déjà assignées. On retrouve par exemple l’algorithme de Ford pour la recherche des chemins optimaux.

  • Principe de partitionnement : ce principe repose sur le fait que résoudre le problème global se révèle souvent plus complexe que résoudre la somme des sous problèmes qui le composent. Toute la difficulté réside alors dans le fusionnement des solutions de chaque sous problème.


Dans ce qui suit, nous détaillerons le principe glouton utilisé dans beaucoup d’algorithmes exacts ou approchés.


  • Algorithmes Gloutons (Greedy algorithms)

C’est une méthode (heuristique ou exacte) simple et d’usage général (appelée aussi algorithme du plus proche voisin). Son principe est qu’à chaque étape durant le processus de recherche, l’option localement optimale est choisie jusqu’à trouver une solution (exacte ou non). Les choix fait durant le processus de recherche ne sont jamais remis en cause (pas de retour arrière). Dans les cas où l'algorithme ne fournit pas systématiquement la solution optimale, on parle d’heuristique gloutonne.
Plusieurs algorithmes exacts importants sont issus de cette technique :

– Algorithme de Dijkstra pour les plus courts chemins.

– Algorithme de Kruskal pour les arbres recouvrants minimaux.
Les algorithmes gloutons ont en général une complexité polynomiale, mais encore faut-il que l'algorithme donne bien une solution optimale et qu'on sache le prouver. Là réside souvent la difficulté dans ce type d’algorithmes.
En tant qu’heuristiques, les méthodes gloutonnes sont souvent utilisées pour trouver une solution initiale à d’autres méthodes plus élaborées.
1   2   3   4

similaire:

I. introduction iconChapitre 1 : Introduction à l'optique géométrique I introduction

I. introduction iconI. Introduction

I. introduction iconI introduction

I. introduction iconA. Introduction

I. introduction iconI introduction

I. introduction iconBibliographie Introduction

I. introduction iconBibliographie introduction

I. introduction iconLeçon 1 introduction

I. introduction icon1. astrometrie introduction

I. introduction iconRésumé Introduction








Tous droits réservés. Copyright © 2016
contacts
p.21-bal.com