Mathématiques pour l’ingénieur troisième année

Systèmes linéaires
Version enseignant Mourad ABOUZAID

ISABTP 3○ année
2021-2022

Dernière compilation : 10 novembre 2021

Table des matières
Introduction 5

1 Définitions 5

2 Systèmes de Cramer 11
2.1 Résolution théorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Systèmes de Cramer triangulaires . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Le pivot de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Applications du Pivot de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Systèmes sur déterminés 29

3.1 Un exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 La méthode des moindres carrés . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3 Mesure de l’erreur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Application : la régression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4 Systèmes sous-déterminés et optimisation 45

4.1 Programme linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3 Simplexe et compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3
Introduction
De nombreux problème (physiques et mathématiques) peuvent se traduire sous forme
d’équations linéaires ou de familles d’équations linéaires. Or les matrices et le calcul ma-
triciel donnent un outil très efficace pour représenter ces types de problèmes et plus
généralement tout problème ayant un caractère linéaire :

● des familles d’équations ou inéquations linéaires,

● des familles de vecteurs (exprimés dans une base),
● des applications linéaires,
● des équations différentielles...

L’objectif de ce cours est de présenter des méthodes algorithmiques de résolution de

systèmes linéaires, rendues possibles par la représentation matricielle.

Après quelques rappels théoriques sur systèmes linéaires et de leurs solutions, nous
verrons comment, en traduisant la résolution d’un système en termes d’opérations matri-
cielles, on peut élaborer ces méthodes algorithmiques.

Nous étudierons essentiellement une méthode : le pivot de Gauss ; dont l’idée générale
est de construire, à partir du système de départ, un système équivalent (i.e. qui admet
les mêmes solutions), plus simple à résoudre. Dans le cas du pivot de Gauss, l’objectif est
d’obtenir un système triangulaire.

Dans un second temps, nous étudierons quelques exemples de problème pouvant se

ramener à des systèmes linéaires. Nous verrons ainsi comment résoudre des systèmes
linéaires comportant plus de contraintes que de degrés de liberté.

1 Définitions

Définition (équation linéaire)

Une équation linéaire portant sur les inconnues x1 , . . . , xp est une équation de la forme

(E) ∶ a1 x1 + a2 x2 + . . . + ap xp = b
où

● Les ai ∈ R (connus) sont les coefficients de l’équation.

● Le réel b ∈ R (connu) est le second membre de l’équation.
Si b = 0, l’équation (E) est dite homogène.

5
Définition (système linéaire)

Un système linéaire portant sur les inconnues x1 , . . . , xp est la donnée d’un ensemble
d’équations linéaires portant sur les inconnues x1 , . . . , xp :

⎧
⎪ a11 x1 + ⋯ + a1p xn = b1 (E1 )
⎪
⎪
⎪
⎪ a x + ⋯ + a2p xn = b2 (E2 )
(S) = ⎨ 21 1 = {(E1 ), . . . , (En )}
⎪
⎪ ⋮ ⋮ ⋮
⎪
⎪
⎪
⎩ n1 1
a x + ⋯ + a x
np n = b n (En )

Ici,
● p ∈ N∗ est le nombre d’inconnues.
● n ∈ N∗ est le nombre d’équations.
● Les réels aij ∈ R (connus) sont les coefficients du système (S).
● Les réels bi ∈ R (connues) forment le second membre de (S).
S’ils sont tous nuls, le système est dit homogène.

Définition (solutions d’un système linéaire)

Soit (S) un système linéaire de n équations à p inconnues.

● Une solution de (S) est un p-uplet (x1 , . . . , xp ) ∈ Rp satisfaisant l’ensemble des

équations.

● Résoudre (S), c’est déterminer l’ensemble de ses solutions.

● Deux systèmes linéaires (S1 ) et (S2 ) sont dits équivalents si ils possèdent le même
ensemble de solutions.

Note : l’ensemble Σ des solutions d’un système linéaire à p inconnues est donc un
sous ensemble de Rp . Dans les cas p = 2 et p = 3, il est alors possible de représenter cet
ensemble comme une partie du plan ou de l’espace, munis de repères.

Précisément,
● En dimension 2, chaque équation peut être associée à une droite du plan, muni
d’un repère.
● En dimension 3, chaque équation peut être associée à un plan de l’espace muni
d’un repère.

L’ensemble Σ des solutions d’un système linéaire correspond alors à l’intersection de

7
droites ou de plans (exercice : faire la liste des différentes intersections possibles dans le
plan et dans l’espace).

Enfin, tout système linéaire peut être représenter sous forme matricielle. Précisément,
Définition (matrices d’un système linéaire)

Soit (S) un système linéaire de n équations à p inconnues. Avec les notations ci-dessus,
on appelle

⎛ a11 ⋯ a1p ⎞
⎜ a21 ⋯ a2p ⎟
● A=⎜ ⎟ ∈ Mnp (R) la matrice de (S),
⎜ ⋮ ⋮ ⎟
⎝ an1 ⋯ anp ⎠
⎛ x1 ⎞
● X = ⎜ ⋮ ⎟ ∈ Mp,1 (R) le vecteur inconnu,
⎝ xp ⎠
⎛ b1 ⎞
● B = ⎜ ⋮ ⎟ ∈ Mn,1 (R) le vecteur second membre.
⎝ bn ⎠
D’après la définition du produit de matrice, on a alors

(S) ⇐⇒ A × X = B

Enfin, on appelle matrice étendue du système (S) la matrice

⎛ a11 a12 ⋯ a1p b1 ⎞

⎜ a21 a22 ⋯ a2p b2 ⎟
à = ⎜ ⎟
⎜ ⋮ ⋮ ⋱ ⋮ ⋮ ⎟
⎝ an1 an2 ⋯ anp bn ⎠

Cette représentation matricielle est le premier outil permettant de confier la résolution

d’un système linéaire à un ordinateur. Elle permet en effet de représenter n’importe quel
système sous la forme d’un tableau de chiffres. Les manipulations permettant d’aboutir à
la résolution d’un système linéaire se traduisant par des manipulations de lignes sur ses
matrices.

9
2 Systèmes de Cramer
2.1 Résolution théorique

Définition (système de Cramer)

Un système de Cramer est un système linéaire de n équations à n inconnues dont la

matrice est inversible.

Un système de Cramer est donc un système linéaire carré de la forme AX = B admettant

pour unique solution le vecteur

X0 = A−1 × B ∈ Rn
Par analogie, les systèmes de Cramer sont également dits inversibles.

D’un point de vue pratique, la résolution d’un tel système est donc équivalent au calcul
de la matrice inverse A−1 .

Notons que Cramer a également donné des formules permettant d’exprimer les coor-
données de l’unique solution X0 cherchée à l’aide de déterminants.

Précisément, pour tout j ∈ {1, . . . , n}, notons Aj la matrice obtenue en remplaçant la

j-ième colonne de A par le second membre B. L’unique solution X0 = (x1 , . . . , xn ) vérifie

det(Aj )
∀j ∈ {1, . . . , n}, xj =
det(A)

Cependant, bien que particulièrement élégante, cette formule n’est jamais utilisée (sauf
éventuellement sur des tout petits systèmes linéaires) car son application nécessite le
calcul de n + 1 déterminants de taille n × n. Or nous verrons dans la suite que la résolution
pratique du système AX = B est équivalente (en temps de calcul) au calcul d’un seul de
ces déterminants.

2.2 Systèmes de Cramer triangulaires

Définition (système triangulaire)

Un système linéaire (S) ∶ AX = B est dit triangulaire supérieur (resp. inférieur) si sa

matrice A est triangulaire supérieure (resp. inférieure) :

⎛ a11 a12 ⋯ a1n ⎞ ⎛ a11 0 ⋯ 0 ⎞

⎜ 0 a22 ⋯ a2n ⎟ ⎜ a21 a22 ⋱ ⋮ ⎟
A = ⎜ ⎟ resp. A = ⎜ ⎟
⎜ ⋮ ⋱ ⋱ ⋮ ⎟ ⎜ ⋮ ⋮ ⋱ 0 ⎟
⎝ 0 ⋯ 0 ann ⎠ ⎝ an1 an2 ⋯ ann ⎠

11
 Autrement dit, un système triangulaire (supérieur) est de la forme

⎧
⎪ a11 x1 + a12 x2 + . . . + a1,n−1 xn−1 + a1n xn = b1 (E1 )
⎪
⎪
⎪
⎪
⎪
⎪ a22 x2 + . . . + a2,n−1 xn−1 + a2n xn = b2 (E2 )
⎪
(T ) ∶ ⎨ ⋱ ⋮ ⋮
⎪
⎪
⎪
⎪
⎪ an−1,n−1 xn−1 + an−1,n xn = bn−1 (En−1 )
⎪
⎪
⎪
⎩ ann xn = bn (En )

On peut montrer qu’un tel système est inversible si et seulement si aucun de ses coefficients
diagonaux n’est nul.

Il existe alors un algorithme “simple” permettant de déterminer l’unique solution d’un

tel système en un minimum d’opérations. Précisément, dans le cas d’un système triangu-
laire supérieur,

1. La dernière équation permet d’obtenir l’inconnue xn :

bn
(En ) ⇒ xn =
ann

2. L’avant-dernière équation permet d’exprimer xn−1 en fonction de xn (calculée pré-

cédemment) :
1
(En−1 ) ⇒ xn−1 = (bn − an−1,n xn )
an−1,n−1
3. etc. jusqu’à la première équation qui permet d’exprimer la première inconnue x1
en fonction des autres :
n
1
(E1 ) ⇒ x1 = (b1 − ∑ a1k xk )
a11 k=2

De façon générale, la coordonnée xj de l’unique solution cherchée est obtenue à partir

de l’équation (Ej ) :

1 ⎛ n ⎞
(Ej ) ⇒ xj = bj − ∑ ajk xk
ajj ⎝ k=j+1 ⎠

On obtient alors l’algorithme suivant :

13
 Entrées : A = (aij ) ∈ Mn (R), B = (b1 , . . . , bn ) ∈ Rn

1. On initialise X à un vecteur à n coordonnées x1 = x2 = . . . = xn = 0.

2. Pour j allant de n à 1 :
n
3. s ← ∑ ajk xk
k=j+1

4. d ← bj − s

5. xj ← d/ajj

6. Renvoyer X = (x1 , . . . , xn )

Pour évaluer la qualité de cette méthode, on doit estimer le nombre d’opérations

nécessaires au calcul de la solution X0 = (x1 , . . . , xn ) cherchée.
Or, pour le calcul d’une coordonnée xj de X0 , on a :
● Nombre d’additions : n − j,
● Nombre de soustractions : 1 (sauf à l’étape 1),
● Nombre de divisions : 1.

Ainsi, pour le calcul des n coordonnées de X0 , on a

n(n − 1)
● Nombre d’additions : (n − 1) + (n − 2) + . . . + 1 = = O(n2 ),
2
● Nombre de soustractions : 1 + 1 + . . . + 1 = n − 1 = O(n),

● Nombre de divisions : 1 + 1 + . . . + 1 = n = O(n).

Le nombre total d’opérations nécessaires est donc

O(n2 ) + O(n) + O(n) = O(n2 )

2.3 Le pivot de Gauss

2.3.1 Opérations élémentaires
Le pivot de Gauss est une méthode de résolution des systèmes de Cramer consistant
à transformer un système donné en un système triangulaire équivalent.

Le principe du pivot est basé sur deux opérations élémentaires que l’on peut effec-
tuer sur les équations d’un système (ou sur les lignes de sa matrice étendue) permettant

15
d’éliminer certaines inconnues de certaines équations, sans changer l’ensemble des solu-
tions. Ces deux opérations élémentaires sont :
● La combinaison : (Ei ) ← (Ei ) + λ.(Ej ), i ≠ j et λ ∈ R.

● La permutation : (Ei ) ↔ (Ej ).

Note : dans certaines applications, on pourra également faire appel à une troisième
opération élémentaire : la multiplication extérieure :

(Ei ) ← λ.(Ei ) λ≠0

2.3.2 Un exemple
Considérons le système suivant :
⎧
⎪ 2x1 + x2 − 2x3 + x4 = 0
⎪
⎪
⎪
⎪ 4x1 − x2 + 4x3 − 2x4 = 6
⎨
⎪
⎪ x1 − x2 + 2x3 − x4 = 3
⎪
⎪
⎪
⎩ −2x1 + 2x2 − 2x3 − x4 = −3

dont la matrice étendue est

⎛ 2 1 −2 1 0 ⎞
⎜ 4 −1 4 −2 6 ⎟
à = ⎜ ⎟
⎜ 1 −1 2 −1 3 ⎟
⎝ −2 2 −2 −1 −3 ⎠

La première étape du Pivot consiste à utiliser la première équation du système pour

éliminer la variable x des autres équations (ou à placer des 0 dans la première colonne,
sous le premier coefficient de la première ligne). Précisément, le premier coefficient de la
première ligne (2) est le premier pivot. On s’appuie dessus pour effectuer les combinaisons
suivantes :

L2 ← L2 − 2L1

L3 ← L3 − 12 L1 ,

L4 ← L4 + L1 .

On obtient alors la matrice

17
 ⎛ 2 1 −2 1 0 ⎞
⎜ 0 −3 8 −4 6 ⎟
Ã(2) = ⎜ ⎟.
⎜ 0 − 32 3 − 32 3 ⎟
⎝ 0 3 −4 0 −3 ⎠

La première étape est terminée. On a traité la première colonne à l’aide de la première

ligne. On passe ensuite à la deuxième colonne que l’on va traiter à l’aide de la deuxième
ligne. Le nouveau pivot est alors le deuxième coefficient de la deuxième ligne (-3) et les
opérations et l’on place des 0 dessous à l’aide des combinaisons
1
L3 ← L3 − L2
2

L4 ← L4 + L2

qui transforment Ã(2) en

⎛ 2 1 −2 1 0 ⎞
⎜ 0 −3 8 −4 6 ⎟
Ã(3) = ⎜ ⎟.
⎜ 0 0 −1 21 0 ⎟
⎝ 0 0 4 −4 3 ⎠

Note : cette seconde étape revient, du point de vue du système à supprimer la va-
riable y des deux dernières équations.

On a terminé le traitement de la seconde colonne. Il reste ici à traiter la troisième

colonne en plaçant un dernier 0 sous le dernier pivot (-1). Cela se fait à l’aide de la
combinaison

L4 ← L4 + 4L3

qui transforme la matrice Ã(3) en

⎛ 2 1 −2 1 0 ⎞
⎜ 0 −3 8 −4 6 ⎟
Ã(4) = ⎜ ⎟.
⎜ 0 0 −1 1
2 0
⎟
⎝ 0 0 0 −2 3 ⎠

On a ici terminé le pivot de Gauss. Le système (S) de départ est donc équivalent au
système triangulaire

19
 ⎧
⎪ 2x1 + x2 − 2x3 + x4 = 0
⎪
⎪
⎪
⎪ − 3x2 + 8x3 − 4x4 = 6
(S) ∶ ⎨
⎪
⎪ − x3 − 12 x4 = 0
⎪
⎪
⎪
⎩ − 2x4 = 3

On résout alors ce système triangulaire “en remontant” et on obtient la solution cher-

chée.

2.3.3 L’algorithme
À partir de l’exemple que l’on vient de voir, on peut construire les premières fonctions
de l’algorithme du pivot de Gauss.
Pour cela, il faut généraliser les opérations précédentes à une matrice générale A de
la forme
⎛ a11 a12 a13 ⋯ a1n ⎞
⎜ a21 a22 a23 ⋯ a2n ⎟
⎜ ⎟
A = (aij ) = ⎜
⎜ a31 a32 a33 ⋯ a3n ⎟
⎟
⎜ ⋮ ⋮ ⋮ ⋱ ⋮ ⎟
⎜ ⎟
⎝ an1 an2 an3 ⋯ ann ⎠
Le premier pivot est a11 . Pour construire A(2) , on effectue les opérations
a21
L2 ← L2 − L1
a11
a31
L3 ← L3 − L1
a11
⋮
an1
Ln ← Ln − L1
a11

On obtient alors la matrice

(2) (2) (2) (2)
⎛ a11 a12 a13 ⋯ a1n ⎞
⎜ ⎟
⎜ ⎟
⎜ (2) (2) (2) ⎟
⋯ a2n ⎟
⎜ 0 a22 a23
⎜ ⎟
⎜ ⎟
(2) ⎜ ⎟
A = (aij ) = ⎜
(2)
⎜ 0 a32
(2) (2)
a33
(2) ⎟
⋯ a3n ⎟
⎜ ⎟
⎜ ⎟
⎜ ⎟
⎜ ⋮ ⋮ ⋮ ⋱ ⋮ ⎟
⎜ ⎟
⎜ ⎟
⎜ ⎟
⎝ (2) (2) (2) ⎠
0 an2 an3 ⋯ ann

D’un point de vue algorithmique, cette opération correspond à une boucle Pour :

21
 Pour i allant de 2 à n :
ai1
Li ← Li − L1
a11

De façon générale, pour passer de

(j) (j) (j) (j)
⎛ a11 a12 ⋯ a1j ⋯ a1n ⎞
⎜ (j)
a22 ⋱ ⋮ ⋮ ⎟
⎜ 0 ⎟
⎜ ⎟
⎜ ⋮ ⋱ ⋱ ⋮ ⋮ ⎟
⎜ ⎟
⎜ (j) ⎟
⎜ ⋮ 0 ajj ⋮ ⎟
A =⎜
(j)
⎜
⎟
⎟
⎜ (j) ⎟
⎜ ⋮ ⋮ aj+1,j ⋱ ⋮ ⎟
⎜ ⎟
⎜ 0 ⋯ 0 ⋮ ⋱ ⋮ ⎟
⎜ ⎟
⎜ ⋮ ⋮ ⋮ ⋱ ⋮ ⎟
⎜ ⎟
(j) (j)
⎝ 0 ⋯ 0 anj ⋯ ⋯ ⋯ ann ⎠

à une matrice A(j+1) qui contient une colonne de zéros supplémentaire, on effectue les
opérations
(j)
aj+1,j
Lj+1 ← Lj+1 − (j)
Lj
ajj
⋮
(j)
anj
Ln ← Ln − (j)
Lj
ajj

qui correspond là encore à une boucle Pour :

Pour i allant de j+1 à n :

aij
Li ← Li − Lj
ajj

Dans une première approche, le pivot de Gauss se résume donc à une double boucle
Pour, permettant de traiter toutes les colonnes une par une. Cependant, on constate qu’à
chaque étape, on divise par le pivot ajj . Cela n’est donc valable si, pour chaque colonne,
le pivot est non nul. Or rien ne nous garantie que cela soit le cas.

23
 Exemple : soit
⎛ 1 −1 0 ⎞
A = ⎜ 1 −1 1 ⎟
⎝ 0 1 1 ⎠
Après la première étape du pivot, on obtient la matrice

⎛ 1 −1 0 ⎞
A2 = ⎜ 0 0 1 ⎟
⎝ 0 1 1 ⎠

Pour pouvoir continuer le Pivot, il faut échanger les deux dernières lignes de A2 :

⎛ 1 −1 0 ⎞
L2 ↔ L3 ↝ A′2 = ⎜ 0 1 1 ⎟
⎝ 0 0 1 ⎠

Une fois que l’on a échangé le pivot avec un pivot non nul, on peut continuer le pro-
cédé. (Ici, on a terminé car la matrice est petite).

Pour trouver un pivot non nul, on a donc parcourus la colonne se trouvant sous le
pivot nul à la recherche d’un coefficient non nul. Une fois repéré, on a échangé la ligne
correspondante avec la ligne du pivot nul.

On peut traduire cette recherche sous forme algorithmique. Précisément, si le j-ième

pivot ajj est nul, on effectue la recherche suivante :

Pour k allant de j+1 à n :

Si akj <> 0 :
Lj ←→ Lk
Arrêt de la boucle

Notons que, puisque chaque étape modifie l’ensemble des coefficients de la matrice
traitée, il est impossible d’anticiper l’apparition d’éventuels pivots nuls. Pour avoir un
algorithme qui marche, il faut donc ajouter cette boucle/test au cœur de la double boucle
précédente afin de s’assurer que l’on travaille toujours avec un pivot non nul.

Notes :
● Cette boucle/test permet de produire un pivot non nul à condition que l’ordina-
teur puisse trouver, parmi les candidats au pivot, un coefficient non nul. On peut
montrer que c’est toujours le cas si la matrice traitée est inversible.

25
 ● En pratique, même pour les matrices inversibles, il peut arriver que l’algorithme
n’aboutisse pas ou renvoie un résultat erroné lorsque les coefficients sont trop gros
ou trop petits, de sorte que l’on arrive aux limites de stockage et/ou de précision de
la machine. Ces problèmes interviennent en particulier lorsque l’on travaille avec
de très gros matrices, nécessitant un nombre important de calculs. Pour palier à
ces problèmes, il est possible d’améliorer le choix du pivot, mais les problèmes de
stabilité des coefficients reste un problème difficile en algorithmique.

2.4 Applications du Pivot de Gauss

2.4.1 Résolution de systèmes linéaires
La première application du Pivot de Gauss est bien entendu la résolution de “gros”
systèmes de Cramer. En effet, couplé à l’algorithme de résolution des systèmes triangu-
laires décrit à la section 2.2, le pivot produit un algorithme de résolution dont le nombre
d’opérations est de l’ordre de grandeur de n3 (n étant le nombre d’équations du système).

2.4.2 Calcul de déterminant

La notion de déterminant est au cœur de nombreux problèmes d’algèbre linéaire.

À la main, la méthode la plus utilisée consiste à développer le déterminant que l’on

souhaite calculer par rapport à l’une de ces lignes ou l’une de ses colonnes.

En pratique, cela revient à remplacer le déterminant n × n cherché par la somme de n

déterminants de taille (n − 1) × (n − 1). On obtient ainsi un processus récursif permettant
de revenir au calcul de déterminants 2 × 2 dont le nombre de calculs nécessaires est alors
de l’ordre de grandeur de n!.

Or en s’appuyant sur le Pivot de Gauss, il est possible de construire un algorithme de

résolution dont le nombre d’opérations nécessaire est de l’ordre de grandeur de n3 .

En effet, les deux opérations élémentaires du Pivot de Gauss (la combinaison et la

permutation) appliquées à une matrice carrée ne modifient que très peu (voire pas du
tout) son déterminant. Précisément,
● Une combinaison Li ← Li + α.Lj ne modifie pas le déterminant,

● Une permutation Li ↔ Lj change le signe du déterminant.

Autrement dit, le déterminant d’une matrice A et de la matrice triangulaire issue du

Pivot de Gauss appliqué à A sont égaux au signe près.

Or le déterminant d’une matrice triangulaire étant égal au produit de ses termes dia-
gonaux, l’application du Pivot de Gauss puis le produit des termes diagonaux produit

27
un algorithme de calcul de déterminant dont le nombre d’opérations est de l’ordre de
grandeur de celui du Pivot.

Notons que pour connaître le signe du déterminant chercher, on doit stocker, au cours
du pivot le signe (−1)d , d donnant le nombre de permutations effectuées.

2.4.3 Inversion de matrices

En adaptant le Pivot de Gauss, on peut également produire un algorithme pour le
calcul de l’inverse d’une matrice A = (aij ) donnée.

En pratique, le processus consiste à appliquer à la matrice double

⎛ a11 a12 ⋯ a1n 1 0 ⋯ 0 ⎞

⎜ a21 a22 ⋯ a2n 0 ⋱ ⋮ ⎟ ⎛ ⎞
⎜ ⎟ = ⎜ A I ⎟
⎜ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ 0 ⎟ ⎝ ⎠
⎝ an1 an2 ⋯ ann 0 ⋯ 0 1 ⎠
un processus fortement inspiré du Pivot de Gauss dans le but de transformer la pre-
mière moitié (A) en la matrice identité.

À l’issue du processus, on peut en effet montrer que la seconde moitié (I) est alors
remplacée par la matrice A−1 :

⎛ ⎞ ⎛ ⎞
⎜ ⎟ ↝ ⎜ A−1 ⎟
PdG++
A I I
⎝ ⎠ ⎝ ⎠

En pratique, pour transformer la matrice A en la matrice identité,

1. On adapte l’opération de “vide-colonne” pour qu’elle place des zéros dans

l’ensemble d’une colonne (sauf le pivot), on transforme la matrice A en une
matrice diagonale.

2. On divise alors chaque ligne par le coefficient diagonal (non nul), pour transformer
la matrice A en la matrice identité.

Enfin, notons que, là encore, cette méthode d’inversion de matrice nécessite un nombre
d’opérations de l’ordre de grandeur de n3 .

3 Systèmes sur déterminés

Contrairement à la section précédente, consacrée à la résolution de systèmes inversibles
(i.e. admettant une unique solution), nous allons présenter ici des méthodes algébriques
permettant d’apporter une réponse à des problèmes dont la modélisation mène à un sys-
tème linéaire admettant strictement plus d’équations (ou de contraintes) que d’inconnues

29
(i.e. n > p).

De tels systèmes sont dits sur-déterminés. Formellement, ils n’admettent aucune solu-
tion. Cependant, on va voir comment, par une approche géométrique, on peut construire
dans ce cas une solution approchée.
Ainsi, soient
● A = (aij ) une matrice rectangulaire à n lignes et p colonnes, avec n > p,

⎛ b1 ⎞
● B = ⎜ ⋮ ⎟ ∈ Rn un vecteur constant,
⎝ bn ⎠

⎛ x1 ⎞
● X = ⎜ ⋮ ⎟ ∈ Rp un vecteur inconnu.
⎝ xp ⎠

Le système linéaire (S) ∶ AX = B n’admettant aucune solution exacte, on appellera

solution de (S) un vecteur X ∈ Rp tel que le vecteur AX ∈ Rn soit le plus proche possible
de B.

Autrement dit, on cherche un vecteur X qui minimise la norme euclidienne ∣∣AX − B∣∣.

⎛ x1 ⎞
Rappel : la norme euclidienne d’un vecteur X = ⎜ ⋮ ⎟ est
⎝ xn ⎠
¿
Án 2 √ 2
∣∣X∣∣ = Á
À ∑ x = x + . . . + x2
i 1 n
i=1

On va voir comment interpréter cette recherche d’un point de vue géométrique, et

on verra comment le calcul matriciel permet, là encore, de construire une méthode de
résolution algorithmique.

3.1 Un exemple
Considérons le système
⎧
⎪ 2x − y = 0
⎪
⎪
(S) ∶ ⎨ x + y = 2 ⇐⇒ AX = B
⎪
⎪
⎪
⎩ x − 2y = 0
avec

31
 ⎛ 2 −1 ⎞ x ⎛ 0 ⎞
A = ⎜ 1 1 ⎟, X = ( ), B = ⎜ 2 ⎟
⎝ 1 −2 ⎠ y ⎝ 0 ⎠

On peut rapidement montrer que ce système n’admet pas de solution (à faire).

x
On cherche donc le vecteur X = ( ) tel que le vecteur AX − B soit le plus petit
y
possible. On cherche donc un minimum à sa norme
√
∣∣AX − B∣∣ = (2x − y)2 + (x + y − 2)2 + (x − 2y)2

ou de manière équivalente le carré de cette norme :

ϕ(x, y) = ∣∣AX − B∣∣2 = (2x − y)2 + (x + y − 2)2 + (x − 2y)2

Or on note ici que la fonction ϕ est alors un polynôme de degré 2 dépendant des
variables (x, y). On sait déterminer, s’il existe les extrema de cette fonction de deux
variables. Cela passe en particulier par la détermination des points critiques de ϕ, i.e. les
couples (x, y) qui annulent les dérivées partielles de ϕ. Or

∂ϕ
(x, y) = 4(2x − y) + 2(x + y − 2) + 2(x − 2y)
∂x
= 12x − 6y − 4
∂ϕ
(x, y) = − 2(2x − y) + 2(x + y − 2) − 4(x − 2y)
∂y
= − 6x + 12y − 4

Les points critiques de ϕ sont donc les solutions du système

12x − 6y = 4
(S) ∶ {
−6x + 12y = 4

On constate ici que le système obtenu est un système de Cramer dont l’unique solution
est
2 2
(x, y) = ( , )
3 3

33
 Ainsi, le protocole ci-dessus produit un unique point critique. On peut alors montrer
que c’est bien un minimum de ϕ (en étudiant par exemple les dérivées seconde de ϕ en
ce point) et donc la meilleure solution possible au système (S).

Exercice : puisque l’exemple ci-dessus porte sur un système à deux inconnues, on

peut le représenter par une famille de trois droites du plan.
1. Tracer les trois droites associées au système (S) dans un repère orthonormé. Com-
ment interpréter géométriquement le fait que le système (S) est sur-déterminé ?
2. Placer également le couple (x, y) solution. Commenter.

3.2 La méthode des moindres carrés

De façon générale, la méthode de résolution approchée utilisée pour résoudre le système
sur-déterminé ci-dessus est appelée la méthode des moindres carrés car elle consiste à
minimiser la norme ∣∣AX − B∣∣ ou plus précisément le carré

ϕ(X) = ∣∣AX − B∣∣2

qui, par définition de la norme euclidienne, est une somme de carrés.

Le vecteur X cherché est alors l’unique point critique de ce polynôme de degré 2 en

les variables (x1 , . . . , xn ). Il correspond donc au système linéaire constitué des équations
linéaires suivante :
∂ϕ
∀i ∈ {1, . . . , n}, (x1 , . . . , xn ) = 0
∂xi

Or on peut montrer que ce système, appelé système des équations normales de (S) est
le système carré, défini par

t
AAX = t AB.

On peut alors utiliser les méthodes de résolution classiques pour résoudre ce système
normal. D’autre part, la matrice t AA de ce système étant particulière (elle est symétrique,
définie positive), on peut améliorer les méthodes de décomposition et donc la performance
des algorithmes de résolution.

Exercice : montrer que le système des équations normales est un système carré et
donner sa taille en fonction de la taille du système (S).

3.3 Mesure de l’erreur

Comme toute méthode d’approximation, la méthode des moindres carrés nécessite,
pour être exploitable en pratique, d’une mesure de l’erreur commise.

35
 Ici, en notant X0 la solution donnée par la méthode des moindres carrés, l’erreur
absolue commise est alors

ε = ∣∣AX0 − B∣∣

En comparant cette erreur absolue avec "la taille du problème", donnée par exemple
par le vecteur ∣∣B∣∣, on obtient l’erreur relative de la méthode :

∣∣AX0 − B∣∣
εr =
∣∣B∣∣

Note : pour des raisons pratiques, on préfère en général utiliser le carré de cette erreur
relative
∣∣AX0 − B∣∣2
ε2r =
∣∣B∣∣2

3.4 Application : la régression

Parmi les applications courantes de la méthodes de résolution exposée ci-dessus, on
trouve la régression, ou le "fit", consistant à construire une "courbe de tendence" à partir
d’un ensemble finie de données expérimentales ou statistiques.

3.4.1 Régression linéaire simple

Rappel : étant donné un ensemble N = {(x1 , y1 ), . . . , (xn , yn )} un ensemble de n
points du plan (muni d’un repère). On appelle droite de régression linéaire du nuage de
point N la droite du plan passant au plus près de chacun des points de N .

Or la mise en équation de ce problème conduit précisément à un système linéaire sur-

déterminé. En effet, construire la droite de régression revient à déterminer l’équation de
la droite du plan passant par tous les points de N . Autrement dit, il s’agit de déterminer
deux coefficients a et b tels que

∀i ∈ {1, . . . , n}, y i = a xi + b

On doit donc résoudre le système linéaire AX = B dont les matrices sont :

37
 a
X = ( ) ∈ R2
b

⎛ x1 1 ⎞
⎜ x2 1 ⎟
A = ⎜ ⎟ ∈ Mn,2 (R)
⎜ ⋮ ⋮ ⎟
⎝ xn 1 ⎠

⎛ y1 ⎞
⎜ y2 ⎟
B = ⎜ ⎟ ∈ Rn
⎜ ⋮ ⎟
⎝ yn ⎠

Il s’agit donc d’un système de n équations à deux inconnues, qui n’admet une solution
exacte que si l’ensemble des points de N sont parfaitement alignés. Sinon, il s’agit d’un
système sur-déterminé.

Sa résolution à l’aide des équations normales produit alors les coefficients (a, b) de la
droite "la plus proche" de l’ensemble des points de N .

Note : le système des équations normales est ici un système de deux équations à
deux inconnues, dont la résolution permet de retrouver les formules implémentées dans
l’ensemble des tableurs et autres logiciels de calcul statistique :

Cov(x, y)
a = , b = y − ax
V (x)
où
● x et y représentent respectivement les ensembles de données (x1 , . . . , xn ) et
(y1 , . . . , yn ),

● x et y représentent leurs moyennes respectives,

● Cov(x, y) représente la covariance des ensembles x et y,

● V (x) représente la variance de l’ensemble de données x.

Exercice : à faire.

Note : pour évaluer la qualité d’une régression linéaire simple, on s’appuie sur le
coefficient de corrélation linéaire des données x et y, défini par

39
 Cov(x, y)
r(x, y) = √ .
V (x)V (y)

Or avec nos notations, on peut montrer que

∣∣AX0 − B∣∣2 = V (y)(1 − r2 (x, y))

Par ailleurs,
n
∣∣B∣∣2 = ∑ yi2 = V (y)
i=1

Autrement dit, l’erreur relative définie plus haut vérifie

ε2r = 1 − r2 (x, y)

En pratique, plus le coefficient r est proche de ±1, plus l’erreur εr est proche de 0 et
meilleure est la régression.

3.4.2 Régression linéaire multiple

La notion de régression linéaire se généralise aux dimensions supérieures.

Ainsi, étant donné un nuage N = {P1 , . . . , Pn } de n points de l’espace muni d’un

repère, il est possible de déterminer l’équation du plan de l’espace passant au plus près
de chacun des points de N .

En effet, en notent Pi = (xi , yi , zi ) les coordonnées des points de N , il s’agit de déter-

miner un plan d’équation

z = ax + by + c

passant par l’ensemble des points de N . On doit donc résoudre le système linéaire
constitué des équations

∀i ∈ {1, . . . , n}, zi = a xi + b yi + c

i.e. le système linéaire AX = B où

41
 ⎛ a ⎞
X = ⎜ b ⎟ ∈ R3
⎝ c ⎠

⎛ x1 y1 1 ⎞
⎜ x2 y2 1 ⎟
A = ⎜ ⎟ ∈ Mn,3 (R)
⎜ ⋮ ⋮ ⎟
⎝ xn yn 1 ⎠

⎛ z1 ⎞
⎜ z2 ⎟
B = ⎜ ⎟ ∈ Rn
⎜ ⋮ ⎟
⎝ zn ⎠

On obtient alors le plan cherché en résolvant le système des équations normales associé
à ces matrices.

Note : formellement, il est bien entendu possible de généraliser ce processus aux

dimensions supérieures, en augmentant le nombre de coordonnées des points du nuage.

3.4.3 Régression quadratique

Il est également possible de généraliser le processus évoqué ci-dessus aux polynômes
de degré 2 (voire plus).

Ainsi, en dimension 2, il est possible de déterminer la parabole passant au plus près des
points d’un ensemble de points du plan. En effet, en notant N = {(x1 , y1 ), . . . , (xn , yn )},
il s’agit de trouver les coefficients a, b, c de l’équation d’une parabole

y = a x2 + b x + c

passant par l’ensemble des points de N .

La mise en équation de ce problème conduit au système linéaire

∀i ∈ {1, . . . , n}, yi = a x2i + b xi + c

soit le système AX = B où

43
 ⎛ a ⎞
X = ⎜ b ⎟ ∈ R3
⎝ c ⎠

⎛ x21 x1 1 ⎞
⎜ x22 x2 1 ⎟
A = ⎜ ⎟ ∈ Mn,3 (R)
⎜ ⋮ ⋮ ⎟
⎝ xn xn 1 ⎠
2

⎛ y1 ⎞
⎜ y2 ⎟
B = ⎜ ⎟ ∈ Rn
⎜ ⋮ ⎟
⎝ yn ⎠

On obtient alors la parabole cherchée en résolvant le système des équations normales

associé à ces matrices.

Par ailleurs, il est là encore possible de généraliser aux polynômes de tous degrés. On
verra en outre qu’il est également possible de généraliser à d’autres types de fonctions
(exponentielle, fonction inverse, etc).

4 Systèmes sous-déterminés et optimisation

4.1 Programme linéaire
On appelle système linéaire sous-déterminé tout système d’équations linéaire conte-
nant plus d’inconnues que de contraintes. Ce sont en particulier des systèmes admettant
une infinité de solutions (on laisse de côté les systèmes incompatibles, qui n’admettent
aucune solution quelque soit le nombre d’inconnues).

Dans ce cadre, l’existence de plusieurs solutions permet en particulier d’ajouter des

contraintes. C’est en particulier un cadre idéal pour de l’optimisation.

Ainsi, si l’on ajoute au problème une fonction (linéaire) dépendant des variables de
départ, il est possible de déterminer, parmi les solutions du système sous-déterminé étu-
dié, laquelle (ou lesquelles) correspondent à une valeur optimale (maximale ou minimale)
de la fonction supplémentaire.

45
Définition (Programme linéaire)

On appelle programme linéaire portant sur les variables (x1 , . . . , xp ) ∈ Rp la donnée de

● un système linéaire (S) d’inconnues (xp , . . . , xp ) admettant une infinité de solu-

tions,
● une fonction p
P ∶ (x1 , . . . , xp ) z→ ∑ αk xk
k=1

Résoudre un tel programme linéaire consiste alors à trouver, parmi l’ensemble

des solutions de (S), celle qui optimise (i.e. maximise ou minimise) la quantité
P (x1 , . . . , xp ).

Notes :
● En général, les contraintes d’un programme linéaire (i.e. les équations du système
différentiel) sont complétées de contraintes de positivité sur les inconnues :

∀i ∈ {1, . . . , p}, xi ⩾ 0

Ces contraintes supplémentaires sont en général issue de la modélisation du pro-

blème de départ sous la forme d’un programme linéaire.

● Dans de nombreuses applications de la notion de programme linéaire, les contraintes

sont, dans un premier temps, données sous la forme d’inégalité linéaires :

a1 x1 + . . . + ap xp ⩽ b ou a1 x 1 + . . . + ap x p ⩾ b

Cependant, quitte à introduire d’une inconnue supplémentaire e dite variable d’écart

(et supposée là encore positive), on peut transformer toute inéquation en une équa-
tion :

a1 x 1 + . . . + ap x p ⩽ b ⇒ a1 x 1 + . . . + ap x p + e = b

a1 x 1 + . . . + ap x p ⩾ b ⇒ a1 x 1 + . . . + ap x p − e = b

4.2 Exemples
Exemple 1 : on considère un chantier que l’on doit terrasser. Pour cela, on a

deux zones à déblayer (les déblais) deux zones à remblayer (les remblais)
un talus D1 de 5000 m3 , un trou R1 de 3000 m3 ,
un talus D2 de 4000 m3 , un trou R2 de 6000 m3 .

47
 D’autre part, on dispose pour le travail d’engins de chantier dont le coût par centaine
de m3 déplacé est présenté dans le tableau ci-dessous (dans lequel apparaissent également
les quantités de matériaux à déplacer) :

R1 R2 Déblais
D1 168 euro/u. 148 euro/u. 50
D2 158 euro/u. 140 euro/u. 40
Remblais 30 60 90

L’objectif est d’organiser le terrassement à moindre coût de façon à avoir à la fin, un

terrain plat.

Pour mettre le problème en équation, on pose

● x11 = la quantité de terre déplacée du talus D1 au trou R1 ,

● x12 = la quantité de terre déplacée du talus D1 au trou R2 ,

● x21 = la quantité de terre déplacée du talus D2 au trou R1 ,

● x22 = la quantité de terre déplacée du talus D2 au trou R2 .

Le coût de cette organisation est alors

C = 168x11 + 148x12 + 158x21 + 140x22

Par ailleurs, pour rendre le terrain complètement plat, les quatre inconnues ci-dessus
doivent vérifier les équations ci-dessous :
● Le talus D1 est vidé ⇒ x11 + x12 = 50

● Le talus D2 est vidé ⇒ x21 + x22 = 40

● Le trou R1 est comblé ⇒ x11 + x12 = 30

● Le trou R2 est comblé ⇒ x12 + x22 = 60

On obtient un système linéaire, dont la matrice étendue est

⎛ 1 1 0 0 50 ⎞
⎜ 0 0 1 1 40 ⎟
à = ⎜ ⎟
⎜ 1 0 1 0 30 ⎟
⎝ 0 1 0 1 60 ⎠

49
 En appliquant le pivot de Gauss à cette matrice étendue, on montre que le système a
quatre inconnues et trois contraintes :

⎛ 1 1 0 0 50 ⎞
⎜ 0 −1 1 0 −20 ⎟ ⎛ 1 1 0 0 50 ⎞
à ←→ ⎜ ⎟ ⇐⇒ ⎜ 0 −1 1 0 −20 ⎟
PDG ⎜ 0 0 1 1 40 ⎟ ⎝ 0 0 1 1 40 ⎠
⎝ 0 0 0 0 0 ⎠
Il est donc possible d’exprimer l’ensemble des solutions de ce système ainsi que la
fonction coût à l’aide d’un des quatre paramètres, n’importe lequel.

Par ailleurs, on peut également montrer que la solution optimale (i.e. celle qui mini-
mise le coût de l’opération) est atteinte lorsque l’un de ces quatre paramètres est nul.

À l’aide des opérations du Pivot de Gauss étendu, il est alors possible de parcourir
l’ensemble de ces représentation et de déterminer quelle variable doit être nulle pour ob-
tenir la solution optimale.

Ainsi, on ajoute dans un premier temps une ligne à la matrice Ã, correspondant à la
fonction coût :

⎛ 1 1 0 0 50 ⎞
⎜ 0 −1 1 0 −20 ⎟
à ↝ ⎜ ⎟
⎜ 0 0 1 1 40 ⎟
⎝ 168 148 158 140 C ⎠

Ainsi, en "vidant" les colonnes associées à toutes les variables sauf x12 , on peut en
particulier exprimer l’ensemble des données du problème à l’aide de la variable x12 :

● On vide C1 à l’aide du pivot 1 :

⎛ 1 1 0 0 50 ⎞
⎜ 0 −1 1 0 −20 ⎟
à ←→ ⎜ ⎟
L4 ← L4 − 168L1 ⎜ 0 0 1 1 40 ⎟
⎝ 0 −20 158 140 C − 8400 ⎠

● On vide de même la colonne C3 :

⎛ 1 1 0 0 50 ⎞
⎜ 0 −1 1 0 −20 ⎟
à ←→ ⎜ ⎟
L3 ← L3 − L2 ⎜ 0 1 0 1 60 ⎟
L4 ← L4 − 158L2
⎝ 0 138 0 140 C − 5240 ⎠

● puis C4 :
⎛ 1 1 0 0 50 ⎞
⎜ 0 −1 1 0 −20 ⎟
à ←→ ⎜ ⎟
L4 ← L4 − 140L3 ⎜ 0 1 0 1 60 ⎟
⎝ 0 −2 0 0 C − 13640 ⎠

51
 On a alors

L1 ⇒ x11 = 50 − x12

L2 ⇒ x21 = x12 − 20

L3 ⇒ x22 = 60 − x12

L4 ⇒ C = 13640 − 2x12

On voit en particulier ici que ça n’est pas la variable x12 qu’il faut annuler pour obtenir
le coût minimal. Au contraire, pour faire diminuer le coût au maximum, il faut prendre
la valeur la plus grande possible de x12 .

Or le seul frein à l’augmentation de la quantité x12 est donné par l’exigence de positivité
de toutes les variables :

L1 ⇒ x12 ⩽ 50

L2 ⇒ x12 ⩾ 20

L3 ⇒ x12 ⩽ 60

La plus grosse contrainte à l’augmentation de x12 est donc la première, associée à la

variable x11 . On cherche donc à exprimer maintenant l’ensemble des données du problème
à l’aide de la variable x11 .

Pour cela, on applique les opérations du pivot à la dernière matrice obtenue, afin de
vider toutes les colonnes sauf celle de x11 , soit, ici, la colonne C2 avec pour pivot le premier
coefficient de la colonne :

⎛ 1 1 0 0 50 ⎞
⎜ 1 0 1 0 30 ⎟
à ←→ ⎜ ⎟
L2 ← L2 + L1 ⎜ −1 0 0 1 10 ⎟
L3 ← L3 − L1
L4 ← L4 + 2L1 ⎝ 2 0 0 0 C − 13540 ⎠

La dernière ligne de cette matrice nous donne en particulier

C = 13540 + 2x11

On note alors que le coût minimal est

Cmin = 13540

53
 atteint pour x11 = 0.

Par ailleurs, la matrice ci-dessus nous donne également les valeurs des différentes
variables associées à cette solution optimale :

x11 = 0

x12 = 50 − x11 = 50

x21 = 30 − x11 = 30

x22 = 10 − x11 = 10

Exemple 2 : une entreprise fabrique deux types de produits : P1 et P2 . La fabrication

de ces produits se fait en trois étapes. Le tableau suivant donne le temps nécessaire à la
fabrication d’une unité de chacun de ces produits à chaque étape ainsi que les temps de
disponibilités de chacun des ateliers :

Étape 1 Étape 2 Étape 3

Produit P1 1h/u. 2h/u. 1h/u. x
Produit P2 2h/u. 1h/u. 1h/u. y
Ressources 20h 22h 12h

Les profits que l’entreprise peut réaliser pour chaque type de produit sont de
● 400=Cpour chaque unité de produit P1 ,
● 600=Cpour chaque unité de produit P2 .

Le directeur de l’usine désire savoir comment il doit organiser sa production pour

maximiser son profit.

Pour mettre le problème en équation, on pose

● x = nombre d’unités de produit P1 produites,

● y = nombre d’unités de produit P2 produites.

Les contraintes imposées par le temps disponible dans chaque atelier se traduisent
alors par :
● Atelier 1 : x + 2y ⩽ 20

● Atelier 2 : 2x + y ⩽ 22

● Atelier 3 : x + y ⩽ 12

55
 Par ailleurs, le profit réalisé par l’entreprise pour une production de x unités de P1
et y unités de P2 est

P = 400x + 600y

On peut alors poser le problème sous la forme d’un programme linéaire :

Maximiser
P = 400x + 600y
sous les contraintes
⎧
⎪ x + 2y ⩽ 20
⎪
⎪
⎪
⎪ 2x + y ⩽ 22
(S) ∶ ⎨
⎪
⎪ x + y ⩽ 12
⎪
⎪
⎪
⎩ x, y ⩾ 0

Le système de contraintes (S) peut alors être remplacé par un système d’équations en
introduisant trois variables d’écarts e1 , e2 et e3 positives :

x + 2y ⩽ 20 ⇒ x + 2y + e1 = 20

2x + y ⩽ 22 ⇒ 2x + y + e2 = 22

x + y ⩽ 12 ⇒ x + y + e3 = 12

Il s’agit donc d’un système linéaire de 3 équations à 5 inconnues que l’on peut repré-
senter par la matrice ci-dessous (dans laquelle on ajoute également une ligne représentant
la fonction P à maximiser) :

⎛ 1 2 1 0 0 20 ⎞
⎜ 2 1 0 1 0 22 ⎟
à = ⎜ ⎟
⎜ 1 1 0 0 1 12 ⎟
⎝ 400 600 0 0 0 P ⎠

Par ailleurs, l’ensemble des solutions du système (S) (et donc l’ensemble des données
du problème) peut être représenté à l’aide de

d = 5−3 = 2

variables choisies parmi les 5 variables x, y, e1 , e2 , e3 et l’on peut montrer que, là

57
encore, la solution optimale est atteinte lorsque 2 de ces 5 variables sont nulles.

La version actuelle du tableau permet ainsi de représenter l’ensemble des solutions et

la fonction P à l’aide des variables x et y :

L1 ⇒ e1 = 20 − x − 2y

L2 ⇒ e2 = 22 − 2x − y

L3 ⇒ e3 = 12 − x − y

et
P = 400x + 600y
L’organisation de production associée à cette matrice est celle consistant alors à pro-
duire 0 unités de P1 et 0 unités de P2 pour un profit de 0=C.

Cela n’est évidement pas la solution optimale, mais c’est une solution possible, qui
permet d’amorcer le processus de recherche.

Ainsi, au vue des coefficients de la fonction P à optimiser, pour augmenter au maxi-

mum le profit P à partir de la solution (0, 0), il faut augmenter la quantité y.

Les équations du cadre ci-dessus limitent cette augmentation si l’on veut respecter les
contraintes de positivité des variables e1 , e2 et e3 :

L1 ⇒ y ⩽ 10

L2 ⇒ y ⩽ 22

L3 ⇒ y ⩽ 12

La contrainte la plus forte est alors donnée par la ligne L1 portant sur la variable e1 .

On applique donc le Pivot de Gauss à la matrice à afin de vider la colonne C2 ,

correspondant à la variable y en s’appuyant sur la ligne L1 :

⎛ 0.5 1 0.5 0 0 10 ⎞
⎜ 1.5 0 −0.5 1 0 12 ⎟
à ↔ ⎜ ⎟
⎜ 0.5 0 −0.5 0 1 2 ⎟
⎝ 100 0 −300 0 0 P − 6000 ⎠

Ce tableau permet en particulier d’exprimer l’ensemble des données du problème et

en particulier la fonction P à l’aide des variables x et e1 :

P = 6000 + 100x − 300e1

59
 Par ailleurs, il correspond à la solution de (S) obtenue en posant

x = 0 et e1 = 0

pour un profit de

P = 6000=C

Le coefficient de x dans P étant ici positif, il ne s’agit pas du profit maximum. On

peut en effet augmenter le profit en augmentant la variable x. Comme précédemment,
l’augmentation de x est contrainte par la contrainte de positivité :

L1 ⇒ y = 10 − 0.5x − 0.5e1 ⇒ x ⩽ 20

L2 ⇒ e2 = 12 − 1.5x + 0.5e1 ⇒ x ⩽ 8

L3 ⇒ e3 = 2 − 0.5x − 0.5e1 ⇒ x⩽4

La contrainte la plus forte étant donnée par la ligne L3 , correspondant à la variable e3 ,

on applique alors le pivot de Gauss à la dernière matrice obtenue afin de vider la colonne C1
correspondant à la variable x en s’appuyant sur la ligne L3 :

⎛ 0 1 1 0 −1 8 ⎞
⎜ 0 0 1 1 −3 6 ⎟
⎜ ⎟
⎜ 1 0 −1 0 2 4 ⎟
⎝ 0 0 −200 0 −200 P − 6400 ⎠

Ce tableau permet en particulier d’exprimer l’ensemble des données du problème et

en particulier la fonction P à l’aide des variables e1 et e3 :

P = 6400 − 200e1 − 200e3

Par ailleurs, il correspond à la solution de (S) obtenue en posant

e1 = 0 et e3 = 0

pour un profit de

P = 6400=C

On constate ici que l’on a augmenté le profit par rapport à la solution précédente.

61
 D’autre part, les coefficients de e1 et e3 dans P étant tous les deux négatifs, on a
atteint la solution optimale : le profit maximal est

Pmax = 6400

obtenu en posant

e1 = 0 et e3 = 0

Les premières lignes de la dernière matrice donnent alors les valeurs des autres va-
riables :

L1 ⇒ y = 8 − e1 + e3 = 8

L2 ⇒ e2 = 6 − e1 + 3e3 = 6

L1 ⇒ x = 4 + e1 − 2e3 = 4

Autrement dit, le profit maximal est atteint en produisant 4 unités de produit P1 et 8

unités de produit P2 .

Par ailleurs, l’égalité e2 = 6 signifie qu’au cours de cette production optimale, 6 des 22
heures disponibles sur l’atelier 2 ne seront pas utilisées.

4.3 Simplexe et compléments

À partir des exemples ci-dessus, on peut développer un algorithme permettant de trai-
ter n’importe quel programme linéaire : l’algorithme du simplexe.

Par ailleurs, une étude théorique de la notion de programme linéaire basée sur les
outils de l’algèbre linéaire permet de tirer de nombreuses informations supplémentaires
des résultats obtenus à partir de l’application du simplexe, notamment en cas de variation
des contraintes de production (temps disponible et/ou prix de vente) mais également en
cas de revente de l’entreprise.

Il est laissé à la lectrice ou au lecteur intéressé.e le soin de consulter la littérature (très

fournie et disponible en ligne) sur ces derniers points.

63