I. introduction








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

3 800 000
P

P2

P1

P3

P4

x3=1

x3=0

x2=0
x2=1
P5

P6

x1=0
x1=1
4 200 000

P7

P8

x4=0
x4=1
x2=0
x2=1
P9

P10

x1=0
x1=1
P11

P12

3 600 000

3 800 000

2 400 000

3 000 000
Commentaires :

  • Relaxation de P

Solution réelle x* = (1 , 1 , 0.5 , 0) Z* = 4 400 000

Solution arrondie = (1 , 1 , 0 , 0) = 3 800 000

On enregistre cette solution comme meilleure solution rencontrée : xbest = et Zbest = 3 800 000
Nous avons 3 800 000 ≤ Zopt ≤ 4 400 000
Création de deux sous problèmes P1 (x3 = 1) et P2 (x3 = 0)


  • Relaxation de P1 Solution réelle x* = (1 , 5/7 , 1 , 0) Z* = 4 371 429 > 3 800 000

Création de deux sous problèmes P3 (x2 = 0) et P4 (x2 = 1)
Note : On va appliquer comme stratégie de parcours le DFS (Parcours en profondeur)


  • Relaxation de P3 Solution entière = (1 , 0 , 1 , 1) = 3 600 000

Arrêt de cette branche, puisque nous avons obtenu une solution entière (qui n’est pas optimale < Zbest)


  • Relaxation de P4 Solution réelle x* = (3/5 , 1 , 1 , 0) Z* = 4 360 000 > 3 800 000

Création de deux sous problèmes P5 (x1 = 0) et P6 (x1 = 1)


  • Relaxation de P5 Solution entière = (0 , 1 , 1 , 1) = 4 200 000

Arrêt de cette branche, puisque nous avons obtenu une solution entière. Mise à jour de xbest et
Zbest = 4 200 000

  • Relaxation de P6 Problème non réalisable  Arrêt de la branche.




  • Relaxation de P2 Solution réelle x* = (1 , 1 , 0 , 2/3) Z* = 4 333 333 > 4 200 000

Création de deux sous problèmes P7 (x4 = 0) et P8 (x4 = 1)


  • Relaxation de P7 Solution entière = (1 , 1 , 0 , 0) = 3 800 000

Arrêt de cette branche.


  • Relaxation de P8 Solution réelle x* = (1 , 6/7 , 0 , 1) Z* = 4 285 714 > 4 200 000

Création de deux sous problèmes P9 (x2 = 0) et P10 (x2 = 1)


  • Relaxation de P9 Solution = (1 , 0 , 0 , 1) = 2 400 000

Arrêt de cette branche, car solution entière.


  • Relaxation de P10 Solution réelle x* = (4/5 , 1 , 0 , 1) Z* = 4 280 000 > 4 200 000

Création de deux sous problèmes P11 (x1 = 0) et P12 (x1 = 1)


  • Relaxation de P11 Solution entière = (0 , 1 , 0 , 1) = 3 000 000

Arrêt de cette branche.


  • Relaxation de P12 Problème non réalisable  Arrêt de la branche.


La meilleure solution trouvée est donc la solution optimale (Nœud P5), ainsi

Solution optimale xopt = (0 , 1 , 1 , 1) Zopt = 4 200 000

Note :

Seules 7 combinaisons ont été considérées (P3 , P5 , P6 , P7 , P9 , P11 , P12), une énumération complète aurait considéré 24=16 combinaisons.
II.2. La Méthode des coupes de Gomory (Gomory cutting planes)
La méthode des coupes (on dit également algorithme du plan sécant ou méthode des troncatures) développé par Ralph E. Gomory (1958) fournit une méthode de résolution des PLNE. L’idée principale est d’ajouter des contraintes qui n’excluent aucun point entier admissible. La méthode consistera à ajouter de telles contraintes linéaires une par une, jusqu’à ce que la solution optimale de la relaxation soit entière. Les contraintes ajoutées sont appelées troncatures ou coupes. On peut résumer la méthode comme suit :


  • Etant donnée un PLNE, résoudre le PLC correspondant à l’aide du simplexe. Si la solution optimale obtenue contient uniquement des valeurs entières, la résolution est terminée.




  • Si une ou plusieurs variables de base dans la solution optimale du PLC ne sont pas entières, on doit alors générer, à partir d’une des lignes du tableau (celle dont la partie fractionnaire est la plus élevée) une contrainte supplémentaire dite coupe de Gomory (qui n’exclue aucune solution réalisable entière).




  • Après ajout de cette contrainte, on détermine une nouvelle solution à l’aide du dual simplexe.
    Le processus est répété jusqu’à ce qu’une solution optimale entière soit obtenue.




  • Génération de la Coupe de Gomory

Notation : étant donné un réel y, [y] désigne le plus grand entier inférieur ou égal à y. Ainsi y = [y] + f , f étant la partie fractionnaire de y. Par exemple : y = 2.7 [y] = 2 f = 0.7

y = 16/5 [y] = 3 f = 1/5

y = -8.1 [y] = -9 f = 0.9

y = 2 [y] = 2 f = 0

Pour générer la nouvelle contrainte (coupe de Gomory), on remplace tout simplement tous les coefficients dans la contrainte obtenue du tableau optimal par leur partie fractionnaire correspondante (fij) et déclarons par la suite que l’expression résultante doit être  à la partie fractionnaire du second membre (fi). On obtient la contrainte :


Remarque : Plusieurs autres méthodes plus ou moins sophistiquées ont été conçues pour générer des coupes permettant d’obtenir plus ou moins rapidement la solution optimale du PLNE.


  • Exemple d’illustration

On veut résoudre le PLNE suivant : Max Z = 100 x1 + 120 x2

Avec 3x1 + 4x2  4100 heures

x1 + 3x2  2400 heures

2x1 + 2x2  2625 heures

x1 , x2  IN
où x1 et x2 représentent les quantités respectives des produits P1 et P2.
En appliquant l’algorithme du simplexe, on obtient le tableau optimal suivant :


MAX

100

120

0

0

0

Solution de base

CB

XB

x1

x2

t1

t2

t3

100

x1

1

0

-1

0

2

1150

120

x2

0

1

1

0

-3/2

325/2

0

t2

0

0

-2

1

5/2

1453/2

cj - zj

0

0

-20

0

-20

-134 500

Solution optimale : x1 = 1150 unités de P1 et x2 = 325/2 = 165.5 unités de P2

Bénéfice maximum Z = 134 500 DA.
Puisque la solution optimale n’est pas entière, on doit poursuivre en construisant la première contrainte additionnelle dont le but est d’éliminer la solution optimale réelle sans enlever des solutions entières réalisables. Il s’agit de créer une contrainte supplémentaire à partir d’une des contraintes du tableau optimal dont la valeur n’est pas entière (x2 ou t2). La pratique consiste à choisir la variable dont la valeur a la plus grande partie fractionnaire. Dans notre cas, la partie fractionnaire de x2 et t2 est la même soit 1/2 (0.5), on choisit arbitrairement de rendre entier x2. D’après le tableau optimal, nous avons :
0 x1 + x2 + t1 + 0 t2 – 3/2 t3 = 325/2
On sépare la partie entière et la partie fractionnaire :
0 x1 + (1+0) x2 + (1+0) t1 + 0 t2 + (-2+1/2) t3 = (162+1/2)
On déduit la coupe de Gomory :

1/2 t3  1/2
Interprétation géométrique de la coupe de Gomory

Puisque le PLNE ne comporte que 2 variables, on peut tracer le graphe des contraintes, puis on trace la coupe de Gomory sur le graphe. Pour cela il faut exprimer la nouvelle contrainte en fonction de x1 et x2. Ceci peut se faire car nous avons d’après la 3ème contrainte 2x1 + 2x2 + t3 = 2625, il s’ensuit que 1/2 t3  1/2 équivaut à x1+x2  1312.

Coupe de Gomory

x1 + x2 1312

Région de solutions réelles exclues par la coupe

x2

x1

Détermination du nouveau tableau optimal

L’algorithme dual simplexe permet de continuer avec le tableau optimal précédent après ajout de la coupe de Gomory. On a : 1/2 t3  1/2  1/2 t3 - t4 = 1/2  -1/2 t3 + t4 = -1/2


MAX

100

120

0

0

0

0

Solution de base

CB

XB

x1

x2

t1

t2

t3

t4

100

x1

1

0

-1

0

2

0

1150

120

x2

0

1

1

0

-3/2

0

325/2

0

t2

0

0

-2

1

5/2

0

1453/2

0

t4

0

0

0

0

-1/2

1

-1/2

cj - zj

0

0

-20

0

-20

0

-134 500


100

x1

1

0

-1

0

0

4

1148

120

x2

0

1

1

0

0

-3

164

0

t2

0

0

-2

1

0

5

760

0

t3

0

0

0

0

1

-2

1

cj - zj

0

0

-20

0

0

-40

-134 480



La solution optimale est : x1 = 1148 unités de P1 et x2 = 164 unités de P2

Bénéfice maximum Z = 134 480 DA.
Puisque cette solution est entière, il n’est pas nécessaire d’effectuer une autre coupe de Gomory.
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