Recherche opérationnelle Chapitre 2 Programmation linéaire
1 Algorithme Simplexe
Une nouvelle méthode du Simplexe géométrique permet à partir d’une solu-
tion initiale (point de départ du polyèdre), lors de toute itération de passer
d’un sommet à un sommet voisin en lequel la valeur de la fonction objectif
est meilleure. L’algoritme s’arrête lorsqu’on ne trouve aucun sommet voisin
dont la valeur de la fonction objectif est meilleure.
1.1 Condition d’utilisation
• Toutes les contraintes du PL doivent être en égalités (forme standard);
• Tous les secondes membres sont positifs;
• Si une contrainte i contient le second membre négatif bi < 0, on mutli-
plie la conttrainte par -1.
• Si le signe d’une variable est inconnu à l’avance par exemple xi ≥ −2,
on peut la remplacer par x0i = xi + 2 ≥ 0. Si on pas la borne inférieur,
on la ramplce par xi = x0i − xi ” avec xi ”, x0i ≥ 0.
• La fonction objectif est à maximiser;
• Introduire les variables d’écarts;
• Solution initiale réalisable en origine comme point de départ, sinon
méthode à deux phases pour trouver une solution admissible comme
nouveau point.
1.2 Exemple
1.2.1 La forme standard d’un PL
maximiser
3x1 + x2 + 2x3
Sous les contraintes
x4 = 30 − x1 − x2 − 3x3
x5 = 24 − 2x1 − 2x2 − 5x3
x6 = 36 − 4x1 − x2 − 2x3
Pr. Khalil IBRAHIMI 1 a.u: 2022-2023/uit
Recherche opérationnelle Chapitre 2 Programmation linéaire
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0
Les variables d’écarts x4 , x5 , x6
Une solution intitiale à ce sytème correspond au sommet O(x1 = 0, x2 =
0, x3 = 0). La fabrication est nulle donne un bénifice Z =0 (nul). Il s’agit
d’une solution admissible au sens mathématique des contraintes.
1.2.2 Base en sommet origine O
Les variables de base en fonction des variables hors - base sont :
x4 = 30 − x1 − x2 − 3x3
x5 = 24 − 2x1 − 2x2 − 5x3
x6 = 36 − 4x1 − x2 − 2x3
Z = 0 + 3x1 + x2 + 2x3
Augmenter la valeur de la fonction objectif Z revient à augmenter la valeur
de l’une des variables hors base. On cherche la variable qui augmente de plus
grande marge de bénifice, donc c’est la variable x1 et les autres variables hors
base sont nulles.
1.2.3 La forme standard d’un PL
La variable x1 est augmenté d’une valeur θ et (x2 = 0, x3 = 0)
x4 = 30 − θ
x5 = 24 − 2θ
x6 = 36 − 4θ
Z = 0 + 3θ
Il faut augmenter la valeur du θ en respectant les contraintes de positivités
des variables. Donc, 30 − θ ≥ 0, 24 − 2θ ≥ 0 et 36 − 4θ ≥ 0, ce qui donne la
maximum possible est θ = 9. On trouve un nouveau sommet C = (0+9, 0, 0),
c’est un programme qui génére un bénifice de 27.
Exemple [Base en sommet C] On cherhce x1 en fonction de x6 et on
obtient x1 = 1/4(36 − x2 − 2x3 − x6 )∗ . En remplace x1 par sa valeur dans les
variables de base x4 et x5 , le nouveau système est :
x1 = 9 − 1/4x2 − 1/2x3 − 1/4x6
Pr. Khalil IBRAHIMI 2 a.u: 2022-2023/uit
Recherche opérationnelle Chapitre 2 Programmation linéaire
x4 = 21 − 3/4x2 − 5/2x3 + 1/4x6
x5 = 6 − 3/2x2 − 4x3 + 1/2x6
Z = 27 + 1/4x2 + 1/2x3 − 3/4x6
Cette opération porte le nom de PIVOT. Un pivot choisit une variable hors-
base xe (entrante, e=1), et une variable xl de base dite sortante (l=6) de la
base.
On augmente la valeur de la fonction objectif. On exprime les variables de
base en C en fonction des variables hors base en C.
Exemple [Base en sommet voisin de C] Augmenter la valeur de la fonction
objectif Z = 27 revient à augmenter la valeur de l’une des variables hors
base. On cherche la variable qui augmente de plus grande marge de bénifice,
donc c’est la variable x3 et les autres variables hors base sont nulles. Donc
x3 = θ, x2 = 0, x6 = 0
x1 = 9 − 1/2θ
x4 = 21 − 5/2θ
x5 = 6 − 4θ
Z = 27 + 1/2θ
En respectant les contraintes non négativités, la valeur maximal d’augmentation
est de 3/2. Donc,
x3 = 1/4(6 − 3/2x2 + 1/2x6 − x5 )
.
Exemple [Base en sommet C] On cherhce x3 en fonction de x5 et on
obtient x3 = 3/2 − 3/8x2 − 1/4x5 + 1/8x6 . En remplace x2 par sa valeur dans
les variables de base x1 et x4 , le nouveau système est :
x1 = 33/4 − 1/16x2 + 1/8x5 − 5/16x6
x3 = 3/2 − 3/8x2 − 1/4x5 + 1/8x6
x4 = 69/4 + 3/16x2 + 5/8x5 − 1/16x6
Z = 111/4 + 1/16x2 − 1/8x5 − 11/16x6
Remarque: x3 est la varirable entrante dans la base et x5 est la variable
sortante de la base. On augmente la valeur de la fonction objectif. On
Pr. Khalil IBRAHIMI 3 a.u: 2022-2023/uit
Recherche opérationnelle Chapitre 2 Programmation linéaire
exprime les variables de base en C en fonction des variables hors base en
vosin de C, D.
Exemple [Base en sommet voisin de D] Augmenter la valeur de la fonction
objectif Z = 111/4 revient à augmenter la valeur de l’une des variables hors
base. On cherche la variable qui augmente de plus grande marge de bénéfice,
donc c’est la seule variable x2 et les autres variables hors base sont nulles.
Donc x2 = θ, x5 = 0, x6 = 0
x1 = 33/4 − 1/16θ
x4 = 69/4 + 3/16θ
x3 = 3/2 − 3/8θ
Z = 111/4 + 1/16θ
En respectant les contraintes non négativités, la valeur maximal d’augmentation
est de 4.
x2 = 8/3(3/2 − x3 − 1/4x5 + 1/8x6 )
Exemple [Base en sommet C] On cherhce x2 en fonction de x3 et on
obtient x2 = 8/3(−3/2 − x3 + 1/4x5 − 1/8x6 ). En remplace x2 par sa valeur
dans les variables de base, le nouveau système est :
x1 = 8 + x3 /6 + x5 /6 − x6 /3
x2 = 4 − 8/3x3 − 2/3x5 + 1/3x6
x4 = 18 − x3 /2 + x5 /2
Z = 28 − 1/6x3 − 1/6x5 − 2/3x6
Remarque: x2 est la varirable entrante dans la base et x3 est la variable sor-
tante de la base. Toutes les coefficients de la fonction Z sont négatifs et donc
pas d’augmentation possible et la solution optimale est x∗ = (8, 4, 0, 18, 0, 0)
qui donne la valeur maximal de Z = 3 ∗ 8 + 4 + 0 = 28. B = {1, 2, 4},
N = {3, 5, 6}
Pr. Khalil IBRAHIMI 4 a.u: 2022-2023/uit
Recherche opérationnelle Chapitre 2 Programmation linéaire
1.3 Mise à jour générale des contraintes par PIVOT
La variable entrante est de la forme :
X
xe = b̂e − âej xj − âel xl
j∈N −{e}
Mise à jour des autres variables de bases i ∈ B − {l}:
X
xi = b̂i − âij xj − âil xl
j∈N −{e}
Mise à jour de la fonction objectif:
X
z = v̂ + ĉj xj + ĉl xl
j∈N −{e}
Le mécanisme PIVOT suivant permet de calculer les coefficients de chaque
variable à chaque itération.
2 Méthode algorithmique du Simplex
Critères de Dantzig
A partir de la forme standard du P.L, on exprime la solution au sommet
à l’origine
• Critère 1. Pour déterminer la colonne qui doit entrer dans la base
(entrante), on choisit celle qui comporte le cj > 0 le plus grand de la
fonction économique.
• Critère 2. Pour déterminer la colonne qui doit sortir de la base, on
choisit celle d’indice l tel que bk /ake soit le plus petit (l = k).
Exemple : Max
Z = 0 + 3x1 + x2 + 2x3
SC
x4 = 30 − x1 − x2 − 3x3
x5 = 24 − 2x1 − 2x2 − 5x3
x6 = 36 − 4x1 − x2 − 2x3
e = 1, l = 6, min(30/1, 24/2 = 12, 36/4 = 9) = 9
Pr. Khalil IBRAHIMI 5 a.u: 2022-2023/uit
Recherche opérationnelle Chapitre 2 Programmation linéaire
2.1 Mécanisme PIVOT
Le PIVOT reçoit en entrée n-uplet (N, B, A, b, c, v, l, e) une forme standard
et retourne n-uplet (N̂ , B̂, Â, b̂, ĉ, v̂) d’une nouvelle forme standard. Il utilise
une variable entrante xe d’indice e et une variable sortante xl d’indice l à
chaque appel du procédure.
1. Calcule des coefficients de nouvelle variable de base xe .
b̂e = bl /ale
Pour tout j ∈ N − {e} faire âej = alj /ale
âel = 1/ale
2. Calcule des coefficients des contraintes restantes.
Pour tout i ∈ B − {l} faire b̂i = bi − aie b̂e
Pour tout j ∈ N − {e} faire âij = aij − aie âej
âil = −aie âel
3. Calcule de la fonction objectif:
v̂ = v + ce b̂e
Pour tout j ∈ N − {e} faire ĉj = cj − ce âej
ĉl = −ce âel
4. Mise à jour d’ensemble de nouvelles varirables de base/hors-base.
N̂ = N − {e} ∪ {l} et B̂ = B − {l} ∪ {e}
5. Retourne la nouvelle forme standard (N̂ , B̂, Â, b̂, ĉ, v̂) =Mécanisme
PIVOT(N, B, A, b, c, v, l, e) du simplexe.
La variable entrante est de la forme :
X
xe = b̂e − âej xj − âel xl
j∈N −{e}
Mise à jour des autres variables de bases i ∈ B − {l}:
X
xi = b̂i − âij xj − âil xl
j∈N −{e}
Mise à jour de la fonction objectif:
X
z = v̂ + ĉj xj + ĉl xl
j∈N −{e}
Théorème.
Considérons l’appel à (N̂ , B̂, Â, b̂, ĉ, v̂)=PIVOT(N, B, A, b, c, v, l, e) dans
lequel la valeur du pivot ale 6= 0. Soit x̄ la solution de base après l’appel,
alors x̄j = 0 pour tout j ∈ N̂ , x̄e = ablel , x̄i = bi − aie b̂e pour tout i ∈ B̂ − {e}
Pr. Khalil IBRAHIMI 6 a.u: 2022-2023/uit
Recherche opérationnelle Chapitre 2 Programmation linéaire
2.2 Formalisme de l’algorithme simplexe
1. Initialisation.
(N, B, A, b, c, v) = initialise − simplexe(A, b, c)
2. Simplexe.
Tant que j ∈ N vérifie cj > 0
faire choisir un indice e ∈ N tel que ce > 0
pour tout indice i ∈ B
faire is aie > 0 alors δi = bi /aie
sinon δi = ∞
choisir un indice l ∈ B qui minimise δi
si δi = ∞
alors retourner non borné
sinon (N, B, A, b, c, v) = PIVOT(N, B, A, b, c, v, l, e)
Fin de tant que
3. Pour i allant de 1 à n, faire si i ∈ B, alors x̄i = bi , sinon x̄i = 0
retourner (x̄1 , x̄2 , ..., x̄n ) la solution optimale.
L’algorithme résume la méthode de maximisation par les tableaux di-
rectement.
Lemme 1 Etand donné un programme linéaire (A, b, c), supposez l’initialisation
retourne une forme standard pour laquelle la solution est réalisable. Si sim-
plexe retourne une solution optimale, cette solution est réalisable pour PL.
Si simplexe retourne non borné, alors le programme PL est non borné.
Lemme 2 Soit (A, b, c) un programme linéaire sous forme canonique.
Etant donné un ensemble de variable de base B, il y a unicité de la forme
standard associée.
Lemme 3 Soit I un ensemble d’indices. Pour tout i ∈ I, soeint αi et βi
des réels, et soit xi une variable à valeur réelle. Soit γ un réel quelconque.
Supposons pour toute configuration des xi , l’on ait
X X
αi xi = γ + β i xi
i i
alors αi = βi pour tout i ∈ I, et γ = 0.
Pr. Khalil IBRAHIMI 7 a.u: 2022-2023/uit
Recherche opérationnelle Chapitre 2 Programmation linéaire
2.3 Terminaison de l’algorithme Simplexe
Chaque itération de l’algorithme simplexe augmentait la valeur de la fonction
objectif associée àla solution de base. Il se peut qu’une itération laisse la
valeur de la fonction objectif inchangée. Ce phénomène porte le nom de
dégénérescence, donc bl = 0.
m
Lemme 1 Si SIMPLEXE n’arrive pas à se terminer en au plus Cn+m itérations,
alors il boucle.
Lemme 2 Si Initialisation-SIMPLEXE retourne une forme standard pour
laquelle la solution de base est réalisable, alors soit SIMPLEXE signale qu’un
PL est non borné, soit il se termine avec une solution réalisable en au plus
m
Cn+m itérations.
2.4 Problème de la soultion de base initiale
Situation
• Initialisation: toujours on a une solution réalisable? si non, comment
construire une solution?
L’objectif est de trouver une solution de base admissible qui servira de
point de départ pour l’algorithme du simplexe.
L’idée est de résoudre un problème intermédiaire de minimisation dont
la solution fournira le point de départ de la méthode du simplexe. Ce
problème intermédiaire porte le nom de Phase I du simplexe. Puis de
suivre la méthode standard du simplexe (Phase II).
• A chaque itération de trouver une variable entrante et une sortante.
• Terminaison: en un nombre fini d’itérations, la solution optimale est
trouvée (convergence) ou non.
Méthode de deux phases La méthode des Deux Phases est utilisée lorsque
les variables artificielles apparaissent dans la forme standard ou canonique
du problème linéaire.
Phase 1. Résolution du problème auxiliaire avec une nouvelle fonction ob-
jectif w = −x0 .
Phase 2. On appel à l’algorithme simplexe à partir de la forme standard de
la phase 1 avec la fonction objectif originale.
Pr. Khalil IBRAHIMI 8 a.u: 2022-2023/uit
Recherche opérationnelle Chapitre 2 Programmation linéaire
Exemple.
Maximiser
z = 2x1 + x2
sous les contraintes
x1 + 2x2 + x3 = 5
3x1 − 2x2 + 3x3 = 2
xi ≥ 0
Trouver la solution de base initiale en utilisant les deux phases.
Problème de la soultion de base initiale
Lemme : Prgramme auxiliéaire Soit L un programme linaéaire sous forme
canonique.
Soit Llaux le programme linéaire à n + 1 variables :
maximiser
w = −x0
sous les contriantes n
X
aij xj − x0 ≤ bi
j=1
pour i = 1, 2, ..., m et
xj ≥ 0
pour j = 0, 1, ..., n.
Alors L est réalisable si est seulement si la valeur de l’objectif optimale de
Laux est 0.
INITALISE-SIMPLEXE (A, b, c) Programme auxiliéaire Soit l l’indice
du bi minimal. Alors si bl ≥ 0, la solution de base initiale est réalisable,
retourne (N, B, A, b, c, 0)
Sinon, former un programme linéaire auxiliéaire Laux (voir le lemme précident)
On appel le PIVOT sur la forme standard finale de Laux (N, B, A, b, c, v) =
P IV OT (N, B, A, b, c, v, l, 0) (entrant = x0, sortant =xl , sans que bl >0)
Solution au programme auxiliéaire On a maintenant la solution réalisable
pour Laux .
Répéter le simplexe sauf l’initialisation, jusqu’à l’obtention d’une solution
optimale pour Laux .
Si la solution de base x̄0 = 0 alors retourne la forme standard finale en
supprimant x0 et en restaurant la fonction objectif originale.
Sinon retourne irréalisable.
Pr. Khalil IBRAHIMI 9 a.u: 2022-2023/uit
Recherche opérationnelle Chapitre 2 Programmation linéaire
Exemple du problème de phase I max
z = 2x1 − x2
sc
2x1 − x2 ≤ 2
x1 − 5x2 ≤ −4
x1 , x2 ≥ 0
1. La solution de base (0, 0) est iréalisable, car la contrainte 2 est violée.
Donc, la phase initiale du simplex ne retourne pas la forme standard évidente.
2. Trouver la forme standard
3. Formuler le programme linéaire auxiliaire.
4. Trouver la solution optimale du problème originale.
Exemple du problème de phase I
2. La forme standard du programme auxiliaire
max
z = −x0
sc
2x1 − x2 + x3 − x0 = 2
x1 − x2 + x4 − x0 = −4
Ou bien sous la forme
x3 = 2 + x0 − 2x1 + x2
x4 = −4 + x0 − x1 + x2
xi ≥ 0
Après appel au PIVOT, on convertit ce programme à un autre programme
linéaire dont la solution est réalisable (e=0, l=4 (la plus négative (-4))).
La solution de base de Laux est x1 = 0, x2 = 4/5, x3 = 14/5 et z = 0 (2
PIVOT) On supprime x0 , puis on utlise la fonction z originale à ce stade,
puis on continue le simplex (Phase II).
Lemme 1 Etand donné un programme linéaire (A, b, c), supposez l’initialisation
retourne une forme standard pour laquelle la solution est réalisable. Si sim-
plexe retourne une solution optimale, cette solution est réalisable pour PL.
Si simplexe retourne non borné, alors le programme PL est non borné.
Pr. Khalil IBRAHIMI 10 a.u: 2022-2023/uit
Recherche opérationnelle Chapitre 2 Programmation linéaire
Lemme 2 Soit (A, b, c) un programme linéaire sous forme canonique.
Etant donné un ensemble de variable de base B, il y a unicité de la forme
standard associée.
Lemme 3 Soit I un ensemble d’indices. Pour tout i ∈ I, soeint αi et βi
des réels, et soit xi une variable à valeur réelle. SoitPγ un réel quelconque.
P
Supposons pour toute configuration des xi , l’on ait i αi xi = γ + i βi xi
alors αi = βi pour tout i ∈ I, et γ = 0.
Terminaison de l’algorithme Simplexe Chaque itération de l’algorithme
simplexe augmentait la valeur de la fonction objectif associée à la solution
de base. Il se peut qu’une itération laisse la valeur de la fonction objectif
inchangée. Ce phénomène porte le nom de dégénérescence, donc bl = 0.
m
Lemme 1 Si SIMPLEXE n’arrive pas à se terminer en au plus Cn+m itérations,
alors il boucle.
Lemme 2 Si Initialisation-SIMPLEXE retourne une forme standard pour
laquelle la solution de base est réalisable, alors soit SIMPLEXE signale qu’un
PL est non borné, soit il se termine avec une solution réalisable en au plus
m
Cn+m itérations.
Pr. Khalil IBRAHIMI 11 a.u: 2022-2023/uit
