Recherche opérationnelle

Dualité et analyse de sensibilité

Le meilleur plan ne suffit pas. Que vaut une heure de plus ? Que se passe-t-il si un prix change ? Jusqu'où peut-on se fier à la réponse ? Le problème dual répond à ces questions, souvent sans refaire le calcul.

Un même problème se regarde de deux côtés. Le fabricant cherche le plan qui rapporte le plus. Un acheteur imaginaire cherche le prix le plus bas pour racheter ses ressources. Ces deux problèmes opposés ont la même réponse, et c'est de là que viennent les prix cachés des ressources.

Les étapes du simplexe font monter la marge du fabricant ; des offres acceptables de plus en plus basses font descendre le coût de l'acheteur. Les deux se rejoignent à 2 200 € et ne peuvent pas se croiser.

Notre atelier de meubles, aux données inventées, fabrique cette semaine x bureaux et y bibliothèques, avec une marge de 50 € et 40 €. Un bureau demande 3 heures et 1 planche ; une bibliothèque, 2 heures et 2 planches. Il dispose de 120 heures et de 80 planches. Résultats calculés sur place, et contrôlés par une seconde méthode.

Planche 1

Problème primal et problème dual

Imaginons quelqu'un qui veut racheter toutes les ressources de l'atelier, au prix u l'heure et v la planche. Il veut payer le moins possible. Mais l'atelier ne vendra que si, pour chaque meuble, les ressources qu'il contient lui sont payées au moins autant que le meuble rapporte.

	Le fabricant (primal)	L'acheteur (dual)
Objectif	maximiser 50x + 40y	minimiser 120u + 80v
Pour les heures et les bureaux	3x + 2y ≤ 120 (la ligne des heures)	3u + v ≥ 50 (la colonne des bureaux)
Pour les planches et les bibliothèques	x + 2y ≤ 80 (la ligne des planches)	2u + 2v ≥ 40 (la colonne des bibliothèques)
Signes	x, y ≥ 0	u, v ≥ 0

Le plan de production (x ; y). Zone bleue : plans admissibles. Cliquez pour choisir un plan. Le fabricant veut aller le plus haut possible.

Les prix (u ; v). Zone verte : offres acceptables, un domaine ouvert vers le haut. Cliquez pour choisir une offre. L'acheteur veut descendre le plus bas possible.

Sur une même échelle, en euros : la marge du plan et le coût de l'offre. Tant que les deux sont admissibles, la marge reste à gauche du coût.

Marge du plan–

Coût de l'offre–

Écart entre les deux–

Plus petit écart sur 5 000 couples admissibles–

Dualité forte sur 3 000 problèmes au hasard : plus grand écart–

–

Deux théorèmes. Dualité faible : la marge d'un plan admissible ne dépasse jamais le coût d'une offre admissible. Chaque offre borne donc tous les plans. Dualité forte : à l'optimum, les deux coïncident, ici à 2 200 € ; un couple d'écart nul prouve que les deux sont optimaux. Enfin, le dual du dual redonne le primal, et si un problème n'a pas de borne, l'autre n'a pas de solution.

Les écarts complémentaires. À l'optimum, une ressource non épuisée a un prix nul, et un produit non rentable au prix des ressources n'est pas fabriqué. Autrement dit, le produit « reste de ressource × prix » vaut zéro pour chaque ressource.

Planche 2

La valeur marginale des ressources

Les solutions du dual, u = 15 € et v = 5 €, ne sont pas de simples nombres auxiliaires. La variable duale d'une ressource est ce que rapporterait une unité de plus. On l'appelle valeur marginale, ou prix fictif. Ce n'est pas le prix du marché : c'est ce que vaut cette ressource pour cet atelier, dans cette situation.

La balance de chaque meuble : la valeur de ce qu'il consomme, au prix des ressources (empilée), contre sa marge (trait noir). Égalité pour les meubles fabriqués. Pour l'armoire, si le trait dépasse, elle mérite d'entrer.

Le domaine, et en pointillé sa forme de départ. La ressource choisie déplace une droite, le sommet glisse le long de l'autre.

Unités de ressource ajoutées

Marge d'une armoire (5 h et 2 planches, pour l'instant non fabriquée)

Valeur marginale de la ressource–

Gain prévu : valeur × unités–

Gain mesuré en résolvant à nouveau–

Le prix reste valable entre–

Armoire : marge − ressources consommées–

Armoire : gain mesuré, et nombre fabriqué–

Ces prix se lisent dans le tableau final du simplexe

Sous les variables d'écart, la ligne z affiche 15, 5, 0, 0 : les prix des heures, des planches, de la capacité et du marché. Résoudre le primal avec le simplexe donne donc aussi le dual, sans calcul de plus.

Ce qu'il faut retenir. Une ressource en excès vaut 0, même si elle a coûté cher : la capacité machine n'a aucun prix ici, car on n'utilise que 20 bureaux sur 30. Et ces prix servent de test de rentabilité pour un produit nouveau : l'armoire consomme 5 h et 2 planches, soit 5 × 15 + 2 × 5 = 85 €. Tant que sa marge reste sous 85 €, la fabriquer revient à retirer les ressources à des usages meilleurs.

Planche 3

Effet d'une modification des coûts, des capacités ou de la demande

L'analyse de sensibilité demande : si une donnée change, que devient la solution ? Trois familles de données, trois comportements. Choisissez une donnée, puis faites varier sa valeur.

Valeur

La solution pour cette valeur. Trait vert : la droite de marge. Traits épais : les contraintes saturées. Point rouge : le plan optimal.

La marge maximale selon la donnée choisie. Chaque couleur correspond à un même couple de contraintes saturées. Sur chaque morceau, la courbe est droite, et sa pente se lit directement.

–

Plan optimal (bureaux ; bibliothèques)–

Marge maximale–

Contraintes saturées–

Pente prévue–

Pente mesurée (à gauche ; à droite)–

Même solution de base, par la formule–

Même plage, par balayage–

Si change…	Le plan	Les prix des ressources	La marge maximale
Un coût ou une marge	Inchangé, dans la plage	Ils changent	Pente = quantité produite
Une capacité saturée	Il glisse, avec les mêmes contraintes saturées	Inchangés, dans la plage	Pente = valeur marginale
Une capacité en excès	Inchangé	Inchangés	Inchangée
Une demande imposée	Sans effet tant qu'elle n'est pas saturée, puis elle force le plan	Elle reçoit un prix : ce qu'elle coûte	Elle baisse, à pente constante

Ce qu'il faut retenir. Une courbe de capacité se plie vers le bas : chaque unité supplémentaire rapporte de moins en moins, c'est la concavité, une loi des rendements décroissants. Une courbe de marge se plie vers le haut : on en profite davantage en s'adaptant. Regardez le contrat de bureaux : gratuit jusqu'à 20, il coûte ensuite 10 € par bureau imposé. Avant d'accepter une commande, voilà un chiffre utile.

Planche 4

La stabilité d'une solution optimale

Les données sont toujours un peu fausses. Une solution est stable si de petites erreurs ne changent pas sa structure, c'est-à-dire les mêmes contraintes saturées et les mêmes produits fabriqués. Ces cartes montrent jusqu'où elle tient. Cliquez pour déplacer le point noir.

Selon les deux marges : chaque couleur est un plan optimal différent. Le plan reste le même dans tout un cône. Losange : ce que garantit la règle des 100 %.

Selon les heures et les planches : chaque couleur est un couple de contraintes saturées. Le plan bouge, mais sa structure reste. Les petits points sont des scénarios tirés au hasard, verts s'ils restent dans la région, rouges sinon.

Erreur sur toutes les données (marges et capacités)

Marges (bureau ; bibliothèque)–

Heures ; planches–

Règle des 100 % : somme des fractions de plage (marges / capacités)–

Même structure après une erreur de cette taille–

Perte si on garde le plan sans recalculer–

Perte si on garde sa structure, et qu'on recalcule les quantités–

Prix de l'heure à gauche ; à droite–

Selon la taille de l'erreur, sur 2 000 scénarios par point. Bleu : part des scénarios où la structure reste optimale. Rouge et violet : pertes moyennes, en % de la marge optimale, avec les deux façons de réagir ci-dessus.

Trois messages. La structure est plus solide que les chiffres : pour de petites erreurs, garder les mêmes contraintes saturées perd bien moins que figer les quantités (0,69 % contre 3,94 % à ± 10 %), avant que les deux se rejoignent quand l'erreur grandit, ou près d'une frontière. La règle des 100 % est prudente : si la somme des changements, rapportés à leur plage, reste sous 100 %, la solution tient à coup sûr ; mais le losange est plus petit que la région réelle. Une frontière est un signal : à 140 h, le prix de l'heure vaut 15 € à gauche et 0 € à droite ; il n'y a plus un seul prix à annoncer, et c'est une solution dite dégénérée.

Planche 5

Exemple : faut-il payer une heure de travail supplémentaire ?

Un employé propose des heures supplémentaires à un certain tarif. Vaut-il la peine de les payer, et combien en prendre ? Le prix dual répond en une ligne, à condition d'en connaître les limites. Faites avancer les heures une par une.

La droite des heures avance. Point rouge : le plan avec des fractions de meuble. Point bleu : le meilleur plan en meubles entiers.

Marge selon les heures : courbe (fractions de meuble) et escalier (meubles entiers). Pointillés : la droite du tarif, partant de la situation à 120 h. On gagne tant que la courbe est au-dessus.

Heures disponibles

Coût d'une heure supplémentaire

–

Valeur marginale de l'heure (en dessous ; au-dessus)–

Plan optimal avec des fractions–

Plan en meubles entiers–

Marge par heure : la moyenne trompeuse–

Meilleur nombre d'heures à acheter, à ce tarif–

Gain net de cet achat–

Ce que rapporte chaque heure après la 120^e, en meubles entiers (barres), contre la valeur marginale (trait). Trait rouge : le tarif. Les gains arrivent par séries, mais leur moyenne suit le trait.

Une seule ressource à la fois ne suffit pas toujours

La réponse complète. Payez l'heure si son coût est inférieur à sa valeur marginale de 15 €, et pas à la marge moyenne de 18,33 € : à 17 €, cette moyenne donne envie d'acheter, alors que chaque heure ferait perdre 2 €. Ne dépassez pas la plage de validité : au-delà de 140 h, la capacité machine est saturée, et l'heure ne vaut plus rien. Et ne soyez pas surpris si l'on fabrique des meubles entiers : la 121^e heure ne rapporte que 10 €, la 124^e en rapporte 30 ; c'est la moyenne qui vaut 15 €. Enfin, les ressources se complètent : 40 heures seules rapportent 300 €, 10 unités de capacité seules rien du tout, mais ensemble 600 €.

Ce qu'il faut garder

Deux problèmes, une réponse

Le dual échange lignes et colonnes, maximum et minimum. La marge d'un plan ne dépasse jamais le coût d'une offre, et à l'optimum les deux sont égaux.

Des prix pour décider

Une variable duale dit ce que vaut une unité de plus de ressource, et elle juge un produit nouveau. Une ressource en excès vaut 0. Le tableau final du simplexe affiche ces prix.

Une validité limitée

Chaque prix et chaque plan valent sur une plage. Au-delà, le calcul doit être refait. Une réponse honnête donne toujours le chiffre et sa plage.

Pour aller plus loin

Dans ce cahier. La programmation linéaire explique le simplexe et ses tableaux. La recherche opérationnelle présente un autre atelier, avec la même idée. Le problème de transport montre des prix duaux comme coûts de livraison, et même un paradoxe : expédier plus pour payer moins.

Sur les calculs. Les plages sont calculées par la formule de la base, puis confirmées par balayage et dichotomie sur le problème complet. Le contrat de bureaux s'écrit x ≥ C : il est écrit −x ≤ −C pour le calcul, et son prix mesure ce que coûte une unité imposée. Les scénarios de la planche 4 tirent chaque donnée uniformément dans ± l'erreur annoncée, indépendamment. Si une capacité diminue et que le plan gardé tel quel n'est plus réalisable, les deux quantités sont réduites dans la même proportion jusqu'à ce qu'il le redevienne.