Programmation linéaire.
Méthode du simplexe.
28 février 2012
Table des matières
1
0.1 Opération de pivotage.
Définition 1 Etant donnée une m × n matrice A, 1 ≤ r ≤ m et 1 ≤ s ≤ n tels
que Asr 6= 0. La matrice D définie par :
1 si j = i, j 6= r
1
As si j = i = r
Dij = Asir
− As si j = r, i 6= r
r
0 sinon
est appelée matrice de pivotage sur l’élément Asr de A.
Théorème 2 Si on applique l’opération de pivotage à la matrice (A, b) du sys-
tème Ax = b, on obtient la matrice (DA, Db). Le système DAx = Db est
équivalent à Ax = b.
0.2 Algorithme du simplexe à la main.
max z = x1 + 2x2
x1 + x2 + x3 =6
x2 + x4 =3
x1 , x2 , x3 , x4 ≥ 0
l’algorithme consiste à construire une suite de bases réalisables, de profit
croissant jusqu’à ce qu’il n’y ait plus de gain possible.
(voir cours pour l’exemple)
1 Algorithme du simplexe .
Théorème 3 Etant donné un programme linéaire
max z = ζ + cx
(P P ) Ax = b
x≥0
où A est une matrice m × n de rang m. (P P ) est écri sous forme canonique par
rapport à une base B.
1. Si c ≤ 0 la base B est optimale, et la solution de base associée est solution
optimale de (P P ).
2. S’il existe s une colonne de A : As ∈
/ B, avec cs > 0 et I = {i : Asi > 0} =
∅ alors (P P ) n’a pas de solution optimale.
2
s
h : Ai ∈
3. S’il existe s une colonne de A / B, avec cs > 0 et I = {i : Asi > 0} =
6
br bi
∅. Soit r tel que Asr = min Asi et soit xt la variable correspondant à la
i∈I
ième t
r ligne de base càd que A = er alors on vérifie après pivotage de la
matrice des coéfficients de (P P ) sur Asr , que la base B 0 = B + {As }\{At }
est réalisable et que le nouveau programme est écrit sous forme canonique
par rapport à la nouvelle base B 0 .
1.1 Exemple.
Le programme (P ) est écrit sous forme canonique par rapport à la base
réalisable B 0 = [3, 4, 5](on écrit les indices des colonnes de A qui sont dans la
base).
2x1 + x2 + x3 =8
x1 + 2x2 + x4 =7
(P ) x2 + x5 = 3
xi ≥ 0, j = 1, ..., 5
4x1 + 5x2 = z(max)
La solution de base associée à B 0 est
x1 = 0, x2 = 0, x3 = 8, x4 = 7, x5 = 3 et z = 0.
cN = (4,
5) > 0, choisissons
par exemple l’indice 1 qui entre en base c1 = 4 > 0,
2 8
A1 = 1 et b̄ = 7 .
0 3
bi
; A1i > 0 = min 82 , 17 = 82 = b11 =⇒ B(r) = 3 sort de la base la
min 1
Ai A1
nouvelle base est B 1 = [1, 4, 5].
Aprés pivotage sur A11 on obtient
x1 + 12 x2 + 12 x3 = 4
3 1
2 x2 − 2 x3 + x4 = 3
(P ) ≡ x2 + x5 = 3
x ≥ 0, j = 1, ..., 5
i
3x2 − 2x3 = −8 + z(max)
1
2 4
c = (0, 3, −2, 0, 0) c2 > 0 A2 = , b̄ = 3 , min{ 41 , 33 , 3 } = b2 =
3
2 2 2
1 A22
1 3
2 =⇒ B(r) = 4, la nouvelle base est B 2 = [1, 2, 5] aprés pivotage sur A22 on
obtient
x1 + 32 x3 − 13 x4 = 3
x2 − 31 x3 + 23 x4 = 2
1 2
(P ) ≡ 3 x3 − 3 x4 + x5 = 1
xi ≥ 0, j = 1, ..., 5
−x3 − 2x4 = −22 + z(max)
3
0, −1,−2) ≤ 0, d’où la base est optimale et la solution de base est
c̄ = (0,
3
0
xB2 = 2 , xN2 = et z(max) = 22 .
0
1
1.2 Algorithme du simplexe.
On dispose d’une base réalisable B 0 .
1. B 0 base réalisable du départ. Itération k = 0.
2. k ( k + 1.
3. à l’itération k. Soit B la base courante x = (xB , xN ) la solution de base
correspondante : calculer
b̄ = B −1 b
π = cB B −1 (les multiplicateurs du simplexe)
cN = cN − πN
4. si cN ≤ 0 : l’optimum est atteint.
si ∃s tel que cs > 0 alors
5. soit As la colonne s de A : calculer As = B −1 As
– si As ≤ 0 stop : l’optimum est n non bornéo(+∞)
– sinon calculer xbs = As = min Ab̄is : Asi > 0
b̄r
r i
6. soit xt la variable correspondant à la rième ligne de la base, càd telle que
B −1 At = er (m-vecteur à composantes toutes nulles sauf la composante
r égale à 1); alors la variable s prend la valeur xbs > 0 (entre en base) ; la
variable t s’annule (xbt = 0)( sort de la base) la nouvelle base réalisable B
b=
s t −1
B + {A } − {A } , calculer l’inverse de la nouvelle base B et retourner
b
à (2).
Remarque 4 - Dans (6) on a supposé que xbs > 0 càd que b̄r > 0. Si b̄r = 0
alors la nouvelle solution obtenue est la même que la précédente, et ce sommet
est représenté par plusieurs bases réalisables c’est un cas de dégénéréscence. Si
(P )est écrit sous forme canonique par rapport à une base optimale B̂ alors :
- Si cÑ < 0 la solution de (P ) est unique.
- Si ∃cs = 0, s ∈ N̂ alors la solution n’est pas unique en générale.
n o
On peut choisir x̂s = min bi : A cs > 0 , on détermine ainsi un ensemble de
b
cs
A i
i
solutions réalisable pour lesquels z = ζ̂.
Théorème 5 Convergence finie.
Sous l’hypothèse de non-dégénéréscence, l’algorithme du simplexe converge
en un nombre fini d’itérations.
Démonstration. Il suffit d’observer que le nombre de sommets est fini, et
que la croissance stricte de z interdit de passer deux fois par le même sommet.