Solution Série TD N° 3

Rappel de l'algorithme de la méthode simplexe algébrique

Exercice 1
1.

A) Résolution du PL avec la méthode simplexe algébrique

Étape 1: Initialisation
 Mise du PL sous forme standard (en rajoutant les variables d'écart)
𝑴𝒂𝒙 𝑍 = 3𝑥1 + 2𝑥2
𝐒𝐮𝐣𝐞𝐭 à:
2𝑥1 + 𝑥2 + 𝑥3 = 5
𝑥1 − 𝑥2 + 𝑥4 = 1
 𝑥1 + 𝑥2 + 𝑥5 = 3
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0
dont l'écriture matricielle est:
𝑴𝒂𝒙 𝑍 = 3𝑥1 + 2𝑥2
𝐒𝐮𝐣𝐞𝐭 à:
𝑥1
2 1 1 0 0 𝑥2 5
[1 −1 0 1 𝑥
0] . 3 = [1]
1 1 0 0 1 𝑥4 3
[𝑥5 ]
2 1 1 0 0
La matrice 𝐴 = [𝑎1 , 𝑎2 , 𝑎3 , 𝑎4 , 𝑎5 ] = [1 −1 0 1 0]
1 1 0 0 1
 Détermination d'une solution de base
o On choisit comme matrice de base (B) celle composée de vecteurs associés
aux variables d'écart:
1 0 0 2 1 5
𝐵 = [0 1 0] , 𝑁 = [1 −1] , 𝑏 = [1] , 𝑐𝐵 = [0,0,0], 𝑐𝑁 = [3,2]
0 0 1 1 1 3
o On pose 𝑋𝑁 = 0
o 𝑋𝐵 = 𝐵 −1 . 𝑏 = 𝑏̅ et 𝑍 = 𝑐𝐵 . 𝑋𝐵
1 0 0 −1 5 5
𝑋𝐵 = [0 1 0] . [1] = [1]
0 0 1 3 3
5
𝑍 = [0,0,0]. [1] = 0
3
o Pour chaque variable hors base 𝑗 ∈ 𝐸𝑁 = {1,2}, on calcule 𝑐𝑗 − 𝑧𝑗 avec 𝑧𝑗 =
𝑐𝐵 . 𝜇𝑗 , 𝜇𝑗 = 𝐵−1 . 𝑎𝑗 et 𝑎𝑗 est la colonne j de la matrice A.
1 0 0 −1 2
c1 − z1 = 3 − [0,0,0]. [0 1 0] . [1] = 3
0 0 1 1
−1
1 0 0 1
𝑐2 − 𝑧2 = 2 − [0,0,0]. [0 1 0] . [−1] = 2
0 0 1 1
Étape 2: Recherche de la solution optimale
 On teste si la solution de base actuelle est optimale, c.à.d. (∀𝑗 ∈ 𝐸𝑁 : 𝑐𝑗 − 𝑧𝑗 ≤ 0).
La solution de base actuelle n’est pas optimale car 𝑐1 − 𝑧1 > 0 et 𝑐2 − 𝑧2 > 0.
 On Détermine la variable entrante 𝑥𝑟 selon le critère:
𝑟 = 𝑎𝑟𝑔 𝑚𝑎𝑥 {𝑐𝑗 − 𝑧𝑗 |𝑐𝑗 − 𝑧𝑗 > 0}
∀𝑗∈𝐸𝑁
𝑟 = 𝑎𝑟𝑔 𝑚𝑎𝑥 {𝑐1 − 𝑧1 = 3, 𝑐2 − 𝑧2 = 2} = 3,
∀𝑗∈𝐸𝑁
où arg max représente l'indice de la variable pour laquelle la valeur de la fonction
concernée atteint son maximum, c.à.d. arg max 𝑓 ≝ {𝑥 ∈ 𝑋|∀𝑥 ′ ∈ 𝑋, 𝑓(𝑥 ) ≥ 𝑓(𝑥 ′ )}
Donc la variable entrante est 𝑥1 .
 On teste l'inexistence d'une solution optimale dont la valeur de Z est finie, c.à.d.
Si (𝜇𝑟 = 𝐵−1 . 𝑎𝑟 ≤ 0).
1 0 0 −1 2
Cette condition n'est pas vérifiée car 𝜇1 = 𝐵−1 . 𝑎1 = [0 1 0] . [1] > 0
0 0 1 1
  On détermine alors la nouvelle solution de base comme suit:
𝑋𝐵 = 𝐵−1 . 𝑏 − 𝐵−1 . 𝑎𝑟 . 𝑥𝑟 = 𝑏 − 𝜇𝑟 . 𝑥𝑟 qui détermine la variable sortante 𝑥𝑘 selon
le critère:
𝑏𝑠 𝑏𝑖
𝑥𝑘 = 𝑋𝐵𝑠 = , 𝑠 = 𝑎𝑟𝑔 𝑚𝑖𝑛 { , 𝜇𝑖𝑟 > 0} ,
𝜇𝑠𝑟 1≤𝑖≤𝑚 𝜇𝑖𝑟
où arg min représente l'indice de la variable pour laquelle la valeur de la fonction
concernée atteint son minimum, c.à.d. arg min 𝑓 ≝ {𝑥 ∈ 𝑋|∀𝑥 ′ ∈ 𝑋, 𝑓 (𝑥 ) ≤ 𝑓(𝑥 ′ )}
On modifie la solution de départ selon l'expression:
𝑋𝐵 = 𝐵−1 . 𝑏 − 𝐵−1 . 𝑎1 . 𝑥1 = 𝑏 − 𝜇1 . 𝑥1
𝑥3 1 0 0 −1 5 1 0 0 −1 2
On aura donc: 𝑋𝐵 = [𝑥4 ] = [0 1 0] . [1] − [0 1 0] . [1] . 𝑥1
𝑥5 0 0 1 3 0 0 1 1
On obtient alors :
𝑥3 = 5 − 2𝑥1
𝑥4 = 1 − 𝑥1 ,
𝑥5 = 3 − 𝑥1
5 1 3
𝑠 = 𝑎𝑟𝑔 𝑚𝑖𝑛 { , , } = 2
1≤𝑖≤𝑚 2 1 1
𝑏2
𝑥4 = 𝑋𝐵2 =
𝜇2𝑟
Le minimum s'obtient à i=2, de base 𝐵 = [𝑎3 , 𝑎4 , 𝑎5 ], le vecteur de la 2ème colonne
(i=2) 𝑎4 de B sera le vecteur sortant, qui correspondant à la variable sortante 𝑥4 .
1 2 0
 La nouvelle base est donc: 𝐵 = [𝑎3 , 𝑎1 , 𝑎5 ] = [0 1 0] , 𝑐𝐵 = [0,2,0].
0 1 1
 La nouvelle solution de base est avec 𝑥1 = 1, 𝑥2 = 0, 𝑥3 = 5 − 2.1 =
3, 𝑥4 = 0, 𝑥5 = 3 − 1 = 2
 La 2ème solution de base réalisable SBR est 𝑋 = (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 )𝑡 = (1,0,3,0,2)𝑡
Avec la nouvelle valeur de la fonction objective est alors : Z= Z0 + (c1 – z1).x1 = 0 +
3.1 =3.
Peut-on améliorer à nouveau la valeur numérique de la fonction objective ?
 Il faut examiner les valeurs cj-zj pour les variables hors base qui sont dans ce cas
EN={x2 ,x4}
𝑐2 − 𝑧2 = 𝑐2 − 𝑐𝐵 . 𝐵−1 . 𝑎2 = 𝑐2 − 𝑐𝐵 . 𝜇2
𝑐4 − 𝑧4 = 𝑐4 − 𝑐𝐵 . 𝐵−1 . 𝑎4 = 𝑐4 − 𝑐𝐵 . 𝜇4
1 2 0 1 2 0 −1
Avec 𝐵 = [𝑎3 , 𝑎1 , 𝑎5 ] = [0 1 0], 𝑑𝑒𝑡 (𝐵) = 1 ≠ 0 ⟹ [0 1 0] =
0 1 1 0 1 1
1 −2 0
[ 0 1 0]
0 −1 1
1 −2 0 1 3
𝑐2 − 𝑧2 = 2 − [0,3,0]. [0 1 0] . [−1] = 2 − [0,3,0]. [−1] = 5
0 −1 1 1 2
1 −2 0 0 −2
𝑐4 − 𝑧4 = 0 − [0,3,0]. [0 1 0] . [1] = 0 − [0,3,0]. [ 1 ] = −3
0 −1 1 0 −1
 La solution de base précédente n’est pas optimale car le critère d’optimalité n’est
pas vérifié pas vérifié, on a 𝑐2 – 𝑧2 > 0.
 La variable entrante dans la base est x2 car:
𝑟 = 𝑎𝑟𝑔 𝑚𝑎𝑥 {𝑐𝑗 − 𝑧𝑗 |𝑐𝑗 − 𝑧𝑗 > 0} = 2
∀𝑗∈𝐸𝑁

Donc le vecteur a2 sera introduit dans la base.

 Recherche de la variable sortante:
On modifie la solution de départ selon l'expression:
𝑋𝐵 = 𝐵−1 . 𝑏 − 𝐵−1 . 𝑎2 . 𝑥2 = 𝑏 − 𝜇2 . 𝑥2
𝑥3 1 −2 0 5 1 −2 0 1
𝑥
On aura donc: 𝑋𝐵 = [ 1 ] = [0 1 0] . [1] − [0 1 0] . [−1] . 𝑥2
𝑥5 0 −1 1 3 0 −1 1 1
On obtient alors :
𝑥3 = 3 − 3𝑥2
𝑥1 = 1 + 𝑥2
𝑥5 = 2 − 2𝑥2
3 2
𝑠 = 𝑎𝑟𝑔 𝑚𝑖𝑛 { , } = {1, 3}
1≤𝑖≤3 3 2

𝑏1
𝑥3 = 𝑋𝐵1 =
𝜇1𝑟
𝑏3
𝑥5 = 𝑋𝐵3 =
𝜇3𝑟
Le minimum s'obtient à (i=1 ou i=3), de base 𝐵 = [𝑎3 , 𝑎1 , 𝑎5 ], le vecteur de la
1ère colonne (i=1) 𝑎3 ou de la 3ème colonne (i=3) 𝑎5 de B sera le vecteur sortant,
qui correspondant à la variable sortante 𝑥3 ou 𝑥5 , on choisit 𝑥5 .
1 2 1
 La nouvelle base est donc: 𝐵 = 𝑎3 , 𝑎1 , 𝑎2 = [0 1 −1] , 𝑐𝐵 = [0,3,2].
[ ]
0 1 1
 La nouvelle solution de base est avec 𝑥1 = 1 + 1 = 2, 𝑥2 = 1, 𝑥3 = 3 − 3.1 =
0, 𝑥4 = 0, 𝑥5 = 0
 La 3ème solution de base réalisable SBR est 𝑋 = (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 )𝑡 =
(2,1,0,0,0)𝑡
Avec la nouvelle valeur de la fonction objective est alors : Z= Z0 + (c2 – z2).x2
=3 + 5.1 =8.
Peut-on améliorer à nouveau la valeur numérique de la fonction objective ?
 Il faut examiner les valeurs cj-zj pour les variables hors base qui sont dans ce cas
EN={x4 ,x5}
𝑐4 − 𝑧4 = 𝑐4 − 𝑐𝐵 . 𝐵−1 . 𝑎4 = 𝑐4 − 𝑐𝐵 . 𝜇4
𝑐5 − 𝑧5 = 𝑐5 − 𝑐𝐵 . 𝐵−1 . 𝑎5 = 𝑐5 − 𝑐𝐵 . 𝜇5
1 2 1
Avec 𝐵 = [𝑎3 , 𝑎1 , 𝑎2 ] = [0 1 −1],
0 1 1
1 2 1 −1 1 −1/2 3/2
𝑑𝑒𝑡 (𝐵) = 2 ≠ 0 ⟹ [0 1 −1] = [0 1/2 1/2]
0 1 1 0 −1/2 1/2
 1 −1/2 −3/2 0 −1/2
1
𝑐4 − 𝑧4 = 0 − [0,3,2]. [0 1/2 1/2 ] . [1] = 0 − [0,3,2]. [ 1/2 ] = −
2
0 −1/2 1/2 0 −1/2
1 −1/2 −3/2 0 −3/2
5
𝑐5 − 𝑧5 = 0 − [0,3,2]. [0 1/2 1/2 ] . [0] = 0 − [0,3,2]. [ 1/2 ] = −
2
0 −1/2 1/2 1 1/2
La solution de base actuelle est optimale et unique (le critère d’optimalité est
vérifié, c.à.d. ∀𝑗 ∈ 𝐸𝑁 : 𝑐𝑗 − 𝑧𝑗 < 0).
Donc la solution optimale unique est 𝑋 ∗ = (𝑥1∗ , 𝑥2∗ , 𝑥3∗ , 𝑥4∗ , 𝑥5∗ )𝑡 = (2,1,0,0,0)𝑡 et
la valeur de la fonction objectif Z=8.

B) Illustration Graphique

2.
A) Résolution du PL avec la méthode simplexe algébrique
Étape 1: Initialisation
 Mise du PL sous forme standard (en rajoutant les variables d'écart)
𝑴𝒊𝒏 𝑍 = 2𝑥1 −𝑥2
𝐒𝐮𝐣𝐞𝐭 à:
−𝑥1 + 3𝑥2 + 𝑥3 = 3
−2𝑥1 − 𝑥2 + 𝑥4 = 2
2𝑥1 + 3𝑥2 + 𝑥5 = 6
3𝑥1 − 2𝑥2 + 𝑥6 = 6
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 ≥ 0
dont l'écriture matricielle est:
𝑴𝒊𝒏 𝑍 = 2𝑥1 − 𝑥2
𝐒𝐮𝐣𝐞𝐭 à:
𝑥1
−1 3 1 0 0 0 𝑥2 3
−2 −1 0 1 0 0 𝑥3 2
[ ]. 𝑥 = [ ]
2 3 0 0 1 0 4 6
3 −2 0 0 0 1 𝑥5 6
[𝑥6 ]
−1 3 1 0 0 0
−2 −1 0 1 0 0
La matrice 𝐴 = [𝑎1 , 𝑎2 , 𝑎3 , 𝑎4 , 𝑎5 , 𝑎6 ] = [ ]
2 3 0 0 1 0
3 −2 0 0 0 1
 Détermination d'une solution de base
o On choisit comme matrice de base (B) celle composée de vecteurs associés
aux variables d'écart:
1 0 0 0 −1 3 3
0 1 0 0 −2 −1 2
𝐵=[ ],𝑁 = [ ] , 𝑏 = [ ] , 𝑐𝐵 = [0,0,0,0], 𝑐𝑁 = [2, −1]
0 0 1 0 2 3 6
0 0 0 1 3 −2 6
o On pose 𝑋𝑁 = 0
o 𝑋𝐵 = 𝐵 −1 . 𝑏 = 𝑏̅ et 𝑍 = 𝑐𝐵 . 𝑋𝐵
1 0 0 0 −1 3 3
0 1 0 0 2 2
𝑋𝐵 = [ ] .[ ] = [ ]
0 0 1 0 6 6
0 0 0 1 6 6
3
2
𝑍 = [0,0,0,0]. [ ] = 0
6
6
o Pour chaque variable hors base 𝑗 ∈ 𝐸𝑁 = {1,2}, on calcule 𝑐𝑗 − 𝑧𝑗 avec 𝑧𝑗 =
𝑐𝐵 . 𝜇𝑗 , 𝜇𝑗 = 𝐵−1 . 𝑎𝑗 et 𝑎𝑗 est la colonne j de la matrice A.
 1 0 0 0 −1 −1
0 1 0 0 −2
c1 − z1 = 2 − [0,0,0,0]. [ ] .[ ] = 3
0 0 1 0 2
0 0 0 1 3
−1
1 0 0 0 3
0 1 0 0 −1
𝑐2 − 𝑧2 = −1 − [0,0,0,0]. [ ] . [ ] = −1
0 0 1 0 3
0 0 0 1 −2
Étape 2: Recherche de la solution optimale
 On teste si la solution de base actuelle est optimale, c.à.d. (∀𝑗 ∈ 𝐸𝑁 : 𝑐𝑗 − 𝑧𝑗 ≥ 0).
La solution de base actuelle n’est pas optimale car 𝑐2 − 𝑧2 < 0.
 On Détermine la variable entrante 𝑥𝑟 selon le critère:
𝑟 = 𝑎𝑟𝑔 𝑚𝑖𝑛{𝑐𝑗 − 𝑧𝑗 |𝑐𝑗 − 𝑧𝑗 < 0}
∀𝑗∈𝐸𝑁
𝑟 = 𝑎𝑟𝑔 𝑚𝑖𝑛{𝑐2 − 𝑧2 = −1} = 2
∀𝑗∈𝐸𝑁
Donc la variable entrante est 𝑥2 .
 On teste l'inexistence d'une solution optimale dont la valeur de Z est finie, c.à.d.
Si (𝜇𝑟 = 𝐵−1 . 𝑎𝑟 ≤ 0).
1 0 0 0 −1 3
0 1 0 0 −1
Cette condition n'est pas vérifiée car 𝜇2 = 𝐵−1 . 𝑎2 = [ ] .[ ] =
0 0 1 0 3
0 0 0 1 −2
3
−1 >
[ ] 0
3 <
−2
 On détermine alors la nouvelle solution de base comme suit:
𝑋𝐵 = 𝐵−1 . 𝑏 − 𝐵−1 . 𝑎𝑟 . 𝑥𝑟 = 𝑏 − 𝜇𝑟 . 𝑥𝑟 qui détermine la variable sortante 𝑥𝑘 selon
le critère:
𝑏𝑠 𝑏𝑖
𝑥𝑘 = 𝑋𝐵𝑠 = , 𝑠 = 𝑎𝑟𝑔 𝑚𝑖𝑛 { , 𝜇𝑖𝑟 > 0}
𝜇𝑠𝑟 1≤𝑖≤𝑚 𝜇𝑖𝑟
On modifie la solution de départ selon l'expression:
𝑋𝐵 = 𝐵−1 . 𝑏 − 𝐵−1 . 𝑎2 . 𝑥2 = 𝑏 − 𝜇2 . 𝑥2
𝑥3 1 0 0 0 −1 3 3
𝑥4 0 1 0 0 2 −1
On aura donc: 𝑋𝐵 = [𝑥 ] = [ ] . [ ] − [ ] . 𝑥2
5 0 0 1 0 6 3
𝑥6 0 0 0 1 6 −2
On obtient alors :
𝑥3 = 3 − 3𝑥2
𝑥4 = 2 + 𝑥2
,
𝑥5 = 6 − 3𝑥2
𝑥6 = 6 + 2𝑥2
3 6
𝑠 = 𝑎𝑟𝑔 𝑚𝑖𝑛 { , } = 1
1≤𝑖≤𝑚 3 3
𝑏1
𝑥3 = 𝑋𝐵1 =
𝜇1𝑟
Le minimum s'obtient à i=1, de base 𝐵 = [𝑎3 , 𝑎4 , 𝑎5 , 𝑎6 ], le vecteur de la 1ère
colonne (i=1) 𝑎3 de B sera le vecteur sortant, qui correspondant à la variable
sortante 𝑥3 .
  La nouvelle base est donc: 𝐵 = [𝑎2 , 𝑎4 , 𝑎5 , 𝑎6 ].
3 0 0 0
−1 1 0 0
𝐵=[ ] , 𝑐 = [−1,0,0,0].
3 0 1 0 𝐵
−2 0 0 1
 La nouvelle solution de base est avec 𝑥1 = 0, 𝑥2 = 1, 𝑥3 = 0, 𝑥4 = 2 + 1 = 3, 𝑥5 =
6 − 3.1 = 3, 𝑥6 = 6 + 2.1 = 8
 La 2ème solution de base réalisable SBR est 𝑋 = (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 )𝑡 =
(0,1,0,3,3,8)𝑡
Avec la nouvelle valeur de la fonction objective est alors :
Z= Z0 + (c2 – z2).x2 = 0 + -1.1 =-1.
Peut-on améliorer à nouveau la valeur numérique de la fonction objective ?
 Il faut examiner les valeurs cj-zj pour les variables hors base qui sont dans ce cas
EN={x1 ,x3}
𝑐1 − 𝑧1 = 𝑐1 − 𝑐𝐵 . 𝐵−1 . 𝑎1 = 𝑐1 − 𝑐𝐵 . 𝜇1
𝑐3 − 𝑧3 = 𝑐3 − 𝑐𝐵 . 𝐵−1 . 𝑎3 = 𝑐3 − 𝑐𝐵 . 𝜇3
3 0 0 0
−1 1 0 0
Avec 𝐵 = [𝑎2 , 𝑎4 , 𝑎5 , 𝑎6 ] = [ ], 𝑑𝑒𝑡 (𝐵) = 3 ≠ 0
3 0 1 0
−2 0 0 1
3 0 0 0 −1 1/3 0 0 0
−1 1 0 0 1/3 1 0 0
⟹[ ] =[ ]
3 0 1 0 −1/3 0 1 0
−2 0 0 1 2/3 0 0 1

1/3 0 0 0 −1 −1/3
1/3 1 0 0 −2 −7/3
𝑐1 − 𝑧1 = 2 − [−1,0,0,0]. [ ] . [ ] = 2 − [−1,0,0,0]. [ ]
−1/3 0 1 0 2 3
2/3 0 0 1 3 7/3
5
=
3
1/3 0 0 0 0 0
1/3 1 0 0 1 1
𝑐4 − 𝑧4 = 0 − [−1,0,0,0]. [ ] . [ ] = 0 − [−1,0,0,0]. [ ] = 0
−1/3 0 1 0 0 0
2/3 0 0 1 0 0
La solution de base actuelle est optimale et multiple car le critère d’optimalité est
vérifié (∀𝑗 ∈ 𝐸𝑁 : 𝑐𝑗 − 𝑧𝑗 ≤ 0) et (𝑐4 – 𝑧4 = 0).
Donc la solution optimale unique est 𝑋 ∗ = (𝑥1∗ , 𝑥2∗ , 𝑥3∗ , 𝑥4∗ , 𝑥5∗ , 𝑥6∗ )𝑡 =
= (0,1,0,3,3,8)𝑡 et la valeur de la fonction objectif Z=-1.

B) Illustration graphique du PL
NOTE:
En vert, les points dont on trouve la solution.
En rouge, les points qui ne satisfont pas les contraintes.
 Exercice 2
1)

 Mise du PL sous forme standard

𝑴𝒂𝒙 𝑍 = 5𝑥1 + 𝑥2 + 6𝑥3 +2𝑥4
𝑺𝒖𝒋𝒆𝒕 à:
4𝑥1 + 4𝑥2 + 4𝑥3 +𝑥4 + 𝑥5 = 44
8𝑥1 + 6𝑥2 + 4𝑥3 +3𝑥4 + 𝑥6 = 36
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 ≥ 0

Tableau 0
cj 5 1 6 2 0 0 Solution de base
CB Quotients
Variable de base x1 x2 x3 x4 x5 x6 XB=B-1.b
0 x5 4 4 4 1 1 0 44 44/4=11
x6: var sortante 0 x6 8 6 4 3 0 1 36 36/4=9 Min
cj-zj 5 1 6 2 0 0 Z=0

x3: variable entrante

Tableau 1
cj 5 1 6 2 0 0 Solution de base
CB
Variable de base x1 x2 x3 x4 x5 x6 XB=B-1.b
0 x5 -4 -2 0 -2 1 -1 8
6 x3 2 1.5 1 0.75 0 0.25 9
cj-zj -7 -8 0 -2.5 0 -1.5 Z=54
 La solution optimale est 𝑋 ∗ = (𝑥1∗ , 𝑥2∗ , 𝑥3∗ , 𝑥4∗ )𝑡 = (0,0,9,0𝑡 ) et la fonction Z=54.
2)

 Mise du PL sous forme standard

𝑴𝒂𝑥 𝑍 = 2 𝑥1 + 4 𝑥 2 + 1 𝑥3 + 1𝑥 4 + 0 𝑥5 + 0 𝑥6 + 0 𝑥7
𝑺𝒖𝒋𝒆𝒕 à ∶
𝑥1 + 3𝑥2 + 𝑥4 + 𝑥5 = 4
2𝑥1 + 𝑥2 + 𝑥6 = 3
𝑥2 + 4𝑥3 + 𝑥7 = 3
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 ≥ 0
 Tableau 0
cj 2 4 1 1 0 0 0
Solution de
CB Variable Quotients
x1 x2 x3 x4 x5 x6 x7 base XB=B-1.b
de base
x5: var sortante 0 x5 1 3 0 1 1 0 0 4 4/3=1.33 Min
0 x6 2 1 0 0 0 1 0 3 3/1=3
0 x7 0 1 4 0 0 0 1 3 3/1=3
cj-zj 2 4 1 1 0 0 0 Z=0

x2: variable entrante

Tableau 1
cj 2 4 1 1 0 0 0 Solution de base
CB Quotients
Var de base x1 x2 x3 x4 x5 x6 x7 XB=B-1.b
4 x2 1/3 1 0 1/3 1/3 0 0 4/3 --
0 x6 5/3 0 0 -1/3 -1/3 1 0 5/3 --
x7: var sortante 0 x7 -1/3 0 4 2/3 -1/3 0 1 5/3 5/34=5/12 Min
cj-zj 2/3 0 1 -1/3 -4/3 0 0 Z=16/3

x3: variable entrante

Tableau 2
cj 2 4 1 1 0 0 0 Solution de
CB Quotients
Var de base x1 x2 x3 x4 x5 x6 x7 base XB=B-1.b
4 x2 1/3 1 0 1/3 1/3 0 0 4/3 4/31/3=4
x6: var sortante 0 x6 5/3 0 0 -1/3 -1/3 1 0 5/3 5/35/3=1 Min
1 x3 -1/12 0 1 1/6 -1/12 0 1/4 5/12 --
cj-zj 3/4 0 0 -1/2 -5/4 0 1/4 Z=23/4

x1: variable entrante

Tableau 3
cj 2 4 1 1 0 0 0 Solution de
CB
Var de base x1 x2 x3 x4 x5 x6 x7 base XB=B-1.b
4 x2 0 1 0 2/5 2/5 -1/5 0 1
2 x1 1 0 0 -1/5 -1/5 3/5 0 1
1 x3 0 0 1 3/20 -1/10 1/20 1/4 1/2
cj-zj 0 0 0 -7/20 -11/10 -9/10 -1/4 Z=13/2
1
 La solution optimale est 𝑋 ∗ = (𝑥1∗ , 𝑥2∗ , 𝑥3∗ , 𝑥4∗ )𝑡 = (1,1, 2 , 0)𝑡 et la fonction Z=13/2.
3)

 Mise du PL sous forme standard

𝑴𝒂𝑥 𝑍 = 𝑥1 − 2 𝑥 2 + 𝑥3 + 0𝑥 4 + 0 𝑥5 + 0 𝑥6
𝑺𝒖𝒋𝒆𝒕 à ∶
𝑥1 + 2𝑥2 + 3𝑥3 + 𝑥4 = 12
2𝑥1 + 𝑥2 − 𝑥3 + 𝑥5 = 6
𝑥1 + 3𝑥2 + 𝑥6 = 3
 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 ≥ 0

Tableau 0
cj 1 -2 1 0 0 0
Solution de
CB Variable Quotients
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
0 x4 1 2 3 1 0 0 12 12/1=12
x5: var sortante 0 x5 2 1 -1 0 1 0 6 6/2=3 Min
0 x6 -1 3 0 0 0 1 3 --
cj-zj 1 -2 1 0 0 0 Z=0

x1: variable entrante

Tableau 1
cj 1 -2 1 0 0 0
Solution de
CB Variable Quotients
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
x4: var sortante 0 x4 0 3/3 7/2 1 -1/2 0 9 97/2=18/7 Min
1 x1 1 1/2 -1/2 0 1/2 0 3 --
0 x6 0 7/2 -1/2 0 1/2 1 12 --
cj-zj 0 -5/2 3/2 0 -1/2 0 Z=3

x3: variable entrante

Tableau 2
cj 2 4 1 1 0 0 Solution de
CB
Var de base x1 x2 x3 x4 x5 x6 base XB=B-1.b
1 x3 0 3/7 1 2/7 -1/7 0 18/7
1 x1 1 5/7 0 1/7 3/7 0 30/7
0 x6 0 26/7 0 1/7 3/7 1 93/7
cj-zj 0 -22/7 0 -3/7 -2/7 0 Z=48/7
30 18
 La solution optimale est 𝑋 ∗ = (𝑥1∗ , 𝑥2∗ , 𝑥3∗ )𝑡 = ( 7 , 0, 7 )𝑡 et la fonction Z=48/7.
4)

 Mise du PL sous forme standard

𝑴𝒂𝑥 𝑍 = 2𝑥1 + 3 𝑥 2 − 𝑥3
𝑺𝒖𝒋𝒆𝒕 à ∶
𝑥1 + 2𝑥2 −𝑥3 + 𝑥4 = 10
3𝑥1 − 2𝑥2 + 𝑥3 + 𝑥5 = 10
𝑥1 − 3𝑥2 + 𝑥3 + 𝑥6 = 10
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 ≥ 0
 Tableau 0
cj 2 3 -1 0 0 0
Solution de
CB Variable Quotients
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
x4: var sortante 0 x4 1 2 -1 1 0 0 10 10/2=5 Min
0 x5 3 -2 1 0 1 0 10 --
0 x6 1 -3 1 0 0 1 10 --
cj-zj 2 3 -1 0 0 0 Z=0

x2: variable entrante

Tableau 1
cj 2 3 -1 0 0 0
Solution de
CB Variable Quotients
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
3 x2 1/2 1 -1/2 1/2 0 0 5 51/2=10
x5: var sortante 0 x5 4 0 0 1 1 0 20 20/4=5 Min
0 x6 5/2 0 -1/2 3/2 0 1 25 255/2=10
cj-zj 1/2 0 1/2 -3/2 0 0 Z=15

x1: variable entrante

Tableau 1
cj 2 3 -1 0 0 0 Solution de
CB Variable base XB=B- Quotients
x1 x2 x3 x4 x5 x6 1
de base .b
3 x2 0 1 -1/2 3/8 -1/8 0 5/2 --
2 x1 1 0 0 1/4 1/4 0 5 --
0 x6 0 0 -1/2 7/8 -5/8 1 25/2 --
cj-zj 0 0 1/2 -13/8 -1/8 0 Z=35/2
 La solution n'est pas bornée.
5)

𝑥1 , 𝑥2 ≥ 0
 Mise du PL sous forme standard
𝑴𝒊𝒏 𝑍 = 2𝑥1 − 𝑥 2
𝑺𝒖𝒋𝒆𝒕 à ∶
−𝑥1 + 3𝑥2 +𝑥3 = 3
−2𝑥1 − 𝑥2 + 𝑥4 = 2
2𝑥1 + 3𝑥2 + 𝑥5 = 6
3𝑥1 − 2𝑥2 + 𝑥6 = 6
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 ≥0
 Tableau 0
cj 2 -1 0 0 0 0
Solution de
CB Variable Quotients
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
x3: var sortante 0 x3 -1 3 1 0 0 0 3 3/3=1 Min
0 x4 -2 -1 0 1 0 0 2 --
0 x5 2 3 0 0 1 0 6 6/3=2
0 x6 3 -2 0 0 0 1 6 --
cj-zj 2 -1 0 0 0 0 Z=0

x2: variable entrante

Tableau 1
cj 2 -1 0 0 0 0
Solution de
CB Variable
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
0 x2 -1/3 1 1/3 0 0 0 1
0 x4 -7/3 0 1/3 1 0 0 3
-1 x5 3 0 -1 0 1 0 3
0 x6 7/3 0 2/3 0 0 1 8
cj-zj 5/3 0 1/3 0 0 0 Z=-1
 La solution optimale est 𝑋 ∗ = (𝑥1∗ , 𝑥2∗ )𝑡 = (0,1)𝑡 et la fonction Z=-1.
Exercice 3

1)
 Mise du PL sous forme standard
𝑴𝒂𝒙 𝑍 = 2𝑥1 + 𝑥 2 + 6𝑥3 + −4𝑥 4
𝑺𝒖𝒋𝒆𝒕 à ∶
𝑥1 + 2𝑥2 +4𝑥3 − 𝑥4 + 𝑥 5 = 6
2𝑥1 + 3𝑥2 − 𝑥3 + 𝑥4 + 𝑥6 = 12
𝑥1 + 𝑥3 + 𝑥4 +𝑥7 = 2
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 ≥0
 Solution de base réalisable avec comme variables de base x1, x2, x4:
𝑡
1 2 −1 6 1 2 −1 −1 6
−1
𝑋𝐵 = (𝑥1 , 𝑥2, 𝑥4 ) , 𝐵 = [2 3 1 ] , 𝑏 = [12] ⟹ 𝑋𝐵 = 𝐵 . 𝑏 = [2 3 1 ] . [12] =
1 0 1 2 1 0 1 2
3/4 −1/2 5/4 6 1
[−1/4 1/2 −3/4] . [12] = [3] , cB = [2,1, −4],
−3/4 1/2 −1/4 2 1
𝑡
4 1 0 0
𝑋𝑁 = (𝑥3, 𝑥5 , 𝑥6 , 𝑥7 ) = 0, 𝑁 = [−1 0 1 0] , cN = [6,0,0,0], 𝐸𝑁 = {3,5,6,7}
1 0 0 1
Donc la solution de base réalisable est : 𝑋 = (𝑥1 , 𝑥2, 𝑥3 , 𝑥4, 𝑥5 , 𝑥6 , 𝑥7 )𝑡 = (1,3,0,1,0,0,0)𝑡
2)
 On teste l'optimalité de cette solution, i;e. (∀𝑗 ∈ 𝐸𝑁 : 𝑐𝑗 − 𝑧𝑗 ≤ 0 |𝑧𝑗 = 𝑐𝐵 . 𝜇𝑗 , 𝜇𝑗 =
𝐵 −1 . 𝑎𝑗 )
 3 1 5
−
4 2 4
1 1 3 4 89 65
𝑐3 − 𝑧3 = 6 − [2,1, −4]. − − . [−1] = 6 − =−
4 2 4 4 4
1
3 1 1
[− 4 2
− ]
4
3/4 −1/2 5/4 1 17 17
𝑐5 − 𝑧5 = 0 − [2,1, −4]. [−1/4 1/2 −3/4] . [0] = 0 − =−
−3/4 1/2 −1/4 0 4 4
3/4 −1/2 5/4 0 5 5
𝑐6 − 𝑧6 = [ ]
0 − 2,1, −4 . [ −1/4 1/2 −3/4] . [1] = 0 + =
−3/4 1/2 −1/4 0 2 2
3/4 1/2 5/4 0 11 11
𝑐7 − 𝑧7 = 0 − [2,1, −4]. [−1/4 1/2 −3/4] . [0] = 0 − =−
−3/4 1/2 −1/4 1 4 4
𝑐6 − 𝑧6 > 0, donc, non, cette solution n'est pas optimale.
 Recherche de solution optimale avec la méthode du simplexe tableaux:
3/4 −1/2 5/4 4 1 0 0 19/4 3/4 −1/2 5/4
𝐵−1 . 𝑁 = [−1/4 1/2 −3/4] . [−1 0 1 0 ] = [ −9/4 −1/4 1/2 −3/4]
−3/4 1/2 −1/4 1 0 0 1 −15/4 −3/4 1/2 −1/4
Tableau 0
cj 2 1 6 -4 0 0 0 Solution
CB Variable de base Quotients
x1 x2 x3 x4 x5 x6 x7
de base XB=B-1.b
2 x1 1 0 19/4 0 3/4 -1/2 5/4 1 --
1 x2 0 1 -9/4 0 -1/4 1/2 -3/4 3 31/2=6
x4: var sortante -4 x4 0 0 -15/4 1 -3/4 1/2 -1/4 1 11/2=2 Min
cj-zj 0 0 -65/4 0 -17/4 5/2 -11/4 Z=1

x6: variable entrante

Tableau 1
cj 2 1 6 -4 0 0 0 Solution
CB Variable de base Quotients
x1 x2 x3 x4 x5 x6 x7
de base XB=B-1.b
2 x1 1 0 1 1 0 0 1 2 2/1=2
x2: var sortante 1 x2 0 1 3/2 -1 1/2 0 -1/2 2 23/2=4/2 Min
0 x6 0 0 -15/2 2 -3/2 1 -1/2 2 --
cj-zj 0 0 5/2 -5 -1/2 0 -3/2 Z=6

x3: variable entrante

Tableau 2
cj 2 1 6 -4 0 0 0 Solution
CB Variable de base
x1 x2 x3 x4 x5 x6 x7
de base XB=B-1.b
2 x1 1 -2/3 0 5/3 -1/3 0 4/3 2/3
6 x3 0 2/3 1 -2/3 1/3 0 -1/3 4/3
0 x6 0 5 0 -3 1 1 -3 12
cj-zj 0 -5/3 0 -10/3 -4/3 0 -2/3 Z=28/3
2 4
 La solution optimale est 𝑋 ∗ = (𝑥1∗ , 𝑥2∗ , 𝑥3∗ , 𝑥4∗ )𝑡 = (3 , 0, 3 , 0)𝑡 et la fonction Z=28/3.
 Exercice 4

 Mise du PL sous forme standard:

𝑴𝒂𝒙 𝑍 = 2𝑥1 − 𝑥 2
𝑺𝒖𝒋𝒆𝒕 à ∶
2𝑥1 + 3𝑥2 = 6
𝑥1 − 2𝑥2 + 𝑥3 = 0
𝑥1 , 𝑥2 , 𝑥3 ≥0

Tableau 0
cj 2 -1 0 Solution
CB Variable de base Quotients
x1 x2 x3
de base XB=B-1.b
-1 x2 2/3 1 0 2 22/3=3
x3: var sortante 0 x3 7/3 0 1 4 47/3=12/7 Min
cj-zj 8/3 0 0 Z=-2

x1: variable entrante

Tableau 1
cj 2 -1 0 Solution
CB Variable de base
x1 x2 x3
de base XB=B-1.b
-1 x2 0 0 -2/7 6/7
2 x1 1 1 3/7 12/7
cj-zj 0 0 -8/7 Z=18/7
12 6
 La solution optimale est 𝑋 ∗ = (𝑥1∗ , 𝑥2∗ )𝑡 = ( 7 , 7)𝑡 et la fonction Z=18/7.
Exercice 5

7 10
 La matrice 𝐵 = [ ] est inversible car 𝑑𝑒𝑡(𝐵) = −21 ≠ 0 et son inverse est 𝐵−1 =
7 7
−1/3 10/21 −1/3 10/21 37
[ ]. Cette base est réalisable car 𝐵−1 . 𝑏 = [ ].[ ] =
1/3 −1/3 1/3 −1/3 26
1/21
[ ] ≥ 0.
11/3
7 10
 Écriture du PL par rapport à la base 𝐵 = [ ]:
7 7
3 5 8]
Soit la matrice hors-base 𝑁 = [ associée à B, on peut écrire:
4 8 6
𝐵. 𝑋𝐵 + 𝑁. 𝑋𝑁 = 𝑏, 𝑋𝐵 = (𝑥1 , 𝑥3 )𝑡 , 𝑋𝑁 = (𝑥2 , 𝑥4 , 𝑥5 )𝑡
{ 𝑡 4
𝑡 3
𝑐𝐵 . 𝑋𝐵 + 𝑐𝑁 . 𝑋𝑁 = 𝑍(𝑋), 𝑐𝐵 = [ ] , 𝑐𝑁 = [10]
4
3
𝑦1
𝑦2
D'où pour un 𝑌 = ( ⋮ ) quelconque de ℝ𝑚 on a:
𝑦𝑚
(𝑐𝐵 −𝑌 . 𝐵). 𝑋𝐵 + (𝑐𝑁𝑡 − 𝑌 𝑡 . 𝑁). 𝑋𝑁 = 𝑍(𝑋) − 𝑌 𝑡 . 𝑏
𝑡 𝑡
 En choisissant Y tel que:
𝑐𝐵𝑡 − 𝑌 𝑡 . 𝐵 = 0 ⟺ 𝑌 𝑡 = 𝑐𝐵𝑡 . 𝐵−1
On obtient alors:
𝑋𝐵 + 𝐵 −1 . 𝑁. 𝑋𝑁 = 𝐵−1 . 𝑏
{ 𝑡
(𝑐𝑁 − 𝑐𝐵𝑡 . 𝐵−1 . 𝑁). 𝑋𝑁 = 𝑍(𝑋) − 𝑐𝐵𝑡 . 𝐵−1 . 𝑏
Qui est l'écriture canonique du PL par rapport à la base B.
Cette écriture peut être représentée sous la forme suivante:

1 ⋯ 0
⋮ ⋱ ⋮ 𝑁 = 𝐵−1 . 𝑁 𝑏 = 𝐵 −1 . 𝑏
0 ⋯ 1
0 … 0 𝑐𝑁 = 𝑐𝑁 − 𝑐𝐵𝑡 . 𝐵−1 . 𝑁 𝑍(𝑋) − 𝑐𝐵𝑡 . 𝐵−1 . 𝑏
s
7 10
dDonc, l'écriture canonique du PL par rapport à la matrice de base 𝐵 = [ ] est:
7 7

1 0 19/21 15/7 4/21 1/21

0 1 −1/3 −1 2/3 11/3

0 0 55/21 53/7 −5/21 𝑍(𝑋) − 311/21

s
dAinsi pour 𝑥2 = 𝑥4 = 𝑥5 = 0, on obtient la solution de base 𝑥1 = 1 , 𝑥3 = 11 et 𝑍 = 311.
21 3 21
La base (𝑥1 , 𝑥1 ) n'est optimale.
Exercice 6

 Mise du PL sous forme standard en ajoutant des variables d'excès, d'écart, et artificielles,
selon qu'il convient:
o Comme la contrainte fonctionnelle 1 est de type '=' il est nécessaire d'ajouter la
variable artificielle x5.
o Comme la contrainte fonctionnelle 2 est de type '≥' il est nécessaire d'ajouter la
variable d'excès x3 et la variable artificielle x6.
o Comme la contrainte fonctionnelle 3 est de type '≤' il est nécessaire d'ajouter la
variable d'écart x4.
𝑴𝒊𝒏 𝑍 = 4𝑥1 + 𝑥 2
𝑺𝒖𝒋𝒆𝒕 à ∶
3𝑥1 + 𝑥2 + 𝑥5 = 3
4𝑥1 + 3𝑥2 − 𝑥3 + 𝑥6 = 6
𝑥1 ∓ 2𝑥2 + 𝑥4 = 4
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 ≥0
 Phase I:
La fonction objective à minimiser est la somme des variables artificielles et qui est:
𝑴𝒊𝒏 𝑍′ = 𝑥5 + 𝑥 6
Tableau 0
cj 0 0 0 0 1 1
Solution de
CB Variable Quotients
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
x5: var sortante 1 x5 3 1 0 0 1 0 3 3/3=1 Min
1 x6 4 3 -1 0 0 1 6 6/4=3/2
0 x4 1 2 0 1 0 0 4 4/1=4
cj-zj -7 -4 1 0 0 0 Z'=9

x1: variable entrante

Tableau 1
cj 0 0 0 0 1 1
Solution de
CB Variable Quotients
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
0 x1 1 1/3 0 0 1/3 0 1 11/3=3
x6: var sortante 1 x6 0 5/3 -1 0 -4/3 1 2 25/3=6/5 Min
0 x4 0 5/3 0 1 -1/3 0 3 35/3=9/5
cj-zj 0 -5/3 1 0 4/3 0 Z'=2

x2: variable entrante

Tableau 2
cj 0 0 0 0 1 1
Solution de
CB Variable
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
0 x1 1 0 1/5 0 3/5 -1/5 3/5
0 x2 0 1 -3/5 0 -4/5 3/5 6/5
0 x4 0 0 1 1 1 -1 1
cj-zj 0 0 0 0 1 1 Z'=0
Bien que Z'=0 et le critère d’optimalité est satisfait, alors la phase I est terminée et le PL
original admet des solutions réalisables.
Débutons la phase II en optimisant cette fois la fonction objectif du modèle original et en
éliminant du dernier tableau Phase I, les deux colonnes associées aux variables artificielles x5 et
x6.
Phase II:
la fonction à optimiser est celle du programme linéaire original qui est :
𝑴𝒊𝒏 𝑍 = 4𝑥1 + 𝑥 2 + 0𝑥3 + 0𝑥 4

Tableau 0
cj 4 1 0 0
Solution de
CB Variable Quotients
x1 x2 x3 x4 base XB=B-1.b
de base
4 x1 1 0 1/5 0 3/5 3/51/5=3
1 x2 0 1 -3/5 0 6/5 --
x4: var sortante 0 x4 0 0 1 1 1 1/1=1 Min
cj-zj 0 0 -1/5 0 Z=18/5

x3: variable entrante

 Tableau 1
cj 4 1 0 0
Solution de
CB Variable de
x1 x2 x3 x4 base XB=B-1.b
base
4 x1 1 0 0 -1/5 2/5
1 x2 0 1 0 3/5 9/5
0 x3 0 0 1 1 1
cj-zj 0 0 0 1/5 Z=17/5
2 9
 La solution optimale est 𝑋 ∗ = (𝑥1∗ , 𝑥2∗ )𝑡 = (5 , 5)𝑡 et la fonction Z=17/5.
Exercice 7

 Mise du PL sous forme standard en ajoutant des variables d'excès, d'écart, et artificielles, selon
qu'il convient:
o Comme la contrainte 1 est de type '≥', et le terme indépendant est négatif ou nulle (la
contrainte est multipliée par -1), il est nécessaire d'ajouter la variable d'écart x3.
o Comme la contrainte 2 est de type '≥' il est nécessaire d'ajouter la variable d'excès x4 et
la variable artificielle x6.
o Comme la contrainte 3 est de type '≥' il est nécessaire d'ajouter la variable d'excès x5 et
la variable artificielle x7.
o

𝑴𝒂𝒙 𝑍 = 3𝑥1 + 5𝑥 2 + 0𝑥3 + 0𝑥4 + 0𝑥5 − 𝑀𝑥6 − 𝑀𝑥7

𝑺𝒖𝒋𝒆𝒕 à ∶
𝑥1 − 𝑥2 + 𝑥3 = 1
2𝑥1 + 𝑥2 − 𝑥4 + 𝑥6 = 5
𝑥1 − 3𝑥2 − 𝑥5 + 𝑥7 = 2
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 ≥0
Où : M>0 et arbitrairement grand.
Tableau 0
cj 3 5 0 0 0 -M -M
Sol de base
CB Variable Quotients
x1 x2 x3 x4 x5 x6 x7 XB=B-1.b
de base
x3: var sortante 0 x3 1 -1 1 0 0 0 0 1 1/1=1 Min
-M x6 2 1 0 -1 -1 1 0 5 5/2
-M x7 1 -3 0 0 0 0 1 2 2/1=2
cj-zj 3+3M 5-2M 0 -M -M 0 0 Z=-7M

x1: variable entrante

 Tableau 1
cj 3 5 0 0 0 -M -M
Solution de
CB Variable
x1 x2 x3 x4 x5 x6 x7 base XB=B-1.b
de base
3 x1 1 -1 1 0 0 0 0 1
-M x6 0 3 -2 -1 0 1 0 3
-M x7 0 -2 -1 0 -1 0 1 1
cj-zj 0 8-M -3-3M -M -M 0 0 Z=3-4M
 Puisque le critère d’optimalité est satisfait et  des variables artificielles dans la base>0, i.e.
x6 =3 et x7=1, donc le PL n’admet pas de solutions réalisables.
Exercice 8

 Mise du PL en forme standard

𝑴𝒂𝒙 𝑍 = 2𝑥1 + 3𝑥 2 + 5𝑥3 + 4𝑥4
𝑺𝒖𝒋𝒆𝒕 à ∶
𝑥1 + 2𝑥2 + 3𝑥3 + 𝑥4 + 𝑥5 = 5
𝑥1 + 𝑥2 + 2𝑥3 + 3𝑥4 + 𝑥6 = 3
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 ≥0

Tableau 0
cj 2 3 5 4 0 0
Solution de
CB Variable Quotients
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
0 x5 1 2 3 1 1 0 5 5/3
x6: var sortante 0 x6 1 1 2 3 0 1 3 3/2 Min
cj-zj 2 3 5 4 0 0 Z'=0

x3: variable entrante

Tableau 1
cj 2 3 5 4 0 0
Solution de
CB Variable Quotients
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
x5: var sortante 0 x5 -1/2 1/2 0 -7/2 1 -3/2 1/2 1/21/2=1 Min
5 x3 3/2 1/2 1 3/2 0 1/2 3/2 3/21/2=3
cj-zj -1/2 1/2 0 -7/2 0 -5/2 Z=15/2

x2: variable entrante

Tableau 2
cj 2 3 5 4 0 0
Solution de
CB Variable
x1 x2 x3 x4 x5 x6 base XB=B-1.b
de base
3 x2 -1 1 0 -7 2 -3 1
5 x3 1 0 1 5 -1 2 1
cj-zj 0 0 0 0 -1 -1 Z=8
 La critère d'optimalité est vérifié et ( j{1,4} |cj-zj=0), donc il y a une infinité des valeurs de
x1, x2, x3, x4 pour la valeur optimale Z = 8, qui sont contenues dans la région de l'espace 2𝑥1 +
3𝑥 2 + 5𝑥3 + 4𝑥4 = 8 qui répond aux contraintes du problème. Une d'elles est: 𝑋 ∗ =
(𝑥1∗ , 𝑥2∗ , 𝑥3∗ , 𝑥4∗ )𝑡 = (0,1,1,0)𝑡 . Une autre est: 𝑋 ∗ = (𝑥1∗ , 𝑥2∗ , 𝑥3∗ , 𝑥4∗ )𝑡 = (1,2,0,0)𝑡