Programmation linéaire *** Problème primal & méthodes de résolution 2021

Chapitre II. Problème primal & méthodes de résolution

*** Partie 02

II.8. Méthode du Simplexe

II.8.1. Principe
La méthode du simplexe consiste à examiner un ensemble de solutions de base réalisables
(sommets du polyèdre convexe), en améliorant la fonction objective à chaque itération. Après un
nombre fini itérations, la solution optimale, s’il existe, est obtenue, sinon la méthode est bloquée.
Pour cela, on doit :
▪ Déterminer une solution de base réalisable initiale (ou de départ).
▪ Passer d’une solution de base réalisable à une autre solution en améliorant à chaque étape la
valeur de la fonction objective.
▪ Arrêter la procédure lorsqu’il n’est pas possible d’améliorer la fonction objective. La dernière
solution trouvée est donc la solution optimale.

II.8.2. Théorie de la méthode du Simplexe

II.8.2.1. Hypothèse simple
Dans cette hypothèse, on suppose que toutes les contraintes sont de type inférieur ou égale ≤.
Dans ce cas, l’ajout de variables d’écart permet d’obtenir une solution de départ réalisable, pour
améliorer cette solution de départ, l’algorithme se déplace d’une solution à d’autre adjacente
meilleure que la précédente, en remplaçant une variable de base par une autre hors base, cela
revient à faire un « changement de base ».
II.8.2.2. Changement de Base
Critère d’entrée d’une variable dans la base
On calcule l’apport de chaque variable hors base à la fonction objective, en représentant la
fonction objective en fonction des variables hors base. Donc, on calcule la quantité cj − zj qui
représente l’apport de chaque variable à la fonction objective, avec zj = CB B −1 aj.

Une variable xinput est introduite dans la base si :

▪ Cas max : cinput − zinput = maxj∈K {cj − zj , cj − zj > 0}

▪ Cas min : cinput − zinput = minj∈K {cj − zj , cj − zj < 0}
▪ Z = Z0 + ∑j∈K(cj − zj )xj
Preuve
Soit le Problème linéaire sous forme matricielle et sous forme standard :
𝑂𝑝𝑡𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 𝐶 𝑋
𝑠. 𝑐. 𝐴𝑋 = 𝑏
{
𝑋0
𝐴(𝑛 𝑥 𝑝) = (𝑎𝑖𝑗 )
𝐴𝐵 : 𝑀𝑎𝑡𝑟𝑖𝑐𝑒 𝑑𝑒 𝑏𝑎𝑠𝑒 (𝑛 𝑥 𝑛)
𝐴 = (𝐴𝐵 , 𝐴𝐻𝐵 ) 𝑎𝑣𝑒𝑐 {
𝐴𝐻𝐵 : 𝑀𝑎𝑡𝑟𝑖𝑐𝑒 ℎ𝑜𝑟𝑠 𝑏𝑎𝑠𝑒 (𝑛 𝑥 (𝑝 − 𝑛))

14
Dr. B. Sidaoui ([email protected])
 Programmation linéaire *** Problème primal & méthodes de résolution 2021

𝑋𝐵1 𝑋𝐻𝐵1
𝑋𝐵 … …
𝑋 = ( ), 𝑋𝐵 = ( … ), 𝑋𝐻𝐵 = ( … )
𝑋𝐻
𝑋𝐵𝑛 𝑋𝐻𝐵𝑝−𝑝
Par conséquence
𝑋𝐵
𝐴𝑋 = 𝑏 ≡ (𝐴𝐵 𝐴𝐻𝐵 ) ( )=𝑏
𝑋𝐻𝐵

On a donc,
𝐴𝐵 𝑋𝐵 + 𝐴𝐻𝐵 𝑋𝐻𝐵 = 𝑏
⇒ 𝑋𝐵 + 𝐴𝐵 −1 𝐴𝐻𝐵 𝑋𝐻𝐵 = 𝐴𝐵 −1 𝑏
−1
⇒ 𝑋𝐵 = 𝐴𝐵 −1 𝑏 − 𝐴𝐵 𝐴𝐻𝐵 𝑋𝐻𝐵
On a aussi:
𝑍 = 𝐶𝑋 𝑒𝑡 𝐶 = (𝐶𝐵 , 𝐶𝐻𝐵 )
⇒ 𝑍 = 𝐶𝐵 𝑋𝐵 + 𝐶𝐻𝐵 𝑋𝐻𝐵
−1
⇒ 𝑍 = 𝐶𝐵 (𝐴𝐵 −1 𝑏 − 𝐴𝐵 𝐴𝐻𝐵 𝑋𝐻𝐵 ) + 𝐶𝐻𝐵 𝑋𝐻𝐵
⇒ 𝑍 = 𝐶𝐵 𝐴𝐵 −1 𝑏 − 𝐶𝐵 𝐴𝐵 −1 𝐴𝐻𝐵 𝑋𝐻𝐵 + 𝐶𝐻𝐵 𝑋𝐻𝐵
⇒ 𝑍 = 𝐶𝐵 𝐴𝐵 −1 𝑏 + (𝐶𝐻𝐵 − 𝐶𝐵 𝐴𝐵 −1 𝐴𝐻𝐵 )𝑋𝐻𝐵
Soit K(= p − n) : le nombre des variables hors base, on note aussi :

𝐴𝐻𝐵 = ∑ 𝑎𝑗 𝑒𝑡 𝐶𝐻𝐵 = ∑ 𝑐𝑗 𝑒𝑡 𝑋𝐻𝐵 = ∑ 𝑥𝑗

𝑗∈𝐾 𝑗∈𝐾 𝑗∈𝐾
−1
𝑍0 = 𝐶𝐵 𝐴𝐵 𝑏
On obtient

𝑍 = 𝑍0 + (𝐶𝐻𝐵 − 𝐶𝐵 𝐴𝐵 −1 𝐴𝐻𝐵 )𝑋𝐻𝐵

𝑍 = 𝑍0 + (∑ 𝑐𝑗 − ∑ 𝐶𝐵 𝐴𝐵 −1 𝑎𝑗 ) ∑ 𝑥𝑗
𝑗∈𝐾 𝑗∈𝐾 𝑗∈𝐾

𝑍 = 𝑍0 + ∑(𝑐𝑗 − 𝐶𝐵 𝐴𝐵 −1 𝑎𝑗 )𝑥𝑗
𝑗∈𝐾

𝑍 = 𝑍0 + ∑(𝑐𝑗 − 𝑧𝑗 )𝑥𝑗 𝑜ù 𝑧𝑗 = 𝐶𝐵 𝐴𝐵 −1 𝑎𝑗
𝑗∈𝐾
Donc, on sélection la variable 𝑥𝑗 ayant la valeur (𝑐𝑗 − 𝑧𝑗 ), qui permet d’optimiser la fonction
objective.
II.8.2.3. Détermination de la variable sortante
Une fois la variable 𝑥𝑖𝑛𝑝𝑢𝑡 sélectionnée. Soit 𝑎𝑖𝑛𝑝𝑢𝑡 le vecteur entrant dans la base (le vecteur
associé au variable entrante), la solution de base est donc :
−1
𝑋𝐵 = 𝐴𝐵 −1 𝑏 − 𝐴𝐵 𝐴𝐻𝐵 𝑋𝐻𝐵
−1 −1
⇒ 𝑋𝐵 = 𝐴𝐵 𝑏 − 𝐴𝐵 𝑎𝑖𝑛𝑝𝑢𝑡 𝑥𝑖𝑛𝑝𝑢𝑡 = 𝛽 − 𝛼𝑖𝑛𝑝𝑢𝑡 𝑥𝑖𝑛𝑝𝑢𝑡
−1
𝛽 = 𝐴𝐵 −1 𝑏, 𝑒𝑡 𝛼𝑖𝑛𝑝𝑢𝑡 = 𝐴𝐵 𝑎𝑖𝑛𝑝𝑢𝑡

15
Dr. B. Sidaoui ([email protected])
 Programmation linéaire *** Problème primal & méthodes de résolution 2021

𝑥𝐵1 𝛽1 𝛼1 𝑖𝑛𝑝𝑢𝑡
… … …
⇒ … = … − … 𝑥𝑖𝑛𝑝𝑢𝑡
… … …
(𝑥𝐵𝑛 ) (𝛽𝑛 ) (𝛼𝑛 𝑖𝑛𝑝𝑢𝑡 )
Pour que la nouvelle solution de base soit réalisable, il faut que chaque 𝑥𝐵𝑖 soit supérieur ou égale
à zéro (contraintes de non négativité), alors on obtient le système suivant :
β1
xinput ≤
xB1 = β1 − α1 input xinput ≥ 0 α1 input
{ ⋮ ⟹ ⋮
xBn = βn − αn input xinput ≥ 0 βn
xinput ≤
{ αn input

On doit sélectionner 𝑥𝐵𝑗 le moins important c’est-à-dire choisir la plus petite valeur.

La variable 𝑥𝑜𝑢𝑡 sort de la base d’après le critère de Dantzig :

βk min β
= { i ,α > 0},
αk input 1 ≤ i ≤ n αi input i input
Où: αk input est appelé Pivot.

II.8.2.4. Détermination des Nouvelles Valeurs des Variables de Base

Ligne pivot : Diviser la ligne pivot par le coefficient pivot :
akj
a(𝑥input) = α 𝑜ù 𝑗 = 1. . 𝑛 𝑒𝑡 αk input = pivot
k input
βk
𝑥input =
αk input
Mettre à jour les autres lignes par:
𝑎kj
a(𝑥B)ij = 𝑎ij − 𝛼𝑖 𝑖𝑛𝑝𝑢𝑡
αk input
𝛽k
𝑥Bi = 𝛽i − 𝛼𝑖 𝑖𝑛𝑝𝑢𝑡
𝛼𝑘 𝑖𝑛𝑝𝑢𝑡
Pour la fonction objective :
𝛽k
Nouvelle valeur de Z = Ancienne valeur de Z + (𝑐𝑖𝑛𝑝𝑢𝑡 − 𝑧𝑖𝑛𝑝𝑢𝑡 )
αk input

II.8.2.5. Critère d’optimalité

La solution de base réalisable est optimale lorsque toutes les variables hors base ayant des
valeurs 𝑐𝑗 − 𝑧𝑗  0 (cas de max) et 𝑐𝑗 − 𝑧𝑗 ≥ 0 (cas de min).

La solution optimale est unique, si toutes les variables hors base ayant des valeurs :
𝑐𝑗 − 𝑧𝑗 < 0 (Cas de max) et 𝑐𝑗 − 𝑧𝑗 > 0 (cas de min)
La solution optimale est multiple, si pour une variable 𝑥𝑗 hors base, on a 𝑐𝑗 − 𝑧𝑗 = 0 et 𝛼𝑗 > 0

La solution optimale est infinie :

Si pour une variable 𝑥𝑗 hors base, on a 𝑐𝑗 − 𝑧𝑗 > 0 et 𝛼𝑗 ≤ 0 (cas max)
Si pour une variable 𝑥𝑗 hors base, on a 𝑐𝑗 − 𝑧𝑗 < 0 et 𝛼𝑗 ≤ 0 (cas min)

16
Dr. B. Sidaoui ([email protected])
 Programmation linéaire *** Problème primal & méthodes de résolution 2021

II.8.3. Forme générale du Simplexe

Max/Min Variables structurelles 𝑥𝑗 Solution de 𝑥out : Select argmin
base βi 𝛽i
𝑥1 … 𝑥𝑖𝑛𝑝𝑢𝑡 … 𝑥𝑝 of
𝛼𝑖 𝑖𝑛𝑝𝑢𝑡
𝛼11 … 𝛼1 𝑖𝑛𝑝𝑢𝑡 … 𝛼1 𝑝 β1 𝛽1
𝑥𝐵 1
𝛼1 𝑖𝑛𝑝𝑢𝑡
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
𝑥𝐵 𝑘 𝛼𝑘1 … 𝛂𝐤 𝐢𝐧𝐩𝐮𝐭 … 𝛼𝑘𝑝 βk 𝜷𝐤
𝑋𝐵
(𝑥𝑜𝑢𝑡 ) 𝜶𝒌 𝒊𝒏𝒑𝒖𝒕
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
𝑥𝐵 𝑛 αn1 … αn input … αnp βn 𝛽n
𝛼n input
𝑐𝑗 − 𝑧𝑗 𝑐1 − 𝑧1 … 𝑐𝑖𝑛𝑝𝑢𝑡 − 𝑧𝑖𝑛𝑝𝑢𝑡 … 𝑐𝑝 − 𝑧𝑝 −𝑍 𝛂𝐤 𝐢𝐧𝐩𝐮𝐭 = 𝐩𝐢𝐯𝐨𝐭

𝑥input = arg (max/min){𝑐𝑗 − 𝑧𝑗 , 𝑗 = 1. . 𝑛}

𝜷𝐤 𝜷𝐤 𝛽i
𝑥out = argof 𝜶 avec 𝜶𝒌 𝒊𝒏𝒑𝒖𝒕
= min {𝛼 , 𝛼𝑖 𝑖𝑛𝑝𝑢𝑡 > 0}
𝒌 𝒊𝒏𝒑𝒖𝒕 𝑖 𝑖𝑛𝑝𝑢𝑡
𝛽k 𝑎kj
𝑥Bi = 𝛽i − 𝛼𝑖 𝑖𝑛𝑝𝑢𝑡 𝛼 et a(𝑥B )ij = 𝑎ij − 𝛼𝑖 𝑖𝑛𝑝𝑢𝑡 𝛼
𝑘 𝑖𝑛𝑝𝑢𝑡 𝑘 𝑖𝑛𝑝𝑢𝑡
𝛽k
−Z = − Z − (𝑐𝑖𝑛𝑝𝑢𝑡 − 𝑧𝑖𝑛𝑝𝑢𝑡 )
𝛼𝑘 𝑖𝑛𝑝𝑢𝑡
Exemple
Soit le PL sous sa forme standard : 𝑀𝑎𝑥 𝑍 = 30𝑥 + 80𝑦 + 0𝑡 1 + 0𝑡2
𝑥 + y + 𝑡1 = 5
𝑠. 𝑐. {𝑥 + 4y + 𝑡2 = 10
𝑥, y, 𝑡1 , 𝑡2  0

Exemples à résoudre
Soit les PL suivants
𝑀𝑎𝑥 3𝑥 + 4𝑦
2x + 3y  180
2𝑥 + 𝑦 ≤ 120
𝑠. 𝑐. {
𝑥 + 3𝑦 ≤ 150
𝑥, 𝑦 ≥ 0
𝑀𝑖𝑛 𝑍 = −2𝑥 − 𝑦
x−y4
𝑠. 𝑐. { + y  6
x
x, y  0

II.8.4. Signification des variables d’écart

3x + 4y  42 ⟹ 3x + 4y + t1 = 42 ⟹ Contrainte non saturée
x + 3y  22 ⟹ x + 3y + t 2 = 22 ⟹ Contrainte non saturée
2x + 2y  26 ⟹ 2x + 2y + t 3 = 26 ⟹ Contrainte non saturée
x  11 ⟹ x + t 4 = 11 ⟹ Contrainte non saturée

17
Dr. B. Sidaoui ([email protected])
 Programmation linéaire *** Problème primal & méthodes de résolution 2021

II.9. Extension de l’algorithme du Simplexe

L'obtention d'une solution de base réalisable est facile lorsque
▪ Toutes les contraintes sont de type "" et b  0
▪ Toutes les contraintes sont de type "" et b  0
Dans le cas "" et "b  0", les variables d'écarts introduites dans chaque contrainte fournissent la
base initiale.
Dans tous les autres cas, il n'existe pas de solution de base de départ immédiate. Pour déterminer
une solution de base initiale, on ajout des variables, appelées des variables artificielles (pour chaque
contrainte de type  ou =), ensuite on applique l’une des méthodes suivantes :
▪ La méthode des 2 phases.
▪ La méthode des pénalités.
II.9.1. Ajout de variables artificielles
Ajouter une variable artificielle dans chaque contrainte de type "" ou "=".
Min Z = x1 + x2 + 3x3 + x4 Min Z = x1 + x2 + 3x3 + x4
avec 2x1 + 3x2 + 6x4  8 Forme Standard 2x1 + 3x2 + 6x4 – t1 = 8
3x1 + x2 + 2x3 – 7x4 = –4  –3x1 – x2 – 2x3 + 7x4 = 4
x1 , x2 , x3 , x4  0 x1 , x2 , x3 , x4 , t1  0

 Introduction des variables artificielles

2x1 + 3x2 + 6x4 – t1 + w1 = 8

–3x1 – x2 – 2x3 + 7x4 + w2 = 4
x1 , x2 , x3 , x4 , t1 , w1 , w2  0
II.9.2. Méthode des deux phases
Formellement nous pouvons présenter la méthode des deux phases comme suit :

• Mettre le P.L. sous forme standard (ajouter les variables d'écarts).

• Ajouter les variables artificielles ai dans chaque contrainte de type "" ou "=".
• Construire la nouvelle fonction objectif w =  ai
• Utiliser l'algorithme du simplexe pour minimiser l'objectif w.
• Itérer jusqu'à ce que l'une de ces trois situations se présente :
o w = 0 et toutes les artificielles sont hors base, dans ce cas, reconstruire la ligne
objectif originale z au moyen des formules z = cBB-1b et cj − zj , passer à la phase II.
o w > 0 (ou w<0), le problème de départ n'a pas de solution réalisable puisqu'il est
impossible d'annuler les variables artificielles.
o w = 0 mais il reste des variables artificielles en base.
▪ Si tous ces éléments sont nuls le système contient une ligne du type aj = 0.
▪ Cette ligne est sans intérêt ; on peut la supprimer.
▪ Si au moins un élément est non nul, il peut servir de pivot même s'il est
négatif
▪ Pour éliminer aj au profit d'une variable structurelle.

18
Dr. B. Sidaoui ([email protected])
 Programmation linéaire *** Problème primal & méthodes de résolution 2021

Exemples
Résoudre les Problèmes linéaires suivants.

Min Z = x1 + x2 + 3x3 + x4
2x1 + 3x2 + 6x4  8
s. c. {−3x1 − x2 − 2x3 + 7x4 = 4
x1 , x2 , x3 , x4  0
max z = x + y + 2v
x + y + v = 12
s. c. { + 5y − 6v = 10
2x
7x + 10y − v = 70
min z = 2x + 3y
2x + 3y = 5
s. c. { x – y = 1
x + 4y = 4
max z = 5 x + 7 y
x + y ≥ 6
x≥4
s. c. { y ≤ 3
x, y ≥ 0
min z = 3 x + 10 y
5x + 6y ≥ 10
s. c. {2 x + 7y ≥ 14
x, y ≥ 0
II.9.3. Méthode des pénalités (ou M-méthode)
C’est une autre méthode qui est utilisée pour éliminer les variables artificielles de la base. Elle
consiste à appliquer le simplexe en optimisant la fonction objective dont les variables artificielles ont
été fortement pénalisées.
▪ Ecrire le PL dans sa forme standard et introduire les variables artificielles requises.
▪ Soit M un nombre arbitrairement grand.
▪ Associer aux les variables artificielles un coût égal à –M  𝑀𝑎𝑥𝑍 = ∑𝑚 𝑗=1 𝑐𝑗 𝑥𝑗 −
𝑟
∑𝑙=1 𝑀𝑤𝑙 (cas de maximisation)
▪ Associer aux les variables artificielles un coût égal à +M  𝑀𝑖𝑛𝑍 = ∑𝑚 𝑗=1 𝑐𝑗 𝑥𝑗 +
𝑟
∑𝑙=1 𝑀𝑤𝑙 .
▪ Résoudre le PL avec le simplexe.

19
Dr. B. Sidaoui ([email protected])