Correction dans la structure de la trace d'execution.

[Projet_Recherche_Operationnelle.git] / rapport / ProjetOptimRO.tex

diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex
index 372670f6167b036fa74ce7f8913ff20c2a746fdd..85ec36eaedc21ee8a665d2c8ac7a828d83df3cb4 100644 (file)
--- a/rapport/ProjetOptimRO.tex
+++ b/rapport/ProjetOptimRO.tex
@@ -21,6 +21,8 @@
 \usepackage{tocbibind}
 \usepackage{lmodern}
 \usepackage{enumitem}
+\usepackage{algorithm2e}
+\usepackage{algorithmic}
 
 
 %%%%%Marges & en-t\^etes
@@ -788,7 +790,7 @@ Le Lagrangien $ L $ de $ \mathcal{P} $ : $$ L((x,y,z),(\lambda_1,\lambda_2)) = x
 \newline
 Le gradient de $ J $ : $$ \nabla J(x,y,z) = (\frac{\partial J}{\partial x}(x,y,z),\frac{\partial J}{\partial y}(x,y,z),\frac{\partial J}{\partial z}(x,y,z)) = (2x,2y,2z). $$
 \newline
-Le gradient de $ g $ : $$ \nabla g(x,y,z) = (\nabla g_1(x,y,z),\nabla g_2(x,z,z)) $$
+Le gradient de $ g $ : $$ \nabla g(x,y,z) = (\nabla g_1(x,y,z),\nabla g_2(x,y,z)) $$
 $$ = ((\frac{\partial g_1}{\partial x}(x,y,z),\frac{\partial g_1}{\partial y}(x,y,z),\frac{\partial g_1}{\partial z}(x,y,z)),(\frac{\partial g_2}{\partial x}(x,y,z),\frac{\partial g_2}{\partial y}(x,y,z),\frac{\partial g_2}{\partial z}(x,y,z)) $$
 $$ = ((2x,2y,0),(2x,0,2z)). $$
 \newline
@@ -808,6 +810,88 @@ La matrice hessienne de $ J $ : $$ H[J](x,y,z) =
  \end{pmatrix} = 2Id_{\mathbb{R}^3} $$
 On en déduit que $ H[J](x,y,z) $ est inversible et que $ H[J](x,y,z)^{-1} = \frac{1}{2}Id_{\mathbb{R}^3} $.
 
+\subsection{Trace d'éxécution de l'algorithme PQS}
+
+En utilisant le problème $ \mathcal{P} $ précédent :
+\newline
+\textit{Entrées} : $ J $ et $ g $ de classe $ \mathcal{C}^2 $, $ \varepsilon = 0.01 $, $ (x_0,y_0,z_0) = (80, 20, 60)$  et $(\lambda_{0_1},\lambda_{0_2}) = (1, 1)$, les rayons : $r = 40$ et $r_1 = r_2 = 10$.
+\newline
+Calcul du Lagrangien $ L $ de $ \mathcal{P} $ en $ (x_0,y_0,z_0)$ :
+\newline
+$ L((80,20,60),(1,1)) = 80^2 + 20^2 + 60^2 -60^2 + 1 * (80^2 +20y^2 - 30^2) + \lambda_2(80^2 + 60^2 -30^2), $
+\newline
+$ L((80,20,60),(1,1)) = 6400 + 400 + 3600 - 3600 + (6400 + 400 - 900) + (6400 + 3600 -900), $
+\newline
+$ L((80,20,60),(1,1)) = 21800. $
+
+\begin{algorithm}
+ \caption {Algorithme PQS pour $ \mathcal{P} $}
+ \begin{algorithmic}
+  \REQUIRE $\varepsilon = 0.01$, $g(x,y,z)\leq 0$, $(x_0,y_0,z_0) = (80, 20 ,60)$, $(\lambda_{0_1},\lambda_{0_2}) = (1, 1)$, $r = 40$ et $r_1 = r_2 = 10$.
+  \ENSURE $\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2$ and \newline
+  $g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 $
+
+  \STATE \textbf{Data :}
+  \STATE $k \leftarrow 0$
+  \STATE $(x_k,y_k,z_k) \leftarrow (80,20,60)$
+  \STATE $ H[J](x,y,z)^{-1} \leftarrow
+   \begin{pmatrix}
+    0.5 & 0   & 0   \\
+    0   & 0.5 & 0   \\
+    0   & 0   & 0.5 \\
+   \end{pmatrix} $
+
+  \WHILE{($\norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon$ or $k < 10$)}
+
+  \STATE {//Première itération :}
+
+  \STATE{//Calcul du gradient de $ J $ :}
+  \STATE $\nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (160,40,120) $
+
+  \STATE {//Calcul des deux composantes du gradient de $ g $ :}
+  \STATE $\nabla g_1(x_k,y_k,z_k) = ((2x_k,2y_k,0)$ \hfill $ //résultat : (60, 20, 0)$
+  \STATE $\nabla g_2(x_k,y_k,z_k) = (2x_k,0,2z_k))$ \hfill $ //résultat : (60, 0, 80)$
+  \STATE $\nabla g(x_k,y_k,z_k) = (\nabla g_1(x_k,y_k,z_k), \nabla g_2(x_k,y_k,z_k))$
+
+  \STATE {//Calcul du gradient de $ L $ :}
+  \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k) $ \hfill $ //résultat : (280, 60, 200)$
+
+  \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
+  \STATE $ d_k = -H[J](x,y,z)^{-1}*\nabla J(x,y,z)$ \hfill $ //résultat : (-(80,20,60))$
+
+  \STATE {//Calcul des nouvelles valeurs des coordonnées :}
+  \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (0,0,0)$
+
+  \STATE {//Deuxième itération :}
+
+  \STATE {//Incrémentation de k}
+  \STATE $ k \leftarrow k+1$ \hfill $ //résultat : 1$
+
+  \STATE{//Calcul du gradient de $ J $ :}
+  \STATE $\nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (0,0,0) $
+
+  \STATE {//Calcul des deux composantes du gradient de $ g $ :}
+  \STATE $\nabla g_1(x_k,y_k,z_k) = ((2x_k,2y_k,0)$ \hfill $ //résultat : (60, 20, 0)$
+  \STATE $\nabla g_2(x_k,y_k,z_k) = (2x_k,0,2z_k))$ \hfill $ //résultat : (60, 0, 80)$
+  \STATE $\nabla g(x_k,y_k,z_k) = (\nabla g_1(x_k,y_k,z_k), \nabla g_2(x_k,y_k,z_k))$
+
+  \STATE {//Calcul du gradient de $ L $ :}
+  \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $ //résultat : (160, 20, 30)$
+
+  \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
+  \STATE $ d_k = -H[J](x_k,y_k,z_k)^{-1} * \nabla J(x,y,z)$ \hfill $ //résultat : (-(0,0,0))$
+
+  \STATE {//Calcul des nouvelles valeurs des coordonnées :}
+  \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (0,0,0)$
+
+  \ENDWHILE
+
+ \end{algorithmic}
+\end{algorithm}
+
+
+\hrulefill
+
 \bibliographystyle{plain}
 \bibliography{stdlib_sbphilo}