\subsection{Dualité}

Considérons le problème linéaire suivant : 
\begin{quote}
La maison d'édition $Castor$ vend et édite des livres et des encyclopédies. A cette fin elle dispose de trois matières premières : des feuilles blanches, des cartouches d'encre et du temps d'impression. Les données sont résumées dans le tableau suivant :
$$
\begin{array}{r|c|c}
&\text{Livre}&\text{Encyclopédie}\\\hline
\text{Pages (par centaines)} &4&1800\\\hline
\text{Cartouches d'encre }& 1 &11\\\hline
\text{Temps d'impression (en heure)}&1&2
\end{array}
$$
Un livre est vendu $20$\euro{} et une encyclopédie $180$\euro{}. La maison d'édition possède quatre millions de pages blanches, $200$ cartouches d'encre et de $120$ heures de temps d'impression.
\end{quote}
En cherchant à optimiser le bénéfice de cette maison d'édition on résout le problème $(P)$ sous forme normal :
$$
(P)
\left\{
\begin{array}{rcl}
4x_1+1800x_2&\leqslant& 40000\\
x_1+11x_2&\leqslant& 200\\
x_1+2x_2&\leqslant&120\\
Max(20x_1+180x_2)&&
\end{array}
\right.$$

A présent une autre maison d'édition arrive sur le marché : $Polux$. Pour rester compétitive $Castor$ choisi de céder des matières premières à $Polux$. Soient 
\begin{description}
\item[$\bullet$] $y_1$ le prix de vente par $Castor$ d'une page blanche à $Polux$ 
\item[$\bullet$] $y_2$ le prix pour une cartouche d'encre,
\item[$\bullet$] $y_3$ le prix pour une heure d'impression.
\end{description}
Bien sur, pour que cela soit rentable pour la maison $Castor$, il faut que le prix que $Polux$ va dépenser pour éditer un livre soit supérieur au prix de vente d'un livre et respectivement pour les encyclopédies.
\begin{description}
\item[$\bullet$] Prix de vente de matière première pour fabriquer un livre : $4y_1+y_2+y_3$. Prix de vente d'un livre : $20$\euro{}.
$$4y_1+y_2+y_3\geqslant 20$$
\item[$\bullet$] Prix de vente de matière première pour fabriquer une encyclopédie : $1800y_1+11y_2+2y_3$. Prix de vente d'une encyclopédie : $180$\euro{}.
$$1800y_1+11y_2+2y_3\geqslant 180$$
\end{description}
Si $Castor$ avait acheté ses matières premières aux même prix que $Polux$, sa dépense aurait été de  $40000y_1+200y_2+120y_3$. Pour rester attractif, il faut que ce prix soit le plus petit possible. La fonction objectif est donc $$Min(40000y_1+200y_2+120y_3)$$
On obtient alors un nouveau problème $(D)$ dit problème dual de $(P)$ : 
$$
(D)
\left\{
\begin{array}{rcl}
4y_1+y_2+y_3\geqslant 20\\
1800y_1+11y_2+2y_3\geqslant 180\\
Min(40000y_1+200y_2+120y_3)&&
\end{array}
\right.$$

\begin{definition}
Soient $n$ et $p$ deux entiers strictement positifs, 
$A\in\M_{(p,n)}(\R)$, $B\in \M_{(p,1)}(\R)$ , $C\in\M_{(1,n)}(\R)$, $X={}^t(X_i)_{i\in[\![1 ; n]\!]}$
le vecteur colonne des indéterminées et le problème $(P)$  sous forme normal
$$(P)\left\{\begin{array}{c}
A.X \leqslant B\\
X\geqslant 0\\
Max(C.X)
\end{array}
\right.$$
On définit le \textbf{problème dual} de $(P)$ noté $(D)$ par:
$$(D)\left\{\begin{array}{c}
{}^tA.Y \geqslant {}^tC\\
Y\geqslant 0\\
Min({}^tB.Y)
\end{array}
\right.$$
où $Y={^t}(Y_i)_{i\in[\![1 ; p]\!]}$ est le vecteur colonne des indéterminées.

On dit que $(P)$ est le \textbf{problème primal} de $(D)$.

A un problème linéaire quelconque on associe un problème dual en considérant la forme normale du primal.
\end{definition}

Par exemple : 

\begin{proposition}
Soit $(P)-(D)$ une paire primale-duale.
\begin{enumerate}
\item Le nombre de variable du problème $(P)$ correspond au nombre de contrainte du problème $(D)$. Précisément :
\begin{enumerate}
\item Une variable positive donne une contrainte de type $\geqslant$.
\item Une variable négative donne une contrainte de type $\leqslant$.
\item Une variable non distinguée donne une contrainte de type $=$.
\end{enumerate}
\item Le nombre de contrainte du problème $(P)$ correspond au nombre de variable du problème $(D)$.
\begin{enumerate}
\item Une contrainte de type $\leqslant$ donne une variable positive.
\item Une contrainte de type $\geqslant$ donne une variable négative.
\item Une contrainte de type $=$ donne une variable non distinguée.
\end{enumerate}
\item Si $(P)$ est un problème de maximisation (resp. minimisation), $(D)$ est un problème de minimisation (resp. maximisation).
\end{enumerate}
Le problème $(P)$ est appelé problème primal.
\end{proposition}

\begin{demo}
Il suffit de se ramener à la forme normal des problèmes.
\end{demo}

\begin{proposition}
Le problème dual d'un problème dual est le problème primal.
\end{proposition}

\begin{demo}
Il suffit de se ramener aux définitions.
\end{demo}

\begin{theoreme}[(Dualité faible)]
Soit $(P)-(D)$ une paire primale-duale. S'il existe une solution admissible à $(P)$ et à $(D)$ alors la valeur de la fonction objectif de $(P)$ est inférieur à celle de $(D)$.
\end{theoreme}

L'interprétation de la dualité faible d'un point de vue économique est que le profit est toujours inférieur ou égale à la valeur des ressources. Dans notre exemple, cela signifie que le profit des ventes de la maison $Castor$ sera toujours plus petit que le prix d'achat des matière première par $Polux$.

\begin{theoreme}[(Dualité forte)]
Soit $(P)-(D)$ une paire primale-duale. 
\begin{description}
\item[$\bullet$] S'ils admettent tous les deux une solution admissible alors ils admettent tous les deux une solution optimale. Précisément l'optimum a la même valeur et la solution du dual correspond aux valeurs des variables d'écarts entrantes du primal en changeant leur signe.
\item[$\bullet$] Si le primal (resp. dual) est non borné alors le dual (resp. primal) n'admet pas de solution admissible 
\end{description}
\end{theoreme}

D'un point de vue économique, la dualité forte s'interprète en précisant que le profit est maximal lorsque toutes les ressources ont été exploité (jusqu'à épuisement de leur valeur).

Illustrons le premier point de ce théorème à l'aide l'exemple des maisons $Castor$ et $Polux$. 

\begin{multicols}2
Le problème primal est

$$
(P)
\left\{
\begin{array}{rcl}
4x_1+1800x_2&\leqslant& 40000\\
x_1+11x_2&\leqslant& 200\\
x_1+2x_2&\leqslant&120\\
Max(20x_1+180x_2)&&
\end{array}
\right.$$

\columnbreak
 et le problème dual est 
 $$
(D)
\left\{
\begin{array}{rcl}
4y_1+y_2+y_3\geqslant 20\\
1800y_1+11y_2+2y_3\geqslant 180\\
Min(40000y_1+200y_2+120y_3)&&
\end{array}
\right.$$
\end{multicols}

En appliquant la méthode du simplexe au primal on abouti au tableau suivant : 
$$
\begin{array}{c|ccccc|c}&x_{1}&x_{2}&e_{1}&e_{2}&e_{3}&\\\hline e_{1}&0&0&1&\dfrac{-1792}{9}&\dfrac{1756}{9}&\dfrac{212320}{9}\\ x_{2}&0&1&0&\dfrac{1}{9}&\dfrac{-1}{9}&\dfrac{80}{9}\\ x_{1}&1&0&0&\dfrac{-2}{9}&\dfrac{11}{9}&\dfrac{920}{9}\\ \hline Max &0&0&0&\dfrac{-140}{9}&\dfrac{-40}{9}&\dfrac{-32800}{9}\end{array}
$$
Nous avons donc que $\dpl{(x_1, x_2)=\left(\dfrac{920}{9}, \dfrac{80}{9}\right)}$ pour un optimum de $\dfrac{32800}{9}$. On observe en particulier que les variables d'écarts entrantes $\dpl{(e_1,e_2,e_3)=\left(0, -\dfrac{140}{9}, -\dfrac{40}{9}\right)}$. Le théorème de la dualité forte permet donc de conclure que le dual admet $\dpl{(y_1,y_2,y_3)=\left(0, \dfrac{140}{9}, \dfrac{40}{9}\right)}$ comme solution avec un optimum de $\dfrac{32800}{9}$.