Niveau : de facile à difficile. Durée estimée : 110 min. 8 exercices avec corrections détaillées.
Rappel des notions clés
Pour résoudre $\max Z = c^\top x$ sous $Ax \le b$, $x \ge 0$ (avec $b \ge 0$), ajoute une variable d'écart par contrainte (ce qui manque pour atteindre l'égalité) : ces écarts forment la base de départ, c'est-à-dire les variables que le tableau calcule, les autres valant $0$. À chaque itération, la variable entrante a le coefficient le plus négatif de la ligne $Z$ ; la sortante donne le plus petit rapport « second membre / coefficient » parmi les coefficients strictement positifs de la colonne entrante (c'est le test du rapport) ; on pivote (on ramène cette colonne à $1$ sur le pivot, $0$ ailleurs) jusqu'à ce que la ligne $Z$ n'ait plus de coefficient négatif.
Exemple : pour $\max Z = 3x_1 + 2x_2$ sous $x_1 + x_2 \le 4$, $x_1 \le 2$ et $x \ge 0$, $x_1$ entre (coefficient $-3$), le plus petit rapport, $2/1$, fait sortir l'écart de $x_1 \le 2$, puis un second pivot donne $x_1 = x_2 = 2$ et $Z = 10$. Le cours d'E. Lancini (Université Dauphine-PSL) écrit cette ligne avec le signe opposé : on y fait entrer un coefficient positif.
Le dual se construit par transposition : une variable $y_i$ par contrainte du primal, une contrainte par variable, $b$ et $c$ échangés. Pour un primal $\max$, $b^\top y$ majore $c^\top x$ dès que $x$ et $y$ sont réalisables, c'est-à-dire respectent toutes leurs contraintes (dualité faible) ; si le primal a un optimum fini, le dual aussi, de même valeur (dualité forte) ; s'il n'est pas borné, le dual n'a aucune solution réalisable.
À l'optimum, une variable non nulle, primale ou duale, impose que sa contrainte associée dans l'autre problème soit saturée, c'est-à-dire vérifiée avec égalité : ce sont les écarts complémentaires. Dans le tableau final, la ligne $Z$ sous les colonnes d'écart donne la solution duale, et $y_i$ est la valeur marginale de la ressource $i$ : le gain d'une unité de plus, tant que la base optimale ne change pas.
Formules à retenir :
- $\max c^\top x,\ Ax \le b,\ x \ge 0 \;\longleftrightarrow\; \min b^\top y,\ A^\top y \ge c,\ y \ge 0$
- $\min c^\top x,\ Ax \ge b,\ x \ge 0 \;\longleftrightarrow\; \max b^\top y,\ A^\top y \le c,\ y \ge 0$
- Dualité forte : $\max c^\top x = \min b^\top y$.
- Écarts complémentaires : $y_i \big(b_i - (Ax)_i\big) = 0$ et $x_j \big((A^\top y)_j - c_j\big) = 0$.
Piège classique : le dual d'une minimisation à contraintes $\ge$ est une maximisation à contraintes $\le$, pas $\ge$. Contrôle : une solution réalisable du dual ne vaut jamais plus qu'une solution réalisable du primal.
Exercices : niveau facile
Exercice 1 : Résous par le simplexe $\max Z = 3x_1 + 5x_2$ sous $x_1 \le 4$, $2x_2 \le 12$, $3x_1 + 2x_2 \le 18$ et $x_1, x_2 \ge 0$, puis donne la valeur des écarts.
Correction :
On ajoute les écarts $s_1, s_2, s_3$ et on pivote tant que la ligne $Z$ a un coefficient négatif.
Itération 1 : $x_2$ entre (coefficient $-5$). Rapports $12/2 = 6$ et $18/2 = 9$, la ligne de $s_1$ ayant un coefficient nul : $s_2$ sort. Itération 2 : $x_1$ entre ($-3$). Rapports $4/1 = 4$ (ligne $s_1$) et $6/3 = 2$ (ligne $s_3$) : $s_3$ sort.
$$\begin{array}{c|ccccc|c} \text{base} & x_1 & x_2 & s_1 & s_2 & s_3 & \text{valeur} \\ \hline s_1 & 0 & 0 & 1 & \tfrac{1}{3} & -\tfrac{1}{3} & 2 \\ x_2 & 0 & 1 & 0 & \tfrac{1}{2} & 0 & 6 \\ x_1 & 1 & 0 & 0 & -\tfrac{1}{3} & \tfrac{1}{3} & 2 \\ \hline Z & 0 & 0 & 0 & \tfrac{3}{2} & 1 & 36 \end{array}$$
Plus aucun coefficient négatif : $x_1 = 2$, $x_2 = 6$ et $Z = 36$, avec $s_1 = 2$ et $s_2 = s_3 = 0$.
Exercice 2 : Écris le dual de $\min C = 4x_1 + 2x_2 + x_3$ sous $x_1 + x_2 + x_3 \ge 10$, $2x_1 - x_2 + 3x_3 \ge 5$ et $x_1, x_2, x_3 \ge 0$. Vérifie que $y = (1, 0)$ est réalisable pour le dual et $x = (0, 0, 10)$ pour le primal. Que peux-tu en conclure ?
Correction :
On transpose et on inverse les sens : les seconds membres passent dans l'objectif, chaque colonne devient une contrainte $\le$.
$\max W = 10y_1 + 5y_2$ sous $y_1 + 2y_2 \le 4$, $y_1 - y_2 \le 2$, $y_1 + 3y_2 \le 1$ et $y_1, y_2 \ge 0$.
Pour $y = (1, 0)$ : $1 \le 4$, $1 \le 2$, $1 \le 1$ et $W = 10$. Pour $x = (0, 0, 10)$ : $10 \ge 10$, $30 \ge 5$ et $C = 10$. Par dualité faible, aucun $C$ réalisable ne descend sous $10$ : $x$ et $y$ sont optimaux, de valeur commune $10$.
L'erreur à éviter : recopier $\ge$ dans le dual, qui n'aurait alors plus de maximum.
Exercice 3 : Résous par le simplexe $\max Z = 2x_1 + x_2$ sous $x_1 + x_2 \le 5$, $x_1 - x_2 \le 3$ et $x_1, x_2 \ge 0$. Garde le tableau final pour l'exercice 4.
Correction :
Simplexe, en surveillant les signes dans le test du rapport.
Itération 1 : $x_1$ entre ($-2$). Rapports $5$ et $3$ : $s_2$ sort. La ligne $Z$ vaut alors $(0,\ -3,\ 0,\ 2 \mid 6)$ et la colonne de $x_2$ contient $2$ (ligne $s_1$) et $-1$ (ligne $x_1$).
Itération 2 : $x_2$ entre. Seule la ligne $s_1$ compte, rapport $2/2 = 1$ : $s_1$ sort. Le $-1$ est exclu, car augmenter $x_2$ fait croître $x_1$.
$$\begin{array}{c|cccc|c} \text{base} & x_1 & x_2 & s_1 & s_2 & \text{valeur} \\ \hline x_2 & 0 & 1 & \tfrac{1}{2} & -\tfrac{1}{2} & 1 \\ x_1 & 1 & 0 & \tfrac{1}{2} & \tfrac{1}{2} & 4 \\ \hline Z & 0 & 0 & \tfrac{3}{2} & \tfrac{1}{2} & 9 \end{array}$$
$x_1 = 4$, $x_2 = 1$ et $Z = 9$ ; les deux contraintes sont saturées.
L'erreur à éviter : retenir le rapport $3/(-1) = -3$ comme le plus petit ; pivoter sur ce $-1$ donnerait $x_2 = -3$.
Exercices : niveau moyen
Exercice 4 : Écris le dual de l'exercice 3, résous-le graphiquement et compare avec la ligne $Z$ finale de l'exercice 3.
Correction :
On transpose, puis on évalue l'objectif aux sommets de la région réalisable.
Dual : $\min W = 5y_1 + 3y_2$ sous $y_1 + y_2 \ge 2$, $y_1 - y_2 \ge 1$ et $y_1, y_2 \ge 0$.
La région est non bornée, mais $W \ge 0$ sur elle : le minimum est atteint en un sommet. Les sommets sont $(2, 0)$ et $(3/2, 1/2)$, intersection de $y_1 + y_2 = 2$ et $y_1 - y_2 = 1$ ; $W(2, 0) = 10$ et $W(3/2, 1/2) = 9$.
Minimum $W = 9$ en $y = (3/2, 1/2)$ : la valeur de $Z$, et les coefficients lus sous $s_1$ et $s_2$ dans la ligne $Z$ finale de l'exercice 3.
Exercice 5 : Données fictives. Un kilo d'aliment A coûte 2 euros et contient 1 unité de protéines et 1 de fibres ; un kilo de B coûte 3 euros et contient 1 unité de protéines et 2 de fibres. Un éleveur veut au moins 3 unités de protéines et 4 de fibres, au moindre coût.
a) Écris le programme linéaire. b) Pourquoi le simplexe ne peut-il pas démarrer en $x = 0$ ? c) Écris le dual et interprète-le.
Correction :
a) Avec $x_1$, $x_2$ les masses de A et B en kg : $\min C = 2x_1 + 3x_2$ (en euros) sous $x_1 + x_2 \ge 3$, $x_1 + 2x_2 \ge 4$ et $x_1, x_2 \ge 0$.
b) Une contrainte $\ge$ s'écrit avec une variable d'excédent, ce qui dépasse le minimum : $x_1 + x_2 - e_1 = 3$. En $x = 0$, $e_1 = -3$ : l'origine n'est pas réalisable, donc pas de base de départ. Il faut des variables artificielles, ajoutées pour démarrer, ou passer par le dual.
c) $\max W = 3y_1 + 4y_2$ sous $y_1 + y_2 \le 2$, $y_1 + 2y_2 \le 3$ et $y_1, y_2 \ge 0$. Lecture : un vendeur fixe le prix $y_1$ d'une unité de protéine et $y_2$ d'une unité de fibre, de sorte que le contenu d'un kilo de A ou de B ne coûte pas plus cher que ce kilo, et maximise sa recette.
Exercice 6 : Résous par le simplexe le dual de l'exercice 5. Lis dans le tableau final les quantités d'aliments et le coût minimal, puis contrôle-les par les écarts complémentaires.
Correction :
On démarre en $y = 0$ avec les écarts $s_1, s_2$, puis on lit le primal dans la ligne $W$ finale.
Itération 1 : $y_2$ entre ($-4$), rapports $2$ et $3/2$ : $s_2$ sort, et la ligne $W$ vaut $(-1,\ 0,\ 0,\ 2 \mid 6)$. Il reste $-1$ sous $y_1$ : on continue. Itération 2 : $y_1$ entre, rapports $1$ (ligne $s_1$) et $3$ (ligne $y_2$) : $s_1$ sort.
$$\begin{array}{c|cccc|c} \text{base} & y_1 & y_2 & s_1 & s_2 & \text{valeur} \\ \hline y_1 & 1 & 0 & 2 & -1 & 1 \\ y_2 & 0 & 1 & -1 & 1 & 1 \\ \hline W & 0 & 0 & 2 & 1 & 7 \end{array}$$
$y_1 = y_2 = 1$ et $W = 7$ ; sous $s_1$ et $s_2$, la ligne $W$ donne $x_1 = 2$ et $x_2 = 1$. Il faut 2 kg d'aliment A et 1 kg de B, pour un coût minimal de 7 euros. Contrôle : $y_1, y_2 > 0$, donc les deux besoins doivent être atteints tout juste, et c'est le cas : $2 + 1 = 3$ et $2 + 2 \times 1 = 4$.
L'erreur à éviter : s'arrêter à $W = 6$ alors qu'un coefficient négatif reste dans la ligne $W$.
Exercices : niveau difficile
Exercice 7 : Soit $\max Z = x_1 + 2x_2$ sous $-x_1 + x_2 \le 2$, $x_1 - 2x_2 \le 4$ et $x_1, x_2 \ge 0$. a) Montre avec le simplexe que $Z$ n'est pas borné. b) Écris le dual et prouve qu'il n'a aucune solution réalisable.
Correction :
a) On cherche une colonne entrante sans coefficient positif. $x_2$ entre ($-2$) ; le $-2$ de la ligne $s_2$ est exclu, donc $s_1$ sort. On lit alors $x_2 = 2 + x_1 - s_1$, $s_2 = 8 + x_1 - 2s_1$ et $Z = 4 + 3x_1 - 2s_1$.
$x_1$ doit entrer ($-3$), mais aucun coefficient positif ne bloque sa hausse : avec $x_1 = t \ge 0$ et $s_1 = 0$, on a $x_2 = 2 + t$, $s_2 = 8 + t$ et $Z = 4 + 3t$. $Z$ tend vers $+\infty$ : le problème n'est pas borné.
b) Dual : $\min W = 2y_1 + 4y_2$ sous $-y_1 + y_2 \ge 1$, $y_1 - 2y_2 \ge 2$ et $y_1, y_2 \ge 0$. Deux fois la première contrainte plus la seconde donnent $-y_1 \ge 4$, impossible avec $y_1 \ge 0$ : le dual n'a aucune solution réalisable, ce qu'annonçait la dualité faible.
Exercice 8 : Données fictives. Un atelier fabrique trois produits, en quantités $x_1, x_2, x_3 \ge 0$, et maximise sa marge $Z = 5x_1 + 4x_2 + 3x_3$ en centaines d'euros, sous trois contraintes de ressources en heures : $2x_1 + 3x_2 + x_3 \le 5$, $4x_1 + x_2 + 2x_3 \le 11$ et $3x_1 + 2x_2 + 2x_3 \le 8$.
a) Résous par le simplexe. b) Donne la solution du dual et contrôle-la par les écarts complémentaires. c) Une heure de plus de ressource 2 est-elle utile ? Un quart d'heure de plus de ressource 1, vendu 50 euros, est-il rentable ?
Correction :
a) Deux pivots suffisent. $x_1$ entre ($-5$), rapports $2{,}5$, $2{,}75$ et $8/3 \approx 2{,}67$ : $s_1$ sort, et la ligne $Z$ vaut $(0,\ \tfrac{7}{2},\ -\tfrac{1}{2},\ \tfrac{5}{2},\ 0,\ 0 \mid \tfrac{25}{2})$. Puis $x_3$ entre ($-1/2$), rapports $5$ et $1$, la ligne $s_2$ ayant un coefficient nul : $s_3$ sort.
$$\begin{array}{c|cccccc|c} \text{base} & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & \text{valeur} \\ \hline x_1 & 1 & 4 & 0 & 2 & 0 & -1 & 2 \\ x_3 & 0 & -5 & 1 & -3 & 0 & 2 & 1 \\ s_2 & 0 & -5 & 0 & -2 & 1 & 0 & 1 \\ \hline Z & 0 & 1 & 0 & 1 & 0 & 1 & 13 \end{array}$$
$x_1 = 2$, $x_2 = 0$, $x_3 = 1$ et $Z = 13$, soit 1 300 euros de marge, avec $s_2 = 1$ heure inutilisée.
b) Dual : $\min W = 5y_1 + 11y_2 + 8y_3$ sous $2y_1 + 4y_2 + 3y_3 \ge 5$, $3y_1 + y_2 + 2y_3 \ge 4$, $y_1 + 2y_2 + 2y_3 \ge 3$ et $y \ge 0$. La ligne $Z$ sous les écarts donne $y = (1, 0, 1)$ et $W = 13 = Z$. Contrôle : $s_2 > 0$ impose $y_2 = 0$ ; $x_1, x_3 > 0$ saturent les contraintes duales 1 et 3 ($2 + 3 = 5$, $1 + 2 = 3$) ; la contrainte 2 vaut $5 > 4$, d'où $x_2 = 0$.
c) $y_2 = 0$ : une heure de ressource 2 ne rapporte rien, il en reste. $y_1 = 1$ : une heure de ressource 1 vaut 100 euros de marge, tant que la base tient. Pour $\delta$ heures de plus, la colonne de $s_1$ donne $x_1 = 2 + 2\delta$, $x_3 = 1 - 3\delta$ et $s_2 = 1 - 2\delta$, positifs ou nuls pour $\delta \in [-1\,;\,1/3]$. Avec $\delta = 0{,}25$, le gain est de 25 euros : payer 50 euros fait perdre 25 euros, ce n'est pas rentable.
Bilan et conseils
Ce qu'il faut retenir : le test du rapport ne prend que les coefficients strictement positifs, et une colonne entrante sans aucun coefficient positif signale un problème non borné. Un dual inverse le sens de l'optimisation et celui des inégalités ; à l'optimum, sa valeur égale celle du primal et se lit dans la ligne $Z$ finale.
Sources
- E. Lancini, Modélisation en programmation linéaire, cours 6 : la méthode du simplexe, Université Dauphine-PSL.
- E. Lancini, Modélisation en programmation linéaire, cours 7 : intro à la dualité, Université Dauphine-PSL.