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} } \)

Vers la méthode du simplexe

Le principe de la méthode du simplexe consiste à se placer dans un un cadre un peu plus algébrique et d'adapter la méthode de Gauss. Reprenons l'exemple précédent de la première section : le domaine est défini par les règles \begin{eqnarray*} A &\geqslant& 0\\ B &\geqslant& 0\\ 2A+4B&\leqslant& 200\\ 30A+15B&\leqslant& 1200 \end{eqnarray*} et on cherche à maximiser le bénéfice $ M=7A+6B$ .

Étape 1.

On va transformer les inéquations par des équations en introduisant des variables qui vont mesurer l'écart des inéquations. On les appelle les variables d'écarts. On pose \[X=200-2A-4B\qquad Y=1200-30A-15B\] On a donc introduit deux nouvelles variables et transformé le problème en \[(P_0) = \left\{ \begin{array}{lllll} 2A&+4B&+1X&+0Y&=200\\ 30A&+15B&+0X&+1Y&=1200 \end{array}\right.\] où $ A$ , $ B$ , $ X$ et $ Y$ sont positives ou nulle. On cherche à maximiser $ M=7A+6B+0X+0Y$ . Ce système de 4 inconnues à 2 équations (linéairement indépendantes) admet une infinité de solution. Le but est de trouver celle qui va maximiser $ M=7A+6B+0X+0Y$ .

Étape 2.

Le quadruplet $ (A,B,X,Y)=(0,0,200,1200)$ est une solution évidente au problème. Mais c'est le pire cas possible car les variables d'écarts sont les plus grandes possibles alors que dans l'idéal il faut qu'elles soient le plus petit possibles et inversement : les solutions $ A$ et $ B$ sont les plus petites possible alors qu'il faut qu'elles soient clairement les plus grandes possibles. Pour cette solution le bénéfice $ M$ est nul. On observe que si $ A$ ou $ B$ augmente alors $ M$ aussi. L'idée est donc de choisir une de ces variables et de l'augmenter au maximum des contraintes possibles.

Étape 2' - Bilan.

Le problème est \[(P_0) = \left\{ \begin{array}{lllll} 2A&+4B&+1X&+0Y&=200\\ 30A&+15B&+0X&+1Y&=1200 \end{array} \right.\] avec pour solution $ (A,B,X,Y)=(0,0,200,1200)$ . Les variables $ A$ et $ B$ sont nulles tandis que les variables $ X$ et $ Y$ ne le sont pas.

Étape 3.

On doit faire augmenter la valeur de $ M$ en choisissant une variable parmi $ A$ ou $ B$ . Puisque le coefficient de $ A$ est plus grand que celui de $ B$ , la valeur de $ M$ augmentera davantage si on augmente celle de $ A$ . On décide alors de laisser dans le quadruplet solution $ (A,B,X,Y)=(0,0,200,1200)$ le $ B$ à $ 0$ , et on va chercher la valeur maximale prise par $ A$ . Avec $ B=0$ le système devient : \[(P_0') = \left\{ \begin{array}{lllll} 2A&&+1X&+0Y&=200\\ 30A&&+0X&+1Y&=1200 \end{array} \right.\] soit encore \[(P_0') = \left\{ \begin{array}{lll} X&=&200-2A\\ Y&=&1200-30A \end{array} \right.\] or $ X\geqslant 0$ et $ Y\geqslant 0$ donc $ 200-2A\geqslant 0$ et $ 1200-30A\geqslant 0$ ce qui équivaut respectivement à $ A\leqslant 100$ et $ A\leqslant 40$ . Donc la plus grande valeur possible pour $ A$ est $ 40$ . Si $ A=40$ et $ B=0$ alors $ X=120$ et $ Y=0$ . A cette étape le quadruplet $ (A,B,X,Y)=(40,0,120,0)$ est solution du problème avec une valeur du bénéfice $ M=7A+6B=240$ .

Étape 4.

A l'étape 2' les variables $ X$ et $ Y$ étaient non nulles et apparaissaient une fois par ligne dans le problème. En appliquant la méthode de Gauss, on va modifier le problème pour que les variables $ A$ et $ X$ apparaissent une et une seule fois par ligne. La deuxième ligne reste donc inchangée et on applique à la première la règle $ L_1\leftarrow 15L_1-L_2$ . On obtient alors le nouveau système \[(P_1) = \left\{ \begin{array}{lllll} &+45B&+15X&-1Y&=1800\\ 30A&+15B&+0X&+1Y&=1200 \end{array} \right.\] De même l'expression du bénéfice $ M=7A+6B$ ne faisait apparaitre que les variables nulles de l'étape 2'. Ici on va donc chercher à exprimer M en fonction de $ B$ et $ Y$ . La deuxième ligne du problème nous donne $ A=40-\dfrac{1}{2}B-\dfrac{1}{30}Y$ . En injectant cette expression dans celle de $ M$ et en simplifiant on obtient $ M=280+\dfrac{5}{2}B-\dfrac{7}{30}Y$ .

Étape 4' - Nouveau bilan.

Le problème est \[(P_1) = \left\{ \begin{array}{lllll} &+45B&+15X&-1Y&=1800\\ 30A&+15B&+0X&+1Y&=1200 \end{array} \right.\] avec un quadruplet solution $ (A,B,X,Y)=(40,0,120,0)$ où les variables non nulles apparaissent une et une seule fois par ligne et où les variables nulles apparaissent dans la fonction de bénéfice $ M=280+\dfrac{5}{2}B-\dfrac{7}{30}Y$ qui vaut maintenant $ 280$ pour le quadruplet solution.

Étape 5.

On réitère ce que l'on a fait à l'étape 3 mais pour le nouveau problème $ P_1$ .

$ \bullet$: On choisit une des variables apparaissant dans l'expression du bénéfice $ M$ pour que celui-ci augmente. Puisque $ B$ et $ Y$ doivent, par contrainte, être positives et que le coefficient de $ Y$ est négatif, on choisit la variable $ B$ . On suppose donc que $ Y$ reste nulle et on cherche la plus grande valeur possible pour $ B$ .
$ \bullet$: Avec $ Y=0$ le système devient : \[(P_1') = \left\{ \begin{array}{lllll} &+45B&+15X&&=1800\\ 30A&+15B&+0X&&=1200 \end{array} \right.\] soit encore \[(P_1') = \left\{ \begin{array}{lll} X&=&120-3B\\ 2A&=&80-B \end{array} \right.\] et puisque $ X$ et $ A$ sont positif on aboutit à $ B\leqslant 40$ et $ B\leqslant 80$ . La plus grande valeur possible pour $ B$ est donc 40. Avec cette valeur $ X=0$ et $ A=20$ . Ainsi $ (A,B,X,Y)=(20,40,0,0)$ ¹.

Étape 6.

On modifie le problème pour que les variables nulles apparaissent dans l'expression de $ M$ et les variables non nulles apparaissent une fois par ligne dans le problème. \[(P_2)=\left\{ \begin{array}{lllll} &+45B&+15X&-1Y&=1800\\ 90A&&-15X&+4Y&=1800 \end{array} \right.\] en faisant $ L_2\leftarrow3L_2-L_1$ . Finalement $ \dpl{M=380-\frac{5}{6}X-\frac{8}{45}Y}$ .

Étape 7.

On s'arrête ! Les coefficients des variables apparaissant dans $ M$ sont tous négatifs ; si on modifie les variables liées à ces coefficient, on ne pourra pas augmenter la valeur du bénéfice. En conclusion : $ A=20$ , $ B=40$ et le bénéfice $ M=380$ .

Algorithmisation

Comme nous l'avons vu le problème consiste à trouver la meilleur solution (celle qui maximise le bénéfice) dans un système qui contient en générale une infinité de solution. Le principe est d'appliquer la méthode du pivot de Gauss en choisissant correctement les pivots à chaque étape. Détaillons le calcul précédent d'un point de vue plus algébrique.

Étape 1 & 2.: On utilise le langage des matrices pour exprimer le problème : \[ \begin{array}{c|cccc|c} &A&B&X&Y&\\\hline X&2&4&1&0&200\\ Y&30&15&0&1&1200\\\hline Ben&7&6&0&0&0 \end{array} \] Dans la première colonne, on a écrit le nom des variables que nous avons introduit pour la résolution du problème. On les appelle les variables hors base. Dans la dernière ligne on a traduit l'expression du bénéfice qui est donc nulle puisque $ X=200$ et $ Y=1200$ . On est au point $ (A,B)=(0,0)$ du domaine des solutions admissibles.
Étape 3 & 4.: Le problème étant posé, on cherche le meilleur pivot. Puisque le $ 7$ est le plus grand coefficient dans l'expression du bénéfice, on choisit la première colonne. On dit que $ A$ est la variable entrante. Pour choisir la ligne on va rajouter une colonne : \[ \begin{array}{c|cccc|c|c} &A&B&X&Y&&\\\hline X&2&4&1&0&200&\dpl{\frac{200}{2}}\\ Y&30&15&0&1&1200&\dpl{\frac{1200}{30}}\\\hline Ben&7&6&0&0&0& \end{array} \] où l'on a fait le rapport entre la colonne des coefficients, par la colonne choisit. Le plus petit est celui du $ Y$ qui vaut 40. On choisit donc la seconde ligne. On dit que $ Y$ est la variable sortante. Le pivot sera donc le coefficient de la deuxième ligne, première colonne. Dans la colonne des variables hors base (c'est à dire la première colonne), on change la variable sortante par la variable entrante. On applique la méthode du pivot : $ \dpl{L_2\leftarrow \frac{1}{30} L_2}$ $ \begin{array}{c|cccc|c} &A&B&X&Y&\\\hline X&2&4&1&0&200\\ A&1&\dpl{\frac{1}{2}}&0&\dpl{\frac{1}{30}}&40\\\hline Ben&7&6&0&0&0 \end{array}$ $ L_1\leftarrow L_1-2L_2$ $ \begin{array}{c|cccc|c} &A&B&X&Y&\\\hline X&0&3&1&\dpl{-\frac{1}{15}}&120\\ A&1&\dpl{\frac{1}{2}}&0&\dpl{\frac{1}{30}}&40\\\hline Ben&7&6&0&0&0 \end{array}$ $ \dpl{L_3 \leftarrow L_3 - 7L_2} $ $ \begin{array}{c|cccc|c} &A&B&X&Y&\\\hline X&0&3&1&\dpl{-\frac{1}{15}}&120\\ A&1&\dpl{\frac{1}{2}}&0&\dpl{\frac{1}{30}}&40\\\hline Ben&0&\dpl{\frac{5}{2}}&0&-\dpl{\frac{7}{30}}&-280 \end{array} $ On est au point $ (A,B)=(40,0)$ du domaine des solutions admissibles et le bénéfice est à $ 280$ . Le problème étant ramené à \[ \begin{array}{c|cccc|c} &A&B&X&Y&\\\hline X&0&3&1&\dpl{-\frac{1}{15}}&120\\ A&1&\dpl{\frac{1}{2}}&0&\dpl{\frac{1}{30}}&40\\\hline Ben&0&\dpl{\frac{5}{2}}&0&-\dpl{\frac{7}{30}}&-280 \end{array} \]
Étape 5 & 6.: On recommence : \[ \begin{array}{c|cccc|c|c} &A&B&X&Y&&\\\hline X&0&3&1&\dpl{-\frac{1}{15}}&120&\dpl{\frac{120}{3}}\\ A&1&\dpl{\frac{1}{2}}&0&\dpl{\frac{1}{30}}&40&\dpl{\frac{40}{\frac{1}{2}}}\\\hline Ben&0&\dpl{\frac{5}{2}}&0&-\dpl{\frac{7}{30}}&-280& \end{array} \] La variable entrante est $ B$ et la sortante est $ X$ . Le pivot est donc le $ 3$ . $ \dpl{L_1\leftarrow\frac{1}{3}L_1}$ $ \begin{array}{c|cccc|c} &A&B&X&Y&\\\hline B&0&1&\dpl{\frac{1}{3}}&\dpl{-\frac{1}{45}}&\dpl{40}\\ A&1&\dpl{\frac{1}{2}}&0&\dpl{\frac{1}{30}}&40\\\hline Ben&0&\dpl{\frac{5}{2}}&0&-\dpl{\frac{7}{30}}&-280 \end{array} $ $ \dpl{L_2\leftarrow L_2-\frac{1}{2}L_1}$ $ \begin{array}{c|cccc|c} &A&B&X&Y&\\\hline B&0&1&\dpl{\frac{1}{3}}&\dpl{-\frac{1}{45}}&40\\ A&1&0&-\dpl{\frac{1}{6}}&\dpl{\frac{2}{45}}&20\\\hline Ben&0&\dpl{\frac{5}{2}}&0&-\dpl{\frac{7}{30}}&-280 \end{array} $ $ \dpl{L_3\leftarrow L_3-\frac{5}{2}L_1}$ $ \begin{array}{c|cccc|c} &A&B&X&Y&\\\hline B&0&1&\dpl{\frac{1}{3}}&\dpl{-\frac{1}{45}}&40\\ A&1&0&-\dpl{\frac{1}{6}}&\dpl{\frac{2}{45}}&20\\\hline Ben&0&0&\dpl{-\frac{5}{6}}&-\dpl{\frac{8}{45}}&-380 \end{array} $ On est au point $ (A,B)=(20,40)$ du domaine des solutions admissibles et le bénéfice est à $ 380$ . Le problème est ramené à \[\begin{array}{c|cccc|c} &A&B&X&Y&\\\hline B&0&1&\dpl{\frac{1}{3}}&\dpl{-\frac{1}{45}}&40\\ A&1&0&-\dpl{\frac{1}{6}}&\dpl{\frac{2}{45}}&20\\\hline Ben&0&0&\dpl{-\frac{5}{6}}&-\dpl{\frac{8}{45}}&-380 \end{array}\]
Étape 7.: On s'arrête car tous les coefficient de la dernière ligne sont négatifs ou nuls.

¹On peut s'arrêter ici car on observe que $ X$ et $ Y$ sont les plus petits possible ; mais continuons pour comprendre le principe de l'algorithme.