Chapitre 6 : Programmation linéaire, Algorithme du
simplexe
ENSIIE - Module de Recherche Opérationnelle
Dimitri Watel ([Link]@[Link])
2016-2017
Dimitri Watel MRO Chap 06 PL Simplex
Objectif
Résoudre un programme linéaire quelconque de la forme
Minimiser c ·x
s.c. A·x = b
x ∈ (R+ )n
Dimitri Watel MRO Chap 06 PL Simplex
Forme standard d’un programme linéaire
Théorème
Tout programme linéaire à variables continues peut être réécrit sous
la forme standard suivante :
Minimiser c ·x
s.c. A·x = b
x ∈ (R+ )n
Preuve au tableau
Dimitri Watel MRO Chap 06 PL Simplex
Forme standard d’un programme linéaire : Exemple
Maximiser y
s.c. 20x − 50y ≥ −150 (1)
2x + 3y ≤ 18 (2)
2x ≥ 8 (3)
y ≤ 5 (4)
x, y ∈ R
Dimitri Watel MRO Chap 06 PL Simplex
Variables d’écart
Toute inéquation X
aij · xi ≤ bj
peut être transformée en une égalité en rajoutant une variable
d’écart s ≥ 0 : X
(aij · xi ) + s = bj
.
(Explication graphique au tableau)
Dimitri Watel MRO Chap 06 PL Simplex
Notations
Minimiser c · tx
t
s.c. A · tx = b
x ∈ (R+ )n
n : nombre de variables. n = |x| = |c| = nb colonnes de A
m : nombre de contraintes. m = |b| = nb lignes de A
Li : ligne i de A
Cj : colonne j de A
On suppose m < n et que rg (A) = m. Sinon
contraintes redondantes : on peut supprimer des contraintes.
ou pas de solution réalisable.
Dimitri Watel MRO Chap 06 PL Simplex
Ensemble des solutions réalisables
Définition
Une solution est dite réalisable si elle satisfait toutes les contraintes
d’égalité et que toutes les variables sont positives.
Une solution optimale est une solution réalisable minimisant
l’objectif.
Soit S l’ensemble des solutions réalisables.
Théorème
S est convexe.
(Preuve au tableau)
Dimitri Watel MRO Chap 06 PL Simplex
Solution de base
Définition
Une solution de base est un point x de (R+ )n satisfaisant
Ax = b
n − m coordonnées de x sont nulles
soit B = (i1 , i2 , . . . , im ) les indices des autres coordonnées,
alors les colonnes (Ci1 , Ci2 , . . . , Cim ) sont linéairement
indépendantes.
B est la base associée à x.
Dimitri Watel MRO Chap 06 PL Simplex
Solution de base : exemple
Minimiser x −y
s.c. −x − y + s = 1 (1)
x, y , s ∈ R+
(Explication graphique au tableau)
Dimitri Watel MRO Chap 06 PL Simplex
Solution de base : notations
Soit x une solution de base où B = {i1 , i2 , . . . , im } et, pour tout
j 6∈ B, xj = 0.
B = {i1 , i2 , . . . , im } N = J1; nK\B
B
A = (Ci )i∈B AN = (Ci )i∈N
x B = (xi )i∈B x N = (xi )i∈N = 0
A · x = AB · x B + AN · x N = AB · x B = b
B est carrée et inversible : x B = (AB )−1 · b.
Remarque : si y n’est pas une solution de base associée à B, alors
y N 6= 0 et y B = (AB )−1 · b − (AB )−1 · (AN ) · y N .
Dimitri Watel MRO Chap 06 PL Simplex
Solution de base réalisable
Définition
Une solution de base est dite réalisable ssi toutes ses composantes
sont positives.
Autrement dit une solution de base réalisable est une solution de
base qui est réalisable.
(Explication graphique au tableau)
Dimitri Watel MRO Chap 06 PL Simplex
Point extrême
Définition
Un point extrême de S est un point qui ne peut s’exprimer comme
combinaison linéaire convexe d’autres points de S
p
P P
Combinaison linéaire convexe : x = λi · yi , λi = 1,
i=1
0 ≤ λi ≤ 1.
Théorème
L’ensemble des solutions de bases réalisables et des points extrêmes
de S sont identiques.
(Preuve au tableau)
Dimitri Watel MRO Chap 06 PL Simplex
Solution de base optimale
Théorème
Si S est borné, tout point de S peut s’exprimer comme
combinaison linéaire convexe de points extrêmes.
Théorème
Si S est borné, il existe toujours une solution optimale qui est
solution de base réalisable.
(Explication graphique et preuve au tableau)
Dimitri Watel MRO Chap 06 PL Simplex
Solution de base dégénérée
Définition
Une solution de base (x B , x N ) est dite dégénérée si une des
composantes de x B = 0.
On dit que le programme est dégénéré si certaines de ses solutions
de base réalisables sont dégénérées.
(Explication graphique au tableau)
Dimitri Watel MRO Chap 06 PL Simplex
Coût réduit
Définition
Soit x = (x B , x N ) une solution de base réalisable associée à B.
Pour tout j ∈ N, le coût réduit ∆j de x est :
X
∆j = c j − ci · a¯ij
i∈B
où a¯ij est la composante (i, j) de la matrice (AB )−1 · AN .
(Intuition graphique au tableau)
Dimitri Watel MRO Chap 06 PL Simplex
Coût réduit et Kuhn Tucker (Version minimisation)
Théorème
Si le programme est non dégénéré, une solution de base réalisable
(x B , x N ) vérifiant
∆j ≥ 0
pour tout j ∈ N est optimale.
(Démonstration à l’aide des conditions de Kuhn-Tucker au tableau.)
Dimitri Watel MRO Chap 06 PL Simplex
Algorithme du simplexe (Version minimisation)
Entrées: Un programme linéaire (P) sous forme standard
Sorties: Une solution optimale de (P)
1: Trouver une solution de base réalisable x = (x B , x N ) de (P)
2: ∆j ← Coûts réduits de x
3: Tant que ∃j \ ∆j < 0 Faire
4: Ā ← ((AB )−1 · AN )
5: b̄ ← ((AB )−1 · b)
6: n e |e ∈ N)
e = arg min(∆ o
7: s = arg min ab̄¯iei |i ∈ B, a¯ie > 0
8: Dans la base B, remplacer s par e
9: x ← La solution de base (réalisable) associée à B
10: ∆j ← Coûts réduits de x
11: Renvoyer x
Dimitri Watel MRO Chap 06 PL Simplex
Comment trouver une solution de départ ?
Pour l’instant,
au hasard
on vous l’a donnée
vous avez déjà lu la fin du cours
Dimitri Watel MRO Chap 06 PL Simplex
Méthode des tableaux
Idée : présenter les calculs différemment afin de les simplifier.
Au programme, vu en TD...
Dimitri Watel MRO Chap 06 PL Simplex
Méthode des 2 phases
Méthode des 2 phases
La méthode des 2 phases permet de trouver une solution de
base réalisable d’un programme linéaire (P) quelconque.
Idée : transformer le programme linéaire (P) en un autre (Q) tel
que
(Q) a une solution de base réalisable triviale
(P) a une solution réalisable ssi les solutions optimales de (Q)
a pour fonction objective 0
dans ce cas, on peut trouver une solution de base réalisable de
(P) à partir d’une solution optimale de (Q)
Dimitri Watel MRO Chap 06 PL Simplex
Méthode des 2 phases : transformer le programme linéaire
On veut résoudre ce programme :
Minimiser c · tx
t
s.c. A · tx = b (P)
x ∈ (R+ )n
Hypothèse : t b ≥ 0.
(Si ce n’est pas le cas, il suffit de multiplier toutes les contraintes
où bi < 0 par −1)
Dimitri Watel MRO Chap 06 PL Simplex
Méthode des 2 phases : transformer le programme linéaire
Minimiser c · tx
t
s.c. A · tx = b (P)
x ∈ (R+ )n
P
Minimiser ϕi
t
s.c. A · tx + tϕ = b (Q)
x, ϕ ∈ (R+ )n
(Preuve que (Q) vérifie bien les 3 propriétés énoncées 2 slides plus
tôt au tableau)
Dimitri Watel MRO Chap 06 PL Simplex
Méthode des 2 phases : algorithme
Entrées: Un programme linéaire sous forme standard (P) où b ≥ 0
Sorties: Une solution optimale de (P)
1: Transformer (P) en un programme linéaire (Q) comme expliqué
précédemment.
2: Résoudre (Q) avec l’algorithme du simplexe ((Q) a une solution
de base réalisable triviale à partir de laquelle on peut démarrer)
∗ , ϕ∗ ← une solution optimale de (Q)
3: xQ Q
4: Si ϕ∗Q 6= 0 Alors
5: (P) n’a pas de solution réalisable, on s’arrête.
6: Sinon
7: xQ∗ est une solution de base réalisable de (P)
8: Résoudre (P) avec l’algorithme du simplexe.
Phase 1 : lignes 1 à 3
Phase 2 : lignes 4 à 8
Dimitri Watel MRO Chap 06 PL Simplex