Recherche opérationnelle
La dualité
- Présentation du cours
- Qu'est-ce que la recherche opérationnelle
- Modéliser un problème de décision
- Le programme linéaire et ses formes
- La résolution graphique
- Le simplexe, la méthode
- Le simplexe, les cas particuliers
- La dualité
- L'analyse de sensibilité
- Le problème de transport
- Le problème d'affectation
- Les graphes, vocabulaire et représentation
- Le plus court chemin
- Le flot maximal
- L'ordonnancement de projet
- La programmation en nombres entiers
- Gestion des stocks et files d'attente
Recherche opérationnelle
Chapitre 6 : La dualité
Deux questions, un seul nombre
La question renversée
Le problème primal
Combien produire ? Maximiser la marge sous contrainte de ressources.
Le problème dual
Combien valent les ressources ? Un investisseur veut racheter l’atelier heure par heure.
Quel prix minimal doit-il proposer pour que l’atelier accepte de tout lui céder plutôt que de produire ?
L’écriture du dual
La règle de transposition
| Primal | Dual |
|---|---|
| \max \mathbf{c}'\mathbf{x} | \min \mathbf{b}'\mathbf{u} |
| \mathbf{Ax} \leq \mathbf{b} | \mathbf{A}'\mathbf{u} \geq \mathbf{c} |
| \mathbf{x} \geq \mathbf{0} | \mathbf{u} \geq \mathbf{0} |
| m contraintes | m variables |
| n variables | n contraintes |
Ce que la transposition signifie
Une contrainte du primal devient une variable du dual, et réciproquement.
\mathbf{A} se lit en lignes dans un cas, en colonnes dans l’autre : c’est la même matrice, lue dans l’autre sens.
Le dual de l’atelier
L’écriture
Les deux problèmes côte à côte
\underbrace{\max\; 30x + 25y}_{\text{primal}} \qquad\qquad \underbrace{\min\; 100u + 80v}_{\text{dual}}
\begin{cases} 2x + y \leq 100\\ x + y \leq 80 \end{cases} \qquad\qquad \begin{cases} 2u + v \geq 30\\ \phantom{2}u + v \geq 25 \end{cases}
Lire la première contrainte du dual
u est le prix d’une heure de découpe, v celui d’une heure de couture.
2u + v \geq 30 : ce que rapporte un sac A vendu en pièces détachées d’heures doit valoir au moins la marge qu’il rapporterait produit. Sinon l’atelier refuse de céder.
La solution
Résolution
Les deux contraintes sont saturées à l’optimum :
\begin{cases} 2u + v = 30\\ \phantom{2}u + v = 25\end{cases} \quad\Longrightarrow\quad u = 5, \quad v = 20
W = 100(5) + 80(20) = 500 + 1\,600 = 2\,100
Le même nombre que le primal
Z^* = W^* = 2\,100 \text{ DH}
Produire pour 2\,100 ou vendre les heures pour 2\,100 : l’atelier est exactement indifférent.
Les théorèmes de la dualité
La dualité faible
L’énoncé
Pour toute solution réalisable \mathbf{x} du primal et toute solution réalisable \mathbf{u} du dual :
\mathbf{c}'\mathbf{x} \;\leq\; \mathbf{b}'\mathbf{u}
Ce qu’elle offre gratuitement
Toute solution du dual est une borne supérieure sur ce que le primal peut atteindre.
Sans résoudre le primal, on sait déjà qu’on ne dépassera pas. C’est ce qui rendra le branch and bound possible au chapitre 14.
La dualité forte
L’énoncé
Si l’un des deux problèmes a un optimum fini, l’autre aussi, et les deux valeurs sont égales.
Une conséquence pratique
Résoudre le dual peut être bien plus rapide : m contraintes deviennent m variables.
Un problème à 500 contraintes et 3 variables se résout en trois itérations par son dual, contre plusieurs centaines par le primal.
Les écarts complémentaires
Le troisième théorème
À l’optimum, pour chaque paire :
u_i \times (\text{ecart de la contrainte } i) = 0 \qquad\text{et}\qquad x_j \times (\text{ecart de la contrainte duale } j) = 0
Ce que cela veut dire en français
Une ressource non saturée a un prix nul. S’il reste des heures inutilisées, une heure de plus ne vaut rien.
Une ressource saturée a un prix positif. C’est elle qui bloque, donc elle qui vaut.
Le prix dual
Sa signification
Prix fictif, prix marginal, shadow price
u_i est l’accroissement de Z si la ressource i augmente d’une unité, toutes choses égales par ailleurs.
Vérification sur l’atelier
Avec 101 heures de découpe : 2x + y = 101, x + y = 80 donnent x = 21, y = 59.
Z = 30(21) + 25(59) = 630 + 1\,475 = 2\,105 = 2\,100 + \mathbf{5}
La décision qui en découle
Une heure supplémentaire de découpe rapporte 5 DH, une heure de couture 20 DH.
Si l’heure supplémentaire coûte 12 DH, on embauche en couture et pas en découpe. C’est la question que le gestionnaire pose vraiment.
Où le prix dual était déjà écrit
La dernière ligne du tableau du chapitre 4
c_j - z_j \;\text{ pour } e_1 = -5, \qquad c_j - z_j \;\text{ pour } e_2 = -20
Les prix duaux sont, au signe près, les coûts réduits des variables d’écart.
Résoudre le primal résout donc le dual du même coup : un seul calcul, deux réponses.
Ce qu’il faut retenir
Le résumé du chapitre
Six points
- Le dual demande combien valent les ressources, quand le primal demande combien produire.
- Contraintes et variables s’échangent : \mathbf{A} se lit transposée.
- Dualité faible : toute solution duale majore toute solution primale.
- Dualité forte : Z^* = W^* = 2\,100 DH.
- Écarts complémentaires : ressource non saturée \Rightarrow prix nul.
- Les prix duaux 5 et 20 étaient déjà dans la dernière ligne du tableau du simplexe.
La suite
Le chapitre 7 pousse la question plus loin : jusqu’où ces prix restent-ils valables, et de combien les données peuvent-elles changer sans que la solution change ?
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)