Algorithme dual simplexe Plan du cours

Publié par

12004/2005 104 Algorithme dual simplexe • Principe : – Lorsque le primal ne possède pas de sbr explicitée, mais que le dual en possède une. – Résoudre implicitement le dual par l'algorithme du simplexe. • Avantages : – Travailler sur le primal, sans devoir rajouter de variables artificielles. – Permet de traiter l'ajout de contraintes. 2004/2005 105 Plan du cours 1. Introduction – Méthodes quantitatives, aide à la décision, modélisation 2.
  • solution optimale du programme
  • analyse post-optimale
  • prix marginal de la ième contrainte
  • prix marginal
  • ax ≤
  • min c1x1
  • solution admissible
  • xk z
  • min cx
  • variables
  • variable
Publié le : mardi 27 mars 2012
Lecture(s) : 546
Tags :
Source : homepages.ulb.ac.be
Nombre de pages : 25
Voir plus Voir moins

Algorithme dual simplexe
•Principe :
– Lorsque le primal ne possède pas de sbr
explicitée, mais que le dual en possède une.
– Résoudre implicitement le dual par
l’algorithme du simplexe.
•Avantages :
– Travailler sur le primal, sans devoir rajouter
de variables artificielles.
– Permet de traiter l’ajout de contraintes.
2004/2005 104
Plan du cours
1. Introduction
– Méthodes quantitatives, aide à la décision, modélisation
2. Programmation linéaire
–Exemples
– Définitions - notations
– Résultats fondamentaux
3. Méthodes de résolution
– Dénombrement
– Algorithme du simplexe
4. Dualité
– Définitions et propriétés
– Algorithme dual simplexe
5. Analyse post-optimale
6. Programmation en nombres entiers
7. Modélisation
8. Logiciels : Excel et MPL 4
2004/2005 105
1Coûts marginaux
• Coût marginal d’une variable hors-base
(reduced cost) :
– Effet sur la valeur optimale de z d’une
augmentation unitaire de la variable hors-
base.
• Rappel : Pour une s.r. Q et une s.b.r. K :
z(Q) = z(B) − (z − c )x∑ j j j
j∈J(B)
2004/2005 106
Coûts marginaux
•Soit K une s.b.r. optimale et x hors base k
(k ∈ J(K)).
–Si on augmente x d’une unité (→ x = 1) en k k
laissant toutes les autres variables hors base à
zéro et si la solution obtenue Q est une s.r. :
z(Q) = z(B) −(z − c )k k
– Pour un P.L. à max (min) : z –c > 0 (< 0)k k
représente la perte correspondante sur z.
– z –c est le coût marginal associé à xk k k
2004/2005 107
2
Prix marginaux
• Prix marginal d’une contrainte (shadow
price) :
– Effet sur la valeur optimale de z d’un
accroissement unitaire d’un des b .i
•Soit b = b + e avec e ’ = (0,0,…,1,0,…,0).mod i i
• En la s.b.r. optimale K :
–1 –1X = K b et z = C X = C K bB B B B
2004/2005 108
Prix marginaux
•Si la base K reste optimale pour b :mod
–1 –1z = C K b = C K (b + e )mod B mod B i
–1 –1= z + C K e = z + C (K )B i B i
= z + zi
ème• z = prix marginal de la i contrainte.i
–1(z correspond à la ième colonne de K , dans le tableau optimal)i
2004/2005 109
3
Plan du cours
1. Introduction
– Méthodes quantitatives, aide à la décision, modélisation
2. Programmation linéaire
–Exemples
– Définitions - notations
– Résultats fondamentaux
3. Méthodes de résolution
– Dénombrement
– Algorithme du simplexe
4. Dualité
– Définitions et propriétés
– Algorithme dual simplexe
5. Analyse post-optimale
6. Programmation en nombres entiers
7. Modélisation
8. Logiciels : Excel et MPL 4
2004/2005 110
PL en variables 0-1
• Définition (forme canonique) :
min c x + c x +…+c x()1 1 2 2 n n
⎧ a x + a x +…+a x ≥ b11 1 12 2 1n n 1 min cX⎪ a x + a x +…+a x ≥ b21 1 22 2 2n n 2 ⎧AX ≥ b⎨ ⎨ n…⎪ X ∈B⎩ 2a x + a x +…+a x ≥ b⎩ m1 1 m2 2 mn n m
x ,x ,…,x ∈{}0;1 et c ,c ,…,c ≥ 01 2 n 1 2 n
avec B = {0;1}2
2004/2005 111
4Terminologie
n• Solution : X ∈ B
2
• Solution admissible (solution réalisable) :
Solution X avec : t = b – AX ≤ 0
n• NB: Nombre de s. admissibles fini : ≤ 2
2 3 42 = 4 2 = 8 2 = 16
10 202 = 1.024 2 = 1.048.576
100 302 = 1,3x10
2004/2005 112
Algorithme de résolution
• Procédure de séparation et d’évaluation
séquentielle (PSES).
• Construction d’une arborescence :
– Chaque sommet correspond à un ensemble
de solutions.
– Au départ, toutes les variables sont libres
(valeur non fixée).
– Progressivement, on fixe les valeurs de
certaines variables.
2004/2005 113
5PSES
• Principe de séparation :
– Choisir une variable libre et construire deux
sous-ensembles de solutions, suivant que
cette variable est portée à 0 ou à 1.
Continuer ainsi jusqu’à obtenir des sous-
ensembles sondables.
• Utilisation de vecteurs φ-booléens :
– Vecteurs dont les composantes peuvent être
égales à 0, 1 ou φ (si la variable
correspondante est libre) → correspondent à
des sous-ensembles de solutions.
2004/2005 114
Exemple
( )φ φ φ φ φ• n = 5
S0
x = 12x = 02
( )( ) φ 1 φ φ φSφ 0 φ φ φ S1 2
x = 0 x = 14 4
S ( )( ) φ 1 φ 1 φφ 1 φ 0 φ S 43
x = 11x = 01
( )( ) S 1 1 φ 0 φ0 1 φ 0 φ S 65
2004/2005 115
6Ensemble sondable
• Ensemble qui ne doit plus être séparé
parce que :
1. On connaît la meilleure solution de
l’ensemble.
2. On connaît une solution meilleure que
toutes celles de l’ensemble.
3. On sait que l’ensemble ne contient aucune
solution admissible.
2004/2005 116
Principe de la PSES
• L’arborescence est parcourue
séquentiellement, en commençant par
les branches de droite (variables portées
à 1) jusqu’à rencontrer un ensemble
sondable.
• A chaque étape, un vecteur de
régression (liste), noté R, est mis à jour.
2004/2005 117
7Vecteur de régression
• Au départ : R = ∅,
• Lorsqu’une variable est portée à 1, on ajoute son indice
dans R :
x , x , x successivement portées à 1 → R = ( i j k )i j k
• Lorsqu’un ensemble sondable est atteint, on remonte
d’un niveau dans l’arborescence et on porte à 0 la
dernière variable fixée à 1. Dans R, l’indice
correspondant est souligné :
→ R = ( i j k )
• On continue à se déplacer vers la droite jusqu’à obtenir
un nouvel ensemble sondable :
x portée à 1 → R = ( i j k l )l
2004/2005 118
Vecteur de régression (2)
• Si l’ensemble est sondable, on remonte et on fixe x à 0 :l
→ R = ( i j k l )
• Si le sous-ensemble obtenu est sondable, on remonte
dans l’arborescence d’autant de niveaux qu’il y a de
variables soulignées à la fin du vecteur R, et on porte à 0
la première variable non-soulignée rencontrée :
→ R = ( i j )
• On continue jusqu’à ce que R = ∅. Toute l’arborescence
a alors été sondée (du moins implicitement) et la
meilleure solution trouvée est une solution optimale du
programme.
2004/2005 119
8Fonction d’évaluation
•Soit S un sous-ensemble de solutions de
l’arborescence :
–vecteur φ-booléen X.
– on construit le vecteur booléen X en
remplaçant les φ de X par des 0.
–on pose B(S) = c X
• B(S) est une borne inférieure :
n
cX ≤ min c x∑ j j
X∈S j=1
2004/2005 120
Tests d’optimalité et
d’admissibilité
•Soit S un sous-ensemble de solutions à
analyser :
–vecteur φ-booléen X
– Xopt - la meilleure solution admissible
trouvée
– Vopt - la valeur de la fonction économique
en Xopt
(initialisation : Vopt = ∞)
2004/2005 121
9
Tests d’optimalité
•T : test d’optimalité1
–Si c X ≥ V : S ne peut contenir de solution opt
meilleure que X → S est sondable →opt
régression.
–Si c X < V : S peut contenir des solutions opt
admissibles meilleures que X → test Topt 2
•T : test d’optimalité conditionnelle2
∀x = φ : on pose x = 0 si cX + c ≥ Vj j j opt
→ permet d’accélérer la procédure.
2004/2005 122→ test T3
Tests d’admissibilité
•T : test d’admissibilité3
–Soit t = b – A X
–Si t ≤ 0 :
X est une solution admissible meilleure que Xopt
(par T )1
→ on pose Xopt = X et Vopt = c X
→ régression.
–Si t possède au moins une composante positive :
X n’est pas admissible.
→ test T4
2004/2005 123
10

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.