Commit | Line | Data |
---|---|---|
e37aec65 JB |
1 | \documentclass[12pt,oneside,a4paper]{book} |
2 | ||
3 | ||
4 | %%%%%Packages | |
5 | ||
6 | \usepackage{latexsym} | |
7 | \usepackage{amssymb} | |
8 | \usepackage[utf8]{inputenc} | |
9 | \usepackage[francais]{babel} | |
10 | \usepackage{color} | |
11 | \usepackage{geometry} | |
12 | \usepackage{graphicx} | |
13 | \usepackage{amsfonts} | |
14 | \usepackage[T1]{fontenc} | |
15 | \usepackage{multirow} | |
16 | \usepackage{fancyhdr} | |
17 | \usepackage{tocbibind} | |
18 | \usepackage{lmodern} | |
19 | ||
20 | ||
21 | %%%%%Marges & en-t\^etes | |
22 | ||
23 | \geometry{hmargin=2.3cm, vmargin=3cm} | |
24 | \fancyhf{} % supprime les en-t\^etes et pieds pr\'ed\'efinis | |
25 | \fancyhead[FC]{\bfseries\thepage} % N∞page centre bas | |
26 | \fancyhead[HC]{\footnotesize\leftmark} % chapitre centre haut | |
27 | \renewcommand{\headrulewidth}{0.2pt} % filet en haut | |
28 | \addtolength{\headheight}{0.5pt} % espace pour le filet | |
29 | \renewcommand{\footrulewidth}{0.2pt} %filet en bas | |
30 | ||
31 | ||
32 | %%%%%Th\'eor\`eme et d\'efinitions | |
33 | ||
34 | \newtheorem{Def}{D\'efinition} | |
35 | \newtheorem{Not}[Def]{Notation} | |
36 | \newtheorem{Th}{Th\'eor\`eme} | |
37 | \newtheorem{Prop}[Th]{Proposition} | |
38 | \newtheorem{Cor}[Th]{Corollaire} | |
39 | \newtheorem{Rmq}{Remarque} | |
40 | ||
41 | ||
42 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
43 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
44 | ||
45 | \begin{document} | |
46 | ||
47 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
48 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
49 | ||
50 | %%%%%Page de garde | |
51 | ||
52 | \begin{center} | |
53 | ||
b0927d0a | 54 | %\includegraphics[scale=0.5]{logo_sciences_rvb.png}\\ |
cec1e8f8 | 55 | \includegraphics[scale=0.5]{polytech.png}\\ |
b0927d0a JB |
56 | |
57 | \vspace*{0.5cm} | |
58 | ||
59 | \footnotesize{ | |
60 | \large \bf D\'epartement d'Informatique, Réseaux et Multimédia\\ | |
61 | \large \bf 5ème année\\ | |
62 | } | |
63 | ||
64 | \vspace*{0.5cm} | |
65 | ||
66 | %\large{Master 2 Professionnel\\ | |
67 | %Math\'ematiques et Informatique des Nouvelles Technologies\\} | |
68 | ||
69 | \large{Projet \\ en \\ Optimisation et Recherche Opérationnelle \\} | |
70 | ||
71 | \vspace*{0.7cm} | |
72 | ||
73 | \begin{tabular}{c} | |
74 | \hline | |
1ac77878 | 75 | ~ \\ |
cec1e8f8 JB |
76 | \LARGE\textbf {Programmation Séquentielle Quadratique} \\ |
77 | \LARGE\textbf {en} \\ | |
78 | \LARGE\textbf {Optimisation non linéraire sous contraintes} \\ | |
1ac77878 | 79 | ~ \\ |
b0927d0a JB |
80 | \hline |
81 | \end{tabular} | |
82 | ||
83 | \vspace*{0.7cm} | |
84 | ||
85 | \includegraphics[scale=0.4]{CE.PNG}\\ | |
86 | ||
87 | \vspace*{0.5cm} | |
88 | ||
89 | \large par\\ | |
90 | ||
91 | %\large \bsc{}\\ | |
92 | %\normalsize{M\'emoire encadr\'e par :} \large St\'ephane \bsc{Ballet}\\ | |
93 | ||
94 | \vspace*{0.2cm} | |
91df3de1 | 95 | \large {\bf Jérôme \bsc{Benoit} et Sylvain \bsc{Papa}}\\ |
b0927d0a JB |
96 | |
97 | %\vspace*{0.1cm} | |
98 | ||
99 | % \large sous la direction de \\ | |
100 | ||
101 | %\vspace*{0.1cm} | |
102 | ||
103 | %Eric Audureau et Thierry Masson | |
104 | ||
105 | %\vspace*{1cm} | |
106 | ||
107 | \vspace*{1cm} | |
108 | ||
109 | %\normalsize{Licence de Mathématiques 3ème année} | |
110 | \normalsize{Année 2018-2019} | |
e37aec65 JB |
111 | |
112 | \end{center} | |
113 | ||
114 | \thispagestyle{empty} | |
115 | ||
116 | \newpage | |
117 | ||
118 | ||
119 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
120 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
121 | ||
122 | ||
123 | \pagestyle{plain} | |
124 | \frontmatter | |
125 | ||
126 | ||
127 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
128 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
129 | ||
130 | ||
131 | ||
132 | %%%%%Table des mati\`eres | |
133 | ||
134 | \tableofcontents | |
135 | ||
136 | \begin{figure}[!b] | |
b0927d0a JB |
137 | \begin{center} |
138 | %\includegraphics{logo_fac2} | |
139 | \includegraphics[scale=0.04]{amu} | |
140 | \end{center} | |
e37aec65 JB |
141 | \end{figure} |
142 | ||
143 | \newpage | |
144 | ||
145 | ||
146 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
147 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
148 | ||
149 | ||
150 | \mainmatter | |
151 | \pagestyle{fancy} | |
152 | ||
153 | ||
154 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
155 | \chapter{Introduction générale} | |
156 | ||
e37aec65 JB |
157 | \vspace{.5em} |
158 | ||
159 | \section{Qu'est-ce que la recherche opérationnelle?} | |
160 | ||
e7e85554 JB |
161 | La recherche opérationnelle est une discipline dite "hybride" au confluent de plusieurs disciplines dont principalement l'analyse numérique, les probabilités, la statistique et l'algorithmie. |
162 | \newline | |
163 | On la considère usuellement comme une sous discipline des mathématiques de la décision. | |
91df3de1 | 164 | |
e37aec65 JB |
165 | \section{Qu'est-ce que l'optimisation?} |
166 | ||
b0927d0a JB |
167 | 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.}. |
168 | 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}. | |
169 | ||
170 | ||
171 | %{\it La relativité}, Que sais-je?, 4ème édition, puf, 2000, \cite{Mavr}; | |
172 | %ainsi que Jean Hladik, {\it La relativité selon Einstein}, L'esprit des sciences, Ellipses, 2000, \cite{Hlad}. | |
e37aec65 JB |
173 | |
174 | ||
175 | ||
176 | ||
177 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
178 | ||
179 | \chapter{Sujets d'étude en travaux dirigés} | |
180 | ||
181 | \section{Cahier des charges} | |
182 | ||
b0927d0a | 183 | 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 |
e37aec65 JB |
184 | à 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). |
185 | ||
186 | \vspace{.5em} | |
187 | ||
b0927d0a JB |
188 | Sur la fond, toutes les sources de connaissance utilisées devront être citées. En particulier, la méthodologie universitaire sera privilégiée |
189 | (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...). | |
190 | 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). | |
e37aec65 JB |
191 | L'accent sera essentiellement mis sur la démarche scientifique utilisée à égal niveau avec le contenu acquis des connaissances. |
192 | ||
193 | \vspace{.5em} | |
194 | ||
b0927d0a JB |
195 | Plusieurs sources devront être croisées afin de prétendre au maximum de vraisemblance |
196 | et d'objectivité scientifique. Le document ne devra pas excéder 10 pages. | |
e37aec65 JB |
197 | On privilégiera les qualités de synthèse, d'organisation ainsi que du contenu du document. |
198 | ||
199 | \section{Proposition de sujets} | |
200 | ||
201 | \subsection{Analyse numérique} | |
202 | ||
203 | \vspace{.5em} | |
204 | ||
205 | 1) Méthode des moindres Carrés (cas général, cas pondéré, cas des équations non linéaires). | |
206 | ||
207 | \vspace{.5em} | |
208 | ||
209 | 2) Méthode de Newton-Raphson (cas d'une variable, cas de deux variables) - Application: extrema d'une fonction à deux variables. | |
210 | ||
211 | \vspace{.5em} | |
212 | ||
213 | 3) Autres méthodes: méthode de Jacobi, de Gauss-Seidel, etc.... | |
214 | ||
215 | \vspace{.5em} | |
216 | ||
e37aec65 JB |
217 | \subsection{Optimisation} |
218 | ||
219 | \vspace{.5em} | |
220 | ||
221 | \subsubsection{Optimisation sans contrainte} | |
222 | ||
223 | {\bf A- Algorithmes déterministes} | |
224 | ||
225 | \vspace{.5em} | |
226 | ||
227 | 1) Régression linéaire sans contrainte (pré-requis: Méthode des moindres carrés). | |
228 | ||
229 | \vspace{.5em} | |
230 | ||
231 | 2) Méthodes de descente: la méthode du gradient (à pas constant ou à pas variable ou à pas optimal). | |
232 | ||
233 | \vspace{.5em} | |
234 | ||
b0927d0a | 235 | 3) Méthode de Newton (ou méthode dite de la tangente) et application à la recherche d'extrema. |
e37aec65 JB |
236 | |
237 | \vspace{.5em} | |
238 | ||
239 | 4) Méthodes de descente: méthode du gradient conjugué (cas linéaire et cas général) | |
240 | ||
241 | \vspace{.5em} | |
242 | ||
243 | 5) Méthode de relaxation | |
244 | ||
245 | \vspace{.5em} | |
246 | ||
247 | {\bf B- Algorithmes probabilistes ou dit stochastiques} | |
248 | ||
249 | \vspace{.5em} | |
250 | ||
251 | 1) Dynamique de métropolis (prérequis: chaines de Markov) | |
252 | ||
253 | \vspace{.5em} | |
254 | ||
255 | 2) Recuit simulé sur un ensemble fini et application au problème du voyageur de commerce (prérequis: dynamique de métropolis) | |
256 | ||
257 | \vspace{.5em} | |
258 | ||
259 | \subsubsection{Optimisation ou minimisation avec contraintes} | |
260 | ||
261 | \vspace{.5em} | |
262 | ||
263 | 1) Régression linéaire avec contraintes (prérequis: méthode des moindres carrés, conditions ou équations dites de Karush-kuhn-Tucker (KKT)) . | |
264 | ||
265 | \vspace{.5em} | |
266 | ||
267 | 2) Cas de la programmation linéaire (prérequis: Lagrangien et multiplicateurs de Lagrange, conditions de KKT). | |
268 | ||
269 | \vspace{.5em} | |
270 | ||
b0927d0a JB |
271 | 3) Algorithmes: méthode du gradient projeté, méthode de Lagrange-Newton pour des contraintes en égalité, |
272 | méthode de Newton projetée pour des contraintes de bornes, méthodes de pénalisation, | |
273 | méthodes de programmation quadratique successive (SQP Sequential Quadratic Programming), | |
e37aec65 JB |
274 | méthode de dualité (méthode d'Uzawa, prérequis: théorie de la dualité convexe) etc... |
275 | ||
276 | \vspace{.5em} | |
277 | ||
e37aec65 JB |
278 | \subsection{Recherche opérationnelle} |
279 | ||
280 | \vspace{.5em} | |
281 | ||
282 | \subsubsection{La programmation linéaire (cas particulier de l'optimisation avec contraintes)} | |
283 | ||
284 | 1) Méthode d'énumération. | |
285 | ||
286 | \vspace{.5em} | |
287 | ||
288 | 2) Méthode du simplexe. | |
289 | ||
290 | \vspace{.5em} | |
291 | ||
b0927d0a | 292 | 3) Application à des problèmes de R.O: |
e37aec65 JB |
293 | |
294 | \vspace{.5em} | |
295 | ||
296 | \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}. | |
297 | ||
298 | \vspace{.5em} | |
299 | ||
300 | \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire. | |
301 | ||
302 | \vspace{.5em} | |
303 | ||
304 | \hspace{.6em} b) Combien d'oeufs extra et sublime doit-il fabriquer pour faire le plus grand bénéfice? | |
305 | ||
306 | \vspace{.5em} | |
307 | ||
308 | \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 : | |
309 | ||
310 | \vspace{.5em} | |
311 | ||
312 | \begin{center} | |
b0927d0a JB |
313 | $ |
314 | \begin{array}{|c|c|c|c|} | |
315 | \hline | |
316 | Atelier & A & B & C \\ | |
317 | \hline | |
318 | Pièce 1 & 3 h & 5 h & 2 h \\ | |
319 | \hline | |
320 | Pièce 2 & 1 h & 3 h & 3 h \\ | |
321 | \hline | |
322 | \end{array} | |
323 | $ | |
e37aec65 JB |
324 | \end{center} |
325 | ||
326 | \vspace{.5em} | |
327 | ||
328 | 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. | |
329 | ||
330 | \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire. | |
331 | ||
332 | \vspace{.5em} | |
333 | ||
334 | \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? | |
335 | ||
336 | \vspace{.5em} | |
337 | ||
e37aec65 JB |
338 | \bibliographystyle{plain} |
339 | \bibliography{stdlib_sbphilo} | |
340 | ||
341 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
342 | ||
343 | \end{document} | |
344 | ||
345 | ||
346 | \begin{thebibliography}{6}\input{MemoireM2Ballet6.synctex.gz(busy)} | |
347 | ||
b0927d0a JB |
348 | %\bibitem[1]{BL} Jean-Pierre \bsc{Bourguignon} et David \bsc{Langlois}, Cours de M1, Module Relativité Générale, |
349 | %Ecole Polytechnique, ParisTech, 2011.\\ | |
350 | ||
351 | %\bibitem[2]{G} Gilles \bsc{Cohen-Tannoudji}, Einstein et la refondation relativiste de la physique, 2005.\\ | |
352 | ||
353 | %\bibitem[3]{D} Pierre \bsc{Duhem}, La théorie physique, son objet, sa structure, Vrin, 2007.\\ | |
354 | ||
355 | %\bibitem[4]{E1} Albert \bsc{Einstein}, Die formale grundlage der allgemeinen Relativittstheorie. Kniglich Preussische | |
356 | %Akademie der Wissenschaften (Berlin),Sitzungsberichte: pp 1030-1085. \\ | |
357 | ||
358 | %\bibitem[5]{G} Christian \bsc{Godin}, Dictionnaire de philosophie, Fayard Edition du temps, 2004.\\ | |
359 | ||
360 | %\bibitem[6]{H} Jean \bsc{Hladik}, La Relativité selon Einstein, L'Esprit des Sciences, Ellipses.\\ | |
361 | ||
362 | %\bibitem[7]{IS} \bsc{Iftime} and \bsc{Stachel}, The hole argument for covariant theories, arKiv:gr-qc/0512021v2, 8 avril 2006.\\ | |
363 | ||
364 | %\bibitem[8]{K} \bsc{Kant}, Critique de la raison pure, Traduction, présentation, notes par Alain Renaut, GF-Flammarion, 2006.\\ | |
365 | ||
366 | %\bibitem[9]{K2} \bsc{Kant}, Prolégomènes à toute métaphysique future, Traduction de Louis Guilermit, Vrin, 1986.\\ | |
367 | ||
368 | %\bibitem[10]{KU} Thomas \bsc{Kuhn}, La structure des révolutions scientifiques, Flammarion Champs Sciences, 2008. | |
369 | ||
370 | %\bibitem[11]{L} Marc \bsc{Lachièze-Rey}, Initiation à la cosmologie, 3ème édition, Dunod, 2000.\\ | |
e37aec65 | 371 | |
b0927d0a | 372 | %\bibitem[12]{Mas} Thierry \bsc{Masson}, Cours de géométrie différentielle, groupe et algèbre de Lie, fibrés et connexions, 2010.\\ |
e37aec65 | 373 | |
b0927d0a | 374 | %\bibitem[13]{Poi} Henri \bsc{Poincaré}, La Science et L'Hypothèse, Flammarion, Paris, 1968.\\ |
e37aec65 | 375 | |
b0927d0a JB |
376 | %\bibitem[14]{Mav} Stamatia \bsc{Mavridès}, La Relativité, Que sais-je, 4ème édition, PUF, 2000.\\ |
377 | ||
378 | %\bibitem[15]{R} Robert \bsc{Rynasiewicz}, The Lessons of the Hole Argument, The British Journal of the Philosophy of Science, | |
379 | %vol; 45 (2), 407-436, Oxford University Press, Oxford Journals, 1994. \\ | |
380 | ||
381 | %\bibitem[16]{S} Standford Encyclopedia of Philosophy.\\ | |
382 | ||
383 | %\bibitem[17]{W} Wikipedia.\\ | |
384 | ||
385 | %\bibitem[1]{Bachtold} {\bf Manuel Bächtold}, L'interprétation de la mécanique quantique, une approche pragmatique, Collection vision des sciences, Hermann, 2008 .\\ | |
1ac77878 | 386 | |
b0927d0a | 387 | %\bibitem[2]{Aspect} {\bf Alain Aspect}, Présentation naïve des inégalités de Bell, 2004.\\ |
b0927d0a | 388 | |
1ac77878 | 389 | \bibitem[3]{Basda} {\bf Jean-Louis Basdevant et Manuel Joffre}, Mécanique Quantique, Les éditions de l'Ecole Polytechnique, 2006.\\ |
b0927d0a | 390 | |
1ac77878 | 391 | %\bibitem[4]{Diu} {\bf Bernard Diu}, Le congrès de Solvay de 1927: petite chronique d'un grand évènement, Bibnum.\\ |
b0927d0a JB |
392 | |
393 | %\bibitem[1]{B} \bsc{Aristote}, Métaphysique, traduction J.Tricot, Vrin, 1974.\\ | |
394 | ||
b0927d0a | 395 | \end{thebibliography} |