Exploitez la dualité

Un brasseur voisin fait une proposition inattendue à notre brasserie : plutôt que de brasser cette semaine, pourquoi ne pas lui louer toutes ses ressources, cuves, malt et houblon ? Il reste à fixer un prix. Trop bas, notre brasseur y perd par rapport à sa propre production ; trop haut, le voisin refuse.

Cette question de prix cache l’une des idées les plus belles de l’optimisation : à tout programme linéaire est associé un programme dual, qui en est le reflet exact. Dans ce chapitre, vous allez apprendre à l’écrire, à l’utiliser pour certifier qu’une solution est optimale, à lire les prix des ressources dans le tableau du simplexe, et à résoudre un jeu entre deux concurrents.

Construire le dual par le raisonnement économique

Rappelons le programme de la brasserie, que nous appellerons désormais le primal :

$$\max \; 3x_1 + 2x_2 \quad \text{s.c.} \quad x_1 + x_2 \leq 4, \quad x_1 + 3x_2 \leq 9, \quad x_1 \leq 3, \quad x_1, x_2 \geq 0$$

Le voisin propose un prix $y_1$ par hectolitre de cuve, $y_2$ par sac de malt et $y_3$ par lot de houblon. Quand notre brasseur acceptera-t-il ? Seulement si louer vaut au moins autant que produire, pour chaque bière :

• les ressources d’un hectolitre de blonde (1 cuve, 1 sac, 1 lot) doivent rapporter au moins 3 : $y_1 + y_2 + y_3 \geq 3$ ;
• celles d’un hectolitre d’ambrée (1 cuve, 3 sacs) au moins 2 : $y_1 + 3y_2 \geq 2$.

Le voisin, lui, veut payer le moins possible pour l’ensemble du stock. Il résout donc :

$$\min \; 4y_1 + 9y_2 + 3y_3 \quad \text{s.c.} \quad y_1 + y_2 + y_3 \geq 3, \quad y_1 + 3y_2 \geq 2, \quad y_1, y_2, y_3 \geq 0$$

C’est le dual de la brasserie. Regardez bien sa structure : les seconds membres du primal (4, 9, 3) sont devenus les coefficients de l’objectif, les coefficients de l’objectif (3, 2) sont devenus les seconds membres, et la matrice des contraintes a été transposée (les colonnes du primal sont les lignes du dual).

Les règles de passage

Sous forme matricielle, le couple primal-dual « canonique » s’écrit :

$$\text{(P)} \;\; \max \; c^T x \;\; \text{s.c.} \;\; Ax \leq b, \; x \geq 0 \qquad\qquad \text{(D)} \;\; \min \; b^T y \;\; \text{s.c.} \;\; A^T y \geq c, \; y \geq 0$$

où $A$ est la matrice des contraintes, $b$ le vecteur des seconds membres, $c$ celui des coûts, et $y$ contient une variable duale par contrainte du primal. Quand le primal n’est pas sous cette forme, on applique les correspondances suivantes (pour un primal de maximisation) :

Primal (max)	Dual (min)
contrainte $i$ de type $\leq$	variable $y_i \geq 0$
contrainte $i$ de type $\geq$	variable $y_i \leq 0$
contrainte $i$ d’égalité	variable $y_i$ de signe quelconque (libre)
variable $x_j \geq 0$	contrainte $j$ de type $\geq$
variable $x_j \leq 0$	contrainte $j$ de type $\leq$
variable $x_j$ libre	contrainte $j$ d’égalité

Le tableau se lit aussi de droite à gauche : le dual du dual est le primal.

Attention

Ces règles supposent un primal de maximisation. Pour dualiser une minimisation, lisez le tableau de droite à gauche (le problème de minimisation joue le rôle de la colonne « Dual »), ou transformez d’abord $\min f$ en $\max(-f)$. Mélanger les deux lectures est la source d’erreur de signe la plus fréquente.

Dualité faible et dualité forte

Prenez n’importe quelle production réalisable $x$ et n’importe quels prix réalisables $y$. Alors

$$c^T x \leq (A^T y)^T x = y^T (A x) \leq y^T b$$

La première inégalité utilise $A^T y \geq c$ et $x \geq 0$, la seconde $Ax \leq b$ et $y \geq 0$. C’est la dualité faible : la valeur de toute solution du primal (max) est inférieure ou égale à celle de toute solution du dual (min). Économiquement, aucun plan de production ne rapporte plus que ce que coûte n’importe quelle offre de location acceptable.

Conséquence immédiate et très pratique : si vous trouvez un $x$ et un $y$ réalisables de même valeur, ils sont tous les deux optimaux. Le $y$ sert de certificat d’optimalité pour $x$.

Dualité faible : toute production réalisable rapporte au plus ce que coûte n'importe quelle offre de prix réalisable. Les deux familles se rejoignent en 11, atteint par x = (3, 1) et y = (2, 0, 1).

Exemple

Pour la brasserie, $x = (3, 1)$ rapporte 11. Essayons les prix $y = (2, 0, 1)$ :

• $y_1 + y_2 + y_3 = 3 \geq 3$ et $y_1 + 3y_2 = 2 \geq 2$ : les prix sont réalisables ;
• le coût total vaut $4 \times 2 + 9 \times 0 + 3 \times 1 = 11$.

Les deux valeurs sont égales : $x = (3, 1)$ est optimal pour le primal, et $y = (2, 0, 1)$ pour le dual, sans avoir besoin de refaire le moindre simplexe.

La dualité forte affirme que ce n’est pas un hasard : si le primal a une solution optimale, le dual aussi, et leurs valeurs optimales sont égales. Les autres situations sont tout aussi encadrées : si le primal est non borné, le dual est irréalisable (et inversement), ce que la dualité faible suffit d’ailleurs à montrer.

À retenir

Dualité faible : pour tout couple réalisable, valeur du primal (max) $\leq$ valeur du dual (min). Dualité forte : à l’optimum, les deux valeurs sont égales. Un couple réalisable de même valeur est donc optimal.

Les écarts complémentaires et les prix des ressources

À l’optimum, un lien plus fin relie les deux problèmes, les écarts complémentaires :

$$y_i \, (b - Ax)_i = 0 \quad \text{pour tout } i, \qquad x_j \, (A^T y - c)_j = 0 \quad \text{pour tout } j$$

En mots : une ressource qui n’est pas épuisée a un prix nul ($y_i = 0$ si la contrainte $i$ n’est pas saturée), et une bière effectivement produite a une contrainte duale saturée (ses ressources, au prix dual, valent exactement son bénéfice).

Exemple

Retrouvons les prix optimaux à partir de la seule production optimale $x = (3, 1)$.

• Le malt n’est pas épuisé (il reste 3 sacs) : $y_2 = 0$.
• On produit de la blonde ($x_1 > 0$) : $y_1 + y_2 + y_3 = 3$.
• On produit de l’ambrée ($x_2 > 0$) : $y_1 + 3y_2 = 2$.

D’où $y_1 = 2$, puis $y_3 = 1$. On retrouve $y = (2, 0, 1)$.

Les deux contraintes duales saturées disent que c = (3, 2) est une combinaison des vecteurs des contraintes actives : 2 × (1, 1) + 1 × (1, 0). Les coefficients sont les prix y₁ = 2 et y₃ = 1 ; le malt, inactif, n'intervient pas.

Mais ces prix, on les avait déjà sous les yeux ! Le dictionnaire final du simplexe (chapitre 2) se terminait par $z = 11 - 2e_1 - e_3$. Les coûts réduits des variables d’écart, au signe près, sont exactement les variables duales : $y_1 = 2$ pour $e_1$ (cuves), $y_2 = 0$ pour $e_2$ (malt, en base, coût réduit nul), $y_3 = 1$ pour $e_3$ (houblon). Un simplexe résout toujours les deux problèmes à la fois.

Ces valeurs ont un sens très concret : ce sont des prix marginaux (ou prix fictifs, shadow prices). Relisez $z = 11 - 2e_1 - e_3$ : laisser un hectolitre de cuve vide fait perdre 2 ; symétriquement, une cuve de plus ferait gagner 200 € (tant que la base optimale ne change pas). Un sac de malt de plus ne rapporterait rien, puisqu’il en reste déjà. Si le brasseur doit investir, c’est dans les cuves, pas dans le malt.

Le prix marginal des cuves, y₁ = 2, est la pente de cette courbe autour de 4 cuves. Il ne vaut qu'entre 3 et 5 cuves : au-delà, le malt bloque et une cuve de plus ne rapporte plus rien.

from scipy.optimize import linprog

res = linprog([-3, -2], A_ub=[[1, 1], [1, 3], [1, 0]], b_ub=[4, 9, 3],
              bounds=[(0, None), (0, None)], method="highs")
# marginals = dérivée de l'objectif minimisé (-z) par rapport à b_ub
print(res.x, -res.fun)            # [3. 1.] 11.0
print(-res.ineqlin.marginals)     # prix des ressources : 2, 0 et 1

Piège

Un prix marginal n’est valable que localement. Si le brasseur ajoute 10 cuves, il ne gagnera pas 2 000 € : très vite, c’est le houblon ou le malt qui bloque, la base optimale change et le prix des cuves tombe. L’analyse de sensibilité consiste justement à calculer l’intervalle dans lequel chaque prix reste valable.

Les jeux matriciels à somme nulle

La dualité a une application inattendue : la théorie des jeux. Chaque samedi, notre brasserie et un concurrent installent chacun un stand sur l’un de deux marchés rennais, sans savoir ce que fera l’autre. Selon les choix, la brasserie prend au concurrent une part de ses ventes (en centaines d’euros) :

Brasserie \ Concurrent	Marché 1	Marché 2
Marché 1	3	1
Marché 2	2	4

Ce que gagne l’un, l’autre le perd : c’est un jeu à somme nulle, décrit par la matrice $A = \begin{pmatrix} 3 & 1 \\ 2 & 4 \end{pmatrix}$. La brasserie (le joueur « ligne ») veut maximiser son gain, le concurrent (le joueur « colonne ») veut le minimiser.

Existe-t-il un choix fixe raisonnable ? En jouant la ligne 1, la brasserie est sûre de gagner au moins 1 ; en jouant la ligne 2, au moins 2. Elle peut donc se garantir 2. Le concurrent, en jouant la colonne 1, ne perd jamais plus de 3 ; en jouant la colonne 2, jamais plus de 4 : il se garantit 3. Comme $2 \lt 3$, il n’y a pas de point selle : quel que soit le choix fixe de l’un, l’autre a intérêt à s’adapter. La solution est de jouer au hasard, avec des probabilités bien choisies : c’est une stratégie mixte.

Si la brasserie joue la ligne 1 avec la probabilité $p$, son gain moyen vaut $3p + 2(1-p) = 2 + p$ si le concurrent va au marché 1, et $p + 4(1-p) = 4 - 3p$ s’il va au marché 2. Le concurrent choisira ce qui l’arrange, donc la brasserie maximise le minimum des deux : elle les égalise, $2 + p = 4 - 3p$, soit $p = \tfrac12$ et un gain garanti $v = 2{,}5$. Le même calcul côté concurrent donne $q = \tfrac34$ pour la colonne 1, et la même valeur $v = 2{,}5$.

La brasserie ne contrôle que p ; le concurrent choisira la droite la plus basse. Le gain garanti est donc l'enveloppe inférieure, maximale à l'intersection : p = 1/2, v = 2,5.

Le lien avec la programmation linéaire

Pour des matrices plus grandes, on ne peut plus égaliser à la main. On écrit le problème du joueur ligne : maximiser $v$ sous $\sum_i p_i A_{ij} \geq v$ pour toute colonne $j$, avec $\sum_i p_i = 1$ et $p \geq 0$. Si tous les gains sont positifs (on peut toujours ajouter une constante à $A$), $v \gt 0$ et le changement de variable $x_i = p_i / v$ donne un programme linéaire :

$$\text{(joueur ligne)} \;\; \min \sum_i x_i \;\; \text{s.c.} \;\; A^T x \geq \mathbf{1}, \; x \geq 0 \qquad \text{(joueur colonne)} \;\; \max \sum_j y_j \;\; \text{s.c.} \;\; A y \leq \mathbf{1}, \; y \geq 0$$

où $\mathbf{1}$ est le vecteur rempli de 1. La valeur du jeu vaut $v = 1 / \sum_i x_i$, et l’on récupère les stratégies par $p = v\,x$ et $q = v\,y$. Et voici le point clé : ces deux programmes sont duaux l’un de l’autre. La dualité forte garantit donc qu’ils ont la même valeur : c’est le théorème du minimax de von Neumann, qui affirme que le gain que la brasserie peut se garantir est exactement la perte maximale que le concurrent peut s’imposer.

Exemple

Pour notre matrice, le programme du joueur ligne est $\min x_1 + x_2$ sous $3x_1 + 2x_2 \geq 1$ et $x_1 + 4x_2 \geq 1$. Sa solution est $x = (0{,}2 ; 0{,}2)$, de valeur $0{,}4$. On en déduit $v = 1/0{,}4 = 2{,}5$ et $p = 2{,}5 \times (0{,}2 ; 0{,}2) = (0{,}5 ; 0{,}5)$. Côté concurrent, $y = (0{,}3 ; 0{,}1)$, d’où $q = (0{,}75 ; 0{,}25)$. Un seul simplexe fournit les deux stratégies, l’une dans la solution, l’autre dans les coûts réduits.

En entretien

« Le dual d’un programme linéaire associe un prix à chaque contrainte. À l’optimum, les deux problèmes ont la même valeur, et une ressource non épuisée a un prix nul : ce sont les écarts complémentaires. Ces prix disent combien rapporterait une unité de ressource en plus. »

En résumé

• Le dual associe une variable à chaque contrainte du primal ; on transpose $A$ et l’on échange les rôles de $b$ et $c$.
• Pour un primal de maximisation, une contrainte $\leq$ donne une variable duale positive, une égalité une variable libre, et une variable positive une contrainte duale $\geq$.
• Dualité faible : primal (max) $\leq$ dual (min) ; dualité forte : égalité à l’optimum. Un couple réalisable de même valeur est optimal.
• Écarts complémentaires : ressource non épuisée, prix nul ; variable primale positive, contrainte duale saturée.
• Les variables duales sont les prix marginaux des ressources, lisibles (au signe près) dans les coûts réduits des écarts du tableau final.
• Un jeu matriciel à somme nulle se résout par deux programmes linéaires duaux ; leur égalité est le théorème du minimax.

Exercices

Exercice · Écrire et résoudre un dual

facile

Écrivez le dual de $\max z = x_1 + x_2$ sous $2x_1 + x_2 \leq 8$, $x_1 + 2x_2 \leq 7$, $x_1, x_2 \geq 0$, dont l’optimum est $(3, 2)$. Utilisez les écarts complémentaires pour trouver la solution duale, puis vérifiez la dualité forte.

Voir la solution

Le dual est $\min 8y_1 + 7y_2$ sous $2y_1 + y_2 \geq 1$, $y_1 + 2y_2 \geq 1$, $y_1, y_2 \geq 0$.

À l’optimum primal, $x_1 = 3 > 0$ et $x_2 = 2 > 0$ : les deux contraintes duales sont saturées, $2y_1 + y_2 = 1$ et $y_1 + 2y_2 = 1$. On trouve $y_1 = y_2 = \tfrac13$, positifs donc réalisables. Valeur duale : $\tfrac83 + \tfrac73 = 5$, égale à la valeur primale $3 + 2 = 5$. La dualité forte est vérifiée. On retrouve d’ailleurs ces valeurs dans le dictionnaire final du chapitre 2, $z = 5 - \tfrac13 e_1 - \tfrac13 e_2$.

En code

Python

import numpy as np
from scipy.optimize import linprog

A, b, c = np.array([[2, 1], [1, 2]]), np.array([8, 7]), np.array([1, 1])
primal = linprog(-c, A_ub=A, b_ub=b)                 # max c'x
dual = linprog(b, A_ub=-A.T, b_ub=-c)                # min b'y sous A'y >= c
print(primal.x, -primal.fun)                         # [3. 2.] 5.0
print(dual.x, dual.fun)                              # [0.333 0.333] 5.0

# Écarts complémentaires : x1, x2 > 0, donc A'y = c
y = np.linalg.solve(A.T, c)
print(y, b @ y)                                      # [0.333 0.333] 5.0
print(-primal.ineqlin.marginals)                     # [0.333 0.333] : les mêmes prix

R

A <- rbind(c(2, 1), c(1, 2)); b <- c(8, 7); cc <- c(1, 1)
# Écarts complémentaires : x1 = 3 > 0 et x2 = 2 > 0, donc A'y = c
y <- solve(t(A), cc)
y                                   # 0.333 0.333 : positifs, donc réalisables
sum(b * y); sum(cc * c(3, 2))       # 5 et 5 : dualité forte vérifiée

# Contrôle : sommets du dual {A'y >= c, y >= 0}, écrit -A'y <= -c
G <- rbind(-t(A), diag(-1, 2)); h <- c(-cc, 0, 0)
for (i in combn(4, 2, simplify = FALSE)) {
  if (abs(det(G[i, ])) < 1e-9) next
  s <- solve(G[i, ], h[i])
  if (all(G %*% s <= h + 1e-9)) cat("sommet", round(s, 3), "coût", sum(b * s), "\n")
}
# sommet 0.333 0.333 coût 5 ; sommet 0 1 coût 7 ; sommet 1 0 coût 8 : le minimum vaut 5

Exercice · Le prix des besoins

moyen

On reprend le problème d’achat de céréales du chapitre 3 : $\min 2x_1 + 3x_2$ sous $x_1 + x_2 \geq 4$, $x_1 + 3x_2 \geq 6$, $x_1, x_2 \geq 0$, d’optimum $(3, 1)$ et de coût 9. Écrivez son dual, résolvez-le graphiquement et interprétez ses variables.

Voir la solution

Le problème est une minimisation avec des contraintes $\geq$ et des variables positives : c’est la forme (D) du cours. Son dual est donc de la forme (P) : $\max 4y_1 + 6y_2$ sous $y_1 + y_2 \leq 2$, $y_1 + 3y_2 \leq 3$, $y_1, y_2 \geq 0$.

Les sommets du domaine sont $(0, 0)$, $(2, 0)$, $(1{,}5 ; 0{,}5)$ et $(0, 1)$, de valeurs 0, 8, 9 et 6. L’optimum est $y = (1{,}5 ; 0{,}5)$, de valeur 9, égale au coût minimal : la dualité forte est vérifiée. Ce sont aussi, au signe près, les coûts réduits $\tfrac32$ et $\tfrac12$ des excédents dans le dictionnaire final $w = 9 + \tfrac32 s_1 + \tfrac12 s_2$.

Interprétation : $y_1 = 1{,}5$ est le coût marginal d’une unité d’amidon exigée en plus (150 €), $y_2 = 0{,}5$ celui d’une unité d’arômes (50 €). On peut aussi y voir le prix maximal qu’un producteur d’amidon ou d’arômes « purs » pourrait demander pour que la brasserie lui achète directement ses nutriments.

En code

Python

from scipy.optimize import linprog

# Primal : min 2 x1 + 3 x2 sous x1 + x2 >= 4, x1 + 3 x2 >= 6 (écrits en <= avec un signe -)
primal = linprog([2, 3], A_ub=[[-1, -1], [-1, -3]], b_ub=[-4, -6])
print(primal.x, primal.fun)                    # [3. 1.] 9.0
print(-primal.ineqlin.marginals)               # [1.5 0.5] : coût d'une unité de besoin en plus

# Dual : max 4 y1 + 6 y2 sous y1 + y2 <= 2, y1 + 3 y2 <= 3
dual = linprog([-4, -6], A_ub=[[1, 1], [1, 3]], b_ub=[2, 3])
print(dual.x, -dual.fun)                       # [1.5 0.5] 9.0

R

# Dual : max 4 y1 + 6 y2 sous y1 + y2 <= 2, y1 + 3 y2 <= 3, y >= 0
G <- rbind(c(1, 1), c(1, 3), c(-1, 0), c(0, -1)); h <- c(2, 3, 0, 0)
S <- NULL
for (i in combn(4, 2, simplify = FALSE)) {
  if (abs(det(G[i, ])) < 1e-9) next
  y <- solve(G[i, ], h[i])
  if (all(G %*% y <= h + 1e-9)) S <- rbind(S, y)
}
cbind(S, valeur = S %*% c(4, 6))
# (1.5, 0.5) : 9 ; (2, 0) : 8 ; (0, 1) : 6 ; (0, 0) : 0
S[which.max(S %*% c(4, 6)), ]      # 1.5 0.5, de valeur 9 = coût minimal du primal

Exercice · Résoudre un jeu matriciel

difficile

Deux joueurs s’affrontent avec la matrice de gains (pour le joueur ligne) $A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}$. Le jeu a-t-il un point selle ? Trouvez les stratégies optimales et la valeur du jeu, puis vérifiez avec le programme linéaire du joueur ligne.

Voir la solution

Minimum de chaque ligne : 1 et 2, donc le joueur ligne se garantit 2 avec une stratégie fixe. Maximum de chaque colonne : 4 et 3, donc le joueur colonne se garantit de ne pas perdre plus de 3. Comme $2 \neq 3$, il n’y a pas de point selle.

Joueur ligne (ligne 1 avec probabilité $p$) : gain $4p + 2(1-p) = 2 + 2p$ contre la colonne 1, $p + 3(1-p) = 3 - 2p$ contre la colonne 2. En égalisant, $p = \tfrac14$ et $v = 2{,}5$.

Joueur colonne (colonne 1 avec probabilité $q$) : perte $4q + (1-q) = 1 + 3q$ contre la ligne 1, $2q + 3(1-q) = 3 - q$ contre la ligne 2. En égalisant, $q = \tfrac12$ et la valeur est bien $2{,}5$.

Vérification : le programme $\min x_1 + x_2$ sous $4x_1 + 2x_2 \geq 1$, $x_1 + 3x_2 \geq 1$ a pour solution $x = p / v = (0{,}1 ; 0{,}3)$, qui sature les deux contraintes ($0{,}4 + 0{,}6 = 1$ et $0{,}1 + 0{,}9 = 1$) et vaut $0{,}4 = 1/v$.

En code

Python

import numpy as np
from scipy.optimize import linprog

A = np.array([[4, 1], [2, 3]])
print(A.min(axis=1).max(), A.max(axis=0).min())   # 2 3 : pas de point selle

# Joueur ligne : min x1 + x2 sous A'x >= 1, x >= 0
res = linprog([1, 1], A_ub=-A.T, b_ub=[-1, -1])
v = 1 / res.fun
print(res.x, v, v * res.x)                  # [0.1 0.3] 2.5 [0.25 0.75]
# La stratégie du joueur colonne est dans les multiplicateurs
print(v * -res.ineqlin.marginals)           # [0.5 0.5]

R

A <- rbind(c(4, 1), c(2, 3))
max(apply(A, 1, min)); min(apply(A, 2, max))     # 2 et 3 : pas de point selle

# Joueur ligne : min x1 + x2 sous A'x >= 1, x >= 0, écrit G x <= h
G <- rbind(-t(A), diag(-1, 2)); h <- c(-1, -1, 0, 0)
S <- NULL
for (i in combn(4, 2, simplify = FALSE)) {
  if (abs(det(G[i, ])) < 1e-9) next
  x <- solve(G[i, ], h[i])
  if (all(G %*% x <= h + 1e-9)) S <- rbind(S, x)
}
x <- S[which.min(rowSums(S)), ]
v <- 1 / sum(x)
x; v; v * x                                       # 0.1 0.3 ; 2.5 ; p = 0.25 0.75
q <- solve(A, rep(1, 2)); q / sum(q)              # joueur colonne (A y = 1) : q = 0.5 0.5