Méthodes et modélisation

pour l’optimisation
M1 informatique, 2024/2025
04 — L’algorithme du simplexe (suite)
 La semaine dernière
max x1 + x2 max x1 + x2
x1 - x 2 ≤ 2 x1 - x 2 + x3 = 2
x1 ≤ 3 x1 + x4 = 3
x2 ≤ 2 x2 + x5 = 2
x 1 , x2 ≥ 0 x1, x2, x3, x4, x5 ≥ 0

programme initial forme équationnelle

x3 = 2 - x 1 + x2
x4 = 3 - x 1
x5 = 2 - x2
z = 0 + x1 + x2
tableau
 La semaine dernière
x3 = 2 - x 1 + x2 x 1 = 2 + x 2 - x3
x4 = 3 - x 1 x4 = 1 - x 2 + x3
x5 = 2 - x2 pivot x5 = 2 - x 2
z = 0 + x1 + x2 z = 2 + 2x2 - x3
base {3, 4, 5} solution (0, 0, 2, 3, 2) base {1, 4, 5} solution (2, 0, 0, 1, 2)
x1 entre, x3 sort x2 entre, x4 sort

x1 = 3 - x4 x1 = 3 - x 4
x 2 = 1 + x 3 - x4 x2 = 2 - x5
x5 = 1 - x 3 + x4 x 3 = 1 + x 4- x 5
z = 4+ x3 - 2x4 z = 5 - x4- x5
base {1, 2, 5} solution (3, 1, 0, 0, 1) base {1, 2, 3} solution (3, 2, 1, 0, 0)
x3 entre, x5 sort
 La semaine dernière
max x1 + x2
x1 = 3 - x4
x1 - x 2 + x3 = 2
x2 = 2 - x5
x1 + x4 = 3
x 3 = 1 + x 4- x 5
x2 + x5 = 2
z = 5 - x4- x5
x1, x2, x3, x4, x5 ≥ 0
base {1, 2, 3} solution (3, 2, 1, 0, 0)
l u t i o n
l a s o
coeffs ≤ 0 — terminaison e r q ue !
v é r i s s i bl e max x1 + x2
a d m i
est
x1 - x 2 ≤ 2
x1 ≤ 3
solution au programme initial : (x1, x2) = (3, 2) x2 ≤ 2
valeur de la fonction objectif = 5
x 1 , x2 ≥ 0
fi
 Qui sort (encore) ?

Considérer le tableau avec les équations :

xi = pi + qi1 x1 + qi2 x2 + … + qij xj + … + qin xn

(les pi et qij sont les coef cients)

Alors, xi sort si xj entre et

x3 = 8 + x1 - 5x2 8/5
x4 = 3 - x1 -

{ qkj }
pk
i= − : qkj < 0 x5 = 7 - 4x2 7/4
k
z = 0 + x1 + 3x2

x3 sort car 8/5 < 7/4

𝖺
𝗋
𝗀
𝗆
𝗂
𝗇
fi
 Tableau

‣ On utilise obligatoirement la notion de tableau

introduite au cours

x3 = 1 + x1 - x2 x1 x2 x3 x4 x5 z
x4 = 3 - x1 -1 1 1 0 0 0 1
x5 = 2 - x2 1 0 0 1 0 0 3
z = 0 + x1 + x2 0 1 0 0 1 0 2
-1 -1 0 0 0 1 0

OUI ! NON !
Et si jamais… ?
 Un autre exemple

max x1 max x1
x1 - x 2 ≤ 1 x1 - x 2 + x3 = 1
- x1 + x 2 ≤ 2 - x1 + x 2 + x4 = 2
x 1 , x2 ≥ 0 x1, x2, x3, x4 ≥ 0

programme initial forme équationnelle

x3 = 1 - x 1 + x2 x1 = 1 + x 2 - x 3
x4 = 2 + x 1 - x 2
z = 0 + x1
x4 = 3 - x3
z = 1 + x2 - x3
?
tableau
 Un autre exemple

‣ il n’y a pas d’équation contraignante — on peut

augmenter x2 par une valeur t ≥ 0 quelconque
‣ pour tout t ≥ 0, la solution suivante est admissible :
(x1, x2, x3, x4) = (1, 0, 0, 3)+t⋅(1, 1, 0, 0)
‣ la valeur de la fonction objectif = 1+t

x1 = 1 + x 2 - x 3
x4 = 3 - x3
z = 1 + x2 - x3
 Un autre exemple

max x1
x1 = 1 + x 2 - x 3
x1 - x 2 ≤ 1
x4 = 3 - x3
- x1 + x 2 ≤ 2
z = 1 + x2 - x3
x 1 , x2 ≥ 0

‣ solutions : (x1, x2, x3, x4) = (1, 0, 0, 3)+t⋅(1, 1, 0, 0)

‣ solutions au programme initial : (x1, x2) = (1, 0)+t⋅(1, 1)
‣ la valeur de la fonction objectif = 1+t
‣ la fonction objectif est non bornée !
Trouver une base
initiale
 Trouver une base initiale

‣ Comment trouver une base initiale pour démarrer

l’algorithme ?

max x1 + x2 max x1 + 2⋅x2

- x1 + x 2 + x 3 = 1 x1 + 3⋅x2 + x3 = 4
x1 + x4 = 3 2⋅x2 + x3 = 2
x2 + x5 = 2 x 1 , x2 , x3 ≥ 0
x1, x2, x3, x4, x5 ≥ 0

facile moins facile ?

 Trouver une base initiale

‣ S’il y a une variable d’écart par ligne et les membres

droits sont non-négatives, alors c’est facile
‣ Mais en général, ce problème est “aussi dif cile” que le
problème d’optimisation
‣ Noter qu’il n’est pas ef cace de tester toutes les bases :

Combien de bases possibles Réponse :

dans une instance ayant le nombre de combinaisons
2n variables et n équations ? de n parmi 2n (colonnes)

( n ) (n!)2
2n (2n)! 4n
= ≥
2n + 1
fi
fi
 Trouver une base initiale
max x1 + 2⋅x2 min x4 + x5
x1 + 3⋅x2 + x3 = 4 x1 + 3⋅x2 + x3 + x4 = 4
2⋅x2 + x3 = 2 2⋅x2 + x3 + x5 = 2
x 1 , x2 , x3 ≥ 0 x 1 , x 2 , x 3 , x 4, x 5 ≥ 0

‣ Supposons qu’on essaye la solution non-admissible

x1 = x 2 = x 3 = 0
‣ Alors, les membres gauches des équations sont plus
petits que les membres droits
‣ On veut minimiser les différences
x4 = 4 - (x1 + 3⋅x2 + x3)
x5 = 2 - (2⋅x2 - x3)
 Trouver une base initiale
max x1 + 2⋅x2 max - x4 - x5
x1 + 3⋅x2 + x3 = 4 x1 + 3⋅x2 + x3 + x4 = 4
2⋅x2 + x3 = 2 2⋅x2 + x3 + x5 = 2
x 1 , x2 , x3 ≥ 0 x 1 , x 2 , x 3 , x 4, x 5 ≥ 0
programme auxiliaire
(type max)
‣ Soit (x1, x2, x3, x4, x5) une solution optimale au
programme auxiliaire
‣ Si l’optimum est 0, alors (x1, x2, x3) est une solution de
base admissible au programme initial
‣ Sinon, le programme initial n’a pas de solution admissible
 Trouver une base initiale
max - x4 - x5
x1 + 3⋅x2 + x3 + x4 = 4 x4 = 4 - x1 - 3⋅x2 - x3

2⋅x2 + x3 + x5 = 2 x5 = 2 - 2⋅x2 - x3

x 1 , x 2 , x 3 , x 4, x 5 ≥ 0 z = -6 + x1 + 5⋅x2 + 2⋅x3
base {4, 5} solution (0, 0, 0, 4, 2)
x2 entre, x5 sort

x2 = 1 -x3/2 -x5/2 x1 = 1 + x3/2 - x4+3x5/2

x4 = 1 - x1 +x3/2 +3x5/2 x2 = 1 - x3/2 - x5/2
z = -1 + x1 -x3/2 -5x5/2 z = 0 - x4 - x5
base {2, 4} solution (0, 1, 0, 1, 0) base {1, 2} solution (1, 1, 0, 0, 0)
x1 entre, x4 sort
 Trouver une base initiale
max x1 + 2⋅x2
x1 = 1 + x3/2 - x4+3x5/2
x1 + 3⋅x2 + x3 = 4
x2 = 1 - x3/2 - x5/2
2⋅x2 + x3 = 2
z = 0 - x4 - x5
x 1 , x2 , x3 ≥ 0
base {1, 2} solution (1, 1, 0, 0, 0)

‣ (x1, x2, x3, x4, x5) = (1, 1, 0, 0, 0)

est une solution optimale au programme auxiliaire
‣ l’optimum est 0, donc (x1, x2, x3) = (1, 1, 0)
est une solution de base admissible au programme initial
qui correspond à la base {1, 2}
 Trouver une base initiale
max cTx max -xn+1-xn+2-…-xn+m
Ax = b A’x’ = b
x≥0 x’ ≥ 0
programme initial programme auxiliaire

‣ Avec variables et equations, supposer que le membre droit de

chaque équation est ≥ 0, c-à-d, bi ≥ 0 (sinon multiplier l’équation par −1)
‣ Ajouter une nouvelle variable par équation : xn+1, xn+2, …, xn+m
‣ A’ = (A | Im), où Im est la matrice identité et x’ = (x1, …, xn, xn+1, …, xn+m)
‣ Résoudre le programme auxiliaire par l’algorithme du simplexe avec la
base admissible initiale B = {n+1, n+2, …, n+m}
‣ Si xn+1 = xn+2 = … = xn+m = 0, alors (x1,...,xn) est une solution de base
admissible au programme initial, sinon le programme initial n’a pas de
solution admissible
𝗇𝗆
L’algorithme du
simplexe
 L’algorithme du simplexe

Hypothèses
‣ On suppose que Ax = b a au moins une solution
‣ sinon, Ax = b, x ≥ 0 n’a pas de solution non plus
‣ peut être détecté par l’élimination de Gauss
‣ On suppose que les lignes de la matrice A sont
indépendantes
‣ sinon, au moins une équation est redondante et peut être
éliminée sans changer les solutions à Ax = b
‣ peut être détecté par l’élimination de Gauss
 L’algorithme du simplexe
Initialisation

1. Convertir le programme en forme équationnelle.

2. Si Ax = b n’a pas de solution, alors
‣ terminer : ``pas de solution’’
3. Faire en sorte que les lignes de A soient indépendantes.
4. Trouver une base initiale (résoudre le programme auxiliaire).
‣ s’il n’y en a pas, terminer : ``pas de solution’’
5. Démarrer la boucle principale avec la base initiale trouvée.
 L’algorithme du simplexe
Boucle principale

1. Exprimer le tableau correspondant à la base courante

2. Si tous les coef cients de z dans le tableau sont ≤ 0, alors
‣ terminer : la solution optimale correspond à la base courante
3. Choisir une variable hors base avec coef cient de z > 0
(la variable entre)
4. Choisir une variable de base ayant une équation parmi les plus
contraignantes (la variable sort)
5. S’il n’y a pas d’équation contraignante, alors
‣ terminer : ``optimum non borné’’
6. Modi er la base courante et GOTO 1
fi
fi
fi
 Questions restantes

‣ S’il y a un choix, comment choisir la variable qui entre

et celle qui sort ?
‣ L’algorithme du simplexe termine-t-il toujours ?
‣ L’algorithme du simplexe est-il ef cace ?

fi
 Critère de pivot
qui entre ? qui sort ?
Critère de pivot (qui entre, qui sort ?)

‣ S’il y a plusieurs variables avec un coef cient positif dans z

‣ Le plus petit indice entre (et sort) (le critère de Bland)
‣ Le plus grand coef cient entre (le critère de Dantzig)
‣ La plus grande augmentation de z
‣ Le côté le plus raide (“steepest edge”)
(en cas d’égalité, on prend le candidat avec le plus petit indice)
‣ S’il y a plusieurs équations les plus contraignantes
‣ Le plus petit indice sort (moins important)
fi
fi
 Le critère de Bland

‣ Le candidat du plus petit indice entre et sort

x4 = 5 - x1 - 3⋅x2 - x3
x5 = 2 - 2⋅x2 - x3
z = 0 + x1 + 3⋅x2 + 2⋅x3
c e !
x1 entre f ca
I n e
fi
 Le critère de Dantzig

‣ Le candidat avec le plus grand coef cient dans z entre

x4 = 5 - x1 - 3⋅x2 - x3
x5 = 2 - 2⋅x2 - x3
z = 0 + x1 + 3⋅x2 + 2⋅x3 e s !
rci c
e x e
l e s
x2 entre po ur
ho ix
re c
N o t
fi
 La plus grande augmentation

‣ La plus grande augmentation de z

‣ x1 → 5, z augmente par 5
‣ x2 → 1, z augmente par 3
‣ x3 → 2, z augmente par 4

x4 = 5 - x1 - 3⋅x2 - x3
x5 = 2 - 2⋅x2 - x3
z = 0 + x1 + 3⋅x2 + 2⋅x3

x1 entre
 Le côté le plus raide (steepest edge)

‣ La plus grande augmentation de z/||xnew-xold||

‣ x1 entre → aug. z/||xnew-xold|| = / + ≈ 0.71
‣ x2 entre → aug. z/||xnew-xold|| = / + + ≈ 0.80
‣ x3 entre → aug. z/||xnew-xold|| = / + + ≈ 1.15

x4 = 5 - x1 - 3⋅x2 - x3
x5 = 2 - 2⋅x2 - x3
u e !
z = 0 + x1 + 3⋅x2 + 2⋅x3 ti q
n pra
p io ne
x3 entre ham
L e c
𝟧
𝟥
𝟦
𝟧
𝟣
𝟤
𝟧
𝟥
𝟤
𝟤
𝟤
𝟤
𝟤
𝟤
𝟤
𝟤
𝟤
𝟤
𝟤
Dégénérescence et
terminaison
 Dégénérescence

‣ Il est possible que l’inégalité la plus contraignante ne

permette pas d’augmenter la variable entrant
‣ Cela s’appelle dégénérescence
x3 = x1 - x2
x4 = 2 - x 1
z = x2

‣ On peut faire un pivot sans augmentation en espérant

que cela permette d’augmenter dans le pivot suivant
 Dégénérescence

x3 = x1 - x2
x4 = 2 - x 1
x2 = x1 - x 3
z = x2
x4 = 2 - x 1
x2 entre x1 = 2 - x4
z = x1 - x3
x3 sort x 2 = 2 - x 3 - x4
x1 entre z = 2 - x 3 - x4
x4 sort

la fonction objectif a augmenté

(et on a trouvé l’optimum)
 Terminaison

‣ Dans certains cas, il est possible d’entrer dans un cycle de

dégénérescence sans augmentation.
‣ Exemple :
‣ variables : x1, x2, x3, x4, base initiale : {3, 4}
‣ x1 entre, x3 sort, nouvelle base {1, 4}
‣ x2 entre, x4 sort, nouvelle base {1, 2}
‣ x3 entre, x1 sort, nouvelle base {2, 3}
‣ x4 entre, x2 sort, nouvelle base {3, 4}
‣ …
‣ Dans ce cas, l’algorithme ne termine jamais.
 Terminaison

‣ Comment éviter ou gérer un potentiel cycle de

dégénérescence ?
1. Utiliser le critère de Bland, mais celui-là est très lent
(le candidat du plus petit indice entre et sort)
2. Certains solveurs peuvent détecter un cycle et changer
au critère de Bland temporairement pour le casser
3. Modifier légèrement la fonction objectif :
une petite perturbation des coef cients bien choisie
fi
Complexité
 Efficacité

‣ Le nombre de pivots est exponentiel dans le pire des cas

‣ En pratique, le pire des cas ne se produit pas,
l’algorithme du simplexe est considéré ef cace
‣ Problème théorique important : trouver un critère de
pivot qui garantit un nombre polynomial de pivots dans
le pire des cas
‣ Il y a d’autres algorithmes ef caces :
‣ la méthode de l’ellipsoïde : polynomiale, lente en pratique
‣ des méthodes de point intérieur : polynomiales, ef caces en
pratique
fi
fi
fi