L'essentiel à connaître
Pour résoudre un programme linéaire à la main, tu ajoutes à chaque contrainte une variable d'écart, la ressource non utilisée, puis tu fais tourner le simplexe jusqu'à ce qu'aucun coût réduit ne soit positif. Fil rouge du quiz (données fictives) : un atelier fabrique par jour $x_1$ produits P1, à 4 € de marge, et $x_2$ produits P2, à 3 € de marge. Chacun prend 1 h de travail, sur 8 h disponibles ; P1 consomme 2 kg de matière et P2 1 kg, sur 12 kg en stock.
Formule : $\max z = 4x_1 + 3x_2$ sous $x_1 + x_2 \le 8$, $2x_1 + x_2 \le 12$, $x_1 \ge 0$ et $x_2 \ge 0$.
Ainsi $x_1 + x_2 \le 8$ devient $x_1 + x_2 + s_1 = 8$, avec $s_1 \ge 0$. Quand l'origine vérifie toutes les contraintes, le simplexe en part : les variables d'écart sont en base (on les calcule), les autres sont hors base (nulles). La dernière ligne du tableau porte les coûts réduits, le gain sur $z$ d'une unité de chaque variable hors base ; au départ, ce sont les marges. Ce quiz suit le signe du cours cité en sources ; si le tien prend l'autre, inverse les signes.
Étape 1 : la variable de plus grand coût réduit positif entre en base ; s'il n'y en a plus, l'optimum est atteint.
Étape 2 : divise chaque second membre par le coefficient de la colonne entrante, seulement s'il est strictement positif. Le plus petit rapport désigne la ligne qui sort ; son coefficient dans la colonne entrante est le pivot. Si aucun coefficient n'est strictement positif, $z$ croît sans limite : le problème est non borné.
Étape 3 : divise la ligne du pivot par le pivot, puis retranche aux autres lignes, coûts réduits compris, le multiple qui annule la colonne entrante.
Au tableau final, une variable de base vaut le second membre de sa ligne. À deux variables, compare aussi $z$ aux sommets du domaine, où l'optimum est atteint s'il existe ; un point qui viole une contrainte n'est pas un sommet. Pour minimiser $w$, maximise $-w$ puis change le signe du résultat. Une contrainte $\ge$ reçoit une variable d'écart retranchée et une variable artificielle ; la phase 1 minimise la somme des artificielles, et un minimum non nul prouve que le problème est infaisable : aucun point ne vérifie les contraintes.
À retenir : à l'optimum d'une maximisation, l'opposé du coût réduit de $s_i$ est le coût marginal de la ressource $i$ (sa variable duale) : le gain d'une unité de cette ressource en plus. Il ne vaut que tant que la base optimale reste réalisable.
Quiz : teste tes connaissances
Les questions montent en difficulté, et les trois dernières sont les plus piégeuses.
Question 1 : Comment écrire la contrainte de matière $2x_1 + x_2 \le 12$ sous forme d'égalité ?
Réponse : B. $s_2 = 12 - 2x_1 - x_2$ est la matière restante, positive ou nulle. Avec $s_2$ retranché (A), tu écrirais une contrainte $\ge$ : au moins 12 kg consommés.
Question 2 : Le domaine du fil rouge a pour sommets $(0;0)$, $(6;0)$, $(4;4)$ et $(0;8)$. Où $z = 4x_1 + 3x_2$ est-il maximal ?
Réponse : D. $z$ vaut $24$ en $(6;0)$, $28$ en $(4;4)$ et $24$ en $(0;8)$. Choisir $(6;0)$ pour la plus grosse marge de P1 (A) oublie que les deux produits se partagent les ressources.
Question 3 : Ton simplexe ne sait que maximiser. Comment minimiser un coût $w = 2x_1 + 5x_2$ ?
Réponse : A. $\min w = -\max(-w)$. Le piège C oublie ce changement de signe : il annoncerait par exemple un coût de $-10$ au lieu de $10$.
Question 4 : L'atelier veut que la production de P2 ne dépasse pas le double de celle de P1. Quelle contrainte ajoutes-tu ?
Réponse : C. La phrase se traduit par $x_2 \le 2x_1$, soit $-2x_1 + x_2 \le 0$ une fois les variables à gauche. Le piège A revient à $x_1 \le 2x_2$ : le double est passé du mauvais côté.
Question 5 : Au départ, la base est $(s_1;\,s_2)$ et les coûts réduits valent $4$ pour $x_1$ et $3$ pour $x_2$. Quel est le premier pivot ?
Réponse : A. $x_1$ entre ; les rapports valent $8 \div 1 = 8$ pour $s_1$ et $12 \div 2 = 6$ pour $s_2$, donc $s_2$ sort. Le piège B compare 8 et 12 sans les diviser par les coefficients.
Question 6 : Après ce premier pivot, que vaut le coût réduit de $x_2$ ?
Réponse : D. La ligne du pivot divisée par 2 devient $x_1 + \frac{1}{2} x_2 + \frac{1}{2} s_2 = 6$ ; on la retranche 4 fois aux coûts réduits : $3 - 4 \times \frac{1}{2} = 1$. Sans diviser par le pivot, on trouve $3 - 4 \times 1 = -1$ (B) et on croit à tort l'optimum atteint.
Question 7 : Les lignes sont maintenant $x_1 + \frac{1}{2} x_2 + \frac{1}{2} s_2 = 6$ et $\frac{1}{2} x_2 + s_1 - \frac{1}{2} s_2 = 2$, et $x_2$ entre en base. Quelle variable sort, et combien vaut $x_2$ ?
Réponse : B. Les rapports valent $6 \div \frac{1}{2} = 12$ et $2 \div \frac{1}{2} = 4$ : $s_1$ sort et $x_2 = 4$, puis $x_1 = 6 - \frac{1}{2} \times 4 = 4$, le sommet de la question 2. Le piège C multiplie par $\frac{1}{2}$ au lieu de diviser.
Question 8 : Au tableau final, $x_1 = x_2 = 4$ et les coûts réduits de $(x_1;\,x_2;\,s_1;\,s_2)$ valent $(0;\,0;\,-2;\,-1)$. Que valent $s_1$ et $s_2$ ?
Réponse : A. Hors base, $s_1$ et $s_2$ valent 0 : $4 + 4 = 8$ h et $2 \times 4 + 4 = 12$ kg, heures et matière sont épuisées. Le piège B prend les coûts réduits, au signe près, pour des valeurs de variables.
Question 9 : Dans un autre problème à maximiser, $x_2$ a un coût réduit de $3$ et sa colonne contient $-1$ et $0$. Que conclus-tu ?
Réponse : C. Chaque unité de $x_2$ ajoute 3 à $z$, sans aucune ligne pour l'arrêter. Infaisable (B) voudrait dire qu'aucun point ne vérifie les contraintes, or le tableau en fournit un.
Question 10 : Un problème contient $x_1 + x_2 \ge 3$. Avec $e$ variable d'écart et $a$ variable artificielle, que poses-tu pour démarrer ?
Réponse : D. Avec $e$ seule en base, l'origine donnerait $e = -3$, interdit ; $a = 3$ offre un départ, que la phase 1 annule. Sans $e$ (C), il ne resterait que $x_1 + x_2 = 3$.
Question 11 : En phase 1, le minimum de la somme des variables artificielles vaut $2$. Que conclus-tu ?
Réponse : B. Un point qui vérifie toutes les contraintes donnerait une somme nulle : un minimum de 2 prouve qu'il n'y en a aucun. Partir de cette base (A) laisserait des contraintes violées.
Question 12 : D'après le tableau final de la question 8, que devient la marge maximale avec 9 h de travail au lieu de 8 ?
Réponse : C. Le coût marginal d'une heure est l'opposé du coût réduit de $s_1$, soit 2 € : $28 + 2 = 30$ €. Contrôle : $x_1 + x_2 = 9$ et $2x_1 + x_2 = 12$ donnent $(3;6)$, et $12 + 18 = 30$. Le piège A lit $-2$ comme une perte.
Question 13 : La colonne entrante vaut $(-1;\,2;\,3)$ et les seconds membres $(2;\,8;\,15)$. Quelle ligne sort ?
Réponse : D. Le coefficient $-1$ ne limite rien : la variable de base de la ligne 1 croît avec la variable entrante. Restent $8 \div 2 = 4$ et $15 \div 3 = 5$. Pivoter sur $-1$ (A ou B) rendrait la variable entrante égale à $-2$.
Question 14 : Mêmes contraintes que le fil rouge, mais l'objectif devient $z = 5x_1 + 2x_2$. Où est l'optimum ?
Réponse : A. En $(6;0)$, $(4;4)$ et $(0;8)$, $z$ vaut $30$, $28$ et $16$. Rester en $(4;4)$ par réflexe (C) est le piège : l'optimum change de sommet quand l'objectif change.
Question 15 : Retour au fil rouge (marges 4 € et 3 €), avec 14 h de travail au lieu de 8. Que devient la marge maximale ?
Réponse : B. Avec $b_1$ heures, la base finale donne $x_1 = 12 - b_1$ et $x_2 = 2b_1 - 12$ : elle n'est réalisable que pour $6 \le b_1 \le 12$. À 14 h, seule la matière limite : l'optimum passe en $(0;12)$, où $z = 36$. Le piège A applique $28 + 2 \times 6 = 40$ hors de ce domaine.
Sources
Pierre Fouilhoux, cours d'optimisation linéaire, Université Sorbonne Paris Nord, 2020 : algorithme du simplexe, phase 1, dualité et coûts marginaux.