[Link]-gestion.

com

Mathématiques appliquées
à la gestion

Giovanni Lazzarini

[Link]
 [Link]

ii

[Link]
 [Link]

Informations générales sur l’UE

Nom de l’UE MATH 306 Mathématiques appliquées à la gestion.

Responsable du cours Giovanni Lazzarini. [site et adresse mél]

Année, semestre Troisième année, premier semestre (S5)

Public concerné
• Licence Droit, Economie, Gestion – Mention Gestion
• Licence Droit, Economie, Gestion – Mention Gestion – Parcours Pas-
serelle DUT GEA
• Licence Droit, Economie, Gestion – Mention Gestion – Parcours Pas-
serelle DUT TC

Crédits 4

Coefficient 4

Heures totales 30h cours magistral, 16h30 TD.

Heures hebdomadaires
• 2h30 cours magistral en amphi, sur 12 semaines ;
• 1h30 TD en groupes, sur 11 semaines.

Syllabus
I. préparation mathématique au test "Score IAE Message" [2 semaines]
II. Éléments d’algèbre linéaire : matrices, systèmes, pivot de Gauss, déter-
minants, rang, applications économiques. [4 ou 5 semaines]

iii

[Link]
 [Link]

iv

III. Recherche opérationnelle : programmation linéaire (résolution graphique,

méthode du simplexe, dualité, analyse marginale), problème d’affecta-
tion, problème de transport, problème du voyageur de commerce. [5 ou
6 semaines]

Modalité de contrôle

Organisation du contrôle continu 2 tests.

Calcul de la note finale

• Session 1 : max(CT ; 0,5CC + 0,5CT)
• Session 2 : CT

[Link]
 [Link]

Table des matières

I Préparation au test "Score IAE message" 1

1 Mathématiques générales 3
1.1 Calcul différentiel et intégral . . . . . . . . . . . . . . . . . . . 3
1.1.1 Dérivation des fonctions polynomiales . . . . . . . . . . 3
1.1.2 Intégration des fonction polynomiales . . . . . . . . . . 3
1.2 Arithmétique et manipulation des nombres . . . . . . . . . . . 4
1.2.1 Identités remarquables (encore une fois !) . . . . . . . . 4
1.2.2 Décomposition en facteurs premiers, critères de divisi-
bilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Pourcentages . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Les trois définitions de pourcentage . . . . . . . . . . . 6
[Link] Un pourcentage est une fraction . . . . . . . . 6
[Link] Un pourcentage est une part . . . . . . . . . . 6
[Link] Un pourcentage est un nombre décimal . . . . 6
1.3.2 Pourcentage d’une évolution . . . . . . . . . . . . . . . 6
[Link] Coefficient multiplicateur . . . . . . . . . . . 6
[Link] Coefficient multiplicateur et évolution . . . . 7
[Link] évolutions successives . . . . . . . . . . . . . 7
[Link] Évolution réciproque . . . . . . . . . . . . . . 8

2 Probabilités et statistiques 9
2.1 Combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Cardinal d’un ensemble . . . . . . . . . . . . . . . . . . 9
2.1.2 k-listes, permutations, arrangements, combinaisons . . 9
2.1.3 Modèles de tirages . . . . . . . . . . . . . . . . . . . . 10
2.2 Calcul des probabilités . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Généralités. Équiprobabilité . . . . . . . . . . . . . . . 10
2.2.2 Probabilité conditionnelle . . . . . . . . . . . . . . . . 11
2.3 Variables aléatoires . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.1 v.a. discrètes finies : généralités . . . . . . . . . . . . . 12

[Link]
 [Link]

vi TABLE DES MATIÈRES

2.3.2 Lois discrètes usuelles . . . . . . . . . . . . . . . . . . . 13

[Link] Loi uniforme . . . . . . . . . . . . . . . . . . 13
[Link] Loi de Bernoulli . . . . . . . . . . . . . . . . 14
[Link] Loi binomiale . . . . . . . . . . . . . . . . . . 14
[Link] Loi de Poisson . . . . . . . . . . . . . . . . . 15
[Link] Loi exponentielle . . . . . . . . . . . . . . . . 15
2.3.3 Indépendance et covariance . . . . . . . . . . . . . . . 15

II Algèbre linéaire 17
3 Systèmes linéaires 19
3.1 Introduction aux systèmes d’équations linéaires . . . . . . . . 19
3.1.1 Exemple : deux droites dans le plan . . . . . . . . . . . 19
3.1.2 Résolution par substitution . . . . . . . . . . . . . . . 20
3.1.3 Exemple : deux plans dans l’espace . . . . . . . . . . . 21
3.1.4 Résolution par la méthode de Cramer . . . . . . . . . . 23
3.1.5 Résolution par inversion de matrice . . . . . . . . . . . 23
3.1.6 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Théorie des systèmes linéaires . . . . . . . . . . . . . . . . . . 25
3.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.2 Différents types de systèmes . . . . . . . . . . . . . . . 27
3.2.3 Systèmes homogènes . . . . . . . . . . . . . . . . . . . 27
3.2.4 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Résolution par la méthode du pivot de Gauss . . . . . . . . . 27
3.3.1 Systèmes échelonnés . . . . . . . . . . . . . . . . . . . 27
3.3.2 Opérations sur les équations d’un système . . . . . . . 28
3.3.3 Méthode du pivot de Gauss . . . . . . . . . . . . . . . 30
3.3.4 Systèmes homogènes . . . . . . . . . . . . . . . . . . . 32
3.3.5 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . 33

4 Introduction aux matrices 35

4.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.2 Matrices particulières . . . . . . . . . . . . . . . . . . . 36
4.1.3 Addition de matrices . . . . . . . . . . . . . . . . . . . 37
4.1.4 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 Multiplication de matrices . . . . . . . . . . . . . . . . . . . . 39
4.2.1 Définition du produit . . . . . . . . . . . . . . . . . . . 40
4.2.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2.3 Pièges à éviter . . . . . . . . . . . . . . . . . . . . . . . 41

[Link]
 [Link]

TABLE DES MATIÈRES vii

4.2.4 Propriétés du produit de matrices . . . . . . . . . . . . 42

4.2.5 La matrice identité . . . . . . . . . . . . . . . . . . . . 42
4.2.6 Puissance d’une matrice . . . . . . . . . . . . . . . . . 43
4.2.7 Formule du binôme . . . . . . . . . . . . . . . . . . . . 43
4.2.8 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . 44
4.3 Matrices triangulaires, transposition, trace, matrices symétriques 45
4.3.1 Matrices triangulaires, matrices diagonales . . . . . . . 45
4.3.2 La transposition . . . . . . . . . . . . . . . . . . . . . . 46
4.3.3 La trace . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3.4 Matrices symétriques . . . . . . . . . . . . . . . . . . . 47
4.3.5 Matrices antisymétriques . . . . . . . . . . . . . . . . . 48
4.3.6 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . 48

5 Inversion des matrices 51

5.1 Définitions et premières propriétés . . . . . . . . . . . . . . . . 51
5.1.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.1.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.1.3 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . 52
[Link] Unicité . . . . . . . . . . . . . . . . . . . . . 52
[Link] Inverse de l’inverse . . . . . . . . . . . . . . . 52
[Link] Inverse d’un produit . . . . . . . . . . . . . . 52
[Link] Simplification par une matrice inversible . . . 53
5.1.4 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . 53
5.2 Méthodes de calcul . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2.1 Matrices 2 × 2 . . . . . . . . . . . . . . . . . . . . . . . 54
5.2.2 Méthode de Gauss pour inverser les matrices . . . . . . 54
5.2.3 Un exemple . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2.4 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . 56
5.3 Systèmes linéaires et matrices élémentaires . . . . . . . . . . . 56
5.3.1 Matrices et systèmes linéaires . . . . . . . . . . . . . . 56
[Link] Matrice augmentée . . . . . . . . . . . . . . . 57
5.3.2 Matrices inversibles et systèmes linéaires . . . . . . . . 57
5.3.3 Les matrices élémentaires . . . . . . . . . . . . . . . . 58
5.3.4 Équivalence à une matrice échelonnée . . . . . . . . . . 60
5.3.5 Matrices élémentaires et inverse d’une matrice . . . . . 62
5.3.6 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . 62
5.4 Application : Modèle input-output de Leontieff . . . . . . . . . 63
5.4.1 Données . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.4.2 La modélisation . . . . . . . . . . . . . . . . . . . . . . 64
5.4.3 Problème de planification . . . . . . . . . . . . . . . . 65
[Link] Remarques . . . . . . . . . . . . . . . . . . . 66

[Link]
 [Link]

viii TABLE DES MATIÈRES

III Programmation linéaire et applications 69

6 Programmation linéaire : approche graphique 71
6.1 Rappels sur les équations de droites . . . . . . . . . . . . . . . 71
6.2 Régionnement du plan . . . . . . . . . . . . . . . . . . . . . . 74
6.3 Un premier exemple : maximisation . . . . . . . . . . . . . . . 77
6.3.1 Un autre exemple de maximisation . . . . . . . . . . . 80
6.4 Un exemple de minimisation . . . . . . . . . . . . . . . . . . . 82
6.5 sensibilité à la variation des données, desserrement des contraintes 84

7 Programmation linéaire : la méthode du simplexe 89

7.1 Définitions et notations . . . . . . . . . . . . . . . . . . . . . . 90
7.1.1 Forme générale, standard, canonique . . . . . . . . . . 91
[Link] Forme générale . . . . . . . . . . . . . . . . . 91
[Link] Forme standard . . . . . . . . . . . . . . . . . 92
[Link] Forme canonique . . . . . . . . . . . . . . . . 94
7.2 Théorème fondamental de la programmation linéaire . . . . . 95
7.3 Méthode du simplexe : un exemple en détail . . . . . . . . . . 98
7.4 Les tableaux du simplexe . . . . . . . . . . . . . . . . . . . . . 101
7.5 Un autre exemple . . . . . . . . . . . . . . . . . . . . . . . . . 104

8 Programmation linéaire : le dual 107

8.1 Un exemple de PL résolu par la méthode du simplexe : pour
réviser ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
8.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.2.1 Cas où le primal est écrit sous forme canonique . . . . 109
8.2.2 Cas où le primal n’est pas écrit sous forme canonique . 111
8.3 Théorème fondamental de la dualité . . . . . . . . . . . . . . . 112
8.4 Résolution du primal par l’intermédiaire du dual . . . . . . . . 113
8.5 Desserrement des contraintes et Valeurs marginales . . . . . . 118
8.5.1 Contraintes saturées . . . . . . . . . . . . . . . . . . . 118
8.5.2 Valeurs marginales . . . . . . . . . . . . . . . . . . . . 118
8.6 Interprétation de la dualité . . . . . . . . . . . . . . . . . . . . 119
8.6.1 Production utilisant des ressources données et maximi-
sant le bénéfice . . . . . . . . . . . . . . . . . . . . . . 119
8.6.2 Régime alimentaire du moindre coût . . . . . . . . . . 120
8.6.3 Lien entre valeurs marginales et problème dual . . . . . 121
8.6.4 Production utilisant des ressources données et maximi-
sant le bénéfice : un autre exemple . . . . . . . . . . . 122
8.6.5 Outils informatiques . . . . . . . . . . . . . . . . . . . 122
[Link] Site n. 1 . . . . . . . . . . . . . . . . . . . . . 122

[Link]
 [Link]

TABLE DES MATIÈRES ix

[Link] Site n. 2 . . . . . . . . . . . . . . . . . . . . . 122

[Link] Wolfram Alpha . . . . . . . . . . . . . . . . . 122
[Link] Excel . . . . . . . . . . . . . . . . . . . . . . 122
8.6.6 Autres problèmes modélisables par la PL . . . . . . . . 123
[Link] Une histoire de fromage . . . . . . . . . . . . 123
[Link] Un problème d’électricité . . . . . . . . . . . 123

[Link]
 [Link]

x TABLE DES MATIÈRES

[Link]
 [Link]

Première partie

Préparation au test "Score IAE

message"

[Link]
[Link]

[Link]
 [Link]

Leçon 1

Mathématiques générales

1.1 Calcul différentiel et intégral

1.1.1 Dérivation des fonctions polynomiales
Rappelons que si f (x) = xn est un monôme, avec n = 1,2 . . . , alors sa
dérivée est f 0 (x) = nxn−1 . En d’autres termes, a.
Exemple 1. Si f (x) = x4 + x7 , alors f 0 (x) = 4x3 + 7x6 .

1.1.2 Intégration des fonction polynomiales

• Soit f (x) = xn une fonction polynomiale, n ∈ N. Alors toutes les
primitives de f sont données par
Z
xn+1
f (x)dx = + const. (1.1)
n+1
En d’autres termes, on augmente de un l’exposant de la variable et on
divise par ce nouvel exposant.
R2
Exemple 2. Soit f (x) = 4 − 3x. Combien vaut −1 f (x)dx ?
2
Solution. 4 a pour primitive 4x et −3x a pour primitive −3 x2 . Donc
" #2
Z 2
x2
f (x)dx = 4x − 3
−1 2 −1
4 1 3 11 15
= (8 − 3 × ) − (4(−1) − 3 × ) = 8 − 6 − (−4 − ) = 2 + = = 7,5.
2 2 2 2 2
(1.2)

[Link]
 [Link]

4 LEÇON 1. MATHÉMATIQUES GÉNÉRALES

1.2 Arithmétique et manipulation des nombres

1.2.1 Identités remarquables (encore une fois !)
Proposition 3. somme fois différence (a + b)(a − b) = a2 − b2
carré du binôme (a + b)2 = a2 + 2ab + b2

Il faut apprendre à s’en servir pour développer des expression, simplifier

des calculs, etc, et pour être plus efficaces en calcul mental :
Exemple 4. Calculer 98 × 99 × 100 × 101 × 102 (sans calculatrice)

solution. on écrit (98 × 102) × (99 × 101) × 100 sous forme d’identité remar-
quable (100−2)×(100+2)×(100−1)×(100+1)×100 et on applique l’identité
remarquable somme × différence. À la fin, on obtient 9 995 000 400.

1.2.2 Décomposition en facteurs premiers, critères de

divisibilité
Définition 5 (Nombre premier). Un nombre naturel premier est un nombre
naturel, différent de 1, qui n’est divisible que par lui-même et par 1. Atten-
tion : 1 n’est pas un nombre premier, le plus petit nombre premier est 2, qui
est aussi l’unique nombre premier pair.

Liste des premiers nombres premiers : 2,3,5,7,11,13,17, 19,23, 29,31,37,

41,47, 53,59,61, 67,71, 73,79, 83,89, 97,101. Les nombres premiers sont im-
portants parce que tout nombre entier est un produit de nombres premiers :

Théorème 6 (théorème fondamental de l’arithmétique). Tout nombre entier

peut se décomposer de façon unique comme un produit de facteurs premiers.

Par exemple, 30 = 2×3×5, et aucun autre nombre ne peut se décomposer

de la même façon.

Théorème 7 (critères de divisibilité). On a les critères suivants :

div. par 2 : un nombre n est divisible par 2 ⇔ il se termines par les chiffres 0,2,4,6,8,
c-a-d s’il est pair.
div. par 3 : un nombre n est divisible par 3 ⇔ la somme de ses chiffres est divisible
par 3.
div. par 4 : un nombre n est divisible par 4 ⇔ ses deux derniers chiffres forment
un nombre divisible par 4.
div. par 5 : un nombre n est divisible par 5 ⇔ il se termine par 0 ou 5.

[Link]
 [Link]

1.2. ARITHMÉTIQUE ET MANIPULATION DES NOMBRES 5

div. par 6 : un nombre n est divisible par 6 ⇔ il est divisible par 2 et par 3.

div. par 9 : un nombre n est divisible par 9 ⇔ la somme de ses chiffres est divisible
par 9.

div. par 10 : un nombre n est divisible par 10 ⇔ il finit par 0.

div. par 11 : un nombre n est divisible par 11 ⇔ la somme de ses chiffres de rang
impair, moins la somme de ses chiffres de rang pair, est un nombre
divisible par 11, c-a-d 0,11,22,33 etc.

1.2.3 Algorithmes
Voici un schéma de rappel sur les fondamentaux de l’algorithmique vus
au lycée.

Conseil Pour lire correctement un algorithme, et suivre pas à pas l’évolu-

tion des quantités en jeu, il est conseillé de construire un tableau de fonction-
nement de l’algorithme.

[Link]
 [Link]

6 LEÇON 1. MATHÉMATIQUES GÉNÉRALES

1.3 Pourcentages
1.3.1 Les trois définitions de pourcentage
[Link] Un pourcentage est une fraction
Un pourcentage permet d’exprimer un nombre comme une fraction de
cent, en utilisant le symbole %. Ainsi, % signifie simplement « divisé par
100 »
t
t% = (1.3)
100
N’oubliez donc jamais qu’un pourcentage est avant tout une fraction, qu’on
peut simplifier comme les autres.
Exercice 8. Transformez 80%, 72%, 36%, 44% en fractions irréductibles.

[Link] Un pourcentage est une part

Le pourcentage représente une proportion, une part d’un ensemble. Le
total est en fait ramené à 100 et le pourcentage représente donc le rapport
d’un sous-ensemble à son ensemble : formule fondamentale
!
Part
Pourcentage = × 100 % (1.4)
Total

Exercice 9. Une galette des rois est coupée en 16 parts. Achille prends 2 parts
de galette. Quel pourcentage de galette Achille a-t-il mangé ?

[Link] Un pourcentage est un nombre décimal

Le pourcentage est aussi un nombre décimal compris entre 0 et 1 lorsque
le pourcentage est inférieur à 100%, et au-dessus de 1 lorsque le pourcentage
est supérieur à 100%.
Exemple 10. Ainsi, 25% = 1/4 = 0,25. Il est impératif de savoir passer
aisément de l’une à l’autre de ces écritures équivalentes.

1.3.2 Pourcentage d’une évolution

[Link] Coefficient multiplicateur
Lorsqu’un quantité passe d’une valeur V1 à une valeur V2 , le coefficient
multiplicateur associé est :
V2
CM = . (1.5)
V1

[Link]
 [Link]

1.3. POURCENTAGES 7

Le pourcentage d’évolution t% entre V1 et V2 est défini par

t V2 − V1 t
= ( variation relative), soit = CM − 1. (1.6)
100 V1 100
• Si t > 0, l’évolution est une hausse ;
• Si t < 0, l’évolution est une baisse.

[Link] Coefficient multiplicateur et évolution

t
• Augmenter une quantité de t% signifie la multiplier par CM = 1+ 100 .
t
• Diminuer une quantité de t% signifie la multiplier par CM = 1 − 100 .

[Link] évolutions successives

Lors de deux évolution successives, les coefficients multiplicateurs se mul-
tiplient :
Si V1 CM CM2
−→ V2 −→ V3 alors CMglobal = CM1 × CM2
1 (1.7)

Attention Erreur capitale à éviter : lors d’évolutions successives, les pour-

centages ne s’additionnent ni se soustraient pas ! Ce sont les coefficients mul-
tiplicateurs qui se multiplient entre eux.
Exemple 11. Un prix subit d’abord une hausse de 10% puis une hausse de
30%. Quel est le pourcentage de la hausse globale ?
Solution. Ce n’est pas 10% + 30% = 40% ! Il faut d’abord calculer les deux
10
coefficients multiplicateurs, qui sont CM1 = 1 + 100 = 1,1 et CM2 = 1,3.
Puis on les multiplie, et on trouve CMglobal = 1,1 × 1,3 = 1,43. Alors le
t
pourcentage de l’évolution globale est 100 = CM − 1 = 0,43 = 43% : c’est
une hausse de 43%.
En revanche, lors de deux (ou plus) évolutions successives, l’ordre des
variations n’importe pas : cela revient ainsi au même d’appliquer une varia-
tion (hausse pu baisse) de a% suivie d’une variation de b%, que d’appliquer
d’abord une variation de b% suivie d’une variation de a%. Cela est dû au fait
que dans le calcul du pourcentage de l’évolution globale, ce sont les coeffi-
cients multiplicateurs qui se multiplient, donc l’ordre des facteurs ne compte
pas.
Exemple 12. Un prix augmente de 10%, puis diminue de 20% : dans ce cas,
le coefficient multiplicateur global est
10 20
CM = (1 + )(1 − ) = 1,1 × 0,8 = 0,88 = 1 − 0,12
100 100

[Link]
 [Link]

8 LEÇON 1. MATHÉMATIQUES GÉNÉRALES

donc globalement il s’agit d’une baisse de 12%.

Si ce même prix diminue d’abord de 20%, puis il augmente de 10%, le
résultat est le même : on a en effet
20 10
CM = (1 − )(1 + ) = 0,88 = 1 − 0,12 (1.8)
100 100
qui correspond encore à une baisse de 12%.

[Link] Évolution réciproque

Le taux de pourcentage t0 % compensant une évolution (hausse ou baisse)
de t% est appelé taux d’évolution réciproque. Pour le déterminer, le produit
des deux coefficients multiplicateurs doit être 1 :

t t0
(1 + )(1 + ) = 1. (1.9)
100 100
Les coefficients multiplicateurs de deux évolutions réciproques sont donc in-
verses l’un de l’autre : CM 0 = CM1

Attention Autre erreur capitale à éviter : si un prix augmente de 60%,

pour revenir à la valeur initiale, il ne doit pas baisser de 60% ! Avec ce qu’on
vient de dire, si ce prix augmente de 60%, le coefficient multiplicateur de cette
hausse est CM = 1 + 60/100 = 1,6. Le coefficient de l’évolution réciproque
est CM 0 = 1,6 1
= 0,625 = 1 − 0,375 = 1 − 37,5 100
. Ce prix pour revenir à sa
valeur initiale doit effectuer une baisse de 37,5%.

[Link]
 [Link]

Leçon 2

Probabilités et statistiques

2.1 Combinatoire
Pour calculer des probabilités, en particulier quand l’univers des issues
possibles est un ensemble fini, il faut souvent savoir compter les éléments
d’un ensemble. La branche des mathématiques qui étudie les configurations
de collections finies d’objets (permutations, combinaisons etc.) s’appelle com-
binatoire, et la partie de la combinatoire qui consiste à compter le nombre
de telles configurations s’appelle dénombrement.

2.1.1 Cardinal d’un ensemble

Définition 13. Soit A un ensemble fini de n éléments. Le nombre n s’appelle
cardinal de A, noté Card(A) (ou |A| ou #A). Pour un ensemble fini, le
cardinal est simplement le nombre d’éléments.

Proposition 14 (Formule d’inclusion-exclusion, version ensembliste). Si A

et B sont deux ensembles finis, alors

Card(A ∪ B) = Card(A) + Card(B) − Card(A ∩ B) (2.1)

Si A et B sont disjoints, c-a-d A ∩ B = ∅, et seulement dans ce cas, alors

Card(A ∪ B) = Card(A) + Card(B).

2.1.2 k-listes, permutations, arrangements, combinai-

sons
Soit A un ensemble de n éléments. Voici un schéma pour se rappeler les
principales formules de dénombrement :

[Link]
 [Link]

10 LEÇON 2. PROBABILITÉS ET STATISTIQUES

Nom Répétitions l’ordre compte formule

k-listes oui oui nk
permutations non oui n!
n!
k-arrangements non oui (n−k)!
= n × (n − 1) × · · · × (n − k + 1)
 
n n!
k-combinaisons non non k
= (n−k)!k!
= Cnk

Un exemple pour rappeler les différentes formules :

2.1.3 Modèles de tirages

Soit U une urne contenant n boules numérotées de 1 à n, et supposons
que nous tirions k boules de cette urne. Voici les trois modèles de tirage les
plus classiques :

Tirages Interprétation combinatoire Formule

Successifs avec remise k-liste nk
n!
Successifs sans remise k-arrangement (n−k)!
 
n
Simultanés k-combinaisons k

2.2 Calcul des probabilités

2.2.1 Généralités. Équiprobabilité
Définition 15. Soit (Ω,A) un espace probabilisable, où Ω est l’ensemble
univers de toutes les issues possibles, et A ⊆ P(Ω) la σ-algèbre (ou tribu)
des événements de Ω. Une probabilité sur Ω est une application P : A → [0,1]
qui vérifie :
(i) P (Ω) = 1 ;
(ii) toute famille dénombrable d’événements deux à deux disjoints (ou in-
compatibles) A1 ,A2 , . . . satisfait :

∞
X
P (A1 ∪ A2 ∪ · · · ) = P (Ai ). (2.2)
i+1

(additivité dénombrable.) En particulier, si A et B sont deux événe-

ments incompatibles, alors P (A ∪ B) = P (A) + P (B).

[Link]
 [Link]

2.2. CALCUL DES PROBABILITÉS 11

Premières propriétés Des propriétés qui définissent la probabilité P , on

déduit les autres qui suivent :
(i) P (∅) = 0
(ii) Pour tout A, on note A le complémentaire de A (événement contraire),
et l’on a P (A = 1 − P (A)).
(iii) Si A ⊆ B, alors P (A) ≤ P (B).
(iv) (Formule d’inclusion-exclusion, version probabiliste) si A et B sont deux
événements, alors P (A ∪ B) = P (A) + P (B) − P (A ∩ B).
Définition 16 (Équiprobabilité). Soit Ω = {a1 ,a2 , . . . ,an } un univers fini.
On dit qu’on est en situation d’équiprobabilité si toute issue a la même
probabilité de se réaliser, et donc P ({a1 }) = · · · = P ({an }) = n1 .
Dans ce cas, la probabilité d’un événements quelconque A est donnée par la
notoire formule
Card(A) nombre des cas favorables nombre d’issues de A
P (A) = = =
Card(Ω) nombre des cas possibles nombre d’issues total
(2.3)

2.2.2 Probabilité conditionnelle

Définition 17. Soient A et B deux événements, avec P (B) 6= 0. La proba-
bilité conditionnelle de A sachant B est
P (A ∩ B)
P (A|B) = PB (A) = . (2.4)
P (B)
Proposition 18 (Formule des probabilités composées).
P (A ∩ B) = P (A|B)P (B) = P (B|A)P (A) (2.5)
Proposition 19 (Formule de la probabilité totale). Soit A1 ,A2 , . . . ,Ap un
système complet d’événements (c-a-d une famille d’événements A1 ,A2 , . . . ,Ap
deux à deux disjoints et telle que A1 ∪ · · · ∪ Ap = Ω). Alors, pour tout événe-
ment B,
p
X
P (B) = P (B|Ai )P (Ai ) = P (B|A1 )P (A1 )+P (B|A2 )P (A2 )+· · ·+P (B|Ap )P (Ap )
i=1
(2.6)
Proposition 20 (Formule de Bayes). Avec la même notation ci-dessus,
P (B|Aj )P (Aj ) P (B|Aj )P (Aj )
P (Aj |B) = = Pp (2.7)
P (B) i=1 P (B|Ai )P (Ai )

pour tout événement B et pour tout j ∈ {1, . . . ,p}.

[Link]
 [Link]

12 LEÇON 2. PROBABILITÉS ET STATISTIQUES

2.3 Variables aléatoires

Définition 21. Une variable aléatoire est une application X définie sur l’uni-
vers Ω et à valeurs dans R.
• Si l’ensemble X(Ω) des valeurs prises par X est discret (c-a-d que
c’est un ensemble fini ou au plus qu’il est infini dénombrable comme
l’ensemble N des naturels), alors X est une v.a. discrète.
• Si X prend valeurs dans un intervalle, ou dans une réunion d’inter-
valles de R, on parle de v.a. continue.
Définition 22 (Fonction de répartition). Soit X une v.a. La fonction de
répartition de X est la fonction
FX : R → [0, + ∞[
x 7→ P (X ≤ x)

Propriétés de FX :
• Pour tout x ∈ R, 0 ≤ FX (x) ≤ 1.
• FX est une fonction croissante.
• limx→−∞ FX (x) = 0 et limx→+∞ FX (x) = 1
• Pour tous réels a < b, on a P (X ∈]a,b]) = P (a < X ≤ b) = FX (b) −
FX (a).

2.3.1 v.a. discrètes finies : généralités

Soit X une v.a. discrète. Pour simplifier la notation, dans la suite, on
supposera qu’elle soit finie, mais les résultats s’étendent aux v.a. infinies
dénombrables.
• L’ensemble des valeurs que peut prendre X est de la forme X(Ω) =
{x1 ,x2 , . . . ,xn }.
• La loi de probabilité de X est le tableau
xi x1 x · · · xn
pi = P (X = xi ) p1 p2 · · · pn
• On a toujours p1 + · · · + pn = 1, car les événements X = xi forment
un système complet d’événements.

Fonction de répartition d’une v.a. finie Si les xi sont rangés dans

l’ordre croissant, x1 < · · · < xn , alors
• La fonction FX est constante par morceaux, et elle vaut FX (xi ) sur
tout l’intervalle [xi ,xi+1 [
• P (X = xi ) = FX (xi ) − FX (xi−1 ).

[Link]
 [Link]

2.3. VARIABLES ALÉATOIRES 13

Espérance mathématique
Définition 23. L’espérance de X, ou valeur moyenne, ou valeur attendue,
est le réel : n X
E(X) = xi p i = x1 p 1 + x2 p 2 + · · · + xn p n (2.8)
i=1
C’est la moyenne des valeurs prises par X, pondérée par les probabilités pi .
Remarque 24. Chaque fois qu’on lit la question « Combien vaut en moyenne
telle quantité X ? » il s’agit de l’espérance de X.
Proposition 25 (Propriétés de l’espérance). • L’espérance est linéaire :
E(aX + bY + c) = aE(X) + bE(Y ) + c.
• Pour toute fonction g : R → R, E[g(X)] = ni=1 g(xi )pi . En d’autre
P

termes : pour calculer l’espérance de la variable g(X), on applique g

aux valeurs xi , et on ne touche pas les probabilités pi .

Variance et écart-type
Définition 26. 1. La variance de X est le réel
n
Var(X) = E[(X − E(X))2 ] = (xi − E(X))2 pi
X
(2.9)
i=1

2. L’écart-type (standard deviation) est la racine carrée de la variance :

q
σ(X) = Var(X). (2.10)

Propriétés de variance et écart-type

• Var(X) ≥ 0
• formule alternative pour la variance : Var(X) = E(X 2 ) − (E(X))2 :
pour s’en souvenir,
Variance = espérance du carré moins carré de l’espérance (2.11)
• En général, Var(X + Y ) 6= Var(X) + Var(Y ) (la variance n’est pas
linéaire), et pour tous a,b ∈ R, Var(aX + b) = a2 Var(X).
• σ(aX) = |a|σ(X).

2.3.2 Lois discrètes usuelles

[Link] Loi uniforme
Définition 27. On dit que X suit une loi uniforme sur l’ensemble X(Ω) =
{1, . . . ,n}, noté X ∼ U(n) si pour tout i = 1, . . . ,n, P (X = i) = n1 .
xi 1 2 ··· n
pi 1/n 1/n · · · 1/n

[Link]
 [Link]

14 LEÇON 2. PROBABILITÉS ET STATISTIQUES

Formules
Espérance E(X) = n+1
2
2
Variance Var(X) = n 12−1

Modèle une urne contient n boules égales numérotées de 1 à n. On tire au

hasard une boule de l’urne et on note sa valeur X. Alors X ∼ U(n).

[Link] Loi de Bernoulli

Définition 28. Soit p ∈]0,1[ un réel. La v.a. X suit une loi de Bernoulli de
paramètre p si elle vaut 1 avec probabilité p et 0 avec probabilité 1 − p :

xi 0 1
pi 1−p p

Formules
Espérance E(X) = p
Variance Var(X) = p(1 − p)

Modèle On lance une pièce truquée, telle qu’on obtient FACE avec pro-
babilité p, et PILE avec probabilité 1 − p. On note Face par 1 et Pile par 0.
Soit X la v.a. qui donne le résultat du lancer. Alors X ∼ B(p).

[Link] Loi binomiale

Définition 29. Soient n ≥ 1 un naturel et  p ∈]0,1[ un réel. La v.a. X suit
X(Ω) = {0,1, . . . ,n}
une loi binomiale de paramètres n et p si  
P (X = k) = n pk (1 − p)n−k
k

xi  
0  
1 ···  
n
n n n
pi 0
p0 (1 − p)n = (1 − p)n 1
p1 (1 − p)n−1 = np(1 − p)n−1 ··· n
pn (1 − p)0 = pn

Formules
Espérance E(X) = np
Variance Var(X) = np(1 − p)

Modèle On lance n fois une pièce truquée, telle qu’on obtient FACE avec
probabilité p, et PILE avec probabilité 1 − p. Les lancers sont identiques et
indépendants. Soit X la v.a. qui donne le nombre de résultats FACE obtenus.
Alors X ∼ B(n,p).

[Link]
 [Link]

2.3. VARIABLES ALÉATOIRES 15

[Link] Loi de Poisson

[Link] Loi exponentielle

2.3.3 Indépendance et covariance

Définition 30. Deux v.a. discrètes X et Y sont indépendantes si pour tout
couple (xi ,yj ) on a la relation

P ((X = xi ) ∩ (Y = yj )) = P (X = xi ) × P (Y = yj ) (2.12)

c-a-d si tous les couples d’événements (X = xi ) et (Y = yj ) sont indépen-

dants.

Propriétés
• E(XY ) = E(X)E(Y ), ce qui n’est pas vrai dans le cas général
• Var(X + Y ) = Var(X) + Var(Y ).

Définition 31 (covariance). Si E(X), E(Y ), E(XY ) existent, on définit la

covariance de X et Y comme

Cov(X,Y ) = E(XY ) − E(X)E(Y ). (2.13)

Propriétés de la covariance
• Cov(X,Y ) = Cov(Y,X)
• Si X et Y sont indépendantes, alors Cov(X,Y ) = 0
• Var(X + Y ) = Var(X) + 2 Cov(X,Y ) + Var(Y )

[Link]
 [Link]

16 LEÇON 2. PROBABILITÉS ET STATISTIQUES

[Link]
 [Link]

Deuxième partie

Algèbre linéaire

17

[Link]
[Link]

[Link]
 [Link]

Leçon 3

Systèmes linéaires

3.1 Introduction aux systèmes d’équations li-

néaires
L’algèbre linéaire est un outil essentiel pour toutes les branches des ma-
thématiques, en particulier lorsqu’il s’agit de modéliser puis résoudre numé-
riquement des problèmes issus de divers domaines : des sciences physiques ou
mécaniques, des sciences du vivant, de la chimie, de l’économie, de la gestion,
des sciences de l’ingénieur . . .
Les systèmes linéaires interviennent à travers leurs applications dans de
nombreux contextes, car ils forment la base calculatoire de l’algèbre linéaire.
Ils permettent également de traiter une bonne partie de la théorie de l’algèbre
linéaire en dimension finie. C’est pourquoi ce cours commence avec une étude
des équations linéaires et de leur résolution.
Le but de ce chapitre est essentiellement pratique : il s’agit de résoudre des
systèmes linéaires. La partie théorique sera revue et prouvée dans le chapitre
« Matrices ».

3.1.1 Exemple : deux droites dans le plan

L’équation d’une droite dans le plan (Oxy) s’écrit

ax + by = e

où a,b et e sont des paramètres réels, a et b n’étant pas simultanément nuls.

Cette équation s’appelle équation linéaire dans les inconnues x et y.

19

[Link]
 [Link]

20 LEÇON 3. SYSTÈMES LINÉAIRES

Par exemple, 2x+3y = 6 est une équation linéaire, alors que les équations
suivantes ne sont pas des équations linéaires :
√
2x + y 2 = 1 ou y = sin(x) ou x = y.

Considérons maintenant deux droites D1 et D2 et cherchons les points qui

sont simultanément sur ces deux droites. Un point (x,y) est dans l’intersection
D1 ∩ D2 s’il est solution du système :
(
ax + by = e
(S)
cx + dy = f

Trois cas se présentent alors :

1. Les droites D1 et D2 se coupent en un seul point. Dans ce cas, illustré
par la figure de gauche, le système (S) a une seule solution.
2. Les droites D1 et D2 sont parallèles. Alors le système (S) n’a pas de
solution. La figure du centre illustre cette situation.
3. Les droites D1 et D2 sont confondues et, dans ce cas, le système (S) a
une infinité de solutions.

Nous verrons plus loin que ces trois cas de figure (une seule solution, aucune
solution, une infinité de solutions) sont les seuls cas qui peuvent se présenter
pour n’importe quel système d’équations linéaires.

3.1.2 Résolution par substitution

Pour savoir s’il existe une ou plusieurs solutions à un système linéaire, et
les calculer, une première méthode est la substitution. Par exemple pour le
système : (
3x + 2y = 1
(S)
2x − 7y = −2

[Link]
 [Link]

3.1. INTRODUCTION AUX SYSTÈMES D’ÉQUATIONS LINÉAIRES 21

Nous réécrivons la première ligne 3x+2y = 1 sous la forme y = 12 − 32 x. Et nous

remplaçons (nous substituons) le y de la seconde équation, par l’expression
1
2
− 32 x. Nous obtenons un système équivalent :
(
y = 12 − 32 x
2x − 7( 12 − 3
2
x)= −2

La seconde équation est maintenant une expression qui ne contient que des
x, et on peut la résoudre :
( (
y = 12 − 32 x y = 1
− 32 x
⇐⇒ 2
(2 + 7 × 32 )x = −2 + 72 x = 3
25

Il ne reste plus qu’à remplacer dans la première ligne la valeur de x obtenue :

(
8
y = 25
3
x = 25

3 8
Le système (S) admet donc une solution unique ( 25 , 25 ). L’ensemble des so-
lutions est donc
3 8
 
S= , .
25 25

3.1.3 Exemple : deux plans dans l’espace

Dans l’espace (Oxyz), une équation linéaire est l’équation d’un plan :

ax + by + cz = d

(on suppose ici que a, b et c ne sont pas simultanément nuls).

L’intersection de deux plans dans l’espace correspond au système suivant
à 2 équations et à 3 inconnues :
(
ax + by + cz = d
a0 x + b0 y + c0 z = d0

Trois cas se présentent alors :

• les plans sont parallèles (et distincts) et il n’y a alors aucune solution
au système,
• les plans sont confondus et il y a une infinité de solutions au système,
• les plans se coupent en une droite et il y a une infinité de solutions.

[Link]
 [Link]

22 LEÇON 3. SYSTÈMES LINÉAIRES

(
2x + 3y − 4z = 7
Exemple 32. 1. Le système n’a pas de solution.
4x + 6y − 8z = −1
En effet, en (
divisant par 2 la seconde équation, on obtient le système
2x + 3y − 4z = 7
équivalent : . Les deux lignes sont clairement
2x + 3y − 4z = − 12
incompatibles : aucun (x,y,z) ne peut vérifier à la fois 2x + 3y − 4z = 7
et 2x + 3y − 4z = − 12 . L’ensemble des solutions est donc S = ∅.
(
2x + 3y − 4z = 7
2. Pour le système , les deux équations définissent
4x + 6y − 8z = 14
le même plan ! Le système est donc équivalent à une seule équation :
2x + 3y − 4z = 7. Si on réécrit cette équation sous la forme z =
1
2
x + 34 y − 74n, alors on peut décrire l’ensemble
o
des solutions sous la
1 3 7
forme : S = (x,y, 2 x + 4 y − 4 ) | x,y ∈ R .
(
7x + 2y − 2z = 1
3. Soit le système . Par substitution :
2x + 3y + 2z = 1

z = 72 x + y − 1
( (
7x + 2y − 2z = 1  2
⇐⇒ 
2x + 3y + 2z = 1 2x + 3y + 2 72 x + y − 12 = 1

( ( (
z = 72 x + y − 1
z = 72 x + y − 1
z = 17 1
x − 10
⇐⇒ 2 ⇐⇒ 2 ⇐⇒ 10
9x + 5y = 2 y = − 95 x + 25 y = − 5 x + 25
9

Pour décrire l’ensemble des solutions, on peut choisir x comme para-

mètre :
9 2 17 1
  
S= x, − x + , x − |x∈R .
5 5 10 10

Géométriquement : nous avons trouvé une équation paramétrique de la

droite définie par l’intersection de deux plans.

Du point de vue du nombre de solutions, nous constatons qu’il n’y a que

deux possibilités, à savoir aucune solution ou une infinité de solutions. Mais
les deux derniers cas ci-dessus sont néanmoins très différents géométrique-
ment et il semblerait que dans le second cas (plans confondus), l’infinité de
solutions soit plus grande que dans le troisième cas. Les chapitres suivants
nous permettront de rendre rigoureuse cette impression.
Si on considère trois plans dans l’espace, une autre possibilité apparaît :
il se peut que les trois plans s’intersectent en un seul point.

[Link]
 [Link]

3.1. INTRODUCTION AUX SYSTÈMES D’ÉQUATIONS LINÉAIRES 23

3.1.4 Résolution par la méthode de Cramer

On note | ac db | = ad − bc le déterminant. On considère le cas d’un système
de 2 équations à 2 inconnues :
(
ax + by = e
cx + dy = f

Si ad − bc 6= 0, on trouve une unique solution dont les coordonnées (x,y)

sont :    
 e b a e 
   
f d  c f 
   
x =   y =  
a b  a b 
 
 c d  c d
   

Notez que le dénominateur égale le déterminant pour les deux coordon-

nées et est donc non nul. Pour le numérateur de la première coordonnée
x, on remplace la première colonne par le second membre ; pour la seconde
coordonnée y, on remplace la seconde colonne par le second membre.
(
tx − 2y = 1
Exemple 33. Résolvons le système suivant la valeur du
3x + ty = 1
paramètre t ∈ R.
Le déterminant associé au système est | 3t −2 2
t | = t + 6 et ne s’annule
jamais. Il existe donc une unique solution (x,y) et elle vérifie :
   
−2
1 t
 1
1t  31 t−3
   
t+2
x= 2 = 2 , y= 2 = 2 .
t +6 t +6 t +6 t +6
n o
t+2 t−3
Pour chaque t, l’ensemble des solutions est S = ,
t2 +6 t2 +6
.

3.1.5 Résolution par inversion de matrice

En termes matriciels, le système linéaire
(
ax + by = e
cx + dy = f

est équivalent à
! ! !
a b x e
AX = Y où A= , X= , Y = .
c d y f

[Link]
 [Link]

24 LEÇON 3. SYSTÈMES LINÉAIRES

Si le déterminant de la matrice A est non nul, c’est-à-dire si ad − bc 6= 0,

alors la matrice A est inversible et
!
−1 1 d −b
A =
ad − bc −c a
et l’unique solution X = ( xy ) du système est donnée par
X = A−1 Y.
(
x+y = 1
Exemple 34. Résolvons le système suivant la valeur du
x + t2 y = t
paramètre t ∈ R.  
Le déterminant du système est  11 t12  = t2 − 1.
 
 
1 1
Premier cas. t 6= +1 et t 6= −1. Alors t2 − 1 6= 0. La matrice A = 1 t2
 
est inversible d’inverse A−1 = 1
t2 −1
t2 −1
−1 1 . Et la solution X = ( xy ) est
t
! ! ! !
−11 t2 −1 1 1 t2 − t t+1
X=A Y = 2 = 2 = 1 .
t − 1 −1 1 t t −1 t−1 t+1
n o
t
Pour chaque t 6= ±1, l’ensemble des solutions est S = . , 1
t+1 t+1
(
x+y = 1
Deuxième cas. t = +1. Le système s’écrit alors : et
x+y = 1
n deux équationso sont identiques. Il y a une infinité de solutions : S =
les
(x,1 − x) | x ∈ R .
(
x+y = 1
Troisième cas. t = −1. Le système s’écrit alors : , les
x + y = −1
deux équations sont clairement incompatibles et donc S = ∅.

3.1.6 Mini-exercices
(
x − 2y = −1
1. Tracer les droites d’équations et résoudre le sys-
−x + 3y = 3
tème linéaire de trois façons différentes (
: substitution, méthode de Cra-
2x − y = 4
mer, inverse d’une matrice. Idem avec .
3x + 3y = −5
(
4x − 3y = t
2. Résoudre suivant la valeur du paramètre t ∈ R : .
2x − y = t2
(
tx − y = 1
3. Discuter et résoudre suivant la valeur du paramètre t ∈ R : .
x + (t − 2)y = −1
(
(t − 1)x + y = 1
Idem avec .
2x + ty = −1

[Link]
 [Link]

3.2. THÉORIE DES SYSTÈMES LINÉAIRES 25

3.2 Théorie des systèmes linéaires

3.2.1 Définitions
Définition 35. On appelle équation linéaire dans les inconnues x1 , . . . ,xp
toute relation de la forme
a1 x1 + · · · + ap xp = b, (3.1)
où a1 , . . . ,ap et b sont des nombres réels donnés.
Remarque 36. • Il importe d’insister ici sur le fait que ces équations
linéaires sont implicites, c’est-à-dire qu’elles décrivent des relations
entre les inconnues, mais ne donnent pas directement les valeurs que
peuvent prendre les inconnues.
• Résoudre une équation signifie donc la rendre explicite, c’est-à-dire
rendre plus apparentes les valeurs que les inconnues peuvent prendre.
• On peut aussi considérer des équations linéaires de nombres rationnels
ou de nombres complexes.
Soit n ≥ 1 un entier.
Définition 37. Un système de n équations linéaires à p inconnues est une
liste de n équations linéaires.
On écrit usuellement de tels systèmes en n lignes placées les unes sous les
autres.
Exemple 38. Le système suivant a 2 équations et 3 inconnues :
(
x1 − 3x2 + x3 = 1
−2x1 + 4x2 − 3x3 = 9
La forme générale d’un système linéaire de n équations à p inconnues est
la suivante :




a11 x1 +a12 x2 +a13 x3 + ··· +a1p xp = b1 (← équation 1)
a21 x1 +a22 x2 +a23 x3 + ··· +a2p xp = b2 (← équation 2)





.. .. .. .. .
= ..

. . . .



 ai1 x1 +ai2 x2 +ai3 x3 + ··· +aip xp = bi (← équation i)
.. .. .. .. .

= ..





 . . . .
+ ···


an1 x1 +an2 x2 +an3 x3 +anp xp = bn (← équation n)
Les nombres aij , i = 1, . . . ,n, j = 1, . . . ,p, sont les coefficients du système.
Ce sont des données. Les nombres bi , i = 1, . . . ,n, constituent le second
membre du système et sont également des données.

[Link]
 [Link]

26 LEÇON 3. SYSTÈMES LINÉAIRES

Il convient de bien observer comment on a rangé le système en lignes (une

ligne par équation) numérotées de 1 à n par l’indice i, et en colonnes : les
termes correspondant à une même inconnue xj sont alignés verticalement les
uns sous les autres. L’indice j varie de 1 à p. Il y a donc p colonnes à gauche
des signes d’égalité, plus une colonne supplémentaire à droite pour le second
membre. La notation avec double indice aij correspond à ce rangement : le
premier indice (ici i) est le numéro de ligne et le second indice (ici j) est le
numéro de colonne. Il est extrêmement important de toujours respecter cette
convention.
Dans l’exemple 38, on a n = 2 (nombre d’équations = nombre de lignes),
p = 3 (nombre d’inconnues = nombre de colonnes à gauche du signe =) et
a11 = 1, a12 = −3, a13 = 1, a21 = −2, a22 = 4, a23 = −3, b1 = 1 et b2 = 9.

Définition 39. Une solution du système linéaire est une liste de p nombres
réels (s1 ,s2 , . . . ,sp ) (un p-uplet) tels que si l’on substitue s1 pour x1 , s2 pour
x2 , etc., dans le système linéaire, on obtient une égalité. L’ ensemble des
solutions du système est l’ensemble de tous ces p-uplets.

Exemple 40. Le système

(
x1 − 3x2 + x3 = 1
−2x1 + 4x2 − 3x3 = 9

admet comme solution (−18, − 6,1), c’est-à-dire

x1 = −18 , x2 = −6 , x3 = 1 .

Par contre, (7,2,0) ne satisfait que la première équation. Ce n’est donc

pas une solution du système.
En règle générale, on s’attache à déterminer l’ensemble des solutions d’un
système linéaire. C’est ce que l’on appelle résoudre le système linéaire. Ceci
amène à poser la définition suivante.

Définition 41. On dit que deux systèmes linéaires sont équivalents s’ils ont
le même ensemble de solutions.

À partir de là, le jeu pour résoudre un système linéaire donné consistera

à le transformer en un système équivalent dont la résolution sera plus simple
que celle du système de départ. Nous verrons plus loin comment procéder de
façon systématique pour arriver à ce but.

[Link]
 [Link]

3.3. RÉSOLUTION PAR LA MÉTHODE DU PIVOT DE GAUSS 27

3.2.2 Différents types de systèmes

Voici un résultat théorique important pour les systèmes linéaires.

Théorème 42. Un système d’équations linéaires n’a soit aucune solution,

soit une seule solution, soit une infinité de solutions.

En particulier, si vous trouvez 2 solutions différentes à un système linéaire,

alors c’est que vous pouvez en trouver une infinité ! Un système linéaire qui
n’a aucune solution est dit incompatible. La démonstration de ce théorème
sera vue dans un chapitre ultérieur (« Matrices »).

3.2.3 Systèmes homogènes

Un cas particulier important est celui des systèmes homogènes, pour les-
quels b1 = b2 = · · · = bn = 0, c’est-à-dire dont le second membre est nul.
De tels systèmes sont toujours compatibles car ils admettent toujours la so-
lution s1 = s2 = · · · = sp = 0. Cette solution est appelée solution triviale.
Géométriquement, dans le cas 2×2, un système homogène correspond à deux
droites qui passent par l’origine, (0,0) étant donc toujours solution.

3.2.4 Mini-exercices
1. Écrire un système linéaire de 4 équations et 3 inconnues qui n’a aucune
solution. Idem avec une infinité de solution. Idem avec une solution
unique.
2. Résoudre le système à n équations et n inconnues dont les équations
sont (Li ) : xi − xi+1 = 1 pour i = 1, . . . ,n − 1 et (Ln ) : xn = 1.
3. Résoudre les systèmes suivants : 
  x1 +x2 = 1
x1 +2x2 +3x3 +4x4 = 0 x1 +2x2 +3x3 = 1


x2 +x3 = 2

 
 

x2 +2x3 +3x4 = 9 x1 +x2 +x3 = 2
x3 +x4 = 3
x1 −x2 +x3 = 3 
  

x3 +2x4 = 0  
x1 +2x2 +2x3 +x4 = 0


3.3 Résolution par la méthode du pivot de

Gauss
3.3.1 Systèmes échelonnés
Définition 43. Un système est échelonné si :

[Link]
 [Link]

28 LEÇON 3. SYSTÈMES LINÉAIRES

• le nombre de coefficients nuls commençant une ligne croît strictement

ligne après ligne.
Il est échelonné réduit si en plus :
• le premier coefficient non nul d’une ligne vaut 1 ;
• et c’est le seul élément non nul de sa colonne.

2x1 +3x2 +2x3 −x4 = 5


Exemple 44. • −x2 −2x3 = 4 est échelonné (mais


3x4 = 1
pas
 réduit).
 2x1 +3x2 +2x3 −x4 = 5

• −2x3 = 4 n’est pas échelonné (la dernière ligne


x3 +x4 = 1
commence avec la même variable que la ligne au-dessus).
Il se trouve que les systèmes linéaires sous une forme échelonnée réduite
sont particulièrement simples à résoudre.
Exemple 45. Le système linéaire suivant à 3 équations et 4 inconnues est
échelonné et réduit.


 x1 +2x3 = 25
x2 −2x3 = 16


x4 = 1

Ce système se résout trivialement en



 x1 = 25 − 2x3
x = 16 + 2x3
 2

x4 = 1.

En d’autres termes, pour toute valeur de x3 réelle, les valeurs de x1 , x2 et

x4 calculées ci-dessus fournissent une solution du système, et on les a ainsi
toutes obtenues. On peut donc décrire entièrement l’ensemble des solutions :
n o
S = (25 − 2x3 ,16 + 2x3 ,x3 ,1) | x3 ∈ R .

3.3.2 Opérations sur les équations d’un système

Nous allons utiliser trois opérations élémentaires sur les équations (c’est-
à-dire sur les lignes) qui sont :
1. Li ← λLi avec λ 6= 0 : on peut multiplier une équation par un réel non
nul.

[Link]
 [Link]

3.3. RÉSOLUTION PAR LA MÉTHODE DU PIVOT DE GAUSS 29

2. Li ← Li + λLj avec λ ∈ R (et j 6= i) : on peut ajouter à l’équation Li

un multiple d’une autre équation Lj .
3. Li ↔ Lj : on peut échanger deux équations.
Ces trois opérations élémentaires ne changent pas les solutions d’un sys-
tème linéaire ; autrement dit ces opérations transforment un système linéaire
en un système linéaire équivalent.
Exemple 46. Utilisons ces opérations élémentaires pour résoudre le système
suivant. 
 x
 +y +7z = −1 (L1 )
2x −y +5z = −5 (L2 )
−x −3y −9z = −5


(L3 )

Commençons par l’opération L2 ← L2 − 2L1 : on soustrait à la deuxième

équation deux fois la première équation. On obtient un système équivalent
avec une nouvelle deuxième ligne (plus simple) :


 +y +7z = −1
x
−3y −9z = −3 L2 ←L2 −2L1
−x −3y −9z = −5



Puis L3 ← L3 + L1 :


 x +y +7z = −1
−3y −9z = −3
−2y −2z = −6

L3 ←L3 +L1


On continue pour faire apparaître un coefficient 1 en tête de la deuxième

ligne ; pour cela on divise la ligne L2 par −3 :


 x +y +7z = −1
y +3z = 1 L2 ← − 13 L2
−2y −2z = −6



On continue ainsi
 

 x +y +7z = −1 
 x +y +7z = −1
y +3z = 1 y +3z = 1
4z = −4 = −1
 

L3 ←L3 +2L2

z L3 ← 41 L3

 

 x +y +7z = −1 
 x +y = 6 L1 ←L1 −7L3
y = 4 L2 ←L2 −3L3 y = 4
= −1 z = −1
 

z 

[Link]
 [Link]

30 LEÇON 3. SYSTÈMES LINÉAIRES

On aboutit à un système réduit et échelonné :



 x = 2 L1 ←L1 −L2
y = 4
z = −1



On obtient ainsi x = 2, y = 4 et z = −1 et l’unique solution du système

est (2,4, − 1).
La méthode utilisée pour cet exemple est reprise et généralisée dans le
paragraphe suivant.

3.3.3 Méthode du pivot de Gauss

La méthode du pivot de Gauss permet de trouver les solutions de n’im-
porte quel système linéaire. Nous allons décrire cet algorithme sur un exemple.
Il s’agit d’une description précise d’une suite d’opérations à effectuer, qui dé-
pendent de la situation et d’un ordre précis. Ce processus aboutit toujours
(et en plus assez rapidement) à un système échelonné puis réduit, qui conduit
immédiatement aux solutions du système.
Partie A. Passage à une forme échelonnée.
Soit le système suivant à résoudre :


 −x2 +2x3 +13x4 = 5
x1 −2x2 +3x3 +17x4 = 4
−x1 +3x2 −3x3 −20x4 = −1



Pour appliquer la méthode du pivot de Gauss, il faut d’abord que le

premier coefficient de la première ligne soit non nul. Comme ce n’est pas
le cas ici, on échange les deux premières lignes par l’opération élémentaire
L1 ↔ L2 :


 x1 −2x2 +3x3 +17x4 = 4 L1 ↔L2
−x2 +2x3 +13x4 = 5
−x1 +3x2 −3x3 −20x4 = −1



Nous avons déjà un coefficient 1 devant le x1 de la première ligne. On

dit que nous avons un pivot en position (1,1) (première ligne, première co-
lonne). Ce pivot sert de base pour éliminer tous les autres termes sur la même
colonne.
Il n’y a pas de terme x1 sur le deuxième ligne. Faisons disparaître le
terme x1 de la troisième ligne ; pour cela on fait l’opération élémentaire L3 ←
L3 + L1 : 
 x1 −2x2 +3x3 +17x4 = 4

−x2 +2x3 +13x4 = 5
−3x4 = 3


x2 L3 ←L3 +L1

[Link]
 [Link]

3.3. RÉSOLUTION PAR LA MÉTHODE DU PIVOT DE GAUSS 31

On change le signe de la seconde ligne (L2 ← −L2 ) pour faire apparaître

1 au coefficient du pivot (2,2) (deuxième ligne, deuxième colonne) :


 x1 −2x2 +3x3 +17x4 = 4
x2 −2x3 −13x4 = −5 L2 ← −L2
−3x4 = 3


x2

On fait disparaître le terme x2 de la troisième ligne, puis on fait apparaître

un coefficient 1 pour le pivot de la position (3,3) :


 x1 −2x2 +3x3 +17x4 = 4
x2 −2x3 −13x4 = −5


2x3 +10x4 = 8 L3 ←L3 −L2



 x1 −2x2 +3x3 +17x4 = 4
x2 −2x3 −13x4 = −5


x3 +5x4 = 4 L3 ← 21 L3

Le système est maintenant sous forme échelonnée.

Partie B. Passage à une forme réduite.

Il reste à le mettre sous la forme échelonnée réduite. Pour cela, on ajoute
à une ligne des multiples adéquats des lignes situées au-dessous d’elle, en
allant du bas à droite vers le haut à gauche.
On fait apparaître des 0 sur la troisième colonne en utilisant le pivot de
la troisième ligne :


 x1 −2x2 +3x3 +17x4 = 4
x2 −3x4 = 3 L2 ←L2 +2L3


x3 +5x4 = 4


 x1 −2x2 2x4 = −8 L1 ←L1 −3L3
x2 −3x4 = 3


x3 +5x4 = 4
On fait apparaître des 0 sur la deuxième colonne (en utilisant le pivot de
la deuxième ligne) :


 x1 −4x4 = −2 L1 ←L1 +2L2
x2 −3x4 = 3


x3 +5x4 = 4

Le système est sous forme échelonnée réduite.

[Link]
 [Link]

32 LEÇON 3. SYSTÈMES LINÉAIRES

Partie C. Solutions. Le système est maintenant très simple à résoudre.

En choisissant x4 comme variable libre, on peut exprimer x1 ,x2 ,x3 en fonction
de x4 :
x1 = 4x4 − 2, x2 = 3x4 + 3, x3 = −5x4 + 4.
Ce qui permet d’obtenir toutes les solutions du système :
n o
S = (4x4 − 2,3x4 + 3, − 5x4 + 4,x4 ) | x4 ∈ R .
Remarque 47. • Arrêtons nous quelque peu sur la notion d’algorithme.
Il s’agit d’une description précise d’une suite d’opérations à effectuer,
dans quel ordre et dans quel cas, qui aboutit au bout d’un nombre fini
d’étapes si possible connu à l’avance au résultat voulu.
• La première raison pour utiliser cet algorithme du pivot Gauss est
que l’on peut certes résoudre les systèmes à 2 ou 3 inconnues par des
manipulations sur les équations menées au petit bonheur la chance et
qui aboutissent à un résultat après un plus ou moins grand nombre
d’opérations. Or l’expérience montre que ces opérations sont le plus
souvent inutiles, redondantes, et surtout cause d’erreurs de calculs. Il
est bien préférable de se laisser guider par une méthode stricte dont
l’application garantit un nombre minimal de calculs (en général).
• La seconde raison est que dans les applications pratiques de l’algèbre
linéaire, lesquelles sont extrêmement nombreuses et importantes, les
systèmes à résoudre sont énormes (des milliers, voire des millions
d’équations et d’inconnues) et qu’il n’est pas question d’effectuer les
calculs à la main. Ce sont des ordinateurs qui s’en chargent, et ces
derniers ont besoin de programmes, lesquels sont la traduction en tel
ou tel langage d’un algorithme.

3.3.4 Systèmes homogènes

Le fait que l’on puisse toujours se ramener à un système échelonné réduit
implique le résultat suivant :
Théorème 48. Tout système homogène d’équations linéaires dont le nombre
d’inconnues est strictement plus grand que le nombre d’équations a une infi-
nité de solutions.
Exemple 49. Considérons le système homogène
3x1 + 3x2 − 2x3 − x5


 = 0
−x1 − x2 + x3 + 3x4 + x5 = 0



 2x1 + 2x2 − x3 + 2x4 + 2x5 = 0



x3 + 8x4 + 4x5 = 0.


[Link]
 [Link]

3.3. RÉSOLUTION PAR LA MÉTHODE DU PIVOT DE GAUSS 33

Sa forme échelonnée réduite est



 x1 + x2 + 13x5 = 0
x3 + 20x5 = 0
− 2x5 = 0.


x4
On pose comme variables libres x2 et x5 pour avoir

x1 = −x2 − 13x5 , x3 = −20x5 , x4 = 2x5 ,

et l’ensemble des solutions :

n o
S = (−x2 − 13x5 ,x2 , − 20x5 ,2x5 ,x5 ) | x2 ,x5 ∈ R

qui est bien infini.

3.3.5 Mini-exercices
1. Écrire un système linéaire à 4 équations et 5 inconnues qui soit éche-
lonné mais pas réduit. Idem avec échelonné, non réduit, dont tous les
coefficients sont 0 ou +1. Idem avec échelonné et réduit.
 2x1 −x2

 +x4 = 1
x2 +x3 −2x4 = 3


2. Résoudre les systèmes échelonnés suivants :


 2x3 +x4 = 4
x4 = −2


 x1 +x2
 +x4 = 0
x2 +x3 = 0


2x3 +x4 = 0
(
x1 +2x2 +x4 = 0
2x3 −3x4 = 0
3. Si l’on passe d’un système (S) par une des trois opérations élémentaires
à un système (S 0 ), alors quelle opération permet de passer de (S 0 ) à
(S) ?
4. Résoudre les systèmes linéaires suivants par la méthode du pivot de
Gauss : 
 2x + y + z
 = 3
x − y + 3z = 8
x + 2y − z = −3




 2x1 + 4x2 − 6x3 − 2x4 = 2
3x1 + 6x2 − 7x3 + 4x4 = 2
5x1 + 10x2 − 11x3 + 6x4 = 3



[Link]
 [Link]

34 LEÇON 3. SYSTÈMES LINÉAIRES

5. Résoudre le système suivant, selon les valeurs de a,b ∈ R :



 x +y −z = a
−x +2z = b


2y +2z = 4

[Link]
 [Link]

Leçon 4

Introduction aux matrices

L’algèbre linéaire :
1) permet d’exprimer un système d’équations compliqué sous une forme
simple et lisible.
2) permet de modéliser de nombreuses situations de l’économie et de la ges-
tion où apparaissent des calculs de type linéaire.
Exemple 50. Dans le cas d’une entreprise qui possède différents magasins
vendant divers produits, une matrice offre un moyen concis d’enregistrer les
stocks.
Magasin skis Bâtons Fixations Outils
1 110 120 90 150
 

2  200
 180 210 110 
3  175 190 160 80 
 

4 140 170 180 140

En lisant une ligne de la matrice, l’entreprise peut déterminer le niveau de
stocks de n’importe lequel de ses magasins. En lisant une colonne, elle peut
déterminer le niveau des stocks de n’importe quel groupe d’articles.
Les matrices sont des tableaux de nombres. La résolution d’un certain
nombre de problèmes d’algèbre linéaire se ramène à des manipulations sur les
matrices. Ceci est vrai en particulier pour la résolution des systèmes linéaires.

4.1 Définition
4.1.1 Définition
Définition 51. • Une matrice réelle A est un tableau rectangulaire
d’éléments de R.

35

[Link]
 [Link]

36 LEÇON 4. INTRODUCTION AUX MATRICES

• Elle est dite de taille n × p si le tableau possède n lignes et p colonnes.

• Les nombres du tableau sont appelés les coefficients de A.
• Le coefficient situé à la i-ème ligne et à la j-ème colonne est noté ai,j .

Un tel tableau est représenté de la manière suivante :

 
a1,1 a1,2 ... a1,j . . . a1,p
 a2,1 a2,2 ... a2,j . . . a2,p 


. . . ... ... ... ... ... 
     
A=
a
 ou A = ai,j 1≤i≤n ou ai,j .
 i,1 ai,2 ... ai,j . . . ai,p 
 1≤j≤p
. . . ... ... ... ... ... 
 

an,1 an,2 ... an,j . . . an,p

Exemple 52. !
1 −2 5
A=
0 3 7
est une matrice 2 × 3 avec, par exemple, a1,1 = 1 et a2,3 = 7.
Encore quelques définitions :

Définition 53. • Deux matrices sont égales lorsqu’elles ont la même

taille et que les coefficients correspondants sont égaux.
• L’ensemble des matrices à n lignes et p colonnes à coefficients dans R
est noté Mn,p (R).

Remarque 54. Dans ce cours, nous nous intéressons aux matrices à coefficients
réels, mais on peut considérer aussi des matrices à coefficients rationnels ou
complexes : on a alors les ensembles Mn,p (Q) et Mn,p (C)

4.1.2 Matrices particulières

Voici quelques types de matrices intéressantes :
• Si n = p (même nombre de lignes que de colonnes), la matrice est dite
matrice carrée. On note Mn (K) au lieu de Mn,n (K).
 
a1,1 a1,2 . . . a1,n
 a2,1 a2,2 . . . a2,n 
 
 . .. .. 
 . ...
 . . . 


an,1 an,2 . . . an,n

Les éléments a1,1 ,a2,2 , . . . ,an,n forment la diagonale principale de la
matrice.

[Link]
 [Link]

4.1. DÉFINITION 37

• Une matrice qui n’a qu’une seule ligne (n = 1) est appelée matrice
ligne ou vecteur ligne. On la note
 
A = a1,1 a1,2 . . . a1,p .

• De même, une matrice qui n’a qu’une seule colonne (p = 1) est appelée
matrice colonne ou vecteur colonne. On la note
 
a1,1
 a2,1 
 
A =  .. 

.
 . 
an,1

• La matrice (de taille n × p) dont tous les coefficients sont des zéros est
appelée la matrice nulle et est notée 0n,p ou plus simplement 0. Dans
le calcul matriciel, la matrice nulle joue le rôle du nombre 0 pour les
réels.

4.1.3 Addition de matrices

Exemple 55. Supposons que les livraisons D soient faites aux magasins de
l’entreprise considérée dans l’exemple 50. Quel est le nouveau niveau des
stocks ?
40 20 50 10
 
25 30 10 60
D= .

15 0 40 70


60 40 10 50
Pour trouver le nouveau niveau des stocks, désignons la matrice initiale par
S et calculons S + D. En additionnant les uns aux autres les éléments cor-
respondants de chaque matrice, nous trouvons :

120 + 40 110 + 20 90 + 50 150 + 10 160 130 140 160

   
200 + 25 180 + 30 210 + 10 110 + 60 225 210 220 170
S+D =  =
   
175 + 15 190 + 0 160 + 40 80 + 70  190 190 200 150


140 + 60 170 + 40 180 + 10 140 + 50 200 210 190 190

Somme de deux matrices

Définition 56 (Somme de deux matrices). Soient A et B deux matrices

ayant la même taille n × p. Leur somme C = A + B est la matrice de taille
n × p définie par
cij = aij + bij .

[Link]
 [Link]

38 LEÇON 4. INTRODUCTION AUX MATRICES

En d’autres termes, on somme coefficients par coefficients. Remarque : on

note indifféremment aij où ai,j pour les coefficients de la matrice A.
Exemple 57.
! ! !
3 −2 0 5 3 3
Si A= et B= alors A+B = .
1 7 2 −1 3 6
!
0 −2
Par contre si B = alors A + B0 n’est pas définie.
8

Produit d’une matrice par un scalaire

 
25
Exemple 58. La matrice colonne A = 40 est une matrice de prix HT. On
 

32
suppose que le taux de la TVA soit de 20%. Quelle est la matrice B des prix
de vente TTC ?
Le coefficient multiplicateur est 1,2. On doit donc multiplier tous les élé-
ments de A par 1,2. On obtient ainsi
     
25 1,2 × 25 30
B = (1,2) = 1,2 × 40 = 1,2 × 40 =  48  (4.1)
     

32 1,2 × 32 38,4

En algèbre linéaire, un simple nombre tel que 12, −2 ou 0,07 est appelé
un scalaire.

 (Produit
Définition 59  d’une matrice par un scalaire). Le produitd’une
matrice A = aij de Mn,p (K) par un scalaire α ∈ K est la matrice αaij
formée en multipliant chaque coefficient de A par α. Elle est notée α · A (ou
simplement αA).

Ce processus s’appelle multiplication par un scalaire parce que l’échelle

des éléments de la matrice est augmentée ou diminuée selon la valeur de ce
scalaire.
Exemple 60.
! !
1 2 3 2 4 6
Si A= et α=2 alors αA = .
0 1 0 0 2 0

La matrice (−1)A est l’opposée de A et est notée −A. La différence A − B

est définie par A + (−B).

[Link]
 [Link]

4.2. MULTIPLICATION DE MATRICES 39

Exemple 61.
! ! !
2 −1 0 −1 4 2 3 −5 −2
Si A = et B = alors A−B = .
4 −5 2 7 −5 3 −3 0 −1

L’addition et la multiplication par un scalaire se comportent sans sur-

prises :

Proposition 62. Soient A, B et C trois matrices appartenant à Mn,p (K).

Soient α ∈ K et β ∈ K deux scalaires.
1. A + B = B + A : la somme est commutative,
2. A + (B + C) = (A + B) + C : la somme est associative,
3. A + 0 = A : la matrice nulle est l’élément neutre de l’addition,
4. (α + β)A = αA + βA,
5. α(A + B) = αA + αB.

4.1.4 Mini-exercices
   
−7 2 1 2 3 21 −6 1
1 0 1
1. Soient A = 0 −1 ,B= 2 3 1 ,C= 0 3 ,D= 2
0 1 0 ,E=
  1 −4 3 2 1 −3 12 1 1 1
1 2
−3 0 . Calculer toutes les sommes possibles de deux de ces matrices.
−8 6
Calculer 3A + 2C et 5B − 4D. Trouver α tel que A − αC soit la matrice
nulle.
2. Montrer que si A + B = A, alors B est la matrice nulle.
3. Que vaut 0 · A ? et 1 · A ? Justifier l’affirmation : α(βA) = (αβ)A. Idem
avec nA = A + A + · · · + A (n occurrences de A).

4.2 Multiplication de matrices

Exemple 63. Reportons-nous à l’exemple 50. Supposons que le prix des skis
soit de 200 euros, celui de bâtons 50 euros, celui des fixations 100 euros
et celui des outils 150 euros. Quelle est la valeur V du stock des différents
magasins ?
On exprime les prix sous la forme d’un vecteur colonne des prix P et on

[Link]
 [Link]

40 LEÇON 4. INTRODUCTION AUX MATRICES

multiplie S et P .

120 110 90 150 200

  
200 180 210 110  50 
 
V = SP = S + D =  
175 190 160 80 100
  
 
140 170 180 140 150
120 × 200 + 110 × 50 + 90 × 100 + 150 × 150 61000
   
200 × 200 + 180 × 50 + 210 × 100 + 110 × 150 86500
= =  (4.2)
   
 175 × 200 + 190 × 50 + 160 × 100 + 80 × 150  72500
140 × 200 + 170 × 50 + 180 × 100 + 140 × 150 75500

4.2.1 Définition du produit

Le produit AB de deux matrices A et B est défini si et seulement si le
nombre de colonnes de A est égal au nombre de lignes de B.

Définition 64 (Produit de deux matrices). Soient A = (aij ) une matrice

n × p et B = (bij ) une matrice p × q. Alors le produit C = AB est une
matrice n × q dont les coefficients cij sont définis par :
p
X
cij = aik bkj
k=1

On peut écrire le coefficient de façon plus développée, à savoir :

cij = ai1 b1j + ai2 b2j + · · · + aik bkj + · · · + aip bpj .

Il est commode de disposer les calculs de la façon suivante.

×
 
 × 
 
←B
×
 
 
×
|
   
   | 
A→ ← AB
   
× × × × − − − cij
  


Avec cette disposition, on considère d’abord la ligne de la matrice A située

à gauche du coefficient que l’on veut calculer (ligne représentée par des ×
dans A) et aussi la colonne de la matrice B située au-dessus du coefficient
que l’on veut calculer (colonne représentée par des × dans B). On calcule
le produit du premier coefficient de la ligne par le premier coefficient de la

[Link]
 [Link]

4.2. MULTIPLICATION DE MATRICES 41

colonne (ai1 × b1j ), que l’on ajoute au produit du deuxième coefficient de la

ligne par le deuxième coefficient de la colonne (ai2 × b2j ), que l’on ajoute au
produit du troisième. . .

4.2.2 Exemples
Exemple 65.  
! 1 2
1 2 3
A= B = −1 1
 
2 3 4
1 1
On dispose d’abord le produit correctement (à gauche) : la matrice obte-
nue est de taille 2×2. Puis on calcule chacun des coefficients, en commençant
par le premier coefficient c11 = 1 × 1 + 2 × (−1) + 3 × 1 = 2 (au milieu),
puis les autres (à droite).
     
1 2 1 2 1 2
−1 1 −1 1 −1 1
     

! 1 1! ! 1 1! ! 1 1!
1 2 3 c11 c12 1 2 3 2 c12 1 2 3 2 7
2 3 4 c21 c22 2 3 4 c21 c22 2 3 4 3 11

Un exemple intéressant est le produit d’un vecteur ligne par un vecteur

colonne :  
b1
 b2 
   
u = a1 a2 · · · an v=  .. 

.
bn
Alors u × v est une matrice de taille 1 × 1 dont l’unique coefficient est a1 b1 +
a2 b2 + · · · + an bn . Ce nombre s’appelle le produit scalaire des vecteurs u et v.
Calculer le coefficient cij dans le produit A × B revient donc à calculer
le produit scalaire des vecteurs formés par la i-ème ligne de A et la j-ème
colonne de B.

4.2.3 Pièges à éviter

Premier piège. Le produit de matrices n’est pas commutatif en
général.
En effet, il se peut que AB soit défini mais pas BA, ou que AB et BA
soient tous deux définis mais pas de la même taille. Mais même dans le cas
où AB et BA sont définis et de la même taille, on a en général AB 6= BA.

[Link]
 [Link]

42 LEÇON 4. INTRODUCTION AUX MATRICES

Exemple 66.
! ! ! ! ! !
5 1 2 0 14 3 2 0 5 1 10 2
= mais = .
3 −2 4 3 −2 −6 4 3 3 −2 29 −2

Deuxième piège. AB = 0 n’implique pas A = 0 ou B = 0.

Il peut arriver que le produit de deux matrices non nulles soit nul. En
d’autres termes, on peut avoir A 6= 0 et B 6= 0 mais AB = 0.
Exemple 67.
! ! !
0 −1 2 −3 0 0
A= B= et AB = .
0 5 0 0 0 0

Troisième piège. AB = AC n’implique pas B = C. On peut avoir

AB = AC et B 6= C.
Exemple 68.
! ! ! !
0 −1 4 −1 2 5 −5 −4
A= B= C= et AB = AC = .
0 3 5 4 5 4 15 12

4.2.4 Propriétés du produit de matrices

Malgré les difficultés soulevées au-dessus, le produit vérifie les propriétés
suivantes :
Proposition 69. 1. A(BC) = (AB)C : associativité du produit,
2. A(B + C) = AB + AC et (B + C)A = BA + CA : distributivité
du produit par rapport à la somme,
3. A · 0 = 0 et 0 · A = 0.

4.2.5 La matrice identité

La matrice carrée suivante s’appelle la matrice identité :
 
1 0 ... 0

 0 1 ... 0  
In =  .... . . .. 

 . . . . 

0 0 ... 1
Ses éléments diagonaux sont égaux à 1 et tous ses autres éléments sont
égaux à 0. Elle se note In ou simplement I. Dans le calcul matriciel, la
matrice identité joue un rôle analogue à celui du nombre 1 pour les réels.
C’est l’élément neutre pour la multiplication. En d’autres termes :

[Link]
 [Link]

4.2. MULTIPLICATION DE MATRICES 43

Proposition 70. Si A est une matrice n × p, alors

In · A = A et A · Ip = A.

4.2.6 Puissance d’une matrice

Dans l’ensemble Mn (K) des matrices carrées de taille n × n à coefficients
dans K, la multiplication des matrices est une opération interne : si A,B ∈
Mn (K) alors AB ∈ Mn (K).
En particulier, on peut multiplier une matrice carrée par elle-même : on
note A2 = A × A, A3 = A × A × A.
On peut ainsi définir les puissances successives d’une matrice :
Définition 71. Pour tout A ∈ Mn (K), on définit les puissances successives
de A par A0 = In et Ap+1 = Ap × A pour tout p ∈ N. Autrement dit,
Ap = A
|
×A× {z
· · · × A}.
p facteurs
 
1 0 1
p
Exemple 72. On cherche à calculer A avec A = 0 −1 0. On calcule A2 ,


0 0 2
3 4
A et A et on obtient :
     
1 0 3 1 0 7 1 0 15
A2 = 
0 1 0

A3 = A2 ×A =  0 −1 0 A4 = A3 ×A = 0 1 0  .
  

0 0 4 0 0 8 0 0 16
L’observation
 de ces premières  puissances permet de penser que la formule
p
1 0 2 −1
est : Ap = 0 (−1)p 0  . Démontrons ce résultat par récurrence.
p
0 0 2
Il est vrai pour p = 0 (on trouve l’identité). On le suppose vrai pour un
entier p et on va le démontrer pour p + 1. On a, d’après la définition,
2p − 1 2p+1 − 1
     
1 0 1 0 1 1 0
Ap+1 p
= A ×A = 0 (−1)
 p
0 ×0 −1 0 = 0 (−1)
    p+1
0 .

p p+1
0 0 2 0 0 2 0 0 2
Donc la propriété est démontrée.

4.2.7 Formule du binôme

Comme la multiplication n’est pas commutative, les identités binomiales
usuelles sont fausses. En particulier, (A + B)2 ne vaut en général pas A2 +
2AB + B 2 , mais on sait seulement que
(A + B)2 = A2 + AB + BA + B 2 .

[Link]
 [Link]

44 LEÇON 4. INTRODUCTION AUX MATRICES

Proposition 73 (Calcul de (A + B)p lorsque AB = BA). Soient A et B

deux éléments de Mn (K) qui commutent, c’est-à-dire tels que AB = BA.
Alors, pour tout entier p ≥ 0, on a la formule
p !
p
X p p−k k
(A + B) = A B
k=0 k
 
p
où k
désigne le coefficient du binôme.
La démonstration est similaire à celle de la formule du binôme pour (a +
p
b) , avec a,b ∈ R.
1 1 1 1 0 1 1 1
   
0 1 2 1 0 0 2 1
Exemple 74. Soit A =  . On pose N = A − I =  .
   
0 0 1 3 0 0 0 3
0 0 0 1 0 0 0 0
La matrice N est nilpotente (c’est-à-dire il existe k ∈ N tel que N k = 0)
comme le montrent les calculs suivants :
0 0 2 4 0 0 0 6
   
0 0 0 6 0 0 0 0
N2 =  N3 =  et N 4 = 0.
   
0 0 0 0 0 0 0 0
 

0 0 0 0 0 0 0 0
Comme on a A = I +N et les matrices N et I commutent (la matrice identité
commute avec toutes les matrices), on peut appliquer la formule du binôme
de Newton. On utilise que I k = I pour tout k et surtout que N k = 0 si k ≥ 4.
On obtient
p ! 3
!
p p
Ap = N k I p−k = N k = I + pN + p(p−1) N 2 + p(p−1)(p−2) N 3.
X X
2! 3!
k=0 k k=0 k
D’où
1 p p2 p(p2 − p + 1)
 
0 1 2p p(3p − 2) 
Ap =  .
 
0 0 1 3p 
0 0 0 1

4.2.8 Mini-exercices
 

0 2 −2
 2 1 0  8 2  5 
1. Soient A = 6 −4 0 ,B = 0 1 0
2 −2 −3
,C = −3 2 ,D= 2
−1
,E =
  −5 5
x y z . Quels produits sont possibles ? Les calculer !
0 0 1 1 0 0
2. Soient A = 0 1 0 et B = 0 0 2
−1 0
. Calculer A2 , B 2 , AB et BA.
 21 1
0
2
0
  01 0 0

3. Soient A = et B =
0 2 0 Calculer Ap et B p pour tout p ≥ 0.
2 0 0 .
0 0 2 3 1 0
Montrer que AB = BA. Calculer (A + B)p .

[Link]
 [Link]

4.3. MATRICES TRIANGULAIRES, TRANSPOSITION, TRACE, MATRICES SYMÉTRIQUES45

4.3 Matrices triangulaires, transposition, trace,

matrices symétriques
4.3.1 Matrices triangulaires, matrices diagonales
Soit A une matrice de taille n×n. On dit que A est triangulaire inférieure
si ses éléments au-dessus de la diagonale sont nuls, autrement dit :

i < j =⇒ aij = 0.

Une matrice triangulaire inférieure a la forme suivante :

0 ··· ··· 0
 
a11
 ... .. 
a
 21 a22 . 

 . .. ... ... ..
 .

 . . . 

 . ..
 . .. 
 . . . 0  
an1 an2 · · · · · · ann

On dit que A est triangulaire supérieure si ses éléments en-dessous de la

diagonale sont nuls, autrement dit :

i > j =⇒ aij = 0.

Une matrice triangulaire supérieure a la forme suivante :

 
a11 a12 . . . . . . . . . a1n
 0 a22 . . . . . . . . . a2n 
 
 .. .. .. .. 
 
 . . . . 
 . .
 
 .. .. .. . 
 . . . 
 . .. .. .. 
 . . .
 . . 

0 . . . . . . . . . 0 ann

Exemple 75. Deux matrices triangulaires inférieures (à gauche), une matrice

triangulaire supérieure (à droite) :
   
4 0 0 ! 1 1 −1
5 0
0 −1 0 0 −1 −1
   
1 −2
3 −2 3 0 0 −1

Une matrice qui est triangulaire inférieure et triangulaire supérieure est

dite diagonale. Autrement dit : i 6= j =⇒ aij = 0.

[Link]
 [Link]

46 LEÇON 4. INTRODUCTION AUX MATRICES

Exemple 76. Exemples de matrices diagonales :

 
−1 0 0 !
2 0
 0 6 0 et
 
0 3
0 0 0

Exemple 77 (Puissances d’une matrice diagonale). Si D est une matrice dia-

gonale, il est très facile de calculer ses puissances Dp (par récurrence sur
p) :
   p 
α1 0 . . . . . . 0 α 0 ... ... 0
 1 p
 0 α2 0 ... 0 0 α2 0 ... 0
  
. .. .. .. ..   .. .. .. .. .. 
   
 ..
D=
 . . . . 

=⇒ Dp =  .
 . . . . 

 0 ... p
 0 αn−1 0  
0
 . . . 0 αn−1 0  
0 ... ... 0 αn 0 ... ... 0 αnp

4.3.2 La transposition
Soit A la matrice de taille n × p
 
a11 a12 . . . a1p

 a21 a22 . . . a2p 

A=  .. .. .. .
. . .
 
 
an1 an2 . . . anp

Définition 78. On appelle matrice transposée de A la matrice AT de taille

p × n définie par :
 
a11 a21 . . . an1
T

 a12 a22 . . . an2 

A =  .. .. ..  .
. . .
 
 
a1p a2p . . . anp

Autrement dit : le coefficient à la place (i,j) de AT est aji . Ou encore la

i-ème ligne de A devient la i-ème colonne de AT (et réciproquement la j-ème
colonne de AT est la j-ème ligne de A).

Notation : La transposée de la matrice A se note aussi souvent tA.

Exemple 79.
 T  
1 2 3 1 4 −7

 4 5 −6
 = 2 5

8
−7 8 9 3 −6 9

[Link]
 [Link]

4.3. MATRICES TRIANGULAIRES, TRANSPOSITION, TRACE, MATRICES SYMÉTRIQUES47

 T  
0 3 ! 1
0 1 −1 T
 1 −5 = (1 − 2 5) = −2
   
3 −5 2
−1 2 5
L’opération de transposition obéit aux règles suivantes :
Théorème 80. 1. (A + B)T = AT + B T
2. (αA)T = αAT
3. (AT )T = A
4. (AB)T = B T AT

4.3.3 La trace
Dans le cas d’une matrice carrée de taille n×n, les éléments a11 , a22 , . . . ,ann
sont appelés les éléments diagonaux.
Sa diagonale principale est la diagonale (a11 ,a22 , . . . ,ann ).
 
a11 a12 . . . a1n
 a21 a22 . . . a2n 
 
 . .. .. 
 . ..
 . . . . 


an1 an2 . . . ann

Définition 81. La trace de la matrice A est le nombre obtenu en addition-
nant les éléments diagonaux de A. Autrement dit, Tr A = a11 + a22 + · · · + ann .
Exemple 82. • Si A = ( 2 1 ), alors Tr A = 2 + 5 = 7.
 1 1 2  05
• Pour B = 11
5 2 8
0 −10
, Tr B = 1 + 2 − 10 = −7.
Théorème 83. Soient A et B deux matrices n × n. Alors :
1. Tr(A + B) = Tr A + Tr B,
2. Tr(αA) = α Tr A pour tout α ∈ K,
3. Tr(AT ) = Tr A,
4. Tr(AB) = Tr(BA).

4.3.4 Matrices symétriques

Définition 84. Une matrice A de taille n × n est symétrique si elle est égale
à sa transposée, c’est-à-dire si
A = AT ,
ou encore si aij = aji pour tout i,j = 1, . . . ,n. Les coefficients sont donc
symétriques par rapport à la diagonale.

[Link]
 [Link]

48 LEÇON 4. INTRODUCTION AUX MATRICES

Exemple 85. Les matrices suivantes sont symétriques :

 
! −1 0 5
0 2
 0

2 −1
2 4

5 −1 0

Exemple 86. Pour une matrice B quelconque, les matrices B · B T et B T · B

sont symétriques.
Preuve : (BB T )T = (B T )T B T = BB T . Idem pour B T B.

4.3.5 Matrices antisymétriques

Définition 87. Une matrice A de taille n × n est antisymétrique si

AT = −A,

c’est-à-dire si aij = −aji pour tout i,j = 1, . . . ,n.

Exemple 88.  
! 0 4 2
0 −1
−4 0 −5
 
1 0
−2 5 0
Remarquons que les éléments diagonaux d’une matrice antisymétrique
sont toujours tous nuls.
Exemple 89. Toute matrice est la somme d’une matrice symétrique et d’une
matrice antisymétrique.
Preuve : Soit A une matrice. Définissons B = 12 (A+AT ) et C = 12 (A−AT ).
Alors d’une part A = B + C ; d’autre part B est symétrique, car B T =
1
2
(AT + (AT )T ) = 12 (AT + A) = B ; et enfin C est antisymétrique, car C T =
1
2
(AT − (AT )T ) = −C.
Exemple :
! ! !
2 10 2 9 0 1
Pour A= alors A = + .
8 −3 9 −3 −1 0
| {z } | {z }
symétrique antisymétrique

4.3.6 Mini-exercices
1. Montrer que la somme de deux matrices triangulaires supérieures reste
triangulaire supérieure. Montrer que c’est aussi valable pour le produit.
2. Montrer que si A est triangulaire supérieure, alors AT est triangulaire
inférieure. Et si A est diagonale ?

[Link]
 [Link]

4.3. MATRICES TRIANGULAIRES, TRANSPOSITION, TRACE, MATRICES SYMÉTRIQUES49

 x1 
x2
3. Soit A =  .. . Calculer AT · A, puis A · AT .
.
xn

4. Soit A = ( ac db ). Calculer Tr(A · AT ).

5. Montrer que la décomposition d’une matrice sous la forme « symétrique
+ antisymétrique » est unique.

[Link]
 [Link]

50 LEÇON 4. INTRODUCTION AUX MATRICES

[Link]
 [Link]

Leçon 5

Inversion des matrices

5.1 Définitions et premières propriétés

5.1.1 Définition
Définition 90 (Matrice inverse). Soit A une matrice carrée de taille n × n.
S’il existe une matrice carrée B de taille n × n telle que

AB = I et BA = I,

on dit que A est inversible. On appelle B l’inverse de A et on la note A−1 .

On verra plus tard qu’il suffit en fait de vérifier une seule des conditions
AB = I ou bien BA = I.

• Plus généralement, quand A est inversible, pour tout p ∈ N, on note :

A−p = (A−1 )p = A
|
−1 −1
A {z· · · A−1} .
p facteurs

• L’ensemble des matrices inversibles de Mn (R) est noté GLn (R) (GL
est l’acronyme de groupe Général Linéaire).

5.1.2 Exemples
Exemple 91. Soit A = ( 10 23 ). Étudier si A est inversible, c’est étudier l’exis-
tence d’une matrice B = ( ac db ) à coefficients dans R, telle que AB = I et
BA = I. Or AB = I équivaut à :
! ! ! ! !
1 2 a b 1 0 a + 2c b + 2d 1 0
AB = I ⇐⇒ = ⇐⇒ =
0 3 c d 0 1 3c 3d 0 1

51

[Link]
 [Link]

52 LEÇON 5. INVERSION DES MATRICES

Cette égalité équivaut au système :



 a + 2c = 1
b + 2d = 0




 3c = 0
3d = 1


Sa résolution est immédiate : a = 1, b = − 23 , 

c = 0, d = 13 . Il n’y
1 −2
a donc qu’une seule matrice possible, à savoir B = 0 13 . Pour prouver
3
qu’elle convient, il faut aussi montrer l’égalité BA = I, dont la vérification
!
−1 1 − 23
est laissée au lecteur. La matrice A est donc inversible et A = .
0 13
3 0
! 92. La matrice A = ( 5 0 ) n’est pas inversible. En effet, soit B =
Exemple
a b
une matrice quelconque. Alors le produit
c d
! ! !
a b 3 0 3a + 5b 0
BA = =
c d 5 0 3c + 5d 0

ne peut jamais être égal à la matrice identité.

Exemple 93. • Soit In la matrice carrée identité de taille n×n. C’est une
matrice inversible, et son inverse est elle-même par l’égalité In In = In .
• La matrice nulle 0n de taille n × n n’est pas inversible. En effet on
sait que, pour toute matrice B de Mn (R), on a B0n = 0n , qui ne peut
jamais être la matrice identité.

5.1.3 Propriétés
[Link] Unicité
Proposition 94. Si A est inversible, alors son inverse est unique.

[Link] Inverse de l’inverse

Proposition 95. Soit A une matrice inversible. Alors A−1 est aussi inver-
sible et on a : (A−1 )−1 = A

[Link] Inverse d’un produit

Proposition 96. Soient A et B deux matrices inversibles de même taille.
Alors AB est inversible et (AB)−1 = B −1 A−1

[Link]
 [Link]

5.2. MÉTHODES DE CALCUL 53

Il faut bien faire attention à l’inversion de l’ordre !

Démonstration. Il suffit de montrer (B −1 A−1 )(AB) = I et (AB)(B −1 A−1 ) =
I. Cela suit de

(B −1 A−1 )(AB) = B −1 (AA−1 )B = B −1 IB = B −1 B = I,

et (AB)(B −1 A−1 ) = A(BB −1 )A−1 = AIA−1 = AA−1 = I.

De façon analogue, on montre que si A1 , . . . ,Am sont inversibles, alors

(A1 A2 · · · Am )−1 = A−1 −1 −1

m Am−1 · · · A1 .

[Link] Simplification par une matrice inversible

Si C est une matrice quelconque de Mn (R), nous avons vu que la relation
AC = BC où A et B sont des éléments de Mn (R) n’entraîne pas forcé-
ment l’égalité A = B. En revanche, si C est une matrice inversible, on a la
proposition suivante :
Proposition 97. Soient A et B deux matrices de Mn (R) et C une matrice
inversible de Mn (R). Alors l’égalité AC = BC implique l’égalité A = B.
Démonstration. Ce résultat est immédiat : si on multiplie à droite l’égalité
AC = BC par C −1 , on obtient l’égalité : (AC)C −1 = (BC)C −1 . En utilisant
l’associativité du produit des matrices on a A(CC −1 ) = B(CC −1 ), ce qui
donne d’après la définition de l’inverse AI = BI, d’où A = B.

5.1.4 Mini-exercices
−1 −1
1. Soient A = ( −1 −2 2 1
3 4 ) et B = ( 5 3 ). Calculer A , B , (AB)−1 , (BA)−1 ,
A−2 .
1 0 0
2. Calculer l’inverse de 0 2 0 .
1 0 3
 −1 −2 0 
3. Soit A = 2 3 0 . Calculer 2A − A2 . Sans calculs, en déduire A−1 .
0 0 1

5.2 Méthodes de calcul

Nous allons voir une méthode pour calculer l’inverse d’une matrice quel-
conque de manière efficace. Cette méthode est une reformulation de la mé-
thode du pivot de Gauss pour les systèmes linéaires. Auparavant, nous com-
mençons par une formule directe dans le cas simple des matrices 2 × 2.

[Link]
 [Link]

54 LEÇON 5. INVERSION DES MATRICES

5.2.1 Matrices 2 × 2
!
a b
Considérons la matrice 2 × 2 : A = .
c d

Proposition 98. A est inversible si et seulement si ad − bc 6= 0, et dans ce

!
−1 1 d −b
cas A =
ad − bc −c a

Remarque 99. Le réel ad − bc s’appelle déterminant de A, et la formule pour

l’inverse se réécrit !
−1 1 d −b
A =
det A −c a
 
1 d −b
Démonstration. On vérifie que si B = ad−bc −c a alors AB = ( 10 01 ). Idem
pour BA.

5.2.2 Méthode de Gauss pour inverser les matrices

La méthode pour inverser une matrice A consiste à faire des opérations
élémentaires sur les lignes de la matrice A jusqu’à la transformer en la ma-
trice identité I. On fait simultanément les mêmes opérations élémentaires
en partant de la matrice I. On aboutit alors à une matrice qui est A−1 . La
preuve sera vue dans la section suivante.

En pratique, on fait les deux opérations en même temps en adoptant la

disposition suivante : à côté de la matrice A que l’on veut inverser, on rajoute
la matrice identité pour former un tableau (A | I). Sur les lignes de cette
matrice augmentée, on effectue des opérations élémentaires jusqu’à obtenir
le tableau (I | B). Et alors B = A−1 .

Ces opérations élémentaires sur les lignes sont :

1. Li ← λLi avec λ 6= 0 : on peut multiplier une ligne par un réel non nul
(ou un élément de R \ {0}).
2. Li ← Li + λLj avec λ ∈ R (et j 6= i) : on peut ajouter à la ligne Li un
multiple d’une autre ligne Lj .
3. Li ↔ Lj : on peut échanger deux lignes.

N’oubliez pas : tout ce que vous faites sur la partie gauche de la matrice
augmentée, vous devez aussi le faire sur la partie droite.

[Link]
 [Link]

5.2. MÉTHODES DE CALCUL 55

5.2.3 Un exemple
 
1 2 1
Calculons l’inverse de A =  4

0 −1.
−1 2 2
Voici la matrice augmentée, avec les lignes numérotées :
 
1 2 1 1 0 0 L1
(A | I) =  4 0 −1 0 1 0 
 
L2
−1 2 2 0 0 1 L3

On applique la méthode de Gauss pour faire apparaître des 0 sur la

première colonne, d’abord sur la deuxième ligne par l’opération élémentaire
L2 ← L2 − 4L1 qui conduit à la matrice augmentée :
 
1 2 1 1 0 0
 0 −8 −5 −4 1 0 
 
L2 ←L2 −4L1
−1 2 2 0 0 1

Puis un 0 sur la première colonne, à la troisième ligne, avec L3 ← L3 + L1 :

 
1 2 1 1 0 0
 0 −8 −5 −4 1 0 
 

0 4 3 1 0 1 L3 ←L3 +L1

On multiplie la ligne L2 afin qu’elle commence par 1 :

 
1 2 1 1 0 0
5 1 1
 0 1 8 2 −8 0  L2 ←− 18 L2
 

0 4 3 1 0 1

On continue afin de faire apparaître des 0 partout sous la diagonale, et on

multiplie la ligne L3 . Ce qui termine la première partie de la méthode de
Gauss :  
1 2 1 1 0 0
5 1
 0 1 8

2
− 18 0 

0 0 12 −1 12 1 L3 ←L3 −4L2

puis  
1 2 1 1 0 0
5 1 1
 0 1 8

2
− 8
0 

0 0 1 −2 1 2 L3 ←2L3

Il ne reste plus qu’à « remonter » pour faire apparaître des zéros au-dessus
de la diagonale :

[Link]
 [Link]

56 LEÇON 5. INVERSION DES MATRICES

 
1 2 1 1 0 0
7 3 5 
 0 1 0

4
− 4
− 4 
L2 ←L2 − 58 L3
0 0 1 −2 1 2
puis
1 0 0 − 12 12 1
 
L1 ←L1 −2L2 −L3
2
7 3 5 
 0 1 0

4
− 4
− 4 
0 0 1 −2 1 2

Ainsi l’inverse de A est la matrice obtenue à droite et après avoir factorisé

tous les coefficients par 14 , on a obtenu :
 
−2 2 2
1
A−1 =  7 −3 −5

4
−8 4 8

Pour se rassurer sur ses calculs, on n’oublie pas de vérifier rapidement

que A × A−1 = I.

5.2.4 Mini-exercices
 
2 −3
1. Si possible calculer l’inverse des matrices : ( 37 12 ), −5 4 , ( 03 20 ), ( α+1 1
2 α ).
 
2. Soit A(θ) = cos θ − sin θ
sin θ cos θ . Calculer A(θ)−1 .
! 

1 3 0
 
2 −2 1  1 0 1 0 2 1 1 1
0 2 −2 0 1 0 0 1
3. Calculer l’inverse des matrices : 2 1 −1 , 3 0 5 , −1 2 0 1 , 0 1 −1 2 ,
−2 1 1 1 1 2 0 1 1 0
0 2 1 3
1 1 1 0 0!
0 1 2 0 0
−1 1 2 0 0 .
0 0 0 2 1
0 0 0 5 3

5.3 Systèmes linéaires et matrices élémentaires

5.3.1 Matrices et systèmes linéaires
Le système linéaire

a11 x1 + a12 x2 + · · ·


 + a1p xp = b1
a21 x1 + a22 x2 + · · · + a2p xp = b2




 ...
an1 x1 + an2 x2 + · · · + anp xp = bn


[Link]
 [Link]

5.3. SYSTÈMES LINÉAIRES ET MATRICES ÉLÉMENTAIRES 57

peut s’écrire sous forme matricielle :

     
a11 . . . a1p x1 b1

 a21 . . . a2p 


 x2 


 b2 

 .. ..   ..  =  .. .
. . . .
     
     
an1 . . . anp xp bn
| {z } | {z } | {z }
A X B

On appelle A ∈ Mn,p (R) la matrice des coefficients du système. B ∈

Mn,1 (R) est le vecteur du second membre. Le vecteur X ∈ Mp,1 (R) est une
solution du système si et seulement si

AX = B.

Nous savons que :

Théorème 100. Un système d’équations linéaires n’a soit aucune solution,

soit une seule solution, soit une infinité de solutions.

[Link] Matrice augmentée

Étant donné un système d’équations linéaires sous forme matricielle AX +
B, la matrice augmentée (A|B) est la matrice des coefficients du système A,
à laquelle on a juxtaposé le vecteur colonne des termes constants B, en les
séparant par un trait vertical. Ainsi, pour le système d’équations

7x + 3y = 45
4x + 5y = 29

la matrice augmentée est

!
7 3 45
(A|B) = .
4 5 29

On peut alors résoudre le système en forme matricielle, en appliquant la

méthode d’élimination gaussienne aux lignes de la matrice augmentée. On y
gagne en clarté et on ne doit pas réécrire chaque fois les inconnues.

5.3.2 Matrices inversibles et systèmes linéaires

Considérons le cas où le nombre d’équations égale le nombre d’inconnues :

[Link]
 [Link]

58 LEÇON 5. INVERSION DES MATRICES

     
a11 . . . a1n x1 b1

 a21 . . . a2n 


 x2 


 b2 

 .. ..   ..  =  .. .
. . . .
     
     
an1 . . . ann xn bn
| {z } | {z } | {z }
A X B
Alors A ∈ Mn (R) est une matrice carrée et B un vecteur de Mn,1 (R).
Pour tout second membre, nous pouvons utiliser les matrices pour trouver la
solution du système linéaire.
Proposition 101. Si la matrice A est inversible, alors la solution du système
AX = B est unique et est : X = A−1 B
 
La preuve est juste de vérifier que si X = A−1 B, alors AX = A A−1 B =
 
AA−1 B = I · B = B. Réciproquement si AX = B, alors nécessairement
X = A−1 B. Nous verrons bientôt que si la matrice n’est pas inversible, alors
soit il n’y a pas de solution, soit une infinité.

5.3.3 Les matrices élémentaires

Pour calculer l’inverse d’une matrice A, et aussi pour résoudre des sys-
tèmes linéaires, nous avons utilisé trois opérations élémentaires sur les lignes
qui sont :
1. Li ← λLi avec λ 6= 0 : on peut multiplier une ligne par un réel non nul
(ou un élément de R \ {0}).
2. Li ← Li + λLj avec λ ∈ R (et j 6= i) : on peut ajouter à la ligne Li un
multiple d’une autre ligne Lj .
3. Li ↔ Lj : on peut échanger deux lignes.
Nous allons définir trois matrices élémentaires ELi ←λLi , ELi ←Li +λLj , ELi ↔Lj
correspondant à ces opérations. Plus précisément, le produit E × A corres-
pondra à l’opération élémentaire sur A. Voici les définitions accompagnées
d’exemples.
1. La matrice ELi ←λLi est la matrice obtenue en multipliant par λ la i-ème
ligne de la matrice identité In , où λ est un nombre réel non nul.

1 0 0 0
 
0 5 0 0
EL2 ←5L2 = 
0 0 1 0
 

0 0 0 1

[Link]
 [Link]

5.3. SYSTÈMES LINÉAIRES ET MATRICES ÉLÉMENTAIRES 59

2. La matrice ELi ←Li +λLj est la matrice obtenue en ajoutant λ fois la

j-ème ligne de In à la i-ème ligne de In .

1 0 0 0
 
−3 1 0 0
EL2 ←L2 −3L1 =
 
 0 0 1 0


0 0 0 1
3. La matrice ELi ↔Lj est la matrice obtenue en permutant les i-ème et
j-ème lignes de In .

1 0 0 0
 
0 0 0 1
EL2 ↔L4 = EL4 ↔L2 =
 
0 0 1 0


0 1 0 0
Les opérations élémentaires sur les lignes sont réversibles, ce qui entraîne
l’inversibilité des matrices élémentaires.

Le résultat de la multiplication d’un matrice élémentaire E par A est la

matrice obtenue en effectuant l’opération élémentaire correspondante sur A.
Ainsi :
1. La matrice ELi ←λLi × A est la matrice obtenue en multipliant par λ la
i-ème ligne de A.
2. La matrice ELi ←Li +λLj × A est la matrice obtenue en ajoutant λ fois la
j-ème ligne de A à la i-ème ligne de A.
3. La matrice ELi ↔Lj × A est la matrice obtenue en permutant les i-ème
et j-ème lignes de A.
Exemple 102. 1.
     
1 0 0 x1 x2 x3 x1 x2 x3
1 1 1 1 
EL2 ← 1 L2 × A = 0 3 0 ×  y1 y2 y3  =  3 y1 y y
   
3 3 2 3 3
0 0 1 z1 z2 z3 z1 z2 z3
2.
     
1 0 −7 x1 x2 x3 x1 − 7z1 x2 − 7z2 x3 − 7z3
EL1 ←L1 −7L3 ×A = 0 1 0 × y1 y2 y3  =  y1
    
y2 y3  
0 0 1 z1 z2 z3 z1 z2 z3
3.      
1 0 0 x1 x2 x3 x1 x2 x3
EL2 ↔L3 × A = 0 0 1 ×  y1 y2 y3  =  z1 z2 z3 
     

0 1 0 z1 z2 z3 y1 y2 y3

[Link]
 [Link]

60 LEÇON 5. INVERSION DES MATRICES

5.3.4 Équivalence à une matrice échelonnée

Définition 103. Deux matrices A et B sont dites équivalentes par lignes si
l’une peut être obtenue à partir de l’autre par une suite d’opérations élémen-
taires sur les lignes. On note A ∼ B.
Définition 104. Une matrice est échelonnée si :
• le nombre de zéros commençant une ligne croît strictement ligne par
ligne jusqu’à ce qu’il ne reste plus que des zéros.
Elle est échelonnée réduite si en plus :
• le premier coefficient non nul d’une ligne (non nulle) vaut 1 ;
• et c’est le seul élément non nul de sa colonne.
Exemple d’une matrice échelonnée (à gauche) et échelonnée réduite (à
droite) ; les ∗ désignent des coefficients quelconques, les + des coefficients
non nuls :
+ ∗ ∗ ∗ ∗ ∗ ∗ 1 ∗ 0 ∗ ∗
   
0 0
0 0 + ∗ ∗ ∗ ∗ 0 0 1 0 ∗ ∗ 0
  

0 0 0 + ∗ ∗ ∗ 0 0 0 1 ∗ ∗ 0
   
   
 0 0 0 0 0 0 + 0 0 0 0 0 0 1
   
0 0 0 0 0 0 0 0 0 0 0 0 0 0
   

0 0 0 0 0 0 0 0 0 0 0 0 0 0
Théorème 105. Étant donnée une matrice A ∈ Mn,p (R), il existe une unique
matrice échelonnée réduite U obtenue à partir de A par des opérations élé-
mentaires sur les lignes.
Ce théorème permet donc de se ramener par des opérations élémentaires
à des matrices dont la structure est beaucoup plus simple : les matrices
échelonnées réduites.
Exemple 106. Soit  
1 2 3 4
A =  0 2 4 6 .
 

−1 0 1 0
A. Passage à une forme échelonnée.
Première itération de la boucle, étape A.1. Le choix du pivot est tout fait,
on garde a111 = 1.
Première itération de la boucle, étape A.2. On ne fait rien sur la ligne
2 qui contient déjà un zéro en bonne position et on remplace la ligne 3 par
L3 ← L3 + L1 . On obtient
 
1 2 3 4
A ∼ 0 2 4 6 .
 

0 2 4 4

[Link]
 [Link]

5.3. SYSTÈMES LINÉAIRES ET MATRICES ÉLÉMENTAIRES 61

Deuxième itération de la boucle, étape A.1. Le choix du pivot est tout

fait, on garde a222 = 2.
Deuxième itération de la boucle, étape A.2. On remplace la ligne 3 avec
l’opération L3 ← L3 − L2 . On obtient
 
1 2 3 4
A ∼ 0 2 4 6  .
 

0 0 0 −2

Cette matrice est échelonnée.

B. Passage à une forme échelonnée réduite.
1
Étape B.1, homothéties. On multiplie la ligne 2 par 2
et la ligne 3 par
− 12 et l’on obtient
 
1 2 3 4
A ∼ 0 1 2 3 .
 

0 0 0 1

Étape B.2, première itération. On ne touche plus à la ligne 3 et on rem-

place la ligne 2 par L2 ← L2 − 3L3 et L1 ← L1 − 4L3 . On obtient
 
1 2 3 0
A ∼ 0 1 2 0 .
 

0 0 0 1

Étape B.2, deuxième itération. On ne touche plus à la ligne 2 et on rem-

place la ligne 1 par L1 ← L1 − 2L2 . On obtient
 
1 0 −1 0
A∼
0 1 2 0


0 0 0 1

qui est bien échelonnée et réduite.

Définition 107. Le rang d’une matrice A, noté rk A, est le nombre de pivots

dans la matrice échelonnée réduite U équivalente par lignes à A.

Par exemple, la matrice de l’exemple 106 a rang 3 car elle est équivalente
par lignes à la matrice échelonnée réduite

−1

1 0 0
0 1 2 0 ,
 

0 0 0 1

[Link]
 [Link]

62 LEÇON 5. INVERSION DES MATRICES

qui a 3 pivots. La matrice

 
1 0 −1 0
0 0 0 1 ,
 

0 0 0 0

a rang 2, car elle est échelonnée réduite et a deux pivots.

Proposition 108. Le rang d’une matrice A est inférieur ou égal au plus
petit entre le nombre de lignes et le nombre de colonnes de A. C’est-à-dire :
si A ∈ Mn,p (R), alors rk A ≤ min{n,p}.

5.3.5 Matrices élémentaires et inverse d’une matrice

Théorème 109. Soit A ∈ Mn (R). La matrice A est inversible si et seulement
si sa forme échelonnée réduite est la matrice identité In .
Remarque 110. Justifions maintenant notre méthode pour calculer A−1 .
Nous partons de (A|I) pour arriver par des opérations élémentaires sur
les lignes à (I|B). Montrons que B = A−1 . Faire une opération élémentaire
signifie multiplier à gauche par une des matrices élémentaires. Notons E le
produit de ces matrices élémentaires. Dire que l’on arrive à la fin du processus
à I signifie EA = I. Donc A−1 = E. Comme on fait les mêmes opérations
sur la partie droite du tableau, alors on obtient EI = B. Donc B = E.
Conséquence : B = A−1 .
Corollaire 111. Les assertions suivantes sont équivalentes :
(i) La matrice A est inversible. ! !
0 0
(ii) Le système linéaire AX = .. a une unique solution X = .. .
. .
0 0
(iii) Pour tout second membre B, le système linéaire AX = B a une
unique solution X.

5.3.6 Mini-exercices
1. Exprimer les systèmes linéaires suivants sous forme matricielle
 et les ré-
( x + z =1
2x + 4y = 7


soudre en inversant la matrice : , −2y + 3z = 1 ,
−2x + 3y = −14 

x+z =1


 x+t=α
 x − 2y = β

.
 x+y+t=2


y+t=4


[Link]
 [Link]

5.4. APPLICATION : MODÈLE INPUT-OUTPUT DE LEONTIEFF 63

2. Écrire les matrices 4 × 4 correspondant aux opérations élémentaires :

L2 ← 13 L2 , L3 ← L3 − 14 L2 , L1 ↔ L4 . Sans calculs, écrire leurs inverses.
Écrire la matrice 4 × 4 de l’opération L1 ← L1 − 2L3 + 3L4 .
3. Écrire les matrices suivantes sous forme échelonnée, puis échelonnée
−2
!
 1 2 3  1 0 2 2 0 0
0 −1 1 0
réduite : 1 4 0
−2 −2 −3
, 1 −1 1 , 1 −2 1 4 .
2 −2 3
−1 2 −1 −2

5.4 Application : Modèle input-output de Leon-

tieff
5.4.1 Données
Considérons une économie pendant une période de référence fixée (un
an, par exemple) et supposons que cette économie se partage en n secteurs
S1 ,S2 , . . . ,Sn , chacun de ceux-ci produisant un seul type de bien. La pro-
duction de chacun de ces secteurs fait l’objet d’une double utilisation : il
s’agit d’une part de satisfaire une demande finale (extérieure aux secteurs de
production) et d’autre part d’alimenter les secteurs de production pour leur
propre activité.
Dénotons par cij la quantité consommée, par le secteur Sj , de la pro-
duction de Si ; dénotons également par xi et bi la production totale de Si
et la demande finale du bien produit par Si . Les nombres cij forment une
matrice carrée C, de taille n, appelée matrice input-output : cij représente,
du point de vue des échanges intersectoriels, l’input du secteur Sj et l’output
du secteur Si .  
c11 c12 . . . c1n
 c21 c22 . . . c2n 
 
C =  ..
 .. . . . 
 . . . .. 

cn1 cn2 . . . cnn
De la même manière, les quantités xi et bi permettent de construire les
vecteurs X et B :    
x1 b1
 x2   b2 
   
X=  .. 
 B=  .. 

 .  .
xn bn
Proposition 112. La quantité finale disponible bi du bien produit par Si est
égale à la production totale de ce bien, diminuée des consommations inter-
sectorielles du bien en question :
bi = xi − (ci1 + · · · + cin ).

[Link]
 [Link]

64 LEÇON 5. INVERSION DES MATRICES

Dans le même ordre d’idées, on peut être amené à considérer la production

totale du secteur Sj , diminuée des diverses consommations de Sj (pour autant
que la même unité soit utilisée pour les diverses productions, par exemple
l’unité monétaire servant à mesurer la valeur de ces productions). Il s’agit là
de la valeur ajoutée du secteur Sj :
vj = xj − (c1j + · · · + cnj ).
Exemple 113. Considérons une économie à trois secteurs : l’agriculture, l’in-
dustrie et les services, pour laquelle les consommations intersectorielles sont
données par  
2 4 3
C= 3 6 1 


1 2 1.
Si les productions des trois secteurs sont respectivement 12, 18 et 9, les
quantités finales disponibles et les valeurs ajoutées se trouvent aisément grâce
au tableau suivant :
agr. ind. serv. x b
agr. 2 4 3 12 3
ind. 3 6 1 18 8
serv. 1 2 1 9 5
x 12 18 9
v 6 6 4
Ainsi, la valeur ajoutée du secteur des services vaut 4, tandis qu’il est possible
de satisfaire à une demande de 8 en produits industriels.

5.4.2 La modélisation
Il est clair que, d’une année à l’autre, les variations de production vont
modifier profondément la matrice input-output. Il serait donc intéressant
d’introduire une notion similaire, mais indépendante de la production. C’est
ainsi que nous considérons le coefficient technique de production aij , égal à
quantité du bien produit par Si que le secteur Sj consomme pour produire
une unité, donc
aij = cij /xj .
Cela définit la matrice des coefficients techniques
 
a11 a12 . . . a1n
 a21 a22 . . . a2n 
 
A =  ..
 .. .. .. 
 . . . . 


an1 an2 . . . ann

[Link]
 [Link]

5.4. APPLICATION : MODÈLE INPUT-OUTPUT DE LEONTIEFF 65

Exemple 114. Pour l’exemple 113, on a par exemple

c12 4
a12 = = = 0,222
x2 18

et, d’une manière générale,

 
0,167 0,222 0,333
0,250 0,333 0,111
A= (5.1)


0,083 0,111 0,111

Proposition 115. Le vecteur de production se décompose en une somme de

deux termes, un relatif à la consommation finale et un relatif aux consom-
mations intersectorielles :
X = B + AX.

Démonstration. En effet, de cij = aij xj on déduit

xi = bi + (ai1 x1 + · · · + ain xn ) = bi + (AX)i ,

qui, mis en forme matricielle, donne la relation annoncée.

5.4.3 Problème de planification

Au lieu de définir comme précédemment la consommation finale dispo-
nible à partir des niveaux de production, envisageons à présent le problème
inverse : étant donnée une demande finale B à satisfaire, quelle production
X les différents secteurs doivent-ils assurer ? Il s’agit donc de résoudre par
rapport à X l’équation
X = B + AX.

Proposition 116. Le vecteur X des productions nécessaires à satisfaire aux

demandes finales B est donné par

X = (In − A)−1 B .

Démonstration. En effet, on a X −AX = B si et seulement si (In −A)X = B,

qui équivaut à la formule donnée.

[Link]
 [Link]

66 LEÇON 5. INVERSION DES MATRICES

Exemple 117. Avec l’exemple 113, évaluons les productions nécessaires à sa-
tisfaire aux demandes finales de 5,9,et 8 dans les trois secteurs. On a
 
0,833 −0,222 −0,333
In − A = −0,250 0,667 −0,111
 

−0,083 −0,111 0,889

 
1,435 0,580 0,611
(In − A)−1 = 0,573 1,763 0,435


0,206 0,275 1,237
   
5 17,282
−1  
X = (In − A) 9 = 22,214
 

8 13,397

[Link] Remarques
A. Il est possible de donner une interprétation concrète des éléments de
la matrice (In − A)−1 . En effet, si on remplace le vecteur B par le k−ième
vecteur unitaire ek = (0, . . . , |{z}
1 , . . . ,0) (demande finale de 1 pour la k-ième
k
production, 0 pour toutes les autres), on a X = (In − A)−1 ek , mais le second
membre n’est autre que la k-ième colonne de (In − A)−1 . Par conséquent, les
diverses colonnes de (In − A)−1 donnent les vecteurs productions nécessaires
pour satisfaire à une demande d’une unité pour les divers biens.

B. De la relation
X = B + AX,
on déduit, en remplaçant successivement X par B + AX,

X = B + A(B + AX)
= B + AB + A2 X
= B + AB + A2 (B + AX)
(5.2)
= B + AB + A2 B + A3 X
...
= (B + AB + A2 B + · · · + Am B) + Am+1 X.

La matrice Am+1 tend vers 0 lorsque m tend vers +∞. En effet,

n n
X 1 X
aij = cij < 1 ∀j,
i=1 xn i=1

[Link]
 [Link]

5.4. APPLICATION : MODÈLE INPUT-OUTPUT DE LEONTIEFF 67

car un secteur doit produire plus qu’il ne consomme. Avec cela, on peut
montrer que limn→+∞ Am = 0. On a par conséquent

X = lim (B + AB + A2 B + · · · + Am B)
m→+∞

et on peut dire que si les secteurs consomment moins qu’ils ne produisent, la

production X nécessaire à satisfaire la demande finale est donnée par

+∞
X = (In + A + A2 + A3 + · · · )B = Am .
X

m=1

Cette formule a une interprétation intéressante : pour satisfaire aux demandes

données par le vecteur B, les secteurs doivent d’abord produire B, puis pour
alimenter les secteurs pour cette productions, ils doivent produire AB, puis
à nouveau A2 B pour alimenter les secteur pour la production AB et ainsi de
suite.

C. Nous avons obtenu d’un côté que X s’exprime en fonction de B comme

X = (In − A)−1 B;

de l’autre côté, le même X dépend de B à travers la relation

X = (In + A + A2 + A3 + · · · )B.

On en déduit

(In + A + A2 + A3 + · · · )B = (In − A)−1 B,

d’où
In + A + A2 + A3 + · · · = (In − A)−1 .
On reconnaît là une généralisation matricielle de la formule bien connue pour
la somme de la série géométrique
1
1 + a + a2 + a3 + · · · = à condition que |a| < 1.
1−a

[Link]
 [Link]

68 LEÇON 5. INVERSION DES MATRICES

[Link]
 [Link]

Troisième partie

Programmation linéaire et
applications

69

[Link]
[Link]

[Link]
 [Link]

Leçon 6

Programmation linéaire :
approche graphique

6.1 Rappels sur les équations de droites

Théorème 118. Dans le plan muni d’un repère, toute droite D a une équa-
tion de la forme :
1. y = mx + p, lorsque D est non parallèle à l’axe des ordonnées.
2. x = k, lorsque D est parallèle à l’axe des ordonnées.

Conclusion : On peut résumer les deux cas, en énonçant que toute droite
D du plan a une équation du type ax + by + c = 0, où a et b ne sont pas
simultanément nuls. Si b = 0, D est parallèle à l’axe des ordonnées et a pour
équation réduite x = −ca
= k, si b 6= 0, D n’est pas parallèle à l’axe des
ordonnées et a une équation réduite de la forme y = −a b
x − ac = mx + p

Définition 119. On appelle équation cartésienne d’une droite D, toute équa-

tion de la forme ax + by + c = 0

En pratique, une droite est entièrement déterminée dès lors que l’on
connaît deux points :
Ainsi : soit (D) la droite passant par A(xA ,yA ) et B(xB ,yB ) : si xA 6= xB , D
n’est pas parallèle à l’axe (Oy) et a donc une équation de la forme y = mx+p
où m = xyBB −y A
−xA
et p est entièrement déterminé en utilisant l’un des deux
points. Il existe également une formule, dès lors que l’on connaît le coefficient
directeur m :
D : y = m(x − xA ) + yA

71

[Link]
 [Link]

72LEÇON 6. PROGRAMMATION LINÉAIRE : APPROCHE GRAPHIQUE

Figure 6.1 – Equation réduite d’une droite

Exemple 120. Déterminer l’équation réduite de la droite (AB) où A(−1; 1)

et B(1; 5)

5−1
Réponse : le coeff. directeur de (AB) est m = 1−(−1)
=2
et p vérifie 1 = (−1) × 2 + p =⇒ p = 3 et (D) à pour équation y = 2x + 3

Remarques : 1. On considère une droite D d’équation réduite y = mx + p

1. D passe par le point O origine du repère si et seulement p = 0

2. Si m = 0, D est parallèle à l’axe des abscisses.

3. Si m > 0, D est « ascendante », et si m < 0, D est « descendante »

2. Parfois il vaut mieux garder une équation cartésienne comme 3x + 7y −

4 = 0, plutôt que de chercher à la mettre sous forme d’équation réduire qui
serait ici : y = −3
7
x + 47

[Link]
 [Link]

6.1. RAPPELS SUR LES ÉQUATIONS DE DROITES 73

Exemple 121. Complétez le tableau suivant en donnant l’expression des droites

A(xA ; yA ) B(xB ; yB ) (D)

1 A(0; 3) B(2; 7)

2 A(10; 50) B(−9; −45)

3 A(1; 7) B(5; 9)

4 A(1; −10) B(−2; 8)

5 A(2; 0) B(−5; 21)

6 A(3; −1) B(8; 1)

7 A(0,01; 5000) B(0,02; 4000)

8 A(20; 27) B(26; 39)

Pour tracer une droite correctement, on cherche toujours deux points à

coordonnées entières afin de les placer sur le repère.
Exemple 122. Donnez deux points à coordonnées entières de chacune des
droites suivantes = :

Fonction M1 ( ; ) M2 ( ; )
1 y = −3x + 4

2 y = −5

3 y = −0,01x + 2,8

4 y = 34 x − 1

−2 2
5 y= 3
x + 3

[Link]
 [Link]

74LEÇON 6. PROGRAMMATION LINÉAIRE : APPROCHE GRAPHIQUE

Exemple 123. Déterminer les équations réduites des droites suivantes :

6.2 Régionnement du plan

Proposition 124. Toute droite D d’équation cartésienne ax + by + c = 0
partage le plan en trois sous-ensembles :
• D = {M (x; y) ∈ R2 /ax + by + c = 0}
• ∆+ = {M (x; y) ∈ R2 /ax + by + c ≥ 0}
• ∆− = {M (x; y) ∈ R2 /ax + by + c ≤ 0}
∆+ et ∆− sont les demi-plans fermés de frontière D.

Pour déterminer l’ensemble-solution d’une inéquation linéaire à deux in-

connues du type ax + by + c ≥ 0 ou ax + by + c ≤ 0, on commence par tracer
la droite-frontière, puis à l’aide d’un point, on détermine par substitution de
quel côté de la frontière sont les couples qui satisfont à l’inéquation. Lorsque
l’inéquation ne comporte qu’une inégalité stricte < ou > la frontière ne fait
pas partie de l’ensemble-solution de l’inéquation.

Exemple 125. Représenter l’ensemble solution de l’inéquation x + 2y ≤ 5.

[Link]
 [Link]

6.2. RÉGIONNEMENT DU PLAN 75

Figure 6.2 – Régionnement du plan

Définition 126. On appelle système de m inéquations linéaires à n incon-

nues un système de la forme :



 a11 x1 + a12 x2 + a13 x3 + ··· + a1n xn ≤ b1
a21 x1 + a22 x2 + a23 x3 + ··· + a2n xn ≤ b2





a31 x1 + a32 x2 + a33 x3 + ··· + a3n xn ≤ b3
 .. .. ..
. . .





am1 x1 + am2 x2 + am3 x3 + · · · + amn xn ≤ bm



où xj est une variable dans la colonne j, aij est le coefficient de la variable

xj sur la ligne i, bi est la constante de la ligne i, n est le nombre d’inconnues
et m est le nombre d’inéquations.
Définition 127. Un n−uplet (k1 ; k2 ; k3 ; ...; kn ) est une solution d’un système
de m inéquations à n inconnues s’il est solution de chacune des inéquations
du système, L’ensemble-solution d’un système d’inéquations linéaires est l’in-
tersection des ensembles-solutions de chacune des inéquations du système.

Exemple 128. Représenter graphiquement l’ensemble solution du système

d’inéquations linéaires suivant :




x1 ≥0
x2 ≥1




x1 +x2 ≤ 9
+3x2 ≤ 24




 2x1
3x1 +2x2 ≤ 24



[Link]
 [Link]

76LEÇON 6. PROGRAMMATION LINÉAIRE : APPROCHE GRAPHIQUE

On prendra comme convention de hachurer (ou colorier) le demi-plan EX-

CLU . ON donnera les coordonnées des sommets du polygone solution.
Réponse :

Figure 6.3 – Exemple

Exemple 129. Représenter graphiquement l’ensemble solution des systèmes

d’inéquations linéaires suivants, puis déterminer les coordonnées des sommets
des polygones.
 
x 1 ≥ 0  1
x ≥0
≥ −1
  

 
x1
x2 ≥0 x2 ≥0

 
 

x2 ≥ −2

 
 

1. x1 +x2 ≤ 12 2. x1 +4x2 ≤ 24 3.
2x 1 +x 2 ≤6
2x1 +x2 ≤ 22 3x1 +x2 ≤ 21

 
 

  
x1 +x2 ≥ 0

 
 
 x +2x2 ≤ 20  x +x2 ≤ 9
 
1 1

[Link]
 [Link]

6.3. UN PREMIER EXEMPLE : MAXIMISATION 77

6.3 Un premier exemple : maximisation

Ce premier exemple sera résolu graphiquement, mais cette méthode n’est
applicable que lorsqu’il n’y a que deux variables.
Exemple 130. Un fabricant produit des tables et des bureaux. Chaque table
nécessite 2,5 heures pour l’assemblage (A), 3 heures pour le polissage (P)
et 1 heure pour la mise en caisse (C). Chaque bureau exige 1 heure pour
l’assemblage, 3 heures pour le polissage et 2 heures pour la mise en caisse.
L’entreprise ne peut disposer, chaque semaine, de plus de 20 heures pour
l’assemblage, de 30 heures pour le polissage, et de 16 heures pour la mise en
caisse. Sa marge de profit est de 3 euros par table et de 4 euros par bureau.
Quelle est la combinaison des produits qui maximisera les profits heb-
domadaires de l’entreprise ? Pour la déterminer, on recourt ci-dessous à la
méthode graphique. Elle se décompose en quatre étapes simples.
1. Formalisation On exprime les données sous forme d’équations ou
d’inégalités. Soient x1 le nombre de tables et x2 le nombre de bureaux
produits. On appelle x1 et x2 les variables de décision ou variables
structurelles. La fonction à optimiser, ou fonction objectif, est le profit
Π = 3x1 + 4x2
avec les contraintes :
• Contrainte sur A : 2,5x1 + x2 ≤ 20
• Contrainte sur P : 3x1 + 3x2 ≤ 30
• Contrainte sur C : x1 + 2x2 ≤ 16
• Contraintes de non-négativité : x1 ≥ 0, x2 ≥ 0.
Les trois premières inégalités sont des contraintes techniques détermi-
nées par l’état de la technologie et la disponibilité des facteurs de pro-
duction ; la quatrième est une contrainte de non-négativité, qui est im-
posée dans tous les problèmes car on ne peut accepter des productions
aux quantités négatives. L’entreprise doit donc résoudre le problème
L’ébénisterie doit donc résoudre le problème :




maximiser 3x1 + 4x2 = Π
sous les contraintes 2,5x1 + x2 ≤ 20




3x1 + 3x2 ≤ 30
x1 + 2x2 ≤ 16





x1 ≥ 0, x2 ≥ 0



2. Région accessible Les inégalités du problème déterminent une ré-

gion du plan, dite région accessible ou acceptable, dénotée F R (en an-
glais, feasible region), qui est la région de toutes les productions pos-
sibles, c-a-d qui respectent toutes les contraintes. Pour dessiner cette

[Link]
 [Link]

78LEÇON 6. PROGRAMMATION LINÉAIRE : APPROCHE GRAPHIQUE

région, on trace les trois droites

Pour A : x2 = −2,5x1 + 20
Pour B : x2 = −x1 + 10
Pour C : x2 = −0,5x1 + 8

plus les deux axes Ox1 et Ox2 .

3. Maintenant que toutes les solutions acceptables au problème ont été

dessinées, il s’agit de trouver la solution optimale, c-a-d celle qui maxi-
mise la fonction objectif. On trace pour cela les « lignes de niveaux »de
la fonction objectif : ici il s’agit de toutes les droites d’isoprofit d’équa-
tions 3x1 + 4x2 = Π, au varier de Π : puisque

3 Π
x2 = − x1 + ,
4 4

ces droites sont toutes parallèles et de pente − 34 . En traçant une série

de droites d’isoprofit telles que les profits soient de plus en plus grands,
on trouve que la droite d’isoprofit correspondant au profit maximal
possible touche la région accessible au point de coordonnées x˜1 = 4 et
x˜2 = 6, qui est à l’intersection des deux droites


3x + 3x2 = 30
1
 x1 + 2x2 = 16

4. Conclusion : la production qui assure le plus grand profit possible est

de 4 tables et 6 chaises. En calculant le profit correspondant, on trouve
Π̃ = 3 × 4 + 4 × 6 = 36 euros.

[Link]
 [Link]

6.3. UN PREMIER EXEMPLE : MAXIMISATION 79

Remarque 131. On peut déjà remarquer deux faits, qui sont vrais en général :
• la solution optimale ne se trouve pas à l’intérieur de la région ac-
cessible, mais à l’intersection de deux contraintes, en un point quali-
fié de point extrême. Dans cet exemple, il y a dix points extrêmes :
(0,20), (0,10), (6,5), (10,0), (0,8), (4,6), (20/3,10/3), (8,0) et (0,0).
Le dernier, qui est l’origine, est l’intersection des contraintes de non-
négativité. Tous ces points sont qualifiés de solutions de base, mais
seuls les cinq derniers sont des solutions acceptables, les autres ne
tombant pas dans la région accessible. Généralement (mais pas tou-
jours) une seule des solutions de base accessibles sera optimale. Ainsi,
si on essaye la solution (20/3,10/3), correspondant à l’intersection des
contraintes A et P, on trouve Π = 3 × 20 3
+ 4 × 103
≈ 33,33, qui est
moins que la valeur optimale Π̃ = 36 trouvée plus haut.
• Parmi les solutions de bases accessibles, la solution trouvée correspond
au point extrême situé le plus loin de l’origine. Ceci est vrai pour tous
les problèmes de maximisation, car si ax1 + bx2 = Π est une droite

[Link]
 [Link]

80LEÇON 6. PROGRAMMATION LINÉAIRE : APPROCHE GRAPHIQUE

d’isoprofit, alors sa distance de l’origine est

Π
√ ,
a2 + b 2
donc si a et b sont constants, cette distance est d’autant plus grande
que Π est plus grand.

6.3.1 Un autre exemple de maximisation

Exemple 132. Une ébénisterie fabrique deux modèles de bureaux : B1 et B2 .
Les temps de découpe, assemblage et finition nécessaires pour chaque modèle
sont indiqués (en heures) dans le tableau suivant, ainsi que le nombre d’heures
disponibles quotidiennement dans chaque atelier.

B1 B2 heures atelier
Découpe 1 2 20
Assemblage 2 1 22
Finition 1 1 12

Un tel tableau se lit de la manière suivante : « Fabriquer un bureau du

modèle B1 nécessite une heure dans l’atelier de découpe, deux heures dans
l’atelier d’assemblage et une heure dans l’atelier de finition ».
L’entreprise vendra 300 e chaque bureau du modèle B1 et 200 e chaque
bureau du modèle B2 . Déterminer le chiffre d’affaire maximum que peut
réaliser l’ébénisterie quotidiennement.
1. On traduit chaque contrainte :
Contrainte de l’atelier de découpe : x1 + 2x2 ≤ 20
Contrainte de l’atelier d’assemblage : 2x1 + x2 ≤ 22
Contrainte de l’atelier de finition : x1 + x2 ≤ 12
À cela s’ajoutent des contraintes de non-négativité puisque le nombre
de bureaux ne peut être négatif, on a donc : x1 ≥ 0 et x2 ≥ 0
Le C.A. z réalisé par l’ébénisterie est alors : z = 300x1 + 200x2
L’ébénisterie doit donc résoudre le problème :




maximiser 300x1 + 200x2 = z
sous les contraintes x1 + 2x2 ≤ 20




2x1 + x2 ≤ 22
x + y ≤ 12





x ≥ 0, y ≥ 0



[Link]
 [Link]

6.3. UN PREMIER EXEMPLE : MAXIMISATION 81

2. On construit le polygone des contraintes : on trace les 5 droites des

contraintes : soit D1 la droite d’équation x + 2y = 20, D1 passe par
(0; 10) et (20; 0). Soit D2 la droite d’équation 2x + y = 22, D2 passe
par (0; 22) et (11; 0). Soit D3 la droite d’équation x + y = 12, D3 passe
par (0; 12) et (12; 0). Ne pas oublier l’axe des abscisses et l’axe des
ordonnées.

Figure 6.4 – Exemple

3. On trace les « lignes de niveaux » du chiffre d’affaire z : ce sont les

droites d’équations 300x + 200y = z : toutes ces droites sont parallèles :
on en trace une sur la figure et on utilise une règle pour simuler les
autres.
Sur la figure, on a tracé la droite D d’équation 300x + 200y = 600 ou
3x + 2y = 6.
4. On cherche parmi toutes les parallèles à D celle qui à la fois à une
intersection non vide avec la zone des contraintes et dont l’ordonnée à
l’origine est la plus grande : ici cette droite passe par le point D(10; 2)
qui correspond à un sommet du polygone de la zone des contraintes.
5. En conclusion, le C.A. sera maximal dès lors que l’ébénisterie produira
10 bureaux du modèle B1 et 2 bureaux du modèle B2 : dans ce cas elle

[Link]
 [Link]

82LEÇON 6. PROGRAMMATION LINÉAIRE : APPROCHE GRAPHIQUE

utilise la capacité maximale d’heures dans les ateliers d’assemblage et

de finition. Enfin son CA sera de 10 × 300 + 2 × 200 = 3 400 e.

On appelle Programme Linéaire le problème mathématique qui consiste

à optimiser (maximiser ou minimiser) une fonction linéaire de plusieurs va-
riables qui sont reliées par des relations linéaires appelées contraintes.
Remarque 133. Il ne faut se tromper sur les mots : ici « programme » ne
signifie pas un programme informatique, mais un « programme de produc-
tion », c-a-d simplement toute production (x1 ,x2 ). Ainsi, les points de la
région accessible donnent les programmes réalisables.

6.4 Un exemple de minimisation

Exemple 134. Un éleveur souhaite que son troupeau consomme la plus faible
ration quotidienne de trois éléments nutritifs A, B et C. Il faut bien sûr
satisfaire les exigences nutritives quotidiennes, qui sont de 14 unités de A,
12 unités de B et 18 unités de C. L’éleveur peut choisir entre deux produits
alimentaires : une unité du produit 1, qui coûte 2 euros, contient deux unités
de A, une unité de B et une unité de C ; une unité du produit 2, qui coûte 4
euros, contient une unités de A, une unité de B et trois unités de C. Quelle est
la combinaison la moins coûteuse de ces deux produits, qui respecte l’exigence
de consommation minimale d’éléments nutritifs ?
Réponse :
1. La fonction objectif à minimiser est

c = 2x1 + 4x2

avec les contraintes :

• Contrainte sur A : 2x1 + x2 ≥ 14
• Contrainte sur P : x1 + x2 ≥ 12
• Contrainte sur C : x1 + 3x2 ≥ 18
• Contraintes de non-négativité : x1 ≥ 0, x2 ≥ 0.
Les contraintes techniques s’écrivent ≥ parce qu’il faut respecter les
exigences de consommation minimales, mais que celles-ci peuvent être
dépassées.
2. Traitons les inégalités comme des équations, exprimons dans chacune x2
en fonction de x1 et traçons-les sur un graphique. Sur le graphique„ aux
inégalités « supérieur ou égal à » correspondront tous les points situés
sur la droite et à droite de celle-ci. La surface ombrée est la région

[Link]
 [Link]

6.4. UN EXEMPLE DE MINIMISATION 83

accessible, qui comprend tous les points respectant les trois contraintes
minimales ainsi que la contrainte de non-négativité.
3. Pour trouver la solution optimale, traçons la fonction objectif sous la
forme d’une série de droites d’isocoût. Nous avons
1 c
x2 = − x1 +
2 4
La droite d’isocoût la plus basse qui touche la région accessible est
tangente à celle-ci au point x˜1 = 9 et x˜2 = 3.
4. ALors le minimum du coût est c̃ = 2 × 9 + 4 × 3 = 30. Tous les autres
programmes réalisables ont un coût strictement supérieur.

Remarque 135. • Dans les cas de minimisation, la solution trouvée cor-

respond au point extrême situé le plus près de l’origine. Ceci est vrai
pour tous les problèmes de minimisation.
• Le point (0,0) continue d’être un point extrême dans un problème de
minimisation, mais en général il n’est pas un point accessible. Cela
nous posera un problème plus tard, lorsqu’il sera question de la mé-
thode du simplexe.

[Link]
 [Link]

84LEÇON 6. PROGRAMMATION LINÉAIRE : APPROCHE GRAPHIQUE

Exemple 136. Dans un gymnase, un groupe d’élèves se charge de la distribu-

tion de pains au chocolat et de croissants lors de la pause de 10 heures. Pour
pouvoir satisfaire la demande, ils doivent disposer au minimum de 108 pains
au chocolat et de 96 croissants. Deux boulangers proposent pour le même
prix :
• l’un le lot A comprenant 12 pains au chocolat et 8 croissants,
• l’autre le lot B composé de 9 pains au chocolat et 12 croissants.
Déterminer le nombre de lots A et le nombre de lots B qui doivent être
achetés pour satisfaire la demande au moindre coût.
Réponse :
On note x1 le nombre de lots A achetés et x2 le nombre de lots B achetés.

 

 minimiser x1 + x2 = c 
 minimiser x1 + x2 = z
sous les contraintes 12x1 + 9x2 ≥ 108  sous les contraintes 4x + 3x ≥ 36

 
1 2
⇐⇒


 8x 1 + 12x 2 ≤ 96 

 2x 1 + 3x 2 ≤ 24
x1 ≥ 0, x2 ≥ 0 x1 ≥ 0, x2 ≥ 0
 

Graphique
Le choix qui minimise la dépense est 6 lots A et 4 lots B : dans ce cas il y
aura exactement le nombre de pains au chocolats et de croissants nécessaires.

6.5 sensibilité à la variation des données, des-

serrement des contraintes
Exemple 137. Un constructeur automobile propose deux modèles sur le mar-
ché français : un modèle A moyen de gamme et un modèle B début de gamme.
Le modèle A est vendu 16 000 e et le modèle B 10 000 e. On suppose
que le marché est tel que toute voiture construite est vendue.
Cependant la construction de chacun de ces modèles nécessite (entre
autres) de l’acier et des heures de travail dont les quantités sont limités.
La fabrication d’une voiture du modèle A nécessite 1 unité de travail et 2
unités d’acier. (on n’a pas besoin de connaître l’expression exacte de chacune
de ces unités)
La fabrication d’une voiture du modèle B nécessite 1 unité de travail et
1 unité d’acier.
Les quantités disponibles pour l’entreprise sont de 400 unités de travail
et 600 unités d’acier.
On se demande donc combien le constructeur doit-il produire de voitures
des modèles A et B, connaissant ces contraintes de production, afin de maxi-
miser son chiffre d’affaire.

[Link]
 [Link]

6.5. SENSIBILITÉ À LA VARIATION DES DONNÉES, DESSERREMENT DES CONTRAINTES85

Notons x1 le nombre de voitures du modèle A, x2 le nombre de voitures

du modèle B, et z le chiffre d’affaire obtenu.
Déterminer graphiquement la répartition qui permet à ’l’entreprise de
maximiser son chiffre d’affaire.

Réponse :
1. Le problème se traduite alors sous la forme :


 maximiser 16000x1 + 10000x2 = Π
sous les contraintes x1 + x2 ≤ 400




 2x 1 + x2 ≤ 600
x1 ≥ 0, x2 ≥ 0


2. On trace les 4droites des contraintes : Soit D1 la droite d’équation x +

y = 400, D1 passe par (0; 400) et (400; 0). Soit D2 la droite d’équation
2x + y = 600, D2 passe par (0; 100) et (300; 0). Ne pas oublier l’axe des
abscisses et l’axe des ordonnées.
On en déduit le polygone des contraintes

[Link]
 [Link]

86LEÇON 6. PROGRAMMATION LINÉAIRE : APPROCHE GRAPHIQUE

3. On »trace « les lignes de niveaux du chiffre d’affaire z : ce sont les

droites d’équations 16000x + 10000y = z
Sur la figure, on a tracé la droite D d’équation 16 000x + 10 000y =
8 000 000 ou 8x + 5y = 4000
4. On cherche parmi toutes les parallèles à D celle qui à la fois à une inter-
section non vide avec la zone des contraintes et dont l’ordonnée à l’ori-
gine est la plus grande : ici cette droite passe par le point Ω(200; 200).
5. En conclusion, le C.A. sera maximal dès lors que l’entreprise produira
200 véhicules de modèle A et 200 véhicules de modèle B : dans ce cas
elle utilise tout son stock d’acier et la capacité maximale d’unités de
travail. Enfin son CA sera de 200 × 16000 + 200 × 10000 = 5 200 000 e.

Figure 6.5 – Exemple 3-A

Remarque : sensibilité à la variation des données

[Link]
 [Link]

6.5. SENSIBILITÉ À LA VARIATION DES DONNÉES, DESSERREMENT DES CONTRAINTES87

• Supposons maintenant que le stock d’acier disponible soit maintenant

de 700 unités au lieu de 600 : l’entreprise doit résoudre le nouveau système :


 maximiser 16000x1 + 10000x2 = Π
sous les contraintes x1 + x2 ≤ 400




 2x1 + x2 ≤ 700
x1 ≥ 0, x2 ≥ 0


La figure ci-dessous permet de résoudre ce système : la droite D1 ne change

pas, D2 est remplacée par D20 : 2x + y = 700. La parallèle à D optimale est
maintenant ∆0 : 8x + 5y = 2900
Le C.A. sera maximal avec une production de 300 véhicules du modèle A
et 100 véhicules du modèle B
Le C.A. maximal est alors 300 × 16000 + 100 × 10000 = 5 800 000 e.
Ainsi, l’augmentation le stock d’acier de 100 unités permet une augmen-
tation du CA de 600 000 e : on dit que le prix marginal de l’unité d’acier est
6 000 e.

Figure 6.6 – Exemple 3-B

[Link]
 [Link]

88LEÇON 6. PROGRAMMATION LINÉAIRE : APPROCHE GRAPHIQUE

• Supposons maintenant que le volume d’unités de travail disponible soit

maintenant de 500 unités au lieu de 400 (le nombre d’unités d’acier restant
à 600) : l’entreprise doit résoudre le nouveau système :


 maximiser 16000x1 + 10000x2 = Π
sous les contraintes x1 + x2 ≤ 500




 2x 1 + x2 ≤ 600
x1 ≥ 0, x2 ≥ 0


Le C.A. sera maximal avec une production de 100 véhicules du modèle A

et 400 véhicules du modèle B
Le C.A. maximal est alors 100 × 16000 + 400 × 10000 = 5 600 000 e.
Ainsi, l’augmentation du volume d’unités de travail de 100 unités permet
une augmentation du CA de 400 000 e : on dit que le prix marginal de l’unité
de travail est 4 000 e.

Figure 6.7 – Exemple 3-C

[Link]
 [Link]

Leçon 7

Programmation linéaire : la
méthode du simplexe

La méthode graphique que nous avons vue dans le chapitre précédent ne

convient que pour des problèmes à deux variables. Elle ne peut donc pas servir
à résoudre des problèmes réels. Mais elle a un grand intérêt pédagogique pour
comprendre la méthode du simplexe que nous présenterons sur un exemple,
ainsi que les théorèmes généraux.

Exemple 138. Soit le problème de maximisation suivant :





maximiser 5x + 3y = Π
sous les contraintes 6x + 2y ≤ 36




2x + 4y ≤ 28
5x + 5y ≤ 40





x ≥ 0, y ≥ 0



Comme il y a deux variables de décision x et y, ce problème peut être résolu

graphiquement, ce que nous faisons d’abord. Après avoir dessiné la région
accessible, on voit que les droites d’isoprofit ont pour équation y = − 53 x + Π3 .
Il s’agit d’une famille de droites de pente m = −5/3. La méthode graphique
montre que l’optimum est Π̃ = 34, atteint au point (x,y) = (5,3).

89

[Link]
 [Link]

90LEÇON 7. PROGRAMMATION LINÉAIRE : LA MÉTHODE DU SIMPLEXE

7.1 Définitions et notations

Le problème général de programmation linéaire consiste en l’optimisation
(maximisation ou minimisation) d’une fonction linéaire de plusieurs variables,
sujette à des contraintes qui peuvent être des équations ou des inéquations
linéaires.

Contraintes Les contraintes se répartissent en deux catégories :

• Celles de type xj ≥ 0 appelées conditions de non-négativité
• toutes les autres, appelées contraintes techniques ou vraies contraintes.

Le variables xj peuvent prendre n’importe quelles valeurs réelles, pourvu

qu’elles vérifient les contraintes. Elles ne prennent donc pas nécessairement
dans la solution optimale des valeurs entières, ce qui est souvent incompatible
avec les phénomènes d’indivisibilité technique et économique : on ne peut
pas construire, par exemple, 0,5 chaises, etc. Pour éviter ces difficultés, on a
mis au point des méthodes de programmation en nombres entiers, qu’on ne
traitera pas ici.

[Link]
 [Link]

7.1. DÉFINITIONS ET NOTATIONS 91

Cela étant, les vraies contraintes peuvent se présenter sous forme d’in-
équations linéaires de sens quelconque (dans le même problème) ≥ ou ≤ ou
d’équations linéaires. Les variables peuvent être positives, négatives ou de
signe quelconque. Enfin la fonction objectif peut être maximisée ou minimi-
sée.

7.1.1 Forme générale, standard, canonique

On peut présenter un problème de PL sous trois formes codifiées : forme
générale, forme standard, forme canonique.

[Link] Forme générale

dans cette formulation, on admet des contraintes sous forme d’équation
et d’inéquation. Toutes les inéquations doivent avoir le même sens (≤ pour
une maximisation et ≥ pour une minimisation), et les variables de décisions
sont soit positives soit de signe quelconque (mais pas seulement négatives).
Un problème de PL en forme générale se présente ainsi :

Forme générale 1. contraintes sous forme d’équation

2. Contraintes sous forme d’inéquations (≤ si pb de max ≥ si pb de min)
3. Variables positives
4. Variables de signe quelconque
Pour mettre un problème de PL en forme générale :
Règle 1. pour obtenir que les inéquations linéaires, vraies contraintes, soient
écrites avec des inégalités de même sens (≤ pour une maximisation
et ≥ pour une minimisation), on multiplie par −1 les deux membres
d’une inégalités dont on veut changer de sens. [Link]. x1 − x2 ≤ 5 devient
−x1 + x2 ≥ −5.
Règle 2. Les variables négatives uj ≤ 0 sont transformées en variables positives
en remplaçant chaque variable négative par son opposée xj = −uj .
Exemple 139. Soit le problème initial




maximiser 4x1 − 3u − 4v = z
sous les contraintes 3x1 + 2u − v = 4




x1 − u + 2v ≥ −2
2x1 + u + v ≤ 8





x1 ≥ 0, u ≤ 0, v de signe quelconque



• On remplace la variable u négative par son opposée x2 = −u, x2 ≥ 0.

[Link]
 [Link]

92LEÇON 7. PROGRAMMATION LINÉAIRE : LA MÉTHODE DU SIMPLEXE

• On multiplie par −1 la première inéquation.

D’où la forme générale :




maximiser 4x1 + 3x2 − 4v = z
sous les contraintes 3x1 − 2x2 − v = 4




−x1 − x2 − 2v ≤ 2
2x1 − x2 + v ≤ 8





x1 ,x2 ≥ 0, v de signe quelconque



Exemple 140. Le problème de l’exemple 138





maximiser 5x + 3y = Π
sous les contraintes 6x + 2y ≤ 36




2x + 4y ≤ 28
5x + 5y ≤ 40





x ≥ 0, x ≥ 0



est déjà donné en forme générale.

[Link] Forme standard

Cette forme est celle utilisée par l’algorithme du simplexe, donc elle est
particulièrement importante d’un point de vue pratique. Dans la forme gé-
nérale, les contraintes techniques sont soit des équations soit des inéquations
linéaires. Pour la forme standard, on transforme toutes les inéquations en
équations, et on fait en sorte que toutes les variables soient positives : par
conséquent, le système des contraintes techniques se présente en forme de
système d’équations linéaires à variables positives :

Forme standard 1. contraintes sous forme d’équation

3. Variables positives

Pour mettre un problème de PL en forme standard :

Règle 3. La transformation d’une inéquation en équation se fait en introduisant
dans le premier membre de l’inéquation une variable d’écart positive,
qui comme son nom l’indique représente l’écart entre le niveau de la
contrainte et la valeur du premier membre.
On procède de la façon suivante :
• On transforme une inégalité ≤, [Link]. 5x1 + 3x2 ≤ 30 en équation en
ajoutant une variable d’écart positive s ≥ 0, de façon que 5x1 + 3x2 +
s = 30. Cette variable représente le deficit, égal à la différence entre
5x1 + 3x2 et 30.

[Link]
 [Link]

7.1. DÉFINITIONS ET NOTATIONS 93

• On transforme une inégalité ≥, [Link]. 4x1 + 7x2 ≥ 60 en équation en

soustrayant une variable d’écart positive s ≥ 0, de façon que 4x1 +
7x2 − s = 60. Cette variable représente l’excédent, égal à la différence
entre 4x1 + 7x2 et 60.
Exemple 141. Le problème de l’exemple 138 : on transforme les inégalités
en égalités en introduisant les variables d’écart s1 , s2 , s3 . D’où le nouveau
problème

Maximiser 5x + 3y = Π


 6x + 2y + s1 = 36
2x + 4y + s2 = 28 (7.1)


5x + 5y + s3 = 40
x, y, s1 , s2 ,s3 ≥ 0

On peut aussi exprimer le système des contraintes en forme matricielle :

 
  
x  
6 2 1 0 0 
y
36
2 4 0 1 0 s1  = 28 (7.2)
    

5 5 0 0 1 s2 

40
s3

Remarque 142. • On introduit autant de variables d’écart distinctes

qu’il y a d’inéquations. En effet, une variable d’écart donnée n’ap-
paraît que dans une seule contrainte.
• Le variables d’écart sont affectées d’un coefficient nul dans la fonction
objectif.
Règle 4. Dans la forme standard, toutes les variables sont positives. Lorsqu’une
variable est de signe quelconque, on la remplace par la différence de
deux variables positives : soit v une variable de signe quelconque ; on
pose v = (v1 − v2 ) avec v1 ≥ 0, v2 ≥ 0.
Exemple 143. Le problème de l’exemple 139 était en forme générale :




maximiser 4x1 + 3x2 − 4v = z
sous les contraintes 3x1 − 2x2 − v = 4




−x1 − x2 − 2v ≤ 2
2x1 − x2 + v ≤ 8





x1 ,x2 ≥ 0, v de signe quelconque



On remplace v par (x3 − x4 ), avec x3 ≥ 0, x4 ≥ 0, et on introduit deux

[Link]
 [Link]

94LEÇON 7. PROGRAMMATION LINÉAIRE : LA MÉTHODE DU SIMPLEXE

variables d’écart s1 et s2 dans les deux inéquations :





maximiser 4x1 + 3x2 − 4x3 + 4x4 = z
sous les contraintes 3x1 − 2x2 − x3 + x4 = 4




−x1 − x2 − 2x3 + 2x4 + s1 = 2
2x1 − x2 + x3 − x4 + s2 = 8





x1 , x 2 , x 3 , x 4 , s 1 , s 2 ≥ 0



On peut aussi exprimer le système des contraintes en forme matricielle :

 
x1
x2 
   
3 −2 −1 1 0 0   4
 x3 

−1 −1 −2 2 1 0  =2 (7.3)

x   
 4
2 −1 1 −1 0 1   8
 s1 
s2

[Link] Forme canonique

La forme canonique est surtout utilisée dans le cadre de la théorie de
la dualité, qui sera développée dans les chapitres suivants. Alors que dans
la forme standard, toutes les contraintes techniques sont écrites sous forme
d’équation, elles le sont sous forme d’inéquations dans la forme canonique.
Dans les deux cas, on requiert que les variables soient positives.

Forme canonique 2. contraintes sous forme d’inéquation (≤ si pb de max ≥ si pb de min)

3. Variables positives
Exemple 144. Le problème de l’exemple 138




maximiser 5x + 3y = Π
sous les contraintes 6x + 2y ≤ 36




2x + 4y ≤ 28
5x + 5y ≤ 40





x ≥ 0, y ≥ 0



est déjà donné en forme canonique (et générale).

Règle 5. La transformation d’une équation en inéquation se fait en dédoublant
chaque équation en deux inéquations de sens contraire. [Link] x1 −x2 = 30
équivaut à 
x − x ≤ 30
1 2
x1 − x2 ≥ 30
(7.4)

[Link]
 [Link]

7.2. THÉORÈME FONDAMENTAL DE LA PROGRAMMATION LINÉAIRE95

Exemple 145. Mettre en forme canonique le problème de forme générale :





maximiser 4x1 − 3x2 − 4v = z
sous les contraintes −x1 − x2 − 2v ≤ 2




2x1 − x2 + v ≤ 4
3x1 − 2x2 − v = 4





x1 , x2 ≥ 0, v de signe quelconque



On dédouble la troisième contrainte en deux inéquations :


3x
1 − 2x2 − v ≤ 4
(7.5)
3x1 − 2x2 − v ≥ 4

ou encore (règle 1)

3x
1 − 2x2 − v ≤ 4
(7.6)
−3x1 + 2x2 + v ≤ −4

d’où la forme canonique, après remplacement de v par (x3 − x4 )



 maximiser 4x1 − 3x2 − 4x3 + 4x4 = z
−x1 − x2 − 2x3 + 2x4 ≤ 2




 sous les contraintes
2x1 − x2 + x3 − x4 ≤ 4




 3x1 − 2x2 − x3 + x4 ≤ 4
−3x1 + 2x2 + x3 − x4 ≤ −4





x1 , x 2 , x 3 , x 4 ≥ 0


7.2 Théorème fondamental de la programma-

tion linéaire
La forme standard d’un problème de PL permet de travailler avec des
systèmes d’équations linéaires, desquels on connaît bien la théorie, et pour
lesquels on dispose de puissants outils mathématiques (pivot de Gauss). Soit
par exemple le problème du début du chapitre :




maximiser 5x + 3y = Π
sous les contraintes 6x + 2y ≤ 36




2x + 4y ≤ 28
5x + 5y ≤ 40





x ≥ 0, y ≥ 0



[Link]
 [Link]

96LEÇON 7. PROGRAMMATION LINÉAIRE : LA MÉTHODE DU SIMPLEXE

en forme standard il devient

Maximiser 5x + 3y = Π


 6x + 2y + s1 = 36
2x + 4y + s2 = 28 (7.7)


5x + 5y + s3 = 40
x, y, s1 , s2 ,s3 ≥ 0

Nous avons à faire à un système de m = 3 équations en n = 5 variables.

Comme n > m, ce système est soit incompatible, soit il admet une infinité
de solutions.

Définition 146. On appelle solution réalisable (ou programme réalisable)

tout choix des valeurs des variables vérifiant et les équations des contraintes
et les conditions de non-négativité.

Le théorème du point extrême, que nous avons introduit au chapitre pré-

cédent, affirme que les valeurs optimales de la fonction objectif se situent aux
coins, ou points extrêmes, de la région accessible. Quand on travaille avec la
forme standard, on préfère parler de solutions de base du système. Or, le
nombre de solutions de base est fini. En effet,

Théorème 147 (Théorème de la base). Dans un système de m équations et

n variables, avec n > m, une solution dans laquelle au moins n − m variables
sont égales à zéro est une solution de base.

Par conséquent, en posant n − m variables égales à zéro et en résolvant

les m équations pour les m variables restantes, on peut trouver une solution
de base. Le nombre de solutions de base est ainsi au plus égal à
!
n n!
=
m (n − m)! m!

Précisons tout d’abord le vocabulaire :

Définition 148. • On appelle solution réalisable de base toute solution

de base du système des contraintes vérifiant les conditions de non-
négativité (c’est une solution réalisable dans laquelle au moins n − m
variables sont égales à zéro).
• Dans une solution de base, les n − m variables rendues égales à zéro
sont appelées variables hors base ou variables non principales, tandis
que les m variables qui ne sont pas rendues égales à zéro sont qualifiées
de variables de base ou variables principales.

[Link]
 [Link]

7.2. THÉORÈME FONDAMENTAL DE LA PROGRAMMATION LINÉAIRE97

Exemple 149. Dans l’exemple de tout à l’heure, on peut choisir comme va-
riables de base s1 , s2 , s3 . Alors


 s1 = 36 −6x − 2y
s2 = 28 −2x − 4y
s3 = 40 −5x − 5y



Les variables x et y sont hors base : si on les rend égales à zéro, on trouve
la solution de base (x,y,s1 ,s2 ,s3 ) = (0,0,36,28,40). Puisque toutes les valeurs
respectent les conditions de positivité, c’est une solution de base réalisable.
Elle correspond en effet à l’origine (x,y) = (0,0), qui est bien un point extrême
de la région accessible.
Mais on aurait pu choisir d’autres variables de base, [Link]. x, s2 , s3 de base
et y, s1 hors base. En portant au second membre y et s1 et en exprimant les
variables principales en fonctions de y et s1 , on trouve :
1
− 13 y


 x = 6 − s
6 1
1
s2 = 16 + s
3 1
− 10
3
y (7.8)
5
− 10


s3 = 10 + s
6 1 3
y

Cela donne, si on annule les variables non principales y = s1 = 0, une

autre solution de base qui est (x,y,s1 ,s2 ,s3 ) = (6,0,0,16,10). Elle est encore
une solution de base réalisable, et graphiquement elle correspond au point
extrême (x,y) = (6,0).
Remarque 150. On voit ainsi que les variables de base correspondent aux
variables « de pivot » de la méthode de Gauss, tandis que les variables hors
base correspondent aux variables libres.

Théorème 151 (Théorème du point extrême). (i) Si un problème de PL

sous forme standard admet une solution réalisable, alors il admet aussi
une solution réalisable de base.
(ii) Si un problème de PL sous forme standard admet une solution optimale
(finie), alors il admet aussi une solution optimale de base.

Conclusion La portée du théorème du point extrême est essentielle : la

(les) solutions du problème devait être cherchée dans l’infinité des solutions
possibles du système d’équations des contraintes (en forme standard). Grâce
au théorème, elle n’a plus à être recherchée que parmi les solutions de base
n
de ce système, dont le nombre est fini et ≤ m .
D’un point de vue mathématique, le problème est donc résolu : on pourrait
toujours calculer toutes les solutions de base, éliminer celles qui ne sont pas

[Link]
 [Link]

98LEÇON 7. PROGRAMMATION LINÉAIRE : LA MÉTHODE DU SIMPLEXE

réalisables, et finalement trouver celle(s) maximisant la valeur de la fonction

objectif.
Mais ce processus de calcul et de tri serait extrêmement lourd à mettre
en oeuvre pour des valeurs élevées de m et de n, même avec l’aide d’un
puissant ordinateur. La méthode du simplexe permet au contraire d’explo-
rer rapidement l’ensemble des solutions de base pour trouver une solution
optimale.
Le théorème du point extrême a également une portée économique es-
sentielle. Dans toute solution de base, les niveaux de m activités, au plus,
sont positifs. Ceci signifie qu’un fonctionnement optimal du système étudié
implique la mise en oeuvre d’activités en nombre au plus égal à celui des
contraintes. Le théorème fondamental est donc un théorème de spécialisation
des activités.
Remarque 152. Rien n’assure que le problème admet une solution réalisable
(et donc une solution réalisable de base). Il peut être impossible.

7.3 Méthode du simplexe : un exemple en dé-

tail
Sachant que l’optimum de la fonction objectif, s’il existe, se trouve en
(au moins) un point extrême de la région accessible, on pourrait trouver
cet optimum simplement en calculant la valeur de la fonction objectif en
chaque point extrême et choisir la plus grande valeur obtenue. Toutefois,
cette méthode n’est pas faisable en pratique, car le nombre de points extrêmes
devient très élevé et cela conduit à un grand nombre de calcul inutiles.
La méthode du simplexe (Dantzig 1947) réduit considérablement le nombre
d’essais. Elle consiste à :
• déterminer un point extrême accessible.
• cheminer de point extrême en point extrême toujours en améliorant
la valeur de la fonction objectif
• savoir s’arrêter quand le point extrême optimal est atteint.
Reprenons l’exemple 138, et résolvons-le en détail avec la méthode du sim-
plexe. On part du problème en forme canonique




maximiser 5x + 3y = Π
sous les contraintes 6x + 2y ≤ 36




2x + 4y ≤ 28
5x + 5y ≤ 40





x1 ≥ 0, x2 ≥ 0



[Link]
 [Link]

7.3. MÉTHODE DU SIMPLEXE : UN EXEMPLE EN DÉTAIL 99

Pour mettre le programme linéaire en forme standard, on transforme les

inégalités en égalités en introduisant les variables d’écart s1 , s2 , s3 . D’où le
nouveau problème

Maximiser 5x + 3y = Π


 6x + 2y + s1 = 36 (7.9)
2x + 4y + s2 = 28


5x + 5y + s3 = 40

Ceci est un système de 3 équations à 5 inconnues. Pour écrire l’ensemble de

ses solutions, on peut choisir s1 ,s2 ,s3 comme variables principales (variables
de base) et les exprimer en fonction de x et y qui sont hors base ou non
principales (variables libres). On a donc

Maximiser 5x + 3y = Π


 s1 = 36 − 6x −2y (7.10)
s2 = 28 − 2x −4y
= 40 − 5x −5y


s3

Cela donne, si on annule les variables non principales x = y = 0, la première

solution de base accessible qui est (x,y,s1 ,s2 ,s3 ) = (0,0,36,28,40). De plus,
Π(0,0) = 0. Ceci correspond bien à l’origine (0,0), qui est bien un programme
principal réalisable, où Π vaut 0.
Si on passe à un autre programme principal réalisable dans lequel x et y
ne sont plus nuls, on aura augmenté Π et le programme sera meilleur puisqu’il
s’agit d’un problème de maximisation. Dans la méthode du simplexe, on ne
fait varier qu’une seule variable non principale à la fois. On a Π = 5x + 3y :
si on augmente x, Π augmente car 5 > 0 ; de même si on augmente y, Π
augmente car 3 > 0 ; nous choisissons d’augmenter x, car c’est x qui a le plus
grand coefficient positif (et donc Π augmentera davantage).
Maintenant on observe les contraintes : y est fixé à 0, et l’on a, si l’on
augmente x,


 s1 = 36 − 6x −2y donc s1 diminue et s’annule pour x = 36/6 = 6
s2 = 28 − 2x −4y donc s2 diminue et s’annule pour x = 28/2 = 14
= 40 − 5x −5y


s3 donc s3 diminue et s’annule pour x = 40/5 = 8

Comme on doit avoir s1 ,s2 ,s3 ≥ 0, on ne peut augmenter x au-delà de 6.

La méthode du simplexe consiste désormais à introduire x dans l’ensemble
des variables de base, et en faire sortir s1 , qui est la première variable de base
à s’annuler quand x croît. On dit que x est la variable entrante et s1 la variable

[Link]
 [Link]

100LEÇON 7. PROGRAMMATION LINÉAIRE : LA MÉTHODE DU SIMPLEXE

sortante. On substitue x = 6 − 16 s1 − 13 y dans les contraintes et aussi dans

l’expression de Π. On arrive à
5 4
Maximiser 30 − s1 + y = Π
6 3
1
− 13 y

 x
 = 6 − s
6 1 (7.11)
1
s2 = 16 + s
3 1
− 10
3
y
5
− 10


s3 = 10 + s
6 1 3
y

Cela donne, si on annule les variables non principales y = s1 = 0, la deuxième

solution de base accessible qui est (x,y,s1 ,s2 ,s3 ) = (6,0,0,16,10). De plus,
Π = 30. Graphiquement, on s’est déplacé de l’origine (0,0) au point extrême
(6,0) le long de la contrainte donnée par la droite horizontale (car on a
augmenté x seulement). (6,0) est bien un programme principal réalisable, où
Π vaut 30, donc il y a bien eu augmentation.
Nouvelle étape : on part de Π = 30 − 56 s1 + 43 y. On itère le procédé :
• si l’on augmente s1 , Π diminue car −5/6 < 0 ;
• si l’on augmente y, Π augmente, car 4/3 > 0
On choisit d’augmenter y, qui entre dans les variables principales. Jusqu’où
peut-on augmenter y ? On observe les contraintes (rappel : s1 = 0) : si y
augmente
1
− 13 y


 x = 6 − s
6 1
donc x diminue et s’annule pour y = 6/(1/3) = 18
1
s2 = 16 + s
3 1
− 10
3
y donc s2 diminue et s’annule pour x = 16/(10/3) =
5
− 10


s3 = 10 + s
6 1 3
y donc s3 diminue et s’annule pour x = 10/(10/3) =

Donc y peut augmenter jusqu’à 3. Alors s3 sort de la base et y entre dans la

base. Exprimons tout en fonction de s1 ,s3 : en substituant y = 3 + 14 s1 − 10
3
s3
on obtient :
1 2
Maximiser 34 − s1 − s3 = Π
2 5
1 1


 x = 5 − s
4 1
+ 10 s3 (7.12)
1 3
y = 3 + s
4 1
− 10 s3
1
s2 = 6 −


s
2 1
+s3

Cela donne, si on annule les variables non principales s1 = s3 = 0, la troisième

solution de base accessible qui est (x,y,s1 ,s2 ,s3 ) = (5,3,0,6,0). De plus, Π =
34. Graphiquement, on s’est déplacé du point extrême (6,0) au point extrême
(5,3) le long d’une droite, et il y a bien eu augmentation de Π, car maintenant
Π vaut 34.
On itère encore le procédé, mais cette fois Π = 34 − 21 s1 − 25 s3 :
• si l’on augmente s1 , Π diminue car −1/2 < 0 ;

[Link]
 [Link]

7.4. LES TABLEAUX DU SIMPLEXE 101

• si l’on augmente s3 , Π diminue, car −2/5 < 0

Donc on ne peut plus augmenter Π : le maximum de Π réalisable est 34,
atteint par la production réalisable (x,y) = (5,3).

7.4 Les tableaux du simplexe

Les calculs que nous avons décrits ci-dessus peuvent être présentés de
façon plus lisible et plus mécanique avec les tableaux du simplexe.

présentation du tableau Le problème en forme standard

Maximiser 5x + 3y = Π


 6x + 2y + s1 = 36 (7.13)
2x + 4y + s2 = 28


5x + 5y + s3 = 40

se réécrit

Maximiser Π
−Π +5x


 + 3y = 0
6x + 2y + s1 = 36


(7.14)


 2x + 4y + s2 = 28
5x + 5y + s3 = 40


x, y, s1 , s2 , s3 ≥ 0.

Ce système donne le tableau du simplexe numéro 1 :

base 2nd membres −Π x y s1 s2 s3

−Π 0 1 5 3
s1 36 6 2 1
s2 28 2 4 1
s3 40 5 5 1

• la première colonne est pour l’instant libre, elle sera utilisée tout à
l’heure ;
• la deuxième colonne sert à rappeler quelles sont les variables de base à
chaque étape ; leurs valeurs figurent dans la colonne suivante lorsqu’on
annule les variables non principales. On considère −Π comme une
autre variable, et elle est toujours de base.

[Link]
 [Link]

102LEÇON 7. PROGRAMMATION LINÉAIRE : LA MÉTHODE DU SIMPLEXE

Choix du pivot Dans la section précédente, nous avons d’abord choisi de

faire croître une variable non principale : ici, dans la présentation adoptée, et
parce qu’il s’agit d’un problème de maximisation, on choisit la variable qui
présente sur la ligne de −Π le plus grand coefficient positif. Ce coefficient est
5 qui correspond à x. On ajoute à 5 une flèche descendante : nous disposons
ainsi d’une colonne remplaçante. Si on a le choix entre plusieurs variables, on
en choisit une au hasard.
Ensuite, nous avons été amenés à calculer pour quelle valeur de x les
variables principales s1 ,s2 ,s3 s’annulaient. Pour ceci, il suffit de calculer pour
chaque ligne autre que celle de −Π le quotient du second membre par le
coefficient situé dans (la même ligne et dans) la colonne remplaçante. On
appelle v1 ,v2 , . . . ces quotients et on les écrit dans la première colonne à
gauche. On retient le plus petit vi positif (qui existe !), ici v1 = 6. Ce choix
détermine la variable principale qui va sortir de base, ici s1 : on marque ceci
par une flèche sortante sur s1 : nous disposons ainsi d’une ligne remplacée.
Le coefficient situé à l’intersection de la colonne remplaçante et de la ligne
remplacée s’appelle le pivot. On l’entoure d’une case.
vi base 2nd membres −Π x y s1 s2 s3
−Π 0 1 5↓ 3
v1 = 36/6 = 6 ← s1 36 6 2 1
v2 = 28/2 = 14 s2 28 2 4 1
v3 = 40/5 = 8 s3 40 5 5 1

Pivotage Ensuite, nous avons substitué x = 6− 16 s1 − 13 y dans les contraintes

et aussi dans l’expression de Π. Ici, on fait des opérations élémentaires sur
les lignes du tableau : on garde la ligne du pivot et l’on élimine x des autres
lignes, puis on divise la ligne de x par 6 pour avoir un pivot égal à 1. Cela
donne d’abord
vi base 2nd membres −Π x y s1 s2 s3
−Π 0 1 5↓ 3
2 1
6 1 6 6
L1 ← 16 L1
28 2 4 1
40 5 5 1
puis
vi base 2nd membres −Π x y s1 s2 s3
4
−Π -30 1 3
− 56 L0 ← L0 − 5L1
2 1
x 6 1 6 6
10
s2 16 0 3
− 13 1 L2 ← L2 − 2L1
10
s3 10 0 3
- 56 1 L3 ← L3 − 5L1

[Link]
 [Link]

7.4. LES TABLEAUX DU SIMPLEXE 103

Nous sommes arrivés à la deuxième solution de base : ici les variables hors
base sont y et s1 , donc si on les pose égales à 0 on obtient, sur la ligne L0 :
−Π = −30, donc la nouvelle valeur de la fonction objectif est bien 30, et
la solution de base est (x,y,s1 ,s2 ,s3 ) = (6,0,0,16,10) qui correspond au point
(6,0) trouvé tout à l’heure.

Itération Maintenant on itère les opérations de choix du pivot et du pivo-

tage : le plus grand coefficient positif de la ligne de −Π est 4/3, donc y entre
dans la base. En calculant les ratios de déplacement vi on trouve que le plus
petit est v3 = 3.

vi base 2nd membres −Π x y s1 s2 s3

4
−Π -30 1 3
↓ − 56
2 1
v1 = 6/(2/6) = 18 x 6 1 6 6
10
v2 = 16/(10/3) = 4,8 s2 16 0 3
− 13 1
10
v3 = 10/(10/3) = 3 ← s3 10 0 - 56 1
3

Alors s3 sort de la base, et le pivot est 10/3. Le pivotage donne d’abord

vi base 2nd membres −Π x y s1 s2 s3

4
−Π -30 1 3
↓ − 56
2 1
6 1 6 6
10
16 0 3
− 13 1
3 0 1 - 14 3
10
L3 ← 3
L
10 3

puis

vi base 2nd membres −Π x y s1 s2 s3

−Π -34 1 − 12 − 25 L0 ← L0 − 43 L3
1 1
x 5 1 0 4
− 10 L1 ← L1 − 26 L3
1
s2 6 0 0 2
1 -1 L2 ← L2 − 10 L
3 3
y 3 0 1 - 14 3
10

Nous sommes arrivés à la troisième solution de base : ici s1 et s3 sont hors

base, donc si on les annule on obtient x = 5, y = 3 et s2 = 6 ; de plus, la
nouvelle valeur de Π est 34. Comme dans la ligne 0 tous les coefficients sont
négatifs, on ne peut améliorer la valeur de Π, donc l’algorithme du simplexe
s’arrête ici et (5,3) est la solution de base optimale.
Il est d’usage de regrouper les tableaux du simplexe des différentes étapes
dans un seul tableau du simplexe : cela donne dans notre exemple :

[Link]
 [Link]

104LEÇON 7. PROGRAMMATION LINÉAIRE : LA MÉTHODE DU SIMPLEXE

vi base 2nd-m −Π x y s1 s2 s3 opération

−Π 0 1 5↓ 3
v1 = 36/6 = 6 ← s1 36 6 2 1
v2 = 28/2 = 14 s2 28 2 4 1
v3 = 40/5 = 8 s3 40 5 5 1
4
−Π -30 1 3
↓ − 56 L0 ← L0 − 56 L1
2 1
v1 = 6/(2/6) = 18 x 6 1 6 6
L1 ← 16 L1
10
v2 = 16/(10/3) = 4,8 s2 16 0 3
− 13 1 L2 ← L2 − 26 L1
10
v3 = 10/(10/3) = 3 ← s3 10 0 - 56 1 L3 ← L3 − 56 L1
3
−Π -34 1 − 12 − 25 4
L0 ← L0 − 10 L3
1 1 1
x 5 1 0 4
− 10 L1 ← L1 − 10 L3
1
s2 6 0 0 2
1 -1 L2 ← L2 − L3
y 3 0 1 - 14 3
10
3
L3 ← 10 L3

7.5 Un autre exemple

Voici un deuxième exemple résolu avec les tableaux du simplexe. Il s’agit
de l’exemple 130, que nous avons résolu graphiquement dans le chapitre pré-
cédent. Le problème en forme canonique est le suivant :




maximiser 3x1 + 4x2 = Π
sous les contraintes 2,5x1 + x2 ≤ 20




3x1 + 3x2 ≤ 30
x1 + 2x2 ≤ 16





x1 ≥ 0, x2 ≥ 0



On introduit les variables d’écart : on obtient

Maximiser Π
−Π +3x


 + 4y = 0
2,5x + y + s1 = 20


(7.15)


 3x + 3y + s2 = 30
x + 2y + s3 = 16


x, y, s1 , s2 , s3 ≥ 0.

ce qui donne le premier tableau du simplexe :

[Link]
 [Link]

7.5. UN AUTRE EXEMPLE 105

base 2nd-m −Π x y s1 s2 s3
−Π 0 1 3 4
s1 20 2,5 1 1
s2 30 3 3 1
s3 16 1 2 1

Les calculs se poursuivent de tableau en tableau, chacun correspondant à

un sommet de la région accessible. L’optimum est atteint lorsque tous les
coefficients de la ligne 0 sont devenus négatifs.

vi base 2nd-m −Π x y s1 s2 s3 opération

−Π 0 1 3 4↓
v1 = 20/1 = 20 s1 20 2,5 1 1
v2 = 30/3 = 10 s2 30 3 3 1
v3 = 16/2 = 8 ← s3 16 1 2 1
−Π -32 1 1↓ -2 L0 ← L0 − 2L3
v1 = 12/2 = 6 s1 12 2 0 1 − 12 L1 ← L1 − 12 L3
3
v2 = 6/(3/2) = 4 ← s2 6 0 0 1 − 32 L2 ← L2 − 32 L3
2
1 1
v3 = 8/(1/2) = 16 y 8 2
1 0 2
L3 ← 12 L3
−Π -36 1 0 − 23 -1 L0 ← L0 − 23 L2
s1 4 0 1 − 43 3
2
L1 ← L1 − 43 L2
2
x 4 1 0 0 3
-1 L2 ← 23 L2
y 6 0 1 0 − 13 1 L3 ← L3 − 13 L2

En lisant la ligne L0 , on obtient la valeur optimale de Π qui est 36 ; cette

valeur est atteinte par le programme réalisable (x,y) = (4,6), qui est bien
conforme à ce qu’on a trouvé dans le chapitre précédent par voie graphique.

[Link]
 [Link]

106LEÇON 7. PROGRAMMATION LINÉAIRE : LA MÉTHODE DU SIMPLEXE

[Link]
 [Link]

Leçon 8

Programmation linéaire : le
dual

8.1 Un exemple de PL résolu par la méthode

du simplexe : pour réviser !
Avant de commencer la théorie de la dualité, traitons encore un exemple
de problème de PL par la méthode du simplexe. Soit le problème de PL
suivant : 

 maximiser 14x1 + 12x2 + 18x3 = Π
 sous les contraintes 2x1 + x2 + x3 ≤ 2




 x1 + x2 + x3 ≤ 4
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0


• Le problème est en forme générale et canonique (les contraintes sont

toutes des ≤ car il s’agit d’un problème de maximisation, et les va-
riables de décision sont non négatives)
• La fonction objectif est Π = 14x1 + 12x2 + 18x3
• Les variables de décision sont x1 ,x2 ,x3
• Les contraintes techniques sont 2x1 + x2 + x3 ≤ 2 et x1 + x2 + x3 ≤ 4
• les conditions de non-négativité sont x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Pour appliquer la méthode su simplexe, il faut d’abord écrire le problème en
forme standard, en rajoutant les variables d’écart :

Maximiser Π


 −Π +14x1 + 12x2 + 18x3 =0
2x1 + x2 + x3 +s1 =2 (8.1)


x1 + x2 + x3 +s2 = 4
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, s1 ≥ 0, s2 ≥ 0

107

[Link]
 [Link]

108 LEÇON 8. PROGRAMMATION LINÉAIRE : LE DUAL

ce qui donne le premier tableau du simplexe :

base 2nd-m −Π x1 x2 x3 s1 s2
−Π 0 1 14 12 18
s1 2 2 1 1 1
s2 4 1 1 3 1

Maintenant, on applique la méthode : les calculs se poursuivent de tableau en

tableau, chacun correspondant à un sommet de la région accessible. L’opti-
mum est atteint lorsque tous les coefficients de la ligne 0 sont devenus négatifs
(vous êtes fortement invités à refaire les calculs !)

vi base 2nd-m −Π x1 x2 x3 s1 s2 opération

−Π 0 1 14 12 18 ↓ 0 0 L0
v1 = 2/1 = 2 s1 2 2 1 1 1 L1
v2 = 4/3 = 1,33 ← s2 4 1 1 3 1 L2
−Π -24 1 8↓ 6 0 0 -6 L0 − 6L2
5
v1 = 23 / 53 = 2
5
← s1 2
3
2
3
0 1 − 13 L1 − 13 L2
3
v2 = 43 / 13 = 4 x3 4
3
1
3
1
3
1 0 1
3
1
L
3 2
−Π − 136
5
1 14
5
↓ 0 − 24
5
− 22
5
L0 − 24 L
5 1
2
v1 = 25 / 25 = 1 ← x1 2
5
1 0 3
5
− 15 3
L
5 1
5
v2 = 65 / 15 = 6 x3 6
5
0 1
5
1 − 15 2
5
L2 − 15 L1
−Π −30 1 -7 0 0 −9 −3 L0 − 7L1
5 3
x2 1 2
1 0 2
− 12 5
L
2 1
x3 1 − 15 0 1 − 12 1
2
L2 − 12 L1

• On s’arrête car dans la ligne L0 de Π, tous les coefficients sont négatifs.

En effet, cette ligne signifie l’équation :

−30 = −Π − 7x1 − 9s1 − 3s2 ⇐⇒ Π = 30 − 7x1 − 9s1 − 3s2

donc si on augmente la valeur d’une quelconque des variables, la valeur

de Π diminuera.
• La valeur optimale est Π̃ = 30.
• Les variables x1 , s1 , s2 sont hors base, donc à l’optimum elles valent 0
• Les variables x2 , x3 sont de base, donc à l’optimum elles prennent la
valeur de leur second membre : x2 = 1, x3 = 1.
• La solution optimale est donc (x˜1 ,x˜2 ,x˜3 ) = (0,1,1), avec des variables
d’écart (s˜1 ,s˜2 ) = (0,0).

[Link]
 [Link]

8.2. DÉFINITIONS 109

En plus, dans ce chapitre, nous allons voir que :

• 9 est la valeur marginale de la variable d’écart s1 (ou de la première
contrainte du problème), et 3 est la valeur marginale de la variable
d’écart s2 (ou de la deuxième contrainte du problème), cf. §8.5.2
• s˜1 = s˜2 = 0 : à l’optimum, les deux contraintes du problème sont
saturées, cf. §8.5.1

8.2 Définitions
Dans la programmation linéaire, à tout problème linéaire de maximisation
correspond un problème de minimisation, et à tout problème de minimisation
correspond un problème de maximisation. Le problème initial s’appelle pro-
blème primal, tandis que le problème qui lui correspond s’appelle problème
dual.
Au départ, le problème dual est défini à l’aide d’une formulation mathé-
matique ; mais des liens vont apparaître à l’aide de théorèmes de dualité. Et
il arrive qu’un problème de programmation linéaire soit plus facile à résoudre
en se servant du dual que du primal.

8.2.1 Cas où le primal est écrit sous forme canonique

Exemple 153. Soit le problème initial ou primal :




maximiser 3x1 + 4x2 + 2x3 = Π
sous les contraintes 2,5x1 + x2 + 5x3 ≤ 20




3x1 + 3x2 + 2x3 ≤ 30 (8.2)
x1 + 2x2 + 4x3 ≤ 16





x1 ≥ 0, x2 ≥ 0, x3 ≥ 0



Le problème dual correspondant est





minimiser 20y1 + 30y2 + 16y3 = c
sous les contraintes 2,5y1 + 3y2 + y3 ≥ 3




y1 + 3y2 + 2y3 ≥ 4 (8.3)
5y1 + 2y2 + 4y3 ≥ 2





y1 ≥ 0, y2 ≥ 0, y3 ≥ 0



Règles de transformation permettant d’obtenir le dual Lorsqu’on

formule le dual à partir du primal donné en forme canonique (contraintes en
forme d’inégalité et variables de décision positives) :

[Link]
 [Link]

110 LEÇON 8. PROGRAMMATION LINÉAIRE : LE DUAL

1. Le sens de l’optimisation est inversé : la maximisation dans le primal

devient une minimisation dans le dual et inversement.
2. Dans les contraintes techniques, les sens de l’inégalité est inversé (≥
devient ≤ et inversement). Cependant, la condition de non-négativité
reste pour les nouvelles variables de décision.
3. Le dual comporte autant de variables de décision yi qu’il y a de contraintes
dans le primal.
4. Le dual comporte autant de contraintes qu’il y a de variables de décision
xj dans le primal.
5. Les coefficients de la fonction objectif du dual sont les seconds membres
des contraintes du primal.
6. Les seconds membres des contraintes du dual sont les coefficients de la
fonction objectif du primal.
7. Chaque colonne de coefficients dans les contraintes du primal devient
une ligne de coefficients dans les contraintes du dual.
Remarque 154. Pour passer aisément du primal au dual, il suffit d’écrire la
transposée d’une matrice : en effet, si l’on écrit la matrice des coefficients des
contraintes, et on y ajoute une ligne avec les coefficients de la fonction objec-
tif, on obtient une matrice dont la transposée sera la matrice des coefficients
du problème dual. [Link]. le problème de l’exemple précédent donne :
2,5 1 5 20 2,5 3 1 3
   
 3 3 2 30   1 3 2 4 
   
(8.4)
1 2 4 16 5 2 4 2
   
   
3 4 2 Π 20 30 16 c
Exemple 155. Le dual du problème §8.1 début du chapitre est :




minimiser 2y1 + 4y2 = c
sous les contraintes 2y1 + y2 ≥ 14




y1 + y2 ≥ 12
y1 + 3y2 ≥ 18





y1 ≥ 0, y2 ≥ 0.



Exemple 156. Étant donné le problème primal :





maximiser 5x + 3y = Π
sous les contraintes 6x + 2y ≤ 36




5x + 5y ≤ 40
2x + 4y ≤ 28





x1 ≥ 0, x2 ≥ 0



[Link]
 [Link]

8.2. DÉFINITIONS 111

, le problème dual correspondant est :



 minimiser 36y1 + 40y2 + 28y3 = c
sous les contraintes 6y1 + 5y2 + 2y3 ≥ 5




 2y1 + 5y2 + 4y3 ≥ 3
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0


Mini-exercice
1. Écrivez le dual du problème de PL :


 minimiser 20y1 + 30y2 + 16y3 = c
sous les contraintes 2,5y1 + 3y2 + y3 ≥ 3




 y1 + 3y2 + 2y3 ≥ 3
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0


2. Même question avec le problème :





maximiser 10x1 + 13x2 = Π
sous les contraintes 5x1 + 15x2 ≤ 6000




10x1 + 8x2 ≤ 7200
11x1 + 20x2 ≤ 9000





x1 ≥ 0, x2 ≥ 0



On remarque aisément que :

Proposition 157. Le dual du dual est le primal de départ. Autrement dit,

le passage au dual est une opération involutive.

8.2.2 Cas où le primal n’est pas écrit sous forme cano-

nique
Quand le primal n’est pas écrit sous forme canonique, il faut d’abord le
mettre en forme canonique, en utilisant les règles vue en §7.1.1
Exemple 158.




maximiser x1 + x2 + x3 = Π
sous les contraintes 2x1 + 3x2 − x3 ≤ 4




x1 − 2x2 + x3 ≥ 1




 6x2 + 5x3 = 6
x1 ≥ 0, x2 ≥ 0, x3 de signe quelconque



Remarque 159. Ce qu’on vient de remarquer sur cet exemple est général :

[Link]
 [Link]

112 LEÇON 8. PROGRAMMATION LINÉAIRE : LE DUAL

• à toute contrainte représentée par une inéquation correspond une va-

riable duale soumise à une condition de non-négativité, et réciproque-
ment ;
• à toute contrainte représentée par une équation correspond une va-
riable duale de signe quelconque, et réciproquement.

8.3 Théorème fondamental de la dualité

On peut démontrer que :

Théorème 160. (Existence) Étant donnés un problème de programmation

linéaire et son dual, une et une seule des trois affirmations suivantes est
vraie :
• les deux problèmes sont impossibles (contraintes incompatibles) ;
• un problème est impossible, et l’autre a au moins un programme réali-
sable, mais n’admet pas de solution optimale (sa fonction objectif tend
vers l’infini)
• les deux problèmes ont des programmes optimaux (finis).
(Dualité) Si la troisième affirmation est vraie, alors la valeur optimale de
la fonction objectif du primal est égale à la valeur optimale de la
fonction objectif du dual.

Exemple 161. L’exemple du début §8.1 a comme valeur optimale Π̃ = 30.

Son problème dual a été écrit dans l’exemple 155. On remarque que le dual
a 2 variables de décision, donc on peut le résoudre graphiquement :





minimiser 2x + 4y = c
sous les contraintes 2x + y ≥ 14




x + y ≥ 12
x + 3y ≥ 18





x ≥ 0, y ≥ 0.



Le graphique montre que la solution optimale est pour (y˜1 ,y˜2 ) = (9,3), et
la valeur optimale de la fonction objectif est c̃ = 2 × 9 + 4 × 3 = 30. Donc
Π̃ = c̃ = 30, et le théorème est vérifié.

[Link]
 [Link]

8.4. RÉSOLUTION DU PRIMAL PAR L’INTERMÉDIAIRE DU DUAL113

On remarque en passant, que la solution optimale du dual, (y˜1 ,y˜2 ) = (9,3),

apparaît déjà dans le dernier tableau du simplexe du primal :
vi base 2nd-m −Π x1 x2 x3 s1 s2 opération
−Π −30 1 -7 0 0 −9 −3 L0 − 7L1
Ce fait, qui est vrai en général, sera énoncé par la proposition 172

8.4 Résolution du primal par l’intermédiaire

du dual
Les liens qui existent entre le programme primal et son dual sont bien
plus nombreux que le théorème 160. En effet, il y a une relation de com-
plémentarité entre les variables de décision d’un programme et les variables
d’écart de son dual.
Remarque 162 (Notation). Pour bien distinguer les variables du problème
primal et dual, on note :

x1 ,x2 , . . . les variables de décision du primal y1 ,y2 , . . . les variables de décision du dual
s1 ,s2 , . . . les variables d’ecart du primal t1 ,t2 , . . . les variables d’écart du dual
Théorème 163. Soit P un programme primal admettant une solution opti-
male, et soit P 0 le programme dual. Dans la solution optimale accessible :

[Link]
 [Link]

114 LEÇON 8. PROGRAMMATION LINÉAIRE : LE DUAL

• si une variable de décision xi du primal prend une valeur non nulle,

alors la variable d’écart correspondante ti du programme dual à né-
cessairement une valeur optimale égale à zéro.
• Vice-versa, si une variable d’écart du primal si prend (à l’optimum)
une valeur non nulle, alors la variable de décision correspondante yi
du programme dual a nécessairement une valeur optimale égale à zéro.
Grâce au théorème 163, la solution d’un problème fournit aussi la solution
complète de l’autre. Cela a les avantages suivants :
1. En passant par le dual, on peut résoudre les problèmes de minimisation
en termes de maximisation, ce qui est plus facile si on doit se servir de
la méthode du simplexe.
2. Dans les exercices, si le primal a deux contraintes, le dual aura deux
variables de décision, donc il peut être résolu par voie graphique.
Exemple 164. Le problème primal de la semaine dernière


 maximiser 14x1 + 12x2 + 18x3 = Π
sous les contraintes 2x1 + x2 + 3x3 ≤ 2




 x1 + x2 + 3x3 ≤ 4
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0


Pour illustrer le théorème 163 nous allons :

1. d’abord résoudre le primal par la méthode du simplexe et en déduire
une solution du dual ;
2. puis résoudre le dual (graphiquement) et en déduire une solution du
primal.
Nous avons déjà résolu le primal par la méthode du simplexe : le primal en
forme standard s’écrit


 maximiser 14x1 + 12x2 + 18x3 = Π
sous les contraintes 2x1 + x2 + 3x3 + s1 = 2




 x1 + x2 + 3x3 + s2 = 4
x1 , x 2 , x 3 , s 1 , s 2 ≥ 0


Le simplexe donne une valeur optimale Π̃ = 30 et une solution optimale




x˜1 =0

x˜2 =1





x˜3 = 1




s˜1 = 0



s˜2 = 0

[Link]
 [Link]

8.4. RÉSOLUTION DU PRIMAL PAR L’INTERMÉDIAIRE DU DUAL115

Le dual s’écrit :




minimiser 2y1 + 4y2 = c
sous les contraintes 2y1 + y2 ≥ 14




en forme canonique y1 + y2 ≥ 12
y1 + 3y2 ≥ 18





y1 ≥ 0, y2 ≥ 0.






minimiser 2y1 + 4y2 = c
sous les contraintes 2y1 + y2 − t1 = 14




et en forme standard  y1 + y2 − t2 = 12 (8.5)
 

 y1 + 3y2 − t3 = 18
y1 , y2 , t1 , t2 , t3 ≥ 0



Par le théorème 160, le dual a une solution optimale, et sa valeur optimale

est la même, c̃ = 30.
Pour trouver une solution optimale du dual, on applique le théorème 163 :
• parmi les variables de décision du primal, x˜1 = 0 et x˜2 , x˜3 6= 0. Alors,
parmi les variables d’écart du dual, t˜1 6= 0 et t˜2 = t˜3 = 0.
• les variables d’écart s1 et s2 du primal sont nulles à l’optimum, donc
les variables de décision y1 et y2 du dual sont non nulles à l’optimum.
Donc t2 = t˜3 = 0 : on les remplace dans le dual, et on trouve le système
˜
linéaire 
2y1 + y2 − t1 = 14




y1 + y2 = 12 (8.6)


y1 + 3y2 = 18
dont la solution est vite calculée : y1 = 9, y2 = 3, t1 = 7, ce qui concorde
avec la solution graphique.
Le même procédé peut s’appliquer dans l’autre sens, à savoir déterminer
la solution optimale du dual et en déduire la solution optimale du primal : la
solution du dual a été trouvée graphiquement : y1 = 9, y2 = 3. Du problème
en forme standard




minimiser 2y1 + 4y2 = c
sous les contraintes 2y1 + y2 − t1 = 14




y1 + y2 − t2 = 12
y1 + 3y2 − t3 = 18





y1 , y2 , t1 , t2 , t3 ≥ 0



on déduit t1 = 7, t2 = t3 = 0. Appliquons le théorème 163 :

• les variables de décision du dual y1 et y2 sont non nulles à l’optimum,
alors les variables d’écart du primal sont nulles : s1 = s2 = 0.

[Link]
 [Link]

116 LEÇON 8. PROGRAMMATION LINÉAIRE : LE DUAL

• parmi les variables d’écart du dual, t1 6= 0, et t2 = t3 = 0. Alors parmi

les variables de décision du primal, x1 = 0, et x2 ,x3 6= 0.
On remplace s1 = s2 = x1 = 0 dans le système des contraintes, on trouve

x + x3 = 2
2
(8.7)
x2 + 3x3 = 4

dont la solution est bien x˜2 = 1 et x˜3 = 1.

En conclusion, la connaissance de la solution du primal donne la solution
du dual, et inversement.

Un autre exemple Le tout premier exemple de PL, au début du chapitre

7:
Exemple 165. Un fabricant produit des tables et des bureaux. Chaque table
nécessite 2,5 heures pour l’assemblage (A), 3 heures pour le polissage (P)
et 1 heure pour la mise en caisse (C). Chaque bureau exige 1 heure pour
l’assemblage, 3 heures pour le polissage et 2 heures pour la mise en caisse.
L’entreprise ne peut disposer, chaque semaine, de plus de 20 heures pour
l’assemblage, de 30 heures pour le polissage, et de 16 heures pour la mise en
caisse. Sa marge de profit est de 3 euros par table et de 4 euros par bureau.
Quelle est la combinaison des produits qui maximisera les profits hebdo-
madaires de l’entreprise ?
Le problème en forme canonique est le suivant :




maximiser 3x1 + 4x2 = Π
sous les contraintes 2,5x1 + x2 ≤ 20




3x1 + 3x2 ≤ 30
x1 + 2x2 ≤ 16





x1 ≥ 0, x2 ≥ 0



Nous avons résolu ce problème au chapitre 7 par méthode graphique : la

solution est (x˜1 ,x˜2 ) = (4,6) et Π = 36. Puis au chapitre 8 nous avons résolu
ce même problème par la méthode du simplexe : nous avons écrit le problème
en forme standard :
Maximiser Π
−Π +3x


 + 4y = 0
2,5x + y + s1 = 20


(8.8)


 3x + 3y + s2 = 30
x + 2y + s3 = 16


x, y, s1 , s2 , s3 ≥ 0.

[Link]
 [Link]

8.4. RÉSOLUTION DU PRIMAL PAR L’INTERMÉDIAIRE DU DUAL117

Avec la méthode du simplexe (voir fin du chapitre 8) nous avons retrouvé la

solution optimale qui est 


 x˜1 = 4

x˜2 = 6






s˜1 = 4

s˜2 = 0






s˜3 = 0
Avec la solution du primal, nous voulons déduire la solution du dual : le
problème dual s’écrit


 minimiser 20y1 + 30y2 + 16y3 = c
sous les contraintes 2,5y1 + 3y2 + y3 ≥ 3




 y1 + 3y2 + 2y3 ≥ 4
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0


en forme canonique :


 minimiser 20y1 + 30y2 + 16y3 = c
sous les contraintes 2,5y1 + 3y2 + y3 − t1 = 3




 y1 + 3y2 + 2y3 − t2 = 4
y1 , y2 , y3 , t1 , t2 ≥ 0


Appliquons le théorème 163 :

• x˜1 = 4 6= 0 et x˜2 = 6 6= 0 donc t˜1 = t˜2 = 0
• s˜1 = 4 donc y˜1 = 0 ; s˜2 = s˜3 = 0 donc y˜2 et y˜3 sont non nuls.
On remplace t1 = t2 = y1 = 0 dans le système des contraintes du dual, on
trouve 
3y + y = 3
2 3
(8.9)
3y2 + 2y3 = 4

dont la solution est x˜3 = 1 et x˜2 = 23 . La solution optimale du dual est la

solution optimale qui est 


 y˜1 = 0

2
y˜2 = 3






y˜3 = 1
t˜1 = 0






˜

t2 = 0
Encore un fois, remarquons que la solution du dual apparaît dans le dernier
tableau du simplexe du primal (fin chapitre 8), à la ligne de Π.

[Link]
 [Link]

118 LEÇON 8. PROGRAMMATION LINÉAIRE : LE DUAL

8.5 Desserrement des contraintes et Valeurs

marginales
8.5.1 Contraintes saturées
Considérons à nouveau le problème "production de tables et bureaux" de
la section précédente. Le problème primal comporte trois contraintes :
• la contrainte "20 heures d’assemblage"
• la contrainte "30 heures de polissage"
• la contrainte "16 heures de mise en caisse"
Définition 166. Une contrainte est dite saturée si à l’optimum la variable
d’écart correspondante est nulle, c-a-d si cette contrainte est satisfaite avec
une égalité.
Dans notre exemple, à l’optimum
• s1 = 4 : cela signifie que la production optimale n’utilise pas entière-
ment les 20 heures d’assemblage disponibles, mais seulement 20-4=16.
Donc la contrainte des heures d’assemblage n’est pas saturée.
• s2 = s3 = 0 : cela signifie que la production optimale utilise entiè-
rement les 30 heures de polissage et les 16 heures de mise en caisse.
Ces facteurs de productions sont épuisés à l’optimum, et les deux
contraintes sont saturées.
Exemple 167. L’exemple du début du chapitre §8.1 : la solution optimale
étant (x˜1 ,x˜2 ,x˜3 ) = (0,1,1), avec des variables d’écart (s˜1 ,s˜2 ) = (0,0) : cela
signifie que les deux contraintes sont saturées.

8.5.2 Valeurs marginales

Toujours dans l’exemple tables-bureaux :
Exemple 168. La dernière ligne du simplexe nous dit qu’à l’optimum
2
Π = 36 − 0s1 − s2 − s3 (8.10)
3
On en déduit que :
• si s2 passe de 0 (qui est sa valeur en ce moment car s2 est hors base) à
1, Π diminue de 23 . Vice-versa, si s2 devient −1, alors Π augmente de
2
3
. Traduction concrète : si l’on desserre la contrainte « 30 heures de
polissage », en ajoutant une heure disponible pour la porter à 31 (par
exemple en agrandissant l’atelier ou en augmentant la main d’oeuvre),
alors le profit maximal Π augmentera de 23 , et il sera 36 + 23 = 36,67.

[Link]
 [Link]

8.6. INTERPRÉTATION DE LA DUALITÉ 119

Définition 169. La valeur marginal (ou prix marginal) d’une contrainte est
l’amélioraton maximale de la valeur de la fonction objectif, par rapport à une
solution optimale, qui résulte d’un desserrement d’une unité de la contrainte.

Cette définition n’est valable que pour les contraintes définies par une
inégalité, auxquelles sont associées des variable d’écart. On parle aussi de la
valeur marginale d’une variable d’écart.
Exemple 170. Ainsi, dans l’exemple précédent,
• la valeur marginale de la contrainte « assemblage » est 0 ; on dit aussi
que la valeur marginale de s1 est 0.
• la valeur marginale de la contrainte « polissage » est 23 . on dit aussi
que la valeur marginale de s2 est 2/3.
• la valeur marginale de la contrainte « mise en caisse » est 1. on dit
aussi que la valeur marginale de s3 est 1.
Remarque 171. Les valeurs marginales des contraintes sont fournies par les
opposés des coefficients de la fonction objectif dans le tableau du simplexe
correspondant à une solution optimale.

Proposition 172. À l’optimum,

1. la valeur absolue d’une variable de décision du dual est égale à celle de
la valeur marginale de la variable d’écart associée du primal.
2. la valeur optimale de la fonction objectif est égale à la somme des pro-
duits des ressources (les seonds membres des contraintes) par leurs va-
leurs marginales.

8.6 Interprétation de la dualité

Les programmes lineaires que nous avons vus ont un sens économique,
tandis que leurs problemes duaux ont été définis à l’aide d’une formulation
mathématique. Cependant, ces problèmes duaux peuvent recevoir une inter-
prétation économique, bien qu’elle ne soit pas toujours simple à exprimer.
Nous allons voir quelques cas classiques :

8.6.1 Production utilisant des ressources données et

maximisant le bénéfice
Par exemple, le problème "tables/bureaux" traité ci-dessus. Dans le pri-
mal, les variables x1 et x2 sont des quantités, des niveaux de production.
Dans le dual, les variables y1 , y2 et y3 seront des prix.

[Link]
 [Link]

120 LEÇON 8. PROGRAMMATION LINÉAIRE : LE DUAL

On peut interpreter le dual de la façon suivante : c’est le problème que se

pose un autre fabricant qui veut louer (s’il s’agit de matériels, ateliers, heures
de travail etc) ou acheter (s’il s’agit de matières premières) les moyens de
production du premier fabricant, de façon à
• minimiser sa dépense c
• désintéresser le premier industriel de toute production.
Dans ce but, le second fabricant offre des prix de location y1 , y2 , y3 (ici
location à l’heure) pour, respectivement, une heure d’assemblage, une heure
de polissage et une heure de mise en caisse, tels que
• sa dépense totale c = 20y1 + 30y2 + 16y3 soit minimale ;
• mais qui puissent être intéressants pour le premier fabricant, le prix
de la location étant au moins égal à son bénefice en cas de production,
ce qui donne


 minimiser 20y1 + 30y2 + 16y3 = c
sous les contraintes 2,5y1 + 3y2 + y3 ≥ 3




 y1 + 3y2 + 2y3 ≥ 4
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0


soit précisément le dual.

8.6.2 Régime alimentaire du moindre coût

Exemple 173. Un éleveur souhaite que son troupeau consomme la plus faible
ration quotidienne de trois éléments nutritifs A, B et C. Il faut bien sûr
satisfaire les exigences nutritives quotidiennes, qui sont de 14 unités de A,
12 unités de B et 18 unités de C. L’éleveur peut choisir entre deux produits
alimentaires : une unité du produit 1, qui coûte 2 euros, contient deux uni-
tés de A, une unité de B et une unité de C ; une unité du produit 2, qui
coûte 4 euros, contient une unités de A, une unité de B et trois unités de C.
Quelle est la combinaison la moins coûteuse de ces deux produits, qui res-
pecte l’exigence de consommation minimale d’éléments nutritifs ? Réponse :
La fonction objectif à minimiser est

c = 2x1 + 4x2

avec les contraintes :

• Contrainte sur A : 2x1 + x2 ≥ 14
• Contrainte sur P : x1 + x2 ≥ 12
• Contrainte sur C : x1 + 3x2 ≥ 18
• Contraintes de non-négativité : x1 ≥ 0, x2 ≥ 0.

[Link]
 [Link]

8.6. INTERPRÉTATION DE LA DUALITÉ 121

Les contraintes techniques s’écrivent ≥ parce qu’il faut respecter les exi-
gences de consommation minimales, mais que celles-ci peuvent être dépassées.
Dans le primal, les variables de décision x1 et x2 sont des quantités. Dans
le dual, les variables y1 , y2 , y3 sont des prix.
Le dual est le problème d’un fabricant de produits de synthèse qui propose
à l’éleveur les éléments nutritifs A, B et C aux prix unitaires y1 , y2 et y3
en quantités correspondant aux besoins minimaux. Ce fabricant cherche à
maximiser son chiffre d’affaires Π = 14y1 +12y2 +18y3 tout en offrant des prix
raisonnables pour l’éleveur, c-a-d que les équivalents nutritifs des produits 1
et 2 ne devront pas coûter plus cher que le prix commercial de ces produits.
Donc 

 maximiser 14y1 + 12y2 + 18y3 = Π
 sous les contraintes 2y1 + y2 + y3 ≤ 2




 y1 + 1y2 + 3y3 ≤ 4
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0


soit précisément le dual.

8.6.3 Lien entre valeurs marginales et problème dual

• Quand une variable d’écart n’est pas nulle à l’optimum (contrainte non
saturée) le desserrement d’une unité de la contrainte n’aura aucune
influence sur la fonction objectif. Dans ce cas, la valeur marginale de
la variable d’écart est nulle.
• Par contre, si une variable d’écart est nulle dans le programme op-
timal, c’est que la contrainte correspondante constitue une goulot
d’étranglement de la production (contrainte non saturée). Dans ce
cas, une desserrement de la contrainte aura un effet bénéfique sur la
fonction économique, et la valeur marginale de la variable d’écart sera
non nulle.

[Link]
 [Link]

122 LEÇON 8. PROGRAMMATION LINÉAIRE : LE DUAL

8.6.4 Production utilisant des ressources données et

maximisant le bénéfice : un autre exemple
Le problème primal Un fabricant de chaînes stéréo en produit trois mo-
dèles : Budget, Mid-range et Splurge. Le bénéfice réalisé sur chacun est res-
pectivement de 15, 20 et 24 euros. Le modèle Budget nécessite trois heures
d’installation électrique et une heure d’enchâssement. Le modèle Mid-range
nécessite une heure d’installation électrique et cinq heures d’enchâssement.
Le modèle Splurge demande trois heures d’installation électrique et deux
heures d’enchâssement.
Le fabricant dispose de 120 heures pour l’installation électrique et de 60
heures pour l’enchâssement.
Quel est le programme de production qui maximise le bénéfice en respec-
tant les contraintes ?

Le problème dual Un deuxième fabricant souhaite louer les moyens de

production du premier fabricant. La question est de savoir quels sont les
meilleurs prix raisonnables, pour une heure d’installation électrique et une
heure d’enchâssement, que le deuxième fabricant peut proposer premier, de
façon à minimiser sa dépense totale et en même temps désintéresser le premier
fabricant de toute production.

8.6.5 Outils informatiques

[Link] Site n. 1

[Link]

[Link] Site n. 2

[Link]

[Link] Wolfram Alpha

[Link]

[Link] Excel

Installer le Solver

[Link]
 [Link]

8.6. INTERPRÉTATION DE LA DUALITÉ 123

8.6.6 Autres problèmes modélisables par la PL

[Link] Une histoire de fromage
Le problème primal Une laiterie s’est spécialisée dans deux fromages. Le
premier est un AOC qui exige plus d’heures de travail et un lait en provenance
d’une région bien précise. Le second demande moins de travail, et peut être
fabriqué avec n’importe quel lait. Par contre sa vente dégage une marge
moindre. La laiterie dispose de 21 000 heures de travail annuel, elle reçoit
4 millions de litres de lait de la zone AOC, et 6 millions de litres d’autres
zones. Le tableau suivant indique les ressources nécessaires pour produire 1
tonne de fromage.

Fromage heures de travail par tonne de fromage litres de lait par tonne de fromage
Fromage 1 (AOC) 30 h 10000 l
Fromage 2 15 h 7500 l

Sachant qu’un kilo du fromage AOC dégage une marge de 3 euros et qu’un
kilo de l’autre fromage seulement 1 euro, quelle production doit fabriquer
cette laiterie pour optimiser ses bénéfices ?

Le problème dual Formulez et résolvez le problème dual.

[Link] Un problème d’électricité

Un revendeur d’électricité a promis à sa clientèle qu’au moins 25% de
son électricité serait d’origine renouvelable. Il a calculé que pour l’année
qui arrive il aura un marché de 18 TWh (térawattheure). Il a aussi pré-
sélectionné trois fournisseurs à qui il va acheter son électricité en gros. Voici
les quantités (en TWh), le taux d’électricité renouvelable et la marge dégagée
(en k euro/TWh) que peuvent lui fournir ces trois producteurs.

Producteur % électricité renouvelable quantité achetable en TWh Marge (Euro / TWh)

Producteur 1 10% 25 900
Producteur 2 46% 6 700
Producteur 3 100% 4 500

Chez quels producteurs et en quelle quantité ce revendeur doit-il acheter

son électricité pour avoir le meilleurs bénéfice possible ?
Formulez et résolvez le problème dual.

[Link]
 [Link]

124 LEÇON 8. PROGRAMMATION LINÉAIRE : LE DUAL

[Link]
 [Link]

Bibliographie

[1] Daniel Fredon, mathématique, économie, gestion, cedic, 1976.

[2] Louis Esch, Mathématique pour économistes et gestionnaires, de boek,
2010.
[3] G. Cullmann, Recherche opérationnelle, théorie et pratique, Masson et
Cie, 1970.
[4] Edward T. Dowling, Mathématiques pour l’économiste, McGraw-Hill,
1995.

125

[Link]