Ataraxy

\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

Dualité

Considérons le problème linéaire suivant :

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$ € et une encyclopédie $ 180$ €. La maison d'édition possède quatre millions de pages blanches, $ 200$ cartouches d'encre et de $ 120$ heures de temps d'impression.

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

$ \bullet$: $ y_1$ le prix de vente par $ Castor$ d'une page blanche à $ Polux$
$ \bullet$: $ y_2$ le prix pour une cartouche d'encre,
$ \bullet$: $ y_3$ le prix pour une heure d'impression.

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.

$ \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$ €. \[4y_1+y_2+y_3\geqslant 20\]
$ \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$ €. \[1800y_1+11y_2+2y_3\geqslant 180\]

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.\]

Définition

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 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 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.

Par exemple :

Proposition

Soit $ (P)-(D)$ une paire primale-duale.

Le nombre de variable du problème $ (P)$ correspond au nombre de contrainte du problème $ (D)$ . Précisément :
1. Une variable positive donne une contrainte de type $ \geqslant$ .
2. Une variable négative donne une contrainte de type $ \leqslant$ .
3. Une variable non distinguée donne une contrainte de type $ =$ .
Le nombre de contrainte du problème $ (P)$ correspond au nombre de variable du problème $ (D)$ .
1. Une contrainte de type $ \leqslant$ donne une variable positive.
2. Une contrainte de type $ \geqslant$ donne une variable négative.
3. Une contrainte de type $ =$ donne une variable non distinguée.
Si $ (P)$ est un problème de maximisation (resp. minimisation), $ (D)$ est un problème de minimisation (resp. maximisation).

Le problème $ (P)$ est appelé problème primal.

Démonstration

Il suffit de se ramener à la forme normal des problèmes.

Proposition

Le problème dual d'un problème dual est le problème primal.

Démonstration

Il suffit de se ramener aux définitions.

Théorème [(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)$ .

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$ .

Théorème [(Dualité forte)]

Soit $ (P)-(D)$ une paire primale-duale.

$ \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.
$ \bullet$: Si le primal (resp. dual) est non borné alors le dual (resp. primal) n'admet pas de solution admissible

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$ . 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.\] 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.\] 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}$ .