Mathématiques pour la gestion
Le pivot de Gauss
- Présentation du cours
- Le langage des fonctions
- La dérivée, ou la notion de marginal
- Calculer une dérivée
- Variations et extremums
- Optimiser en gestion
- Les fonctions de deux variables
- Optimiser sans contrainte
- Optimiser sous contrainte
- Les systèmes d'équations linéaires
- Les matrices
- Le pivot de Gauss
- Déterminant, inverse et formules de Cramer
Mathématiques pour la gestion
Chapitre 10 : Le pivot de Gauss
La méthode
Le principe en une phrase
Rendre le système trivial avant de le résoudre
Un système comme \left\{\begin{aligned} x + 3y + 2z &= 190\\ -5y - 3z &= -270\\ 11z &= 440 \end{aligned}\right. se résout sans réfléchir : la dernière ligne donne z, la deuxième donne y, la première donne x.
Le pivot de Gauss consiste à ramener tout système à cette forme, par des transformations qui ne changent pas les solutions.
Le principe en une phrase (suite)
Les trois opérations autorisées
Les opérations élémentaires sur les lignes
- Échanger deux lignes.
- Multiplier une ligne par un nombre non nul.
- Ajouter à une ligne un multiple d’une autre ligne.
Pourquoi elles ne changent rien
Chacune est réversible : on peut toujours revenir en arrière par une opération du même type.
Une solution du système de départ est donc solution du système transformé, et réciproquement. On modifie l’écriture, jamais l’ensemble des solutions.
Les trois opérations autorisées (suite)
L’opération interdite
Multiplier une ligne par zéro. Ce n’est pas réversible : on détruit une équation, donc de l’information, et l’on se retrouve avec des solutions qui n’en étaient pas.
La descente
L’objectif : des zéros sous la diagonale
Forme échelonnée
On veut obtenir
\left(\begin{array}{ccc|c} \bullet & \bullet & \bullet & \bullet\\ 0 & \bullet & \bullet & \bullet\\ 0 & 0 & \bullet & \bullet \end{array}\right)
Le premier terme non nul de chaque ligne s’appelle le pivot.
La marche à suivre
- Choisir un pivot en première colonne (si possible un 1, quitte à échanger deux lignes).
- L’utiliser pour annuler tous les termes situés en dessous.
- Recommencer avec la deuxième colonne, en n’utilisant plus que les lignes restantes.
- Continuer jusqu’à la dernière colonne.
La descente, sur l’atelier
Étape 0 — écrire la matrice augmentée
\left(\begin{array}{ccc|c} 2 & 1 & 1 & 110\\ 1 & 3 & 2 & 190\\ 1 & 1 & 3 & 170 \end{array}\right)
Le premier coefficient est un 2. On échange L_1 et L_2 pour obtenir un pivot égal à 1 — les calculs seront tous entiers.
\left(\begin{array}{ccc|c} 1 & 3 & 2 & 190\\ 2 & 1 & 1 & 110\\ 1 & 1 & 3 & 170 \end{array}\right)
Première colonne
Étape 1 — annuler sous le premier pivot
L_2 \leftarrow L_2 - 2L_1 : \big(2-2,\ 1-6,\ 1-4 \mid 110 - 380\big) = \big(0,\ -5,\ -3 \mid -270\big)
L_3 \leftarrow L_3 - L_1 : \big(1-1,\ 1-3,\ 3-2 \mid 170-190\big) = \big(0,\ -2,\ 1 \mid -20\big)
\left(\begin{array}{ccc|c} 1 & 3 & 2 & 190\\ 0 & -5 & -3 & -270\\ 0 & -2 & 1 & -20 \end{array}\right)
Deuxième colonne
Étape 2 — annuler sous le deuxième pivot
Le pivot est -5. Pour éviter les fractions, on emploie la combinaison entière L_3 \leftarrow 5L_3 - 2L_2
\big(0,\ -10 + 10,\ 5 + 6 \mid -100 + 540\big) = \big(0,\ 0,\ 11 \mid 440\big)
\left(\begin{array}{ccc|c} 1 & 3 & 2 & 190\\ 0 & -5 & -3 & -270\\ 0 & 0 & 11 & 440 \end{array}\right)
La forme échelonnée est atteinte.
Deuxième colonne (suite)
Une astuce à connaître
Multiplier la ligne à modifier avant de soustraire — ici 5L_3 - 2L_2 — permet de rester dans les entiers.
C’est autorisé par la deuxième opération élémentaire, et cela supprime la principale source d’erreurs de calcul.
La remontée
Résoudre de bas en haut
Étape 3 — la substitution ascendante
Troisième ligne : 11z = 440 \Longrightarrow z = 40.
Deuxième ligne : -5y - 3(40) = -270 \Longrightarrow -5y = -150 \Longrightarrow y = 30.
Première ligne : x + 3(30) + 2(40) = 190 \Longrightarrow x + 170 = 190 \Longrightarrow x = 20.
\boxed{x = 20, \quad y = 30, \quad z = 40}
La réponse au problème de gestion
L’atelier doit produire 20 articles A, 30 articles B et 40 articles C pour saturer exactement ses trois postes.
La vérification, toujours
Reporter dans le système de départ
2(20) + 30 + 40 = 40 + 70 = 110 \quad \checkmark 20 + 3(30) + 2(40) = 20 + 90 + 80 = 190 \quad \checkmark 20 + 30 + 3(40) = 50 + 120 = 170 \quad \checkmark
Une vérification coûte trente secondes
Elle est toujours possible et toujours concluante : ou bien les trois égalités tombent juste, ou bien il y a une erreur quelque part.
Aucun autre exercice de ce cours ne se contrôle aussi facilement. Il n’y a donc aucune raison de s’en priver.
Les cas particuliers
Ce que la forme échelonnée révèle
Lire le résultat de la descente
| Dernière ligne obtenue | Conclusion |
|---|---|
| \alpha z = \beta avec \alpha \neq 0 | solution unique |
| 0 = \beta avec \beta \neq 0 | aucune solution |
| 0 = 0 | infinité de solutions |
La méthode se conclut elle-même
C’est l’avantage décisif du pivot sur la substitution : il ne faut rien deviner à l’avance.
On applique la descente, et la forme finale annonce d’elle-même dans lequel des trois cas du chapitre 8 on se trouve.
Un système incompatible
Une contrainte de trop
\left(\begin{array}{ccc|c} 1 & 1 & 1 & 100\\ 2 & 2 & 2 & 250\\ 1 & 2 & 3 & 180 \end{array}\right) \ \xrightarrow{\ L_2 - 2L_1\ }\ \left(\begin{array}{ccc|c} 1 & 1 & 1 & 100\\ 0 & 0 & 0 & 50\\ 1 & 2 & 3 & 180 \end{array}\right)
La deuxième ligne se lit 0 = 50 : impossible.
Un système incompatible (suite)
L’interprétation
Les deux premières contraintes portent sur la même combinaison de ressources, mais annoncent deux totaux différents.
Le cahier des charges est contradictoire. Le calcul ne le corrige pas : il le révèle, et c’est déjà un résultat exploitable.
Un système indéterminé
Une contrainte redondante
\left(\begin{array}{ccc|c} 1 & 1 & 1 & 100\\ 2 & 2 & 2 & 200\\ 1 & 2 & 3 & 180 \end{array}\right) \ \xrightarrow{\ L_2 - 2L_1,\ L_3 - L_1\ }\ \left(\begin{array}{ccc|c} 1 & 1 & 1 & 100\\ 0 & 0 & 0 & 0\\ 0 & 1 & 2 & 80 \end{array}\right)
Il ne reste que deux équations utiles pour trois inconnues.
En posant z = t : la troisième ligne donne y = 80 - 2t, puis la première x = 100 - y - z = 20 + t.
(x, y, z) = (20 + t,\ 80 - 2t,\ t)
Un système indéterminé (suite)
La marge de manœuvre
Il existe une infinité de plans admissibles. En gestion, t ne peut pas être quelconque : il faut y \geq 0, donc t \leq 40, et t \geq 0.
Sur l’intervalle [0 ; 40], on choisira le t qui minimise le coût ou maximise la marge — et l’on rejoint alors la programmation linéaire.
Le coût de la méthode
Pourquoi c’est la méthode des logiciels
Un ordre de grandeur
Le pivot de Gauss demande environ \dfrac{n^3}{3} opérations pour n inconnues.
Pour n = 3 : une dizaine d’opérations. Pour n = 100 : environ 330\,000 — l’affaire d’un instant pour un ordinateur.
La comparaison qui compte
La méthode de Cramer, que le chapitre 11 présentera, exige un nombre d’opérations qui croît comme n! — une croissance sans commune mesure.
Pour n = 20, Gauss reste immédiat quand Cramer devient hors de portée de toute machine. Tous les tableurs et tous les logiciels utilisent le pivot de Gauss.
Une précaution numérique
Le choix du pivot
Quand un pivot est très petit, la division par ce pivot amplifie les erreurs d’arrondi.
Les logiciels choisissent donc systématiquement, dans la colonne traitée, le coefficient de plus grande valeur absolue, quitte à échanger deux lignes. C’est ce qu’on appelle le pivot partiel.
À la main, on préfère au contraire un pivot égal à 1 : le critère est la simplicité du calcul, pas la stabilité numérique.
Ce qu’il faut retenir
Le résumé du chapitre
Cinq points
- Trois opérations élémentaires sur les lignes, toutes réversibles, ne changent pas les solutions.
- Descente : obtenir des zéros sous la diagonale. Remontée : lire les inconnues de bas en haut.
- Multiplier avant de soustraire permet de rester dans les entiers.
- La forme échelonnée annonce elle-même le cas : solution unique, aucune, ou une infinité.
- C’est la méthode réellement employée par les logiciels, parce qu’elle est la moins coûteuse.
La suite
Gauss résout un système, une fois. Mais si le second membre change chaque semaine — la demande, les capacités — on aimerait un objet calculé une seule fois et réutilisable.
C’est la matrice inverse, chapitre 11.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)