Chapitre 4 · Semestre 5

La dualité et l'analyse de sensibilité

Intelligence Artificielle et Recherche Opérationnelle

Cours Exercices Résumé QCM

Objectifs du chapitre — À la fin de ce chapitre, vous saurez :

écrire le programme dual d'un programme linéaire ;

énoncer les théorèmes de dualité faible et forte et le théorème des écarts complémentaires ;

interpréter les variables duales comme des prix fictifs (valeurs marginales des ressources) ;

lire la solution duale dans le tableau optimal du simplexe ;

calculer les intervalles de stabilité d'un second membre et d'un coefficient de l'objectif.

4.1 Le programme dual

À tout programme linéaire (le primal) est associé un autre programme, le dual, construit avec les mêmes données. Pour un primal de maximisation sous forme canonique :

$$\text{Primal : } \max Z = c^{T} x \;\; \text{s.c.} \;\; Ax \le b,\; x \ge 0 \qquad \text{Dual : } \min W = b^{T} y \;\; \text{s.c.} \;\; A^{T} y \ge c,\; y \ge 0$$

Les règles de passage sont simples :

Primal (max)	Dual (min)
$m$ contraintes $\le$	$m$ variables $y_i \ge 0$
$n$ variables $x_j \ge 0$	$n$ contraintes $\ge$
Coefficients de l'objectif $c_j$	Seconds membres des contraintes
Seconds membres $b_i$	Coefficients de l'objectif
Matrice $A$	Matrice transposée $A^{T}$

Une contrainte d'égalité dans le primal donne une variable duale de signe quelconque ; le dual du dual est le primal.

Fil rouge. Pour l'atelier de meubles de Salé ($\max 300x_1 + 200x_2$ sous menuiserie, finition et bois), on associe $y_1$, $y_2$, $y_3$ aux trois contraintes :

$$\min W = 100\,y_1 + 80\,y_2 + 40\,y_3 \quad \text{s.c.} \quad \begin{cases} 2y_1 + y_2 + y_3 \ge 300 & \text{(table)} \\ y_1 + y_2 \ge 200 & \text{(chaise)} \\ y_1, y_2, y_3 \ge 0 \end{cases}$$

4.2 L'interprétation économique

Imaginons un investisseur qui veut racheter les ressources de l'atelier : il propose un prix $y_1$ par heure de menuiserie, $y_2$ par heure de finition, $y_3$ par plateau de bois. Pour que l'atelier accepte, ces prix doivent rapporter au moins autant que la fabrication : les ressources consommées par une table (2 heures de menuiserie, 1 de finition, 1 plateau) doivent valoir au moins 300 DH, celles d'une chaise au moins 200 DH. L'investisseur minimise le prix total $W$.

Définition — Prix fictif (valeur duale, prix implicite) : valeur $y_i$ d'une unité supplémentaire de la ressource $i$, c'est-à-dire l'augmentation de l'objectif optimal quand $b_i$ augmente d'une unité : $y_i = \partial Z^* / \partial b_i$.

Le prix fictif est le prix maximal que l'entreprise devrait accepter de payer pour une unité de ressource en plus. Il est nul pour une ressource abondante (contrainte non saturée).

4.3 Les théorèmes de dualité

Dualité faible : pour toute solution réalisable $x$ du primal et $y$ du dual, $Z(x) \le W(y)$. Toute solution duale donne une borne supérieure du profit.
Dualité forte : si le primal a une solution optimale, le dual aussi, et $Z^* = W^*$. Si l'un est non borné, l'autre est impossible.
Écarts complémentaires : à l'optimum,
- si une contrainte primale est non saturée, la variable duale associée est nulle : $y_i\,s_i = 0$ ;
- si une variable primale est positive, la contrainte duale associée est saturée : $x_j\,e_j = 0$.

Application au fil rouge. La contrainte de bois n'est pas saturée ($s_3 = 20$) : $y_3 = 0$. Comme $x_1 = 20 > 0$ et $x_2 = 60 > 0$, les deux contraintes duales sont saturées :

$$2y_1 + y_2 = 300 \qquad y_1 + y_2 = 200 \quad \Rightarrow \quad y_1 = 100,\; y_2 = 100$$

$W^* = 100 \times 100 + 80 \times 100 + 0 = 18\,000 = Z^*$ . Une heure de menuiserie ou de finition supplémentaire vaut 100 DH ; un plateau de bois de plus ne vaut rien.

4.4 Lire le dual dans le tableau optimal

Le tableau final du simplexe donne directement la solution duale : les coûts réduits des variables d'écart dans la ligne $Z$ sont les valeurs des variables duales. Dans le tableau 4 du chapitre 3, les coefficients de $s_1$, $s_2$, $s_3$ sont 100, 100 et 0 : ce sont $y_1$, $y_2$, $y_3$. Résoudre le primal, c'est donc aussi résoudre le dual, et inversement. Quand le primal a beaucoup de contraintes et peu de variables, il est souvent plus rapide de résoudre le dual.

4.5 Sensibilité d'un second membre

Le prix fictif n'est valable que dans un certain intervalle : au-delà, la base optimale change. Quand $b_i$ varie de $\Delta$, les variables de base varient de $\Delta$ fois les coefficients de la colonne de $s_i$ dans le tableau optimal. On écrit qu'elles restent positives.

Pour la menuiserie ($b_1 = 100 + \Delta$), la colonne de $s_1$ dans le tableau final donne :

$$x_2 = 60 - \Delta \ge 0 \qquad s_3 = 20 - \Delta \ge 0 \qquad x_1 = 20 + \Delta \ge 0$$

Donc $-20 \le \Delta \le 20$ : entre 80 et 120 heures de menuiserie, chaque heure vaut 100 DH. Au-delà de 120 heures, on bute sur la limite de 40 tables ($s_3 = 0$) : le bois devient rare et la menuiserie perd de sa valeur.

De la même façon, pour la finition ($b_2 = 80 + \Delta$) : $x_2 = 60 + 2\Delta$, $s_3 = 20 + \Delta$, $x_1 = 20 - \Delta$, d'où $b_2 \in [60 ; 100]$.

4.6 Sensibilité d'un coefficient de l'objectif

Quand la marge unitaire d'un produit varie, la solution reste optimale tant que les coûts réduits restent positifs ou nuls. Avec deux variables, cela revient à la condition graphique du chapitre 2 : la pente de l'objectif reste comprise entre celles des contraintes saturées. Pour la table : $c_1 \in [200 ; 400]$ ; pour la chaise : $1 \le 300 / c_2 \le 2$, soit $c_2 \in [150 ; 300]$.

Dans ces intervalles, les quantités optimales ne changent pas ; seule la valeur de $Z$ varie. Les logiciels (solveur d'Excel, rapport de sensibilité) donnent ces intervalles sous les noms « augmentation admissible » et « diminution admissible ».

4.7 Méthode : exploiter la dualité

Écrire le dual (transposer, échanger objectif et seconds membres, inverser le sens des inégalités).
Trouver la solution duale : coûts réduits des variables d'écart dans le tableau optimal, ou écarts complémentaires.
Vérifier $Z^* = W^*$.
Interpréter chaque $y_i$ comme la valeur marginale de la ressource $i$.
Calculer l'intervalle de validité avec la colonne de $s_i$ dans le tableau optimal.
Conclure sur une décision : acheter, louer ou vendre une unité de ressource à un prix donné.

Les pièges à éviter

Oublier de transposer la matrice : la colonne d'une variable primale devient la ligne d'une contrainte duale.
Croire qu'un prix fictif est valable pour n'importe quelle quantité supplémentaire : il ne l'est que dans l'intervalle de stabilité.
Confondre le prix fictif (valeur marginale interne) et le prix d'achat de la ressource sur le marché.
Donner un prix fictif positif à une ressource non saturée.
Lire les variables duales dans la colonne du second membre au lieu de la ligne $Z$.

Exercice 1 — Dual de la fabrique de peinture

On reprend la fabrique de Mohammedia (chapitre 3) : $\max Z = 5x_1 + 4x_2$ sous $6x_1 + 4x_2 \le 24$ (M1) et $x_1 + 2x_2 \le 6$ (M2). Le tableau optimal donne $x_1 = 3$, $x_2 = 1{,}5$, $Z = 21$, avec, dans la ligne $Z$, les coefficients $3/4$ pour $s_1$ et $1/2$ pour $s_2$. La colonne de $s_1$ vaut $(1/4 ; -1/8)$ et celle de $s_2$ vaut $(-1/2 ; 3/4)$ pour les lignes $(x_1 ; x_2)$.

Travail à faire :

Écrivez le programme dual et donnez son interprétation.
Donnez la solution duale et vérifiez les théorèmes de dualité forte et des écarts complémentaires.
Déterminez l'intervalle de stabilité de la disponibilité de M1 et de M2.
Un fournisseur propose 2 tonnes de M2 supplémentaires à 400 DH la tonne. Faut-il accepter ? Quelle sera la nouvelle production ?

Voir le corrigé

1) $\min W = 24\,y_1 + 6\,y_2$ sous $6y_1 + y_2 \ge 5$ (peinture d'extérieur) et $4y_1 + 2y_2 \ge 4$ (peinture d'intérieur), $y_1, y_2 \ge 0$. $y_1$ et $y_2$ sont les valeurs (en milliers de DH par tonne) attribuées à M1 et M2 ; le dual cherche la valorisation minimale des stocks qui « couvre » la marge de chaque produit.

2) $y_1 = 3/4$, $y_2 = 1/2$. $W = 24 \times 0{,}75 + 6 \times 0{,}5 = 18 + 3 = 21 = Z^*$ (dualité forte). Écarts complémentaires : $x_1 > 0$ et $x_2 > 0$, donc les deux contraintes duales doivent être saturées : $6 \times 0{,}75 + 0{,}5 = 5$ et $4 \times 0{,}75 + 2 \times 0{,}5 = 4$ . Les deux matières sont épuisées ($s_1 = s_2 = 0$), leurs prix fictifs peuvent être positifs .

3) M1 ($24 + \Delta$) : $x_1 = 3 + \Delta/4 \ge 0$ et $x_2 = 1{,}5 - \Delta/8 \ge 0$, d'où $-12 \le \Delta \le 12$ : $b_1 \in [\mathbf{12} ; \mathbf{36}]$. M2 ($6 + \Delta$) : $x_1 = 3 - \Delta/2 \ge 0$ et $x_2 = 1{,}5 + 3\Delta/4 \ge 0$, d'où $-2 \le \Delta \le 6$ : $b_2 \in [\mathbf{4} ; \mathbf{12}]$.

4) Une tonne de M2 vaut 500 DH pour la fabrique (prix fictif), plus que les 400 DH demandés, et 8 tonnes restent dans l'intervalle de stabilité : il faut accepter. Gain net : $2 \times (500 - 400) = \mathbf{200}$ DH par jour. Nouvelle production : $x_1 = 3 - 2/2 = \mathbf{2}$ tonnes, $x_2 = 1{,}5 + 3 \times 2/4 = \mathbf{3}$ tonnes. Vérification : M1 $= 12 + 12 = 24$ , M2 $= 2 + 6 = 8$ , $Z = 10 + 12 = 22$, soit + 1 millier de DH avant le coût de 800 DH.

Exercice 2 — Dual d'un problème de ration

On reprend la ration de Béni Mellal (chapitre 2) : $\min Z = 4x_1 + 3x_2$ sous $2x_1 + x_2 \ge 10$ (protéines), $x_1 + x_2 \ge 7$ (énergie), $x_1 + 3x_2 \ge 12$ (minéraux), dont l'optimum est $x_1 = 3$, $x_2 = 4$, $Z = 24$.

Écrivez le dual et interprétez-le.
Calculez la solution duale par les écarts complémentaires.
L'éleveur veut porter l'exigence d'énergie à 8 unités. Estimez le surcoût.

Voir le corrigé

1) $\max W = 10y_1 + 7y_2 + 12y_3$ sous $2y_1 + y_2 + y_3 \le 4$ (aliment 1), $y_1 + y_2 + 3y_3 \le 3$ (aliment 2), $y \ge 0$. Un fabricant de compléments vend les nutriments à l'unité ($y_1$, $y_2$, $y_3$) : il maximise sa recette en restant moins cher que chaque aliment.

2) Minéraux : $3 + 12 = 15 > 12$, contrainte non saturée, donc $y_3 = 0$. $x_1, x_2 > 0$ : contraintes duales saturées, $2y_1 + y_2 = 4$ et $y_1 + y_2 = 3$, d'où $y_1 = \mathbf{1}$, $y_2 = \mathbf{2}$. $W = 10 + 14 = 24 = Z^*$ .

3) Une unité d'énergie en plus coûte $y_2 = 2$ DH (dans l'intervalle de stabilité) : le coût passe à environ 26 DH. Vérification : avec $2x_1 + x_2 = 10$ et $x_1 + x_2 = 8$, on obtient $x_1 = 2$, $x_2 = 6$ (minéraux $2 + 18 = 20 \ge 12$ ), coût $8 + 18 = 26$ .

Exercice 3 — Faut-il payer des heures supplémentaires ?

Dans le problème des coffrets de Tétouan (exercice 2 du chapitre 3), le tableau optimal donne $x_3 = 20$, $x_2 = 20$, $s_3 = 10$ et, dans la colonne de $s_1$ (main-d'œuvre), les coefficients $2$, $-1$ et $-5$ pour ces trois lignes ; le coût réduit de $s_1$ est 20 (centaines de DH).

Que vaut une heure de main-d'œuvre supplémentaire ?
Dans quel intervalle cette valeur est-elle valable ?
Un intérimaire propose 2 heures à 1 500 DH l'heure. Faut-il accepter ?

Voir le corrigé

1) Le prix fictif de la main-d'œuvre est $y_1 = 20$ centaines de DH, soit 2 000 DH par heure.

2) Avec $40 + \Delta$ heures : $x_3 = 20 + 2\Delta \ge 0$ ($\Delta \ge -10$), $x_2 = 20 - \Delta \ge 0$ ($\Delta \le 20$), $s_3 = 10 - 5\Delta \ge 0$ ($\Delta \le 2$). Intervalle : de 30 à 42 heures. Au-delà de 42 heures, l'emballage devient saturé.

3) 2 heures restent dans l'intervalle ; chacune rapporte 2 000 DH et coûte 1 500 DH : il faut accepter, pour un gain net de $2 \times 500 = $ 1 000 DH. Une troisième heure ne serait plus valorisée à 2 000 DH.

L'essentiel — Dualité et sensibilité

Primal $\max c^T x$, $Ax \le b$, $x \ge 0$ ⇔ dual $\min b^T y$, $A^T y \ge c$, $y \ge 0$ (transposition ; objectif ↔ seconds membres).
Contrainte d'égalité dans le primal → variable duale de signe quelconque ; le dual du dual est le primal.
Dualité faible : $Z(x) \le W(y)$ ; forte : $Z^* = W^*$ ; primal non borné ⇒ dual impossible.
Écarts complémentaires : $y_i\,s_i = 0$ et $x_j\,e_j = 0$.
Prix fictif $y_i = \partial Z^* / \partial b_i$ : prix maximal à payer pour une unité de ressource en plus ; nul si la ressource est abondante.
Solution duale = coûts réduits des variables d'écart dans la ligne $Z$ du tableau optimal.
Intervalle d'un second membre : variables de base $+ \Delta \times$ colonne de $s_i$ $\ge 0$.
Intervalle d'un coefficient de l'objectif : coûts réduits $\ge 0$ (en 2D : pente entre les contraintes saturées).
Fil rouge : $y = (100 ; 100 ; 0)$, $W^* = 18\,000$ ; $b_1 \in [80 ; 120]$, $b_2 \in [60 ; 100]$.

S'entraîner sur des sujets réels

Des sujets réels de concours (master, licence d'excellence) avec une épreuve de Intelligence Artificielle et Recherche Opérationnelle : énoncé complet et corrigé indicatif.

Voir les 13 sujets de concours en Intelligence Artificielle et Recherche Opérationnelle →