12/7/23, 4:30 PM M1.4.1 - PL -2324: Méthode de simplexe: 5.

1 - PL -2324: Méthode de simplexe: 5.2 Base, solution de base, forme canonique par rapport à une base

 ÉLÉMENTS DE RECHERCHE OPÉRATIONNELLE -


Programmation linéaire 2023-2024
Dashboard My courses M1.4.1 - PL -2324 5. Méthode de simplexe Méthode de simplexe



Méthode de simplexe 

5.2 Base, solution de base, forme canonique par rapport à une


base

Définition 5.2.1 Etant donné un programme linéaire sous forme standard :

Min z = cx
Ax = b (P)
x ≥ 0

tel que le système linéaire Ax = b soit de plein rang, on appelle base de ce programme linéaire un ensemble J ⊂
{1,2,...,n} d’indices de colonnes tel que AJ soit carrée non singulière. AJ est la matrice de base correspondante à J.

Définition 5.2.2 Si J est une base, les m variables associées aux indices de J sont appelées variables de base, elles
constituent un sous-vecteur xJ de x. Les autres variables sont appelées variables hors base.

Exemple 5.2.3. Dans l’exemple 5.1.8, m = 3 et il y a 5 variables au total. Le plein rang est 3, donc une base aura 3 indices
et il y aura systématiquement 3 variables de bases et 2 variables hors base. Donnons quelques exemples

⎡1 1 0 ⎤
La famille {1, 3, 4} associée aux variables {x, e1, e2} ne forme pas une base car la sous matrice associée ⎢ 3 0 1 ⎥ n’est
⎢ ⎥
⎣0 0 0 ⎦
pas inversible.
⎡ 2 1 0⎤
La famille {2, 3, 5} associée aux variables {y, e1, e3} forme une base car la sous matrice associée ⎢ −4 0 0 ⎥ est
⎢ ⎥
⎣ 1 0 1⎦
inversible. Ici, {x, e2} sont hors base.

⎡1 2 1 ⎤
La famille {1, 2, 3} associée aux variables {x, y, e1} forme une base car la sous matrice associée ⎢ 3 −4 0 ⎥ est
⎢ ⎥
⎣0 1 0 ⎦
inversible. Ici, {e2, e3} sont hors base.

Définition 5.2.4

Si J est une base du programme linéaire (P). On appelle solution de base associée à la base J qu'on notera x (J), la
solution du système linéaire Ax = b définie par :
xJ = (AJ)-1 b

xJ = 0

Remarque 5.2.5. La solution de base est définie tout à bord par mettre les variables de hors bas à 0, ensuite retrouvé
les variables de base en résolvant le système Ax = b, ce qui donne le résultat xJ = (AJ)-1 b.

Définition 5.2.6

Une solution de base x (J) est dite dégénérée si certaines de ses composantes xJ ont une valeur nulle.
Une solution de base est dite réalisable s'elle vérifie les contraintes de non négativité, i.e. xJ ≥ 0.
Une base J est dite réalisable si la solution de base associée est réalisable.

Exemples 5.2.7 Voyons ce que cela donne sur les exemples précédents 5.2.3.

i-skills.ma/mod/lesson/view.php?id=541&pageid=362 1/3
12/7/23, 4:30 PM M1.4.1 - PL -2324: Méthode de simplexe: 5.2 Base, solution de base, forme canonique par rapport à une base

Considérons la base {2, 3, 5}. La solution de base correspondante est (0, -3, 10, 0, 6). Ce n’est donc pas une solution
de base réalisable (y = -3 < 0).
Considérons la base {1, 3, 5}. La solution de base correspondante est (4, 0, 0, 0, 3) et c’est une solution de base
réalisable. Elle est aussi solution de base dégénérée (puisque e1 est une variable de base avec une valeur de 0)

Définition 5.2.8 Etant un problème écrit sous forme standard :

 Min z = cx
Ax = b (P)
 x ≥ 0

 S'il vérifie les deux propriétés suivantes :

1. Les coefficients de la fonction objectif associés aux variables de base sont nuls; cJ = 0

2. La matrice associée aux variables de base AJ est la matrice identité (à une permutation près),


on dit qu’il est écrit sous forme canonique par rapport à la base J correspondante.

 Définition 5.2.9. Etant donné, un PL écrit sous forme canonique par rapport à une base J, on appelle “ vecteur coût
relatif à la base J " , le vecteur c(J) =( cJ, c J ) avec cJ = 0.

Définition 5.2.10 Un P.L. (P) sera dit écrit sous forme canonique par rapport à une base réalisable J,

 Min z = cx
Ax = b (P)
x ≥ 0

si en plus de (1) et (2) dans la définition 5.2.8 on a :

3. b ≥ 0 c’est à dire J est une base réalisable.

Exemple 5.2.11. Dans l'exemple 5.1.8, le programme standard ci-dessous est écrit sous forme canonique par rapport à
la base J={ 3, 4, 5}. Puisque b =(4, 12, 3) ≥ 0, J est une base réalisable et on a aussi x(J) =(0, 0, 4, 12, 3) et c(J) =(5, 7, 0,
0, 0)

Max z = 5x + 7y
s.c. x + 2y + e1 =4
3x − 4y + e2 = 12
y + e3 = 3
x, y, e1, e2 , e3 ≥ 0

Remarque 5.2.12 Etant un PL écrit sous la forme canonique dans le cas de maximisation ou minimisation. Lorsque les
coefficients bi sont positifs ou nuls, on obtient systématiquement une forme canonique par rapport à une base
réalisable associée aux variables d'écart. La solution de base sera définie en mettant les variables du problème initial
hors base (donc nulles) et les variables d’écart dans la base et égales aux bi . Cette écriture est le point de départ de
l’algorithme du simplexe.

Remarque 5.2.13. Passage de la forme standard à la forme canonique par rapport à une base

Etant donné un P.L. écrit sous forme standard

Min z = cx
Ax = b (P)
x ≥ 0

tel que (Ax = b) est de plein rang.

Si J est une base de (P), on peut passer de la forme standard (P) à la forme équivalente dite forme canonique par
rapport à la base J comme suit :

où π est tel que : π AJ = c J

π est appelé vecteur multiplicateur du Simplexe relatif à la base J

i-skills.ma/mod/lesson/view.php?id=541&pageid=362 2/3
12/7/23, 4:30 PM M1.4.1 - PL -2324: Méthode de simplexe: 5.2 Base, solution de base, forme canonique par rapport à une base

Théorème 5.2.14 Si le vecteur coût relatif à une base réalisable J d’un PL où la fonction objective est à minimiser (resp.
à maximiser) est positif ou nul (resp. négatif ou nul), la solution de base associée à J est solution optimale du PL
étudié.

 Remarque 5.2.15. Etant un programme linéaire écrit sous forme canonique par rapport à une base réalisable comme
suit :

 Min z = cx - z0
Ax = b (P)
 x ≥ 0

 Il est intéressant pour 3 raisons :

1. la solution de base x(J) associée à la base J se lit immédiatement : xJ = b ; x J = 0


2. l’évaluation de la fonction objective en x(J) se lit facilement : c’est la constante z0 .


3. la troisième raison qui est la raison essentielle est qu’on peut facilement vérifier si la solution de base actuelle x
(J) est solution optimale ou non (théorème 5.2.14).



Next

You have completed 14% of the lesson

14%

 Jump to... Discussions autour de la section 5 ►

◄ Discussions autour de la section 4 

Stay in touch Data retention summary

i-skills.ma
 http://www.i-skills.ma
 [email protected]

PROUDLY MADE WITH

Made with  by conecti.me

i-skills.ma/mod/lesson/view.php?id=541&pageid=362 3/3