Embed Size (px)
Citation preview
Décomposition de Benders;
cas linéaire
( ) ( )( )
T
La décomposition de Benders est bien adapté pour solutionnerdes problèmes comportant des variables contrariantes.
Considérons le problème typique suivant Min
Sujet à,
o0
ù ,
P
b
f y
F y
y
c x
Ax
xx
Yc
+
∈− ≥
≥∈
( ) ( ) ( )
1 21
T
1
, , est une matrice , est une fonctionà valeurs réelles, et , , est un vecteur de
fonctions à valeurs réelles.
n n
m
R y R A m n f
F y f y f y
m
∈ ×
= …
Les sont à traiter dans le sens où elles apparissent linéairement dans le problème, ce qui n'est pasnécessairement le cas p v
variables faciles
ariables contrariou anr les .tes
x
y
Par exemple les variables peuvent être contraintes à prendre des valeurs entières, et alors nous avons un problème de programmation linéaire mixte si les fonctions , et sont linéaires.
y
f F
Problème équivalent
( ) ( )( )
( )
T
Hypo
Déter
thèse
minons d'abord un problème équivalent àMin
Sujet à, .
. La matrice est de plein rang. possède une solution optim
s
ale fi e
0
ni .
:
f y
F y
y
P
b
i Aii P
c x
Ax
Yx
+
− ≥∈≥
( )( )
( ) ( ) ( ){ }{ }1
T
1 0
de sur l'espace des variables contrariantes pourgénérer le problème equivalent :
Min
Projec
Min :
tion
y Y x
P
EP
EP f y c x Ax F y b∈ ≥
+ ≥ +
( )( )
( ) ( ) ( ){ }{ }1
T
1 0
de sur l'espace des variables contrayantes pourgénérer le problème equivalent :
Min
Projec
Min :
tion
y Y x
P
EP
EP f y c x Ax F y b∈ ≥
+ ≥ +
( ){ }Dénotons par
= : il existe au moins un 0 tel que .y x Ax F y bΓ ≥ ≥ +
( )( )
* *
*
Puisque par l'hypothèse . il existe une solution optimale ,de , alors il s'ensuit que . Ainsi .
ii x y
P y Y Y∈ Γ Γ ≠ Φ∩ ∩
( ){ }
( ){ }T
0
De plus, puisque pour tout , : , 0 ,
alors pour ces valeurs de , par conventionMin : .
x
y
x Ax F y b x
y
c x Ax F y b≥
∉Γ≥ + ≥ = Φ
∉Γ≥ + = ∞
( )( )
( ) ( ) ( ){ }{ }1
T
1 0
de sur l'espace des variables contrayantes pourgénérer le problème equivalent :
Min
Projec
Min :
tion
y Y x
P
EP
EP f y c x Ax F y b∈ ≥
+ ≥ +
( ){ }
( ){ }T
0
De plus, puisque pour tout , : , 0 ,
alors pour ces valeurs de , par conventionMin : .
x
y
x Ax F y b x
y
c x Ax F y b≥
∉Γ≥ + ≥ = Φ
∉Γ≥ + = ∞
( ) ( )( )
( ) ( ) ( ){ }{ }
1 2
T
2 0
Ainsi il n'y a pas de perte de généralité de restreindre à appartenir à Γ dans . Donc le problème suivant est équivalent à :
Min Min : .y Y x
yEP EP
P
EP f y c x Ax F y b∈ Γ ≥
+ ≥ +∩
Pour une valeur fixée de , considérons la paire de problèmesprimal-dual suivante:
y
( )( )
TMin sujet à
0
yP c x
Ax F y b
x
≥ +≥
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
{ }( )
( )
T
* *
*
Notons d'abord que le domaine réalisable du dual n'est pas vide.: : , 0 .En effet, puisque qu'il existe une solution optimale , de
,alors est solution optimal d
u A u c u
x y
P x
≤ ≥ ≠ Φ
*u primal lorsque .Par le théorème de dualité en programmation linéaire, il s'ensuitque le dual possède une solution optimale.
y y=
( ) ( ) ( ){ }{ }T
2 0 Min Min :
y Y xEP f y c x Ax F y b
∈ Γ ≥+ ≥ +
∩
Pour une valeur fixée de , considérons la paire de problèmesprimal-dual suivante:
y
( )( )
TMin sujet à
0
yP c x
Ax F y b
x
≥ +≥
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
{ }T
Appliquons le théorème de Goldman au domaine réalisable du dual: : , 0 ,et puisque par hypothèse, la matrice est de plein rang
est l'enveloppe convexe des points
u A u c u K C
AK
≤ ≥ = +
=
{ }{ }
T
T
extrêmes de: , 0
: 0, 0 .u A u c u
C u A u u
≤ ≥
= ≤ ≥
{ }T
Appliquons le théorème de Goldman au domaine réalisable du dual: : , 0 ,et puisque par hypothèse, la matrice est de plein rang
est l'enveloppe convexe des points
u A u c u K C
A
K
≤ ≥ = +
=
{ }{ }
T
extrêmes de: , 0
: 0, 0 .T
u A u c u
C u A u u
≤ ≥
= ≤ ≥
{ } { }{ }
1 T
1
Soient
, , l'ensemble des points extrêmes de : , 0
, , l'ensemble des générateurs du cône
p
q
u u u A u c u
v v C
≤ ≥…
…
{ }{ }
T
est l'enveloppe convexe des points extrêmes de: , 0
: 0, 0 .T
K
u A u c u
C u A u u
=≤ ≥
= ≤ ≥
{ } { }{ }
1 T
1
Soient
, , l'ensemble des points extrêmes de : , 0
, , l'ensemble des générateurs du cône
p
q
u u u A u c u
v v C
≤ ≥…
…
{ }T
1 1
11
1 q
Par conséquent, si : , 0 , alors
, , ,ou encore
où
1 , , , 0
, , 0
p qj j
j j
j j
p
j p
j
u u A u c u
u z t z K t C
u u vα β
α α α
β β
= =
=
∈ ≤ ≥
= + ∈ ∈
= +
= ≥
≥
∑ ∑
∑ …
…
{ }1
Contraintes équivalentes à la condition spécifiées en
termes des générateurs du cône , , q
y
v v
∈Γ
…
( ) ( )( )T
Pour n'importe laquelle valeur de ,
borné 0supérieurement
Théorème
,
1
1,
.j
y
y
D F y b v
j q
+ ≤⇔ ∀ = …
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
( )
( )( )T
Procédons par contradiction pour démontrerla nécessité des conditions. Pour ce faire, supposons qu'il existe
un indice , 1
Preuve. nécessit
, tel q e
é
u 0.kk k q F y b v≤ ≤ + >
( )Considérons une solution quelconque du problème .
Alors .yu D
u z t= +
( )T T
Il est facile de vérifier que pour tout 0,
puisque 0, 0, 0, 0 .
k
k k
t v C
A v A t v t
λ
λ
λ λ
≥
+ ∈
≤ ≤ ≥ ≥
( ) ( )( )T
Pour n'importe laquelle valeur de ,
borné 0supérieurement
Théorème
,
1
1,
.j
y
y
D F y b v
j q
+ ≤⇔ ∀ = …
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
( )Preuve. nécessité
( )Considérons une solution quelconque du problème .
Alors .yu D
u z t= +
( )T T
Il est facile de vérifier que pour tout 0,
puisque 0, 0, 0, 0 .
k
k k
t v C
A v A t v t
λ
λ
λ λ
≥
+ ∈
≤ ≤ ≥ ≥
( )
( )( ) ( ) ( )( ) ( )( )
( )
T T T
Par conséquent est une solution réalisable de .
Mais la valeur de la fonction économique du dual devient
,
une contradiction puisque par hypothèse, est borné.
ky
k k
y
z t v D
F y b u v F y b u F y b v
D
λ
λ
λ λ→∞
+ +
+ + = + + + → ∞
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
( )
1 1
1 1 q1
La suffisance des conditions est vérifiée par simplessubstitutions. En effet
où 1 , , , , , , 0.
suffi
sa ce
n
p qj j
j j
j j
p
j p
j
u z t u vα β
α α α β β
= =
=
= + = +
= ≥
∑ ∑
∑ … …
( )( ) ( )( ) ( )( )
( )( )
( )( )
T T T
1 1
T
1T
Alors
puisque 0, 0,
1, ,
p qj j
j j
j j
pj
j
j
jj
F y b u F y b u F y b v
F y b u
F y b v
j q
α β
α
β
= =
=
+ = + + +
≤ +
+ ≤ ≥
=
∑ ∑
∑
…
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
( )( ) ( )( ) ( )( )
( )( )
( )( )
T T T
1 1
T
1T
Alors
puisque 0, 0,
1, ,
p qj j
j j
j j
pj
j
j
jj
F y b u F y b u F y b v
F y b u
F y b v
j q
α β
α
β
= =
=
+ = + + +
≤ +
+ ≤ ≥
=
∑ ∑
∑
…
( )( ){ }1
T
1, ,où Max .
p
j
j
j
j p
M M
M F y b u
α=
=
≤ =
= +
∑
…□
{ } ( )( )T
Corollaire 2:
0 .1, ,
jF y b v
yj q
+ ≤∈Γ ⇔ ∀ = …
( )
( )( )T
Procédons par contradiction pour démontrerla nécessité des conditions. Pour ce faire, supposons qu'il existe
un indice , 1
Preuve. nécessit
, tel q e
é
u 0.kk k q F y b v≤ ≤ + >
( )Par le théorème 1, il s'ensuit que n'est pas borné supérieurement.yD
( )Mais alors, par le théorème de dualité forte en programmation
linéaire, n'est pas réalisable et .yP y ∉Γ
{ } ( )( )T
Corollaire 2:
0 .1, ,
jF y b v
yj q
+ ≤∈Γ ⇔ ∀ = …
( )
( )( )( )
T
Pour démontrer la suffisance des conditions
supposons que 0, 1, , . Par le
théorème 1, il s'en
Preuve.
suit que est borné supérieuremen
suffisance
t.
j
y
F y b v j q
D
+ ≤ = …
( ) ( )Ainsi, puisque est réalisable, alors possède une solution
optimale.y yD D
( )Par le théorème de dualité forte en programmation linéaire, il
s'ensuit que possède également une solution optimale
finie, et .yP
y ∈Γ □
( ) ( ) ( ){ }{ }
{ } ( )( )
T2
0
T
à partir de
Min Min :
en utilisant le corollaire 2
0 .1, ,
po
Poursuivons la dérivation du problème équi
ur remplacer la contraint
valen
e par n
t
u
y Y x
j
EP f y c x Ax F y b
F y b vy
j q
y
∈ Γ ≥+ ≥ +
+ ≤∈Γ ⇔ ∀ =
∈Γ
∩
…
ensemble de contraintes explicitement spécifiées en termes des générateurs du cône
( ) ( ) ( ){ }{ }
( )( )
T3
0
T
Min Min :
Sujet à 0, 1, ,
y Y x
j
EP f y c x Ax F y b
F y b v j q
∈ ≥+ ≥ +
+ ≤ = …
( ) ( ) ( ){ }{ }
( )( )
T3
0
T
Min Min :
Sujet à 0, 1, ,
y Y x
j
EP f y c x Ax F y b
F y b v j q
∈ ≥+ ≥ +
+ ≤ = …
( )
( )( )T
Maintenant, se rapportant à la preuve du corollaire 2,
possède une solution optimale finie lorsque les conditions
0
1, ,sont vérifiées.
y
j
D
F y b v
j q
+ ≤ ∀ = …
( ){ } ( )( ){ }TT T
0 0
Alors, dans ce cas, par le théorème de dualité forte en programmation linéaire,
Min : Max : .x u
c x Ax F y b F y b u A u c≥ ≥
≥ + = + ≤
( ) ( ) ( ){ }{ }
( )( )
T3
0
T
Min Min :
Sujet à 0, 1, ,
y Y x
j
EP f y c x Ax F y b
F y b v j q
∈ ≥+ ≥ +
+ ≤ = …
( ){ } ( )( ){ }TT T
0 0
Alors, dans ce cas, par le théorème de dualité forte en programmation linéaire,
Min : Max : .x u
c x Ax F y b F y b u A u c≥ ≥
≥ + = + ≤
( )
( ) ( ) ( )( ){ }{ }( )( )
3
T T4
0
T
Ainsi, devient
Min Max :
Sujet à 0, 1, ,
y Y u
j
EP
EP f y F y b u A u c
F y b v j q
∈ ≥+ + ≤
+ ≤ = …
( )
( ) ( ) ( )( ){ }{ }( )( )
3
T T4
0
T
Ainsi, devient
Min Max :
Sujet à 0, 1, ,
y Y u
j
EP
EP f y F y b u A u c
F y b v j q
∈ ≥+ + ≤
+ ≤ = …
( )( ){ } ( )( ){ }T TT
1, ,0
De plus, lorsque , alors
Max : Max .j
j pu
y
F y b u A u c F y b u=≥
∈Γ
+ ≤ = +…
( )
( ) ( ) ( )( ){ }{ }( )( )
4
T
51, ,
T
Ainsi, devient
Min Max
Sujet à 0, 1, ,
j
y Y j p
j
EP
EP f y F y b u
F y b v j q
∈ =+ +
+ ≤ =
…
…
( )
( ) ( ) ( )( ){ }{ }( )( )
4
T
51, ,
T
Ainsi, devient
Min Max
Sujet à 0, 1, ,
j
y Y j p
j
EP
EP f y F y b u
F y b v j q
∈ =+ +
+ ≤ =
…
…
( ) ( ){ }
( )( ){ }( )( )
6 0
T0
1, ,T
Min
Sujet à Max
0, 1, ,
y Y
j
j p
j
EP f y y
F y b u y
F y b v j q
∈
=
+
+ =
+ ≤ =
…
…
( )0 4En utilisant une variable fictive , peut s'écrirey EP
( ) ( ){ }
( )( ){ }( )( )
6 0
T0
1, ,T
Min
Sujet à Max
0, 1, ,
y Y
j
j p
j
EP f y y
F y b u y
F y b v j q
∈
=
+
+ =
+ ≤ =
…
…
( )0
6
Puisque apparait dans la fonction économique à minimiser, le problème peut également s'écrire
y
EP
( ) ( ){ }
( )( ){ }( )( )
7 0
T0
1, ,T
Min
Sujet à Max
0, 1, ,
y Y
j
j p
j
EP f y y
F y b u y
F y b v j q
∈
=
+
+ ≤
+ ≤ =
…
…
( ) ( ){ }
( )( ){ }( )( )
7 0
T0
1, ,T
Min
Sujet à Max
0, 1, ,
y Y
j
j p
j
EP f y y
F y b u y
F y b v j q
∈
=
+
+ ≤
+ ≤ =
…
…
Finalement, nous obtenons le problème équivalent suivant:
( ) ( ){ }
( )( )( )( )
0
T
0T
Min
Sujet à , 1, ,
0, 1, ,
y Y
j
j
EP f y y
F y b u y j p
F y b v j q
∈+
+ ≤ =
+ ≤ =
…
…
Méthode de résolution de Benders
( ) ( ){ }
( )( )( )( )
0
T
0T
Dans la méthode de résolution de Benders, le problème équivalent Min
Sujet à , 1, ,
0, 1, ,
est résolu avec l'approche de relaxation.
y Y
j
j
EP f y y
F y b u y j p
F y b v j q
∈+
+ ≤ =
+ ≤ =
…
…
( ) ( ){ }
( )( )( )( )
0
T0
T
Min
Sujet à , 1, ,
0, 1, ,
y Y
j
j
EP f y y
F y b u y j p
F y b v j q
∈+
+ ≤ =
+ ≤ =
…
…
( )
{ }1 T
Déterminer une première relaxation de en
identifiant un point extrême de : , 0 (en
utilisant une phase I du
Initialisation
simplexe par exemple).
. EP
u u A u c u≤ ≥
Soit =1, =0. Aller à l'étape 1.µ ϕ
( )
( ) ( ){ }
( )( )( )( )
0
T
0T
Résoudre la relaxation de
Mi
Étape
n
Sujet à , 1, ,
0 ,
, ,
1.
1
y Y
j
j
EP
EP f y y
F y b u y j
F y b v j
µϕ
µ
ϕ
∈+
+ ≤ =
+ ≤ =
…
…
( )si ou 0, alors il n'y a pas de contraintes du type correspondantµ ϕ =
( )0Soit , une solution optimale de .y y Y EPµϕ∈
( )
( )0Étape 2. Mécanisme pour vérifier si , est ré
Résoudre le
alisable
problème
po
dual
u .
:
r
y
y y E
D
P
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
( )
( )( )T
)
Par le théorème 1, il existe au moins une contrainte du deuxièmetype qui est violée:
Si n'est pas borné su
0 pour un certain ,
périeu
1, ,
re n
.
me t
j
yi
F y b j j
D
v q+ > = …
( )Utiliser le dernier tableau du simplexe lors de la résolution de
pour générer un élement .yD v C∈ɶ
( )( )T
Augmenter de 1 en ajoutant à la relaxation la contrainte
0
et reprendre l'étape 1.
F y b v
ϕ
+ ≤ɶ
–
T Min Sujet à
0
c xAx bx
=≥
Itération où est variable d'entrée : 0
Problème non borné: 0
s s
s
x c
a•
<
≤
T T
00
B
s
R s
B B
x bx x
x
c x c x z
−
= =
= =
–
T Min Sujet à
0
c xAx bx
=≥
Itération où est variable d'entrée : 0
Problème non borné: 0
s s
s
x c
a•
<
≤
T T
00
B
s
R s
B B
x bx x
x
c x c x z
−
= =
= =
T T
Soit obtenu à partir de en augmentant de 1:
1 0 ;00
s
B s s s
s B B s
x x x
x a x b ax x c x c x c
• • − − = = ≥ = +
ɶ
ɶɶ ɶ ɶ
T Min Sujet à
0
c xAx bx
=≥
Itération où est variable d'entrée : 0
Problème non borné: 0
s s
s
x c
a•
<
≤
T T
00
B
s
R s
B B
x bx x
x
c x c x z
−
= =
= =
T T
Soit obtenu à partir de en augmentant de 1:
1 0 ;00
s
B s s s
s B B s
x x x
x a x b ax x c x c x c
• • − − = = ≥ = +
ɶ
ɶɶ ɶ ɶ
} ( )
( )T T T T
Soit
ˆ 1 0 1 00 0 0
ˆ 0
ˆ 0
s s
B B s B B s
b a abx x x
Ax bAx A x x
Ax b
c x c x x c x c c x c
• • − − = − = − = ≥
= ⇒ = − ==
= − = + − = <
ɶ
ɶɶ
ɶ
( )
( )0Étape 2. Mécanisme pour vérifier si , est ré
Résoudre le
alisable
problème
po
dual
u .
:
r
y
y y E
D
P
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
( )
( )( )T
0
Si possède une solution optimale , mais que la valeur
optim
)
ale
,
yD ui
y b u
i
F y+ >
( )( )T
0
alors est augmenté de 1 en ajoutant à la relaxation la contrainte correspondante
.
Reprendre l'étape 1.
F y b u y
µ
+ ≤
( )
( )0Étape 2. Mécanisme pour vérifier si , est ré
Résoudre le
alisable
problème
po
dual
u .
:
r
y
y y E
D
P
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
( )
( )( )T
0
Si possède une solution optimale , et que la valeur
optimale
) yD u
F y b u
iii
y+ ≤
( )0alors , est une solution réalisable et optimale de .y y EP
( )
( )( )T
0
Si possède une solution optimale , et que la valeur
optimale
) yD u
F y b u
iii
y+ ≤
( )0alors , est une solution réalisable et optimale de .y y EP
( )
( )( )
( )( ) ( )( ){ } ( )( )
0T
T T T
01, ,
En effet toutes les contraintes de sont satisfaites à , :
1. 0, 1, ,
2. Pour tout 1, ,
Max .
Aller à l'étape 3.
j
j j
j p
EP y y
y F y b v j q
j p
F y b u F y b u F y b u y=
∈Γ⇒ + ≤ =
=
+ ≤ + = + ≤…
…
…
( ) ( ){ }
( )( )( )( )
0
T0
T
Min
Sujet à , 1, ,
0, 1, ,
y Y
j
j
EP f y y
F y b u y j p
F y b v j q
∈+
+ ≤ =
+ ≤ =
…
…
( )
( ) ( )
( )
T
Il suffit de prendre comme étant les multiplicateurs optÉtape 3. Déterminer une solution optimal
imaux
de ou de résoudre le primal
Min Sujet à
0
e , e
.
d .
y y
x
D P
c x
A
P
x
y
F y
x
b
x
≥ +
≥
Nous appliquons directement la stratégie de relaxationoù 1 puisque l'ensemble comporte l'indice associé àN
ou
ote
à .
. V V
v u
=
ɶ
Cas convexe
( )
( )( )( )( )
1
T
0T
Si est convexe et , , , sont convexes sur , la dimention
de la relaxation peut être réduite en éliminant les
contraintes satisfaites avec inégalité:
, 1, ,
0, 1, ,
à chaqu
m
j
j
Y f f f Y
EP
F y b u y j
F y b v j
µϕ
µ
ϕ
+ < =
+ < =
…
…
…
e fois que la valeur optimale de la restriction eststrictement croissante.
Cas où n’est pas bornée inférieurement(((( ))))µϕEP
( )( )
( )0
Notons que peut ne pas être borné inférieurement si
trop de contraintes de sont relaxées. Dans ce cas, pour
obtenir quand même une solution , de à l'étape 1,
nous devo bons rner artificie
EP
EP
y y EP
µϕ
µϕ
( )le problèmllem e .ent EPµϕ
( )
T
Par exemple, si certaines contraintes spécifiant sont descontraintes de non négativité des variables ( i.e., 0), alors
le problème peut être borné artificiellement en ajoutant
la contrainte
Y
y
EP
e y
µϕ
≥
=
[ ]
2
1T 2où 1, 1 et est un scalaire suffisemment grand.
n
i
i
n
y t
e R t
=
≤
= ∈
∑
…
( )
T
Par exemple, si certaines contraintes spécifiant sont descontraintes de non négativité des variables ( i.e., 0), alors
le problème peut être borné artificiellement en ajoutant
la contrainte
Y
y
EP
e y
µϕ
≥
=
[ ]
2
1T 2où 1, 1 et est un scalaire suffisemment grand.
n
i
i
n
y t
e R t
=
≤
= ∈
∑
…
( )
2T
1
0
Quand la contrainte est active pour une grande valeur de
,
nous pouvons soupçonner que n'est pas borné inférieurement,
mais nous pouvons quand même poursuivre à l'étape 2 avec ,po
n
i
i
t
e y y t
EP
y y
µϕ
=
= =∑
ur générer une contrainte additionnelle.
( )
2T
1
0
Quand la contrainte est active pour une grande valeur de
,
nous pouvons soupçonner que n'est pas borné inférieurement,
mais nous pouvons quand même poursuivre à l'étape 2 avec ,po
n
i
i
t
e y y t
EP
y y
µϕ
=
= =∑
ur générer une contrainte additionnelle.
( )Puisque par hypothèse possède une solution optimale finie,alors cette contrainte additionnelle devient redondante à la finde la résolution.
P
Bornes inférieure et supérieure
sur la valeur optimale
( )
( )( )
0
À chaque itération de la procédure, la valeur optimale
de est une sur le valeur optimale
de
borne inférieure
.
E
f y y
P
E
LB
P
µϕ
+
De plus, puisque la procédure est une application de la stratégiede relaxation, il s'ensuit que la suite des valeurs optimales des relaxations es non décroisst ante.
( )Pour dériver une , remarquons qu'à chaque
itération où possède une solution optimale finie, alors
par la dualité forte en programmation linéaire, il existe une
soluti
borne supér
on optimal
ieure
e f
inie
yD
( )( )( )
TT
de telle que
.
yx P
c x F y b u= +
( )
( ) ( )( ) ( )( )
TT
Mais alors , est une solution réalisable de et la valeurde cette solut
borne supérieure
ion
est une sur la valeur optimale de .
c x f y F y b u f y
x y P
P
+ = + +
Malheureusement, la suite de ces valeurs n'est pas non croissanteau cours des itérations.
Dénotons par générée au coursdes itérations. Cette valeur es
lat m
plus petite borne supérieuise à jour à chaque itérat
rn.
eio
UB
( ) ( ){ }{ }T
0Min Min :
y Y xf y c x Ax F y b
∈ ≥+ ≥ +
( ) ( ){ }{ } ( )T T
0Min :
xf y c x Ax F y b f y c x
≥+ ≥ + = +
( )
( )( )
0
À chaque itération de la procédure, la valeur optimale
de est une sur le valeur optimale
de
borne inférieure
.
E
f y y
P
E
LB
P
µϕ
+
Dénotons par générée au coursdes itérations. Cette valeur es
lat m
plus petite borne supérieuise à jour à chaque itérat
rn.
eio
UB
Si alors la solution associée à la borne supérieure est -optimale.
LB BU εε
− ≤
Illustration du déroulement de la procédure de Benders.
•
••
•
•
••
∗∗
∗∗
∗∗
∗
1 2 3 4 ⋯ itération
( ) valeur optimale de
valeur de la solution ,
EP
x y
µϕ•
∗
UB
LB}ε
solution -optimaleε
Méthode de résolution de Benders
avec bornes
La variante suivante de la méthode de résolution de Benderspermet d'identifier une solution -optimale en ajoutant un critère d'arrêt basé sur
.
Les modifications apportées à la méthode originale
LBUB
ε
ε− ≤
sontindiquée ros en uge.
( ) ( ){ }
( )( )( )( )
0
T0
T
Min
Sujet à , 1, ,
0, 1, ,
y Y
j
j
EP f y y
F y b u y j p
F y b v j q
∈+
+ ≤ =
+ ≤ =
…
…
( )
{ }1 T
Déterminer une première relaxation de en
identifiant un point extrême de : , 0 (en
utilisant une phase I du
Initialisation
simplexe par exemple).
. EP
u u A u c u≤ ≥
Soit Soit =1, =0. Aller à l'étape . 1.UBµ ϕ = ∞
( )
( ) ( ){ }( )( )( )( )
0
T
0T
Résoudre la relaxation de
Min
Sujet à , 1, ,
0,
Étape
, ,
1.
1
j
j
EP
EP f y y
F y b u y j
F y b v j
µϕ
µ
ϕ
+
+ ≤ =
+ ≤ =
…
…
( )si ou 0, alors il n'y a pas de contraintes du type correspondantµ ϕ =
( )0Soit , une solution optimale de .y y Y EPµϕ∈
( ) 0Soit .Si , terminer la procédure car la solution associéeà est -optimale.
LB f y y
UB LB
UB
εε
= +
− ≤
( )
( )0Étape 2. Mécanisme pour vérifier si , est ré
Résoudre le
alisable
problème
po
dual
u .
:
r
y
y y E
D
P
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
( )
( )( )T
)
Par le théorème 1, il existe au moins une contrainte du deuxièmetype qui est violée:
Si n'est pas borné su
0 pour un certain ,
périeu
1, ,
re n
.
me t
j
yi
F y b j j
D
v q+ > = …
( )Utiliser le dernier tableau du simplexe lors de la résolution de
pour générer un élement .yD v C∈ɶ
( )( )T
Augmenter de en ajoutant à la relaxation la contrainte
0
et reprendre l'étape 1.
F y b v
ϕ
+ ≤ɶ
( )
( )0Étape 2. Mécanisme pour vérifier si , est ré
Résoudre le
alisable
problème
po
dual
u .
:
r
y
y y E
D
P
( )
( )( )T
0
Si possède une solution optimale , mais que la valeur
optim
)
ale
,
yD ui
y b u
i
F y+ >
( ) ( )( ){ }T
mettre à jour la borne supérieure
Min , .UB UB f y F y b u= + +
Si , terminer la procédure car la solution associéeà la borne supérieure est -optimale.
UB LB
UB
εε
− ≤
( )( )T
0
est augmenté de 1 en ajoutant à la relaxation la contrainte correspondante
.
Repr
Autrement
endre l'étape 1.
F y b u y
µ
+ ≤
( )
( )0Étape 2. Mécanisme pour vérifier si , est ré
Résoudre le
alisable
problème
po
dual
u .
:
r
y
y y E
D
P
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
( )
( )( )T
0
Si possède une solution optimale , et que la valeur
optimale
) yD u
F y b u
iii
y+ ≤
( )0alors , est une solution réalisable et optimale de .y y EP
( )
( )( )T
0
Si possède une solution optimale , et que la valeur
optimale
) yD u
F y b u
iii
y+ ≤
( )0alors , est une solution réalisable et optimale de .y y EP
( )
( )( )
( )( ) ( )( ){ } ( )( )
0T
T T T
1, ,
En effet toutes les contraintes de sont satisfaites à , :
1. 0, 1, ,
2. Pour tout 1, ,
Max .
Aller à l'étape 3.
j
j j
j p
EP y y
y F y b v j q
j p
F y b u F y b u F y b u=
∈Γ⇒ + ≤ =
=
+ ≤ + = +…
…
…
( ) ( ){ }
( )( )( )( )
0
T0
T
Min
Sujet à , 1, ,
0, 1, ,
y Y
j
j
EP f y y
F y b u y j p
F y b v j q
∈+
+ ≤ =
+ ≤ =
…
…
( )
( ) ( )
( )
T
Il suffit de prendre comme étant les multiplicateurs optÉtape 3. Déterminer une solution optimal
imaux
de ou de résoudre le primal
Min Sujet à
0
e , e
.
d .
y y
x
D P
c x
A
P
x
y
F y
x
b
x
≥ +
≥
Nous appliquons directement la stratégie de relaxationoù 1 puisque l'ensemble comporte l'indice associé àN
ou
ote
à .
. V V
v u
=
ɶ
( )( )
TMin sujet à
0
yP c x
Ax F y b
x
≥ +≥
(((( )))) (((( ))))y yP DRésoudre au lieu de à l'étape 2
( ) ( )
Souvent, une fois la valeur de fixée, le problème en possèdeune structure intéressante. Dans ce cas, il serait plus intéressant
de résoudre plutôt que à l'étape 2 afin d'en profiter.
Mais nousy y
y x
P D
( ) devons avoir un moyen de récupérer les valeurs des
variables et nécessaires pour formuler les relaxations . j ju v EPµϕ
( ) ( )( )T
T
Max Sujet à
0
yD F y b u
A u cu
+
≤≥
( ) ( )( )
TMin Sujet à
, .0
c x
A
P
bx
y
F y
yx
f
Y
+
−∈≥
≥( ) ( ) ( ){ }{ }T
1 0 Min Min :
y Y xEP f y c x Ax F y b
∈ ≥+ ≥ +
( ) ( ){ }
( )( )( )( )
0
T0
T
Min
Sujet à , 1, ,
0, 1, ,
y Y
j
j
EP f y y
F y b u y j p
F y b v j q
∈+
+ ≤ =
+ ≤ =
…
…
(((( )))) (((( ))))y yP DRésoudre au lieu de à l'étape 2
( ) ( )
Souvent, une fois la valeur de fixée, le problème en possèdeune structure intéressante. Dans ce cas, il serait plus intéressant
de résoudre plutôt que à l'étape 2 afin d'en profiter.
Mais nousy y
y x
P D
( ) devons avoir un moyen de récupérer les valeurs des
variables et nécessaires pour formuler les relaxations . j ju v EPµϕ
( )Si , la résolution de génère une solution optimale .
Se référant à la dualité forte en programmation linéaire, il s'ensuitque les multiplicateurs optimaux du simplexe sont une solution
optimale d
yy P x∈Γ
( )e . Nous pouvons donc les utiliser pour générer
une nouvelle contrainte à ajouter à la relaxation.yD
( )Si , la résolution de génère une solution optimale .
Se référant à la dualité forte en programmation linéaire, il s'ensuitque les multiplicateurs optimaux du simplexe sont une solution
optimale d
yy P x∈Γ
( )e . Nous pouvons donc les utiliser pour générer
une nouvelle contrainte à ajouter à la relaxation.yD
( )
Mais il faut remarquer que les multiplicateurs optimaux dusimplexe ne constituent pas nécessairement une solution de base
de , et par conséquent ne constituent pas nécessairement
un point extrême du yD
polytope dual.
Ainsi, une telle solution peut éventuellement s'exprimer commeune combinaison linéaire convexe d'autres solutions du polytopedual générées au cours de l'étape 2.
( )Néanmoins, la procédure converge quand même, et une telle
contrainte dans peut éventuellement devenir redondante.EPµϕ
( ) ( )Maintenant si , n'est pas réalisable et n'est pas
borné supérieurement à l'étape 2. y yy P D∉Γ
( )
( )
T
Dans ce cas, si nous resolvons , la solution optimale , ,
du problème de la phase I
Min sujet à
, , 0( étant les variables d'écart et , les variables artificielles)a une v
yP x s a
e a
Ax Is Ia F y b
x s a
s a
− + = +
≥
T
aleur positive:
0.e a >
( )( )
TMin sujet à
0
yP c x
Ax F y b
x
≥ +≥
Dénotons par le vecteurs de multiplicateurs optimaux.π
π
( )
( )
T
Dans ce cas, si nous resolvons , la soltion optimale , ,
du problème de la phase I
Min sujet à
, , 0( étant les variables d'écart et , les variables artificielles)a une va
yP x s a
e a
Ax Is Ia F y b
x s a
s a
− + = +
≥
T
leur positive:
0.e a >
Dénotons par le vecteurs de multiplicateurs optimaux.π
π
( )( )T
T
Alors est une solution optimale du dual suivant
Max
Sujet à 00.
F y b
A
I
I e
π
π
πππ
+
≤− ≤
≤
Dénotons par le vecteurs de multiplicateurs optimaux.π
( )( )T
T
Alors est une solution optimale du dual suivant
Max
Sujet à 00.
F y b
A
I
I e
π
π
πππ
+
≤− ≤
≤
T 0e a >
T
Par conséquent
0 .0
AC
π ππ
≤ ⇒ ∈≥
( )( )T T
Également, par la dualité forte en programmation linéaire
0. F y b e aπ+ = >
( )( )T
Donc nous pouvons ajouter la contrainte
0
pour générer une nouvelle relaxation où augmente de 1.
F y b π
ϕ
+ ≤
( )( )T
Donc nous pouvons ajouter la contrainte
0
pour générer une nouvelle relaxation où augmente de 1.
F y b π
ϕ
+ ≤
C'est également le cas que n'est pas nécessairement un générateurdu cône. Néanmoins, la procédure converge quand même et la contrainte correspondante peut éventuellement devenir redondante.
π
Programmation linéaire mixte
( )( ) ( ) { }T
Au départ, Benders a développé sa procédure pour résoudre des problèmes de programmation linéaire mixte; i.e., dans
, , et : 0et entiers .
P
f y c y F y Ay Y y y= = = ≥
( ) ( )( )
TMin Suj t
,0e à
.
c x
A
P
bx
y
F y
yx
f
Y
+
−∈≥
≥( ) TTMin Sujet à
0 0, ent, iers.
c y
Ay
P
A b
x
y
c
xx
+
−≥
≥≥
Observons que les hypothèses de convexité ne sont pas vérifiées dans ce cas puisque n'est pas un ensemble convexe.Y
( ) ( )( )
TMin Suj t
,0e à
.
c x
A
P
bx
y
F y
yx
f
Y
+
−∈≥
≥( ) TTMin Sujet à
0 0, ent, iers.
c y
Ay
P
A b
x
y
c
xx
+
−≥
≥≥
( ) ( )( ) ( )
Dans ce cas, et les relaxations sont des problèmes
de programmation linéaire en nombres entiers, et et
sont des problèmes de programmation linéaire.y y
EP EP
P D
µϕ
( ) { }
( )( )
T0
TT0
TT
Min
Sujet à , 1, ,
0, 1, ,
0, entier
j
j
EP c y y
A y b u y j p
A y b v j q
y
+
+ ≤ =
+ ≤ =
≥
…
…
Exemple numérique
1 2 3
1 3
2 3
1 2 3
Min 10 10 15 40 Sujet à 2 2
1, , , 0
x x x y
x x y
x x y
x x x y
+ + +
+ + ≥
+ + ≥
≥
1 2 3 1 3
0 , ,1 2 3 0 2 3
Projection sur l'espace de la variable 10 10 15 : 2 2 ,
Min 40 Min1y x x x
y
x x x x x yy
x x y≥ ≥
+ + + ≥ − + + ≥ −
( ) 1 2 3
1 3
2 3
1 2 3
Min 10 10 15
Sujet à 2 21
, , 0
yP x x x
x x y
x x y
x x x
+ +
+ ≥ −
+ ≥ −
≥
( ) ( ) ( )1 2
1
2
1 2
1 2
Max 2 2 1
Sujet à 101015
, 0
yD y u y u
u
u
u u
u u
− + −
≤
≤
+ ≤
≥
( )Domaine réalisable de yD
1 10u =
2 10u =
1 2 15u u+ =
10
10( )5,10
( )10,5 Points extrêmes0 10 10 5 0
, , , ,0 0 5 10 10
( )[ ]
T
Puisque ce domaine réalisable est borné, alors
domaine réalisable de
puisque se reduit à 0,0 . est l'enveloppe convexe des points extrêmes.
yD K
C
K
=
( ) ( ) ( )1 2
1
2
1 2
1 2
Max 2 2 1
Sujet à 101015
, 0
yD y u y u
u
u
u u
u u
− + −
≤
≤
+ ≤
≥
( )Domaine réalisable de yD
1 10u =
2 10u =
1 2 15u u+ =
10
10( )5,10
( )10,5Points extrêmes0 10 10 5 0
, , , ,0 0 5 10 10
( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )
0
0
0
0
0
0
Min 40
Sujet à 2 2 0 1 0
2 2 10 1 0
2 2 10 1 5
2 2 5 1 10
2 2 0 1 100
EP y y
y y y
y y y
y y y
y y y
y y y
y
+
− + − ≤
− + − ≤
− + − ≤
− + − ≤
− + − ≤
≥
( ) ( ) ( )1 2
1
2
1 2
1 2
Max 2 2 1
Sujet à 101015
, 0
yD y u y u
u
u
u u
u u
− + −
≤
≤
+ ≤
≥
[ ]T1PrenonItération 1 s 0. ,10u =
[ ]
( )( ) ( )
T1
1 0
0 0
Prenons 0,10Ainsi
Min 40
Sujet à 2 2 0 1 10 10 10
Itération 1.
0
u
EP y y
y y y y y
y
=
+
− + − ≤ ≡ ≤ +
≥
( )1
0
0
Solution optimale de 0, 10.
Alors 40 10
EP
y y
LB y y
= =
= + =
1 10u =
2 10u =
1 2 15u u+ =
10
10( )5,10
( )10,5
( ) ( ) ( )1 2
1
2
1 2
1 2
Max 2 2 1
Sujet à 101015
, 0
yD y u y u
u
u
u u
u u
− + −
≤
≤
+ ≤
≥
( ) 0Résoudre avec 0, 10yD y y= =
( ) 1 2
1
2
1 2
1 2
Max 2
Sujet à 101015
, 0
yD u u
u
u
u u
u u
+
≤
≤
+ ≤
≥
( )1 2
1 2
Solution optimale de :
10, 5.
Alors 40 2 25.
yD
u u
UB y u u
= =
= + + =
( ) ( )
1 2 0
0
Puisque 2 25 10,ajouter la contrainte suivante à la relaxation
2 2 10 1 5
u u y
y y y
+ = > =
− + − ≤
( )( ) ( )( ) ( )
2 0
0 0
0 0
Min 40
Sujet à 2 2 0 1 10
Itér
10
a
10
2 2 10 1 5 25 25
tion 2.
0
EP y y
y y y y y
y y y y y
y
+
− + − ≤ ≡ ≤ +
− + − ≤ ≡ ≤ +
≥
( )1
0
0
Solution optimale de 0, 25.
Alors 40 25
EP
y y
LB y y
= =
= + =
( )0
Puisque 25,alors 0, 25 est une solution optimale de .
UB LB
y y EP
= =
= =
( )Pour retrouver la solution , du problème original,
résoudre où 0 :y
x y
P y = ( ) 1 2 3
1 3
2 3
1 2 3
Min 10 10 15
Sujet à 2 21
, , 0
yP x x x
x x y
x x y
x x x
+ +
+ ≥ −
+ ≥ −
≥( ) 1 2 3
1 3
2 3
1 2 3
Min 10 10 15
Sujet à 21
, , 0
yP x x x
x x
x x
x x x
+ +
+ ≥
+ ≥
≥
( ) 1 2 3Solution optimale de : 1, 0, 1.yP x x x= = =
( ) 1 2 3Solution optimale de : 1, 0, 1, 0.Valeur optimale 25.
P x x x y= = = =
=
Illustration graphique
( )Domaine réalisable de EP
1y
2y
( ) ( ){ }
( )( )( )( )
0
T
0T
Min
Sujet à , 1, ,
0, 1, ,
y Y
j
j
EP f y y
F y b u y j p
F y b v j q
∈+
+ ≤ =
+ ≤ =
…
…
![[ MAINE DE BIRAN ] ······ MÉMOIRE DÉCOMPOSITION PENSÉE II --LNPR](https://img.pdfslide.fr/doc/110x75/577d1eb11a28ab4e1e8f07e8/-maine-de-biran-memoire-decomposition-pensee-ii-lnpr.jpg)
