| 1 | \documentclass[12pt,oneside,a4paper]{book} |
| 2 | |
| 3 | |
| 4 | %%%%%Packages |
| 5 | |
| 6 | |
| 7 | \usepackage{latexsym} |
| 8 | \usepackage{amsmath} |
| 9 | \usepackage{mathtools} |
| 10 | \usepackage{amssymb} |
| 11 | \usepackage[utf8]{inputenc} |
| 12 | \usepackage[francais]{babel} |
| 13 | \usepackage{color} |
| 14 | \usepackage{geometry} |
| 15 | \usepackage{graphicx} |
| 16 | \usepackage{amsfonts} |
| 17 | \usepackage[T1]{fontenc} |
| 18 | \usepackage{multirow} |
| 19 | \usepackage{fancyhdr} |
| 20 | \usepackage{tocbibind} |
| 21 | \usepackage{lmodern} |
| 22 | |
| 23 | |
| 24 | %%%%%Marges & en-t\^etes |
| 25 | |
| 26 | \geometry{hmargin=2.3cm, vmargin=3cm} |
| 27 | \fancyhf{} % supprime les en-t\^etes et pieds pr\'ed\'efinis |
| 28 | \fancyhead[FC]{\bfseries\thepage} % N∞page centre bas |
| 29 | \fancyhead[HC]{\footnotesize\leftmark} % chapitre centre haut |
| 30 | \renewcommand{\headrulewidth}{0.2pt} % filet en haut |
| 31 | \addtolength{\headheight}{0.5pt} % espace pour le filet |
| 32 | \renewcommand{\footrulewidth}{0.2pt} % filet en bas |
| 33 | |
| 34 | |
| 35 | %%%%%Th\'eor\`eme et d\'efinitions |
| 36 | |
| 37 | \newtheorem{Def}{D\'efinition} |
| 38 | \newtheorem{Not}[Def]{Notation} |
| 39 | \newtheorem{Th}{Th\'eor\`eme} |
| 40 | \newtheorem{Prop}[Th]{Proposition} |
| 41 | \newtheorem{Cor}[Th]{Corollaire} |
| 42 | \newtheorem{Rmq}{Remarque} |
| 43 | |
| 44 | \newcommand{\norme}[1]{\left\Vert #1\right\Vert} |
| 45 | |
| 46 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 47 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 48 | |
| 49 | \begin{document} |
| 50 | |
| 51 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 52 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 53 | |
| 54 | %%%%%Page de garde |
| 55 | |
| 56 | \begin{center} |
| 57 | |
| 58 | %\includegraphics[scale=0.5]{logo_sciences_rvb.png}\\ |
| 59 | \includegraphics[scale=0.5]{polytech.png}\\ |
| 60 | |
| 61 | \vspace*{0.5cm} |
| 62 | |
| 63 | \footnotesize{ |
| 64 | \large \bf D\'epartement d'Informatique, Réseaux et Multimédia\\ |
| 65 | \large \bf 5ème année\\ |
| 66 | } |
| 67 | |
| 68 | \vspace*{0.5cm} |
| 69 | |
| 70 | %\large{Master 2 Professionnel\\ |
| 71 | %Math\'ematiques et Informatique des Nouvelles Technologies\\} |
| 72 | |
| 73 | \large{Projet \\ en \\ Optimisation et Recherche Opérationnelle \\} |
| 74 | |
| 75 | \vspace*{0.7cm} |
| 76 | |
| 77 | \begin{tabular}{c} |
| 78 | \hline |
| 79 | ~ \\ |
| 80 | \LARGE\textbf {Programmation Séquentielle Quadratique} \\ |
| 81 | \LARGE\textbf {en} \\ |
| 82 | \LARGE\textbf {Optimisation non linéraire sous contraintes} \\ |
| 83 | ~ \\ |
| 84 | \hline |
| 85 | \end{tabular} |
| 86 | |
| 87 | \vspace*{0.7cm} |
| 88 | |
| 89 | \includegraphics[scale=0.4]{CE.PNG}\\ |
| 90 | |
| 91 | \vspace*{0.5cm} |
| 92 | |
| 93 | \large par\\ |
| 94 | |
| 95 | %\large \bsc{}\\ |
| 96 | %\normalsize{M\'emoire encadr\'e par :} \large St\'ephane \bsc{Ballet}\\ |
| 97 | |
| 98 | \vspace*{0.2cm} |
| 99 | \large {\bf Jérôme \bsc{Benoit} et Sylvain \bsc{Papa}}\\ |
| 100 | |
| 101 | %\vspace*{0.1cm} |
| 102 | |
| 103 | % \large sous la direction de \\ |
| 104 | |
| 105 | %\vspace*{0.1cm} |
| 106 | |
| 107 | %Eric Audureau et Thierry Masson |
| 108 | |
| 109 | %\vspace*{1cm} |
| 110 | |
| 111 | \vspace*{1cm} |
| 112 | |
| 113 | %\normalsize{Licence de Mathématiques 3ème année} |
| 114 | \normalsize{Année 2018-2019} |
| 115 | |
| 116 | \end{center} |
| 117 | |
| 118 | \thispagestyle{empty} |
| 119 | |
| 120 | \newpage |
| 121 | |
| 122 | |
| 123 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 124 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 125 | |
| 126 | |
| 127 | \pagestyle{plain} |
| 128 | \frontmatter |
| 129 | |
| 130 | |
| 131 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 132 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 133 | |
| 134 | |
| 135 | %%%%%Table des mati\`eres |
| 136 | |
| 137 | \tableofcontents |
| 138 | |
| 139 | \begin{figure}[!b] |
| 140 | \begin{center} |
| 141 | %\includegraphics{logo_fac2} |
| 142 | \includegraphics[scale=0.04]{amu} |
| 143 | \end{center} |
| 144 | \end{figure} |
| 145 | |
| 146 | \newpage |
| 147 | |
| 148 | |
| 149 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 150 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 151 | |
| 152 | |
| 153 | \mainmatter |
| 154 | \pagestyle{fancy} |
| 155 | |
| 156 | |
| 157 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 158 | \chapter{Introduction générale} |
| 159 | |
| 160 | \vspace{.5em} |
| 161 | |
| 162 | \section{Qu'est-ce que la recherche opérationnelle?} |
| 163 | |
| 164 | \subsection{Présentation rapide} |
| 165 | |
| 166 | La recherche opérationnelle est une discipline dite "hybride" au confluent de plusieurs disciplines dont principalement les mathématiques (l'analyse numérique, les probabilités, la statistique) et l'informatique (l'algorithmie). |
| 167 | \newline |
| 168 | On la considère usuellement comme une sous discipline des mathématiques de la décision. Elle a de nombreuses applications, particulièrement en intelligence artificielle. |
| 169 | |
| 170 | \subsection{Définition de la problèmatique} |
| 171 | |
| 172 | Définissons le problème central $ \mathcal{P} $ que se propose de résoudre la recherche opérationnelle : |
| 173 | \begin{Def} |
| 174 | Soient $(n, p, q) \in \mathbb{N}^3$, $x \in \mathbb{R}^n$, une fonction $g: \mathbb{R}^n \longrightarrow \mathbb{R}^p$ représentant les contraintes d'inégalités, une fonction $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$ représentant les contraintes d'égalités et une fonction dite objectif $J: \mathbb{R}^n \longrightarrow \mathbb{R}$. |
| 175 | \newline |
| 176 | La problèmatique $ \mathcal{P} $ se définit par : |
| 177 | $$ |
| 178 | \mathcal{P} \left \{ |
| 179 | \begin{array}{r c l} |
| 180 | \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\ |
| 181 | g(x) \leq 0 \\ |
| 182 | h(x) = 0 |
| 183 | \end{array} |
| 184 | \right . |
| 185 | $$ |
| 186 | \end{Def} |
| 187 | \begin{Def} |
| 188 | On définit $ \mathcal{C} $ l'ensemble des contraintes par : |
| 189 | $$ \mathcal{C} = \left \{ x \in \mathbb{R}^n \ | \ g(x) \leq 0 \land h(x) = 0 \right \} $$ |
| 190 | \end{Def} |
| 191 | Elle se doit de résoudre les problèmes d'existence d'une solution ($ \mathcal{C} \neq \emptyset $ et $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $ défini dans $ \mathcal{C} $) ainsi que de construction d'une solution dans $ \mathcal{C} $. |
| 192 | |
| 193 | \section{Qu'est-ce que l'optimisation?} |
| 194 | |
| 195 | \subsection{Définition} |
| 196 | |
| 197 | La recherche d'une méthode permettant de trouver la solution au problème $ \mathcal{P} $ dans $ \mathcal{C} $ est l'activité principale de l'optimisation. |
| 198 | \newline |
| 199 | Si la modélisation de la problèmatique $ \mathcal{P} $ est considérée comme un art, la recherche d'une solution au problème $ \mathcal{P} $ dans $ \mathcal{C} $ est, elle, une science. |
| 200 | |
| 201 | \subsection{Quelques définitions annexes} |
| 202 | |
| 203 | Définissons quelques notions supplémentaires de base nécessaires à la suite : |
| 204 | \begin{Def} |
| 205 | Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $. |
| 206 | \newline |
| 207 | On dit que $ x^\ast $ est \textbf{intérieur} à $ A $ si $ A $ est un voisinage de $ x^\ast $. On appelle intérieur de $ A $ l'ensemble des points intérieurs à $ A $ et on le note $ \mathring{A} $. |
| 208 | \end{Def} |
| 209 | \begin{Def} |
| 210 | Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $. |
| 211 | \newline |
| 212 | On dit que $ x^\ast $ est \textbf{adhérent} à $ A $ si et seulement si $ \forall V \in \mathcal{V}(x^\ast) \ A \cap V \neq \emptyset $. On appelle adhérence de $ A $ l'ensemble des points adhérents à $ A $ et on le note $ \overline{A} $. |
| 213 | \end{Def} |
| 214 | |
| 215 | \begin{Def} |
| 216 | Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $. |
| 217 | \newline |
| 218 | On dit que $ f $ est continue en $ x^\ast $ si |
| 219 | $$ \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \exists \alpha \in \mathbb{R}_{+}^{*} \ \forall x \in \mathbb{R}^n \ \norme{x - x^\ast} \leq \alpha \Longrightarrow |f(x) - f(x^\ast)| \leq \varepsilon $$ |
| 220 | \end{Def} |
| 221 | \begin{Def} |
| 222 | Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $. |
| 223 | \newline |
| 224 | On dit que la $ k^{ième} $ dérivée partielle de $ f $ existe au point $ x^\ast \in \mathbb{R}^n $ si l’application |
| 225 | $$ t \longmapsto f(x^\ast_1,\ldots,x^\ast_{k-1},x^\ast_k + t,x^\ast_{k+1},\ldots,x^\ast_n) $$ |
| 226 | définie sur un voisinage de $ 0 $ dans $ \mathbb{R} $ et à valeurs dans $ \mathbb{R} $ est dérivable en $ 0 $. |
| 227 | \newline |
| 228 | Dans ce cas on note |
| 229 | $$ \frac{\partial f}{\partial x_k}(x^\ast) $$ ou $$ \partial_k f(x^\ast) $$ |
| 230 | cette dérivée. |
| 231 | \end{Def} |
| 232 | \begin{Def} |
| 233 | Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ |
| 234 | et $ x^\ast, h \in \mathbb{R}^n $. |
| 235 | \newline |
| 236 | On dit que $ f $ est différentiable en $ x^\ast $ si il existe une application linéraire $ d_{x^\ast}f $ de $ \mathbb{R}^n $ dans $ \mathbb{R} $ telle que |
| 237 | \[ |
| 238 | f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \underset{h \rightarrow 0}{\mathrm{o}}(\norme{h}) |
| 239 | \] |
| 240 | Autrement dit il existe une application $ \varepsilon_{x^\ast} $ définie sur le voisinage de $ 0 $ dans $ \mathbb{R}^n $ et à valeurs dans $ \mathbb{R} $ |
| 241 | telle que $ \lim\limits_{h \rightarrow 0} \varepsilon_{x^\ast}(h) = 0 $ et |
| 242 | \[ |
| 243 | f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \norme{h}\varepsilon_{x^\ast}(h) |
| 244 | \] |
| 245 | On appelle $ d_{x^\ast}f $ la différentielle de $ f $ en $ x^\ast $. |
| 246 | \end{Def} |
| 247 | \begin{Rmq} |
| 248 | On peut démontrer que : $$ d_{x^\ast}f = \sum_{i=1}^n\frac{\partial f}{\partial x_i}(x^\ast) $$. |
| 249 | \end{Rmq} |
| 250 | \begin{Def} |
| 251 | Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable. |
| 252 | \newline |
| 253 | Le gradient de $ f $, noté $\nabla f$, en $ x^\ast \in \mathbb{R}^n$ se définit par : |
| 254 | \[ |
| 255 | \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast)) |
| 256 | \] |
| 257 | \end{Def} |
| 258 | \begin{Rmq} |
| 259 | $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle $ |
| 260 | \end{Rmq} |
| 261 | |
| 262 | \subsection{Conditions d'existence d'un extremum} |
| 263 | |
| 264 | On peut démontrer que $ \mathcal{C }$ est un ensemble fermé de $ \mathbb{R}^n $ si $ g $ et $ h $ sont continues. |
| 265 | On peut en déduire que si $ J $ est continue, $ \mathcal{C }$ est un ensemble fermé et borné de $ \mathbb{R}^n $. |
| 266 | \begin{Th}[Théorème de Weierstrass] |
| 267 | Soient $ \mathcal{C} \neq \emptyset \subset \mathbb{R}^n $ un fermé borné et $ f : \mathcal{C} \longrightarrow \mathbb{R} $ une fonction continue. |
| 268 | \newline |
| 269 | Alors $$ \exists x^\ast \in \mathcal{C} \ \forall x \in \mathcal{C} \ f(x) \geq f(x^\ast) $$ |
| 270 | Autrement dit $ x^\ast $ est un minimum global de $ J $ sur $ \mathcal{C} $. |
| 271 | \newline |
| 272 | De la même façon, il existe maximum global de $ J $ sur $ \mathcal{C} $. |
| 273 | \end{Th} |
| 274 | On en déduit que $ \mathcal{P} $ admet au moins une solution dans le cas où $ J, g ,h $ sont continues. |
| 275 | \subsection{Conditions de caractérisation d'un extremum} |
| 276 | |
| 277 | Dans le cas où $ J, g, h $ sont continûment différentiable et ses dérivées sont continues (c'est à dire de classe $ \mathcal{C}^1 $), la recherche du mimimum consiste à faire une descente par gradient de $ J $ sur $ \mathcal{C} $ avec comme critère d'arrêt : $ \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \norme{\nabla J(x^\ast)} < \varepsilon $. |
| 278 | \newline |
| 279 | On peut en déduire que une condition nécessaire et suffisante pour que $ x^\ast \in \mathring{\mathcal{C}} $ soit un des extremums locaux de $ J $ est que $ \nabla J(x^\ast) = 0 $. Mais si $ x^\ast \in \overline{\mathcal{C}}\setminus\mathring{\mathcal{C}} $ (la frontière de $ \mathcal{C} $) alors $ \nabla J(x^\ast) $ n'est pas nécessairement nul. Il sera par conséquent nécessaire de trouver d'autres caratérisations d'un extremum. |
| 280 | |
| 281 | \subsubsection{Conditions de Kuhn-Tucker et Lagrange} |
| 282 | |
| 283 | \begin{Th} |
| 284 | Soient $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $. |
| 285 | \newline |
| 286 | Une condition nécessaire pour que $ x^\ast \in \mathcal{C}$ soit un minimum local est : |
| 287 | \newline |
| 288 | \newline |
| 289 | \centerline{$ \{ \nabla g_1(x^\ast),\ldots,\nabla g_p(x^\ast),\nabla h_1(x^\ast),\ldots,\nabla h_q(x^\ast) \} $ sont linéairement indépendants.} |
| 290 | \newline |
| 291 | \newline |
| 292 | et |
| 293 | $$ \forall i \in I \ \exists \mu_i \in \mathbb{R}_{+} \land \forall j \in J \ \exists \lambda_j \in \mathbb{R} \ \nabla J(x^\ast) + \sum_{i \in I}\mu_i{\nabla g_i(x^\ast)} + \sum_{j \in J}\lambda_j{\nabla h_j(x^\ast)} = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $$ |
| 294 | On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange. |
| 295 | \end{Th} |
| 296 | Il est à noter que une condition d'égalité peut se répresenter par deux conditions d'inégalité : $ \forall x \in \mathbb{R}^n \ \forall i \in \{ 1,\ldots,q \} \ h_i(x) = 0 \Longleftrightarrow h_i(x) \leq 0 \land h_i(x) \geq 0 $. |
| 297 | \newline |
| 298 | \newline |
| 299 | Dans ce projet, nous nous proposons d'étudier une des méthodes d'optimisation non linéaire avec contraintes nommée programmation quadratique séquentielle. |
| 300 | |
| 301 | % Dans cette section nous prenons appui sur l'ouvrage {\it Optimisation et contrôle des systèmes linéaires} \cite{Berg} de Maïtine Bergounioux \footnote{Maïtine Bergounioux, {\it Optimisation et contrôle des systèmes linéaires}, Dunod, 2001.}. |
| 302 | % Nous utiliserons aussi l'ouvrage de Francis Filbet\footnote{Francis Filbet, {\it Analyse numérique - Algorithme et étude mathématique}, Dunod, 2009.}, {\it Analyse numérique - Algorithme et étude mathématique} \cite{Filb}. |
| 303 | |
| 304 | %{\it La relativité}, Que sais-je?, 4ème édition, puf, 2000, \cite{Mavr}; |
| 305 | %ainsi que Jean Hladik, {\it La relativité selon Einstein}, L'esprit des sciences, Ellipses, 2000, \cite{Hlad}. |
| 306 | |
| 307 | |
| 308 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 309 | |
| 310 | \chapter{Méthodes de programmation quadratique séquentielle} |
| 311 | |
| 312 | % \section{Cahier des charges} |
| 313 | % |
| 314 | % Il s'agit de travailler en binôme ou bien seul sur des sujets complémentaires et d'approfondissement du cours. Le travail en question effectué durant les TDs consistera |
| 315 | % à effectuer un dossier sur un thème. Le dossier devra être tapé en Latex ou Tex puisque il peut y avoir des formules de mathématiques ou de physiques. Il pourra aussi comporter une partie "implémentation effective" d'algorithmes (en annexe). |
| 316 | % |
| 317 | % \vspace{.5em} |
| 318 | % |
| 319 | % Sur la fond, toutes les sources de connaissance utilisées devront être citées. En particulier, la méthodologie universitaire sera privilégiée |
| 320 | % (citations en note de bas de page et dans le corps du document, liste des références en fin de document dans la bibliographie, etc...). |
| 321 | % Wikipédia pourra être utilisé mais cela devra être mentionné en tant que référence (note de bas de page ou citation dans le corps du document). |
| 322 | % L'accent sera essentiellement mis sur la démarche scientifique utilisée à égal niveau avec le contenu acquis des connaissances. |
| 323 | % |
| 324 | % \vspace{.5em} |
| 325 | % |
| 326 | % Plusieurs sources devront être croisées afin de prétendre au maximum de vraisemblance |
| 327 | % et d'objectivité scientifique. Le document ne devra pas excéder 10 pages. |
| 328 | % On privilégiera les qualités de synthèse, d'organisation ainsi que du contenu du document. |
| 329 | % |
| 330 | % \section{Proposition de sujets} |
| 331 | % |
| 332 | % \subsection{Analyse numérique} |
| 333 | % |
| 334 | % \vspace{.5em} |
| 335 | % |
| 336 | % 1) Méthode des moindres Carrés (cas général, cas pondéré, cas des équations non linéaires). |
| 337 | % |
| 338 | % \vspace{.5em} |
| 339 | % |
| 340 | % 2) Méthode de Newton-Raphson (cas d'une variable, cas de deux variables) - Application: extrema d'une fonction à deux variables. |
| 341 | % |
| 342 | % \vspace{.5em} |
| 343 | % |
| 344 | % 3) Autres méthodes: méthode de Jacobi, de Gauss-Seidel, etc.... |
| 345 | % |
| 346 | % \vspace{.5em} |
| 347 | |
| 348 | \section{Optimisation} |
| 349 | |
| 350 | % \vspace{.5em} |
| 351 | |
| 352 | % \subsubsection{Optimisation sans contrainte} |
| 353 | % |
| 354 | % {\bf A- Algorithmes déterministes} |
| 355 | % |
| 356 | % \vspace{.5em} |
| 357 | % |
| 358 | % 1) Régression linéaire sans contrainte (pré-requis: Méthode des moindres carrés). |
| 359 | % |
| 360 | % \vspace{.5em} |
| 361 | % |
| 362 | % 2) Méthodes de descente: la méthode du gradient (à pas constant ou à pas variable ou à pas optimal). |
| 363 | % |
| 364 | % \vspace{.5em} |
| 365 | % |
| 366 | % 3) Méthode de Newton (ou méthode dite de la tangente) et application à la recherche d'extrema. |
| 367 | % |
| 368 | % \vspace{.5em} |
| 369 | % |
| 370 | % 4) Méthodes de descente: méthode du gradient conjugué (cas linéaire et cas général) |
| 371 | % |
| 372 | % \vspace{.5em} |
| 373 | % |
| 374 | % 5) Méthode de relaxation |
| 375 | % |
| 376 | % \vspace{.5em} |
| 377 | % |
| 378 | % {\bf B- Algorithmes probabilistes ou dit stochastiques} |
| 379 | % |
| 380 | % \vspace{.5em} |
| 381 | % |
| 382 | % 1) Dynamique de métropolis (prérequis: chaines de Markov) |
| 383 | % |
| 384 | % \vspace{.5em} |
| 385 | % |
| 386 | % 2) Recuit simulé sur un ensemble fini et application au problème du voyageur de commerce (prérequis: dynamique de métropolis) |
| 387 | % |
| 388 | % \vspace{.5em} |
| 389 | |
| 390 | \subsubsection{Optimisation ou minimisation avec contraintes} |
| 391 | |
| 392 | % \vspace{.5em} |
| 393 | % |
| 394 | % 1) Régression linéaire avec contraintes (prérequis: méthode des moindres carrés, conditions ou équations dites de Karush-kuhn-Tucker (KKT)) . |
| 395 | % |
| 396 | % \vspace{.5em} |
| 397 | % |
| 398 | % 2) Cas de la programmation linéaire (prérequis: Lagrangien et multiplicateurs de Lagrange, conditions de KKT). |
| 399 | % |
| 400 | % \vspace{.5em} |
| 401 | % |
| 402 | % 3) Algorithmes: méthode du gradient projeté, méthode de Lagrange-Newton pour des contraintes en égalité, |
| 403 | % méthode de Newton projetée pour des contraintes de bornes, méthodes de pénalisation, |
| 404 | % méthodes de programmation quadratique successive (SQP Sequential Quadratic Programming), |
| 405 | % méthode de dualité (méthode d'Uzawa, prérequis: théorie de la dualité convexe) etc... |
| 406 | % |
| 407 | % \vspace{.5em} |
| 408 | % |
| 409 | % \subsection{Recherche opérationnelle} |
| 410 | % |
| 411 | % \vspace{.5em} |
| 412 | % |
| 413 | % \subsubsection{La programmation linéaire (cas particulier de l'optimisation avec contraintes)} |
| 414 | % |
| 415 | % 1) Méthode d'énumération. |
| 416 | % |
| 417 | % \vspace{.5em} |
| 418 | % |
| 419 | % 2) Méthode du simplexe. |
| 420 | % |
| 421 | % \vspace{.5em} |
| 422 | % |
| 423 | % 3) Application à des problèmes de R.O: |
| 424 | % |
| 425 | % \vspace{.5em} |
| 426 | % |
| 427 | % \hspace{.3em} 3.1) Fêtes de Pâques: A l'approche des fêtes de Pâques, un artisan chocolatier décide de confectionner des oeufs en chocolats. En allant inspecter ses réserves, il constate qu'il lui reste 18 kg de cacao, 8 kg de noisettes et 14 litres de lait. Ce chocolatier a deux spécialités: l'oeuf {\it extra} et l'oeuf {\it sublime}. Un oeuf {\it extra} nécessite 1kg de cacao, 1 kg de noisettes et 2 litres de lait tandis qu'un oeuf {\it sublime} nécessite 3 kg de cacao, 1 kg de noisettes et 1 litre de lait. Il fera un bénéfice de 20 euros en vendant un oeuf {\it extra}, et de 30 euros en vendant un oeuf {\it sublime}. |
| 428 | % |
| 429 | % \vspace{.5em} |
| 430 | % |
| 431 | % \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire. |
| 432 | % |
| 433 | % \vspace{.5em} |
| 434 | % |
| 435 | % \hspace{.6em} b) Combien d'oeufs extra et sublime doit-il fabriquer pour faire le plus grand bénéfice? |
| 436 | % |
| 437 | % \vspace{.5em} |
| 438 | % |
| 439 | % \hspace{.3em} 3.2) Organisation du travail: La fabrication d'une pièce $P_1$ a un prix de revient de 150 euros et celle d'une pièce $P_2$ coûte 100 euros. Chaque pièce est traitée successivement dans trois ateliers. Le nombre d'heures-machines par pièce est indiqué dans le tableau suivant : |
| 440 | % |
| 441 | % \vspace{.5em} |
| 442 | % |
| 443 | % \begin{center} |
| 444 | % $ |
| 445 | % \begin{array}{|c|c|c|c|} |
| 446 | % \hline |
| 447 | % Atelier & A & B & C \\ |
| 448 | % \hline |
| 449 | % Pièce 1 & 3 h & 5 h & 2 h \\ |
| 450 | % \hline |
| 451 | % Pièce 2 & 1 h & 3 h & 3 h \\ |
| 452 | % \hline |
| 453 | % \end{array} |
| 454 | % $ |
| 455 | % \end{center} |
| 456 | % |
| 457 | % \vspace{.5em} |
| 458 | % |
| 459 | % Pour éviter le chômage technique, l'atelier A doit obligatoirement fournir 1200 heures machines, l'atelier B doit obligatoirement fournir 3000 heures machines et l'atelier C doit obligatoirement fournir 1800 heures machines. |
| 460 | % |
| 461 | % \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire. |
| 462 | % |
| 463 | % \vspace{.5em} |
| 464 | % |
| 465 | % \hspace{.6em} b) Combien faut-il fabriquer de pièces $P_1$ et $P_2$ pour minimiser le coût de revient de l'ensemble de la production et pour assurer le fonctionnement des trois ateliers excluant tout chômage technique? |
| 466 | % |
| 467 | % \vspace{.5em} |
| 468 | |
| 469 | \bibliographystyle{plain} |
| 470 | \bibliography{stdlib_sbphilo} |
| 471 | |
| 472 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 473 | |
| 474 | \end{document} |
| 475 | |
| 476 | |
| 477 | \begin{thebibliography}{6}\input{MemoireM2Ballet6.synctex.gz(busy)} |
| 478 | |
| 479 | %\bibitem[1]{BL} Jean-Pierre \bsc{Bourguignon} et David \bsc{Langlois}, Cours de M1, Module Relativité Générale, |
| 480 | %Ecole Polytechnique, ParisTech, 2011.\\ |
| 481 | |
| 482 | %\bibitem[2]{G} Gilles \bsc{Cohen-Tannoudji}, Einstein et la refondation relativiste de la physique, 2005.\\ |
| 483 | |
| 484 | %\bibitem[3]{D} Pierre \bsc{Duhem}, La théorie physique, son objet, sa structure, Vrin, 2007.\\ |
| 485 | |
| 486 | %\bibitem[4]{E1} Albert \bsc{Einstein}, Die formale grundlage der allgemeinen Relativittstheorie. Kniglich Preussische |
| 487 | %Akademie der Wissenschaften (Berlin),Sitzungsberichte: pp 1030-1085. \\ |
| 488 | |
| 489 | %\bibitem[5]{G} Christian \bsc{Godin}, Dictionnaire de philosophie, Fayard Edition du temps, 2004.\\ |
| 490 | |
| 491 | %\bibitem[6]{H} Jean \bsc{Hladik}, La Relativité selon Einstein, L'Esprit des Sciences, Ellipses.\\ |
| 492 | |
| 493 | %\bibitem[7]{IS} \bsc{Iftime} and \bsc{Stachel}, The hole argument for covariant theories, arKiv:gr-qc/0512021v2, 8 avril 2006.\\ |
| 494 | |
| 495 | %\bibitem[8]{K} \bsc{Kant}, Critique de la raison pure, Traduction, présentation, notes par Alain Renaut, GF-Flammarion, 2006.\\ |
| 496 | |
| 497 | %\bibitem[9]{K2} \bsc{Kant}, Prolégomènes à toute métaphysique future, Traduction de Louis Guilermit, Vrin, 1986.\\ |
| 498 | |
| 499 | %\bibitem[10]{KU} Thomas \bsc{Kuhn}, La structure des révolutions scientifiques, Flammarion Champs Sciences, 2008. |
| 500 | |
| 501 | %\bibitem[11]{L} Marc \bsc{Lachièze-Rey}, Initiation à la cosmologie, 3ème édition, Dunod, 2000.\\ |
| 502 | |
| 503 | %\bibitem[12]{Mas} Thierry \bsc{Masson}, Cours de géométrie différentielle, groupe et algèbre de Lie, fibrés et connexions, 2010.\\ |
| 504 | |
| 505 | %\bibitem[13]{Poi} Henri \bsc{Poincaré}, La Science et L'Hypothèse, Flammarion, Paris, 1968.\\ |
| 506 | |
| 507 | %\bibitem[14]{Mav} Stamatia \bsc{Mavridès}, La Relativité, Que sais-je, 4ème édition, PUF, 2000.\\ |
| 508 | |
| 509 | %\bibitem[15]{R} Robert \bsc{Rynasiewicz}, The Lessons of the Hole Argument, The British Journal of the Philosophy of Science, |
| 510 | %vol; 45 (2), 407-436, Oxford University Press, Oxford Journals, 1994. \\ |
| 511 | |
| 512 | %\bibitem[16]{S} Standford Encyclopedia of Philosophy.\\ |
| 513 | |
| 514 | %\bibitem[17]{W} Wikipedia.\\ |
| 515 | |
| 516 | %\bibitem[1]{Bachtold} {\bf Manuel Bächtold}, L'interprétation de la mécanique quantique, une approche pragmatique, Collection vision des sciences, Hermann, 2008 .\\ |
| 517 | |
| 518 | %\bibitem[2]{Aspect} {\bf Alain Aspect}, Présentation naïve des inégalités de Bell, 2004.\\ |
| 519 | |
| 520 | % \bibitem[3]{Basda} {\bf Jean-Louis Basdevant et Manuel Joffre}, Mécanique Quantique, Les éditions de l'Ecole Polytechnique, 2006.\\ |
| 521 | |
| 522 | %\bibitem[4]{Diu} {\bf Bernard Diu}, Le congrès de Solvay de 1927: petite chronique d'un grand évènement, Bibnum.\\ |
| 523 | |
| 524 | %\bibitem[1]{B} \bsc{Aristote}, Métaphysique, traduction J.Tricot, Vrin, 1974.\\ |
| 525 | |
| 526 | \end{thebibliography} |