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 JB |
54 | %\includegraphics[scale=0.5]{logo_sciences_rvb.png}\\ |
55 | \includegraphics[scale=0.5]{index2.png}\\ | |
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 | ~ \\ |
91df3de1 | 76 | \huge\textbf {Programmation Séquentielle Quadratique} \\ |
1ac77878 | 77 | \huge\textbf {en} \\ |
91df3de1 | 78 | \huge\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 | ||
9ba07da7 SP |
161 | La recherche opérationnelle est une discipline dite "hybride" au confluent de plusieurs disciplines dont principalement l'analyse numérique, les probalilites et la statistique. On la considère usuellement comme une sous discipline des |
162 | mathematique de la décision. | |
91df3de1 | 163 | |
e37aec65 JB |
164 | \section{Qu'est-ce que l'optimisation?} |
165 | ||
b0927d0a JB |
166 | 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.}. |
167 | 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}. | |
168 | ||
169 | ||
170 | %{\it La relativité}, Que sais-je?, 4ème édition, puf, 2000, \cite{Mavr}; | |
171 | %ainsi que Jean Hladik, {\it La relativité selon Einstein}, L'esprit des sciences, Ellipses, 2000, \cite{Hlad}. | |
e37aec65 JB |
172 | |
173 | ||
174 | ||
175 | ||
176 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
177 | ||
178 | \chapter{Sujets d'étude en travaux dirigés} | |
179 | ||
180 | \section{Cahier des charges} | |
181 | ||
b0927d0a | 182 | 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 |
183 | à 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). |
184 | ||
185 | \vspace{.5em} | |
186 | ||
b0927d0a JB |
187 | Sur la fond, toutes les sources de connaissance utilisées devront être citées. En particulier, la méthodologie universitaire sera privilégiée |
188 | (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...). | |
189 | 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 |
190 | L'accent sera essentiellement mis sur la démarche scientifique utilisée à égal niveau avec le contenu acquis des connaissances. |
191 | ||
192 | \vspace{.5em} | |
193 | ||
b0927d0a JB |
194 | Plusieurs sources devront être croisées afin de prétendre au maximum de vraisemblance |
195 | et d'objectivité scientifique. Le document ne devra pas excéder 10 pages. | |
e37aec65 JB |
196 | On privilégiera les qualités de synthèse, d'organisation ainsi que du contenu du document. |
197 | ||
198 | \section{Proposition de sujets} | |
199 | ||
200 | \subsection{Analyse numérique} | |
201 | ||
202 | \vspace{.5em} | |
203 | ||
204 | 1) Méthode des moindres Carrés (cas général, cas pondéré, cas des équations non linéaires). | |
205 | ||
206 | \vspace{.5em} | |
207 | ||
208 | 2) Méthode de Newton-Raphson (cas d'une variable, cas de deux variables) - Application: extrema d'une fonction à deux variables. | |
209 | ||
210 | \vspace{.5em} | |
211 | ||
212 | 3) Autres méthodes: méthode de Jacobi, de Gauss-Seidel, etc.... | |
213 | ||
214 | \vspace{.5em} | |
215 | ||
e37aec65 JB |
216 | \subsection{Optimisation} |
217 | ||
218 | \vspace{.5em} | |
219 | ||
220 | \subsubsection{Optimisation sans contrainte} | |
221 | ||
222 | {\bf A- Algorithmes déterministes} | |
223 | ||
224 | \vspace{.5em} | |
225 | ||
226 | 1) Régression linéaire sans contrainte (pré-requis: Méthode des moindres carrés). | |
227 | ||
228 | \vspace{.5em} | |
229 | ||
230 | 2) Méthodes de descente: la méthode du gradient (à pas constant ou à pas variable ou à pas optimal). | |
231 | ||
232 | \vspace{.5em} | |
233 | ||
b0927d0a | 234 | 3) Méthode de Newton (ou méthode dite de la tangente) et application à la recherche d'extrema. |
e37aec65 JB |
235 | |
236 | \vspace{.5em} | |
237 | ||
238 | 4) Méthodes de descente: méthode du gradient conjugué (cas linéaire et cas général) | |
239 | ||
240 | \vspace{.5em} | |
241 | ||
242 | 5) Méthode de relaxation | |
243 | ||
244 | \vspace{.5em} | |
245 | ||
246 | {\bf B- Algorithmes probabilistes ou dit stochastiques} | |
247 | ||
248 | \vspace{.5em} | |
249 | ||
250 | 1) Dynamique de métropolis (prérequis: chaines de Markov) | |
251 | ||
252 | \vspace{.5em} | |
253 | ||
254 | 2) Recuit simulé sur un ensemble fini et application au problème du voyageur de commerce (prérequis: dynamique de métropolis) | |
255 | ||
256 | \vspace{.5em} | |
257 | ||
258 | \subsubsection{Optimisation ou minimisation avec contraintes} | |
259 | ||
260 | \vspace{.5em} | |
261 | ||
262 | 1) Régression linéaire avec contraintes (prérequis: méthode des moindres carrés, conditions ou équations dites de Karush-kuhn-Tucker (KKT)) . | |
263 | ||
264 | \vspace{.5em} | |
265 | ||
266 | 2) Cas de la programmation linéaire (prérequis: Lagrangien et multiplicateurs de Lagrange, conditions de KKT). | |
267 | ||
268 | \vspace{.5em} | |
269 | ||
b0927d0a JB |
270 | 3) Algorithmes: méthode du gradient projeté, méthode de Lagrange-Newton pour des contraintes en égalité, |
271 | méthode de Newton projetée pour des contraintes de bornes, méthodes de pénalisation, | |
272 | méthodes de programmation quadratique successive (SQP Sequential Quadratic Programming), | |
e37aec65 JB |
273 | méthode de dualité (méthode d'Uzawa, prérequis: théorie de la dualité convexe) etc... |
274 | ||
275 | \vspace{.5em} | |
276 | ||
e37aec65 JB |
277 | \subsection{Recherche opérationnelle} |
278 | ||
279 | \vspace{.5em} | |
280 | ||
281 | \subsubsection{La programmation linéaire (cas particulier de l'optimisation avec contraintes)} | |
282 | ||
283 | 1) Méthode d'énumération. | |
284 | ||
285 | \vspace{.5em} | |
286 | ||
287 | 2) Méthode du simplexe. | |
288 | ||
289 | \vspace{.5em} | |
290 | ||
b0927d0a | 291 | 3) Application à des problèmes de R.O: |
e37aec65 JB |
292 | |
293 | \vspace{.5em} | |
294 | ||
295 | \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}. | |
296 | ||
297 | \vspace{.5em} | |
298 | ||
299 | \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire. | |
300 | ||
301 | \vspace{.5em} | |
302 | ||
303 | \hspace{.6em} b) Combien d'oeufs extra et sublime doit-il fabriquer pour faire le plus grand bénéfice? | |
304 | ||
305 | \vspace{.5em} | |
306 | ||
307 | \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 : | |
308 | ||
309 | \vspace{.5em} | |
310 | ||
311 | \begin{center} | |
b0927d0a JB |
312 | $ |
313 | \begin{array}{|c|c|c|c|} | |
314 | \hline | |
315 | Atelier & A & B & C \\ | |
316 | \hline | |
317 | Pièce 1 & 3 h & 5 h & 2 h \\ | |
318 | \hline | |
319 | Pièce 2 & 1 h & 3 h & 3 h \\ | |
320 | \hline | |
321 | \end{array} | |
322 | $ | |
e37aec65 JB |
323 | \end{center} |
324 | ||
325 | \vspace{.5em} | |
326 | ||
327 | 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. | |
328 | ||
329 | \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire. | |
330 | ||
331 | \vspace{.5em} | |
332 | ||
333 | \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? | |
334 | ||
335 | \vspace{.5em} | |
336 | ||
e37aec65 JB |
337 | \bibliographystyle{plain} |
338 | \bibliography{stdlib_sbphilo} | |
339 | ||
340 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
341 | ||
342 | \end{document} | |
343 | ||
344 | ||
345 | \begin{thebibliography}{6}\input{MemoireM2Ballet6.synctex.gz(busy)} | |
346 | ||
b0927d0a JB |
347 | %\bibitem[1]{BL} Jean-Pierre \bsc{Bourguignon} et David \bsc{Langlois}, Cours de M1, Module Relativité Générale, |
348 | %Ecole Polytechnique, ParisTech, 2011.\\ | |
349 | ||
350 | %\bibitem[2]{G} Gilles \bsc{Cohen-Tannoudji}, Einstein et la refondation relativiste de la physique, 2005.\\ | |
351 | ||
352 | %\bibitem[3]{D} Pierre \bsc{Duhem}, La théorie physique, son objet, sa structure, Vrin, 2007.\\ | |
353 | ||
354 | %\bibitem[4]{E1} Albert \bsc{Einstein}, Die formale grundlage der allgemeinen Relativittstheorie. Kniglich Preussische | |
355 | %Akademie der Wissenschaften (Berlin),Sitzungsberichte: pp 1030-1085. \\ | |
356 | ||
357 | %\bibitem[5]{G} Christian \bsc{Godin}, Dictionnaire de philosophie, Fayard Edition du temps, 2004.\\ | |
358 | ||
359 | %\bibitem[6]{H} Jean \bsc{Hladik}, La Relativité selon Einstein, L'Esprit des Sciences, Ellipses.\\ | |
360 | ||
361 | %\bibitem[7]{IS} \bsc{Iftime} and \bsc{Stachel}, The hole argument for covariant theories, arKiv:gr-qc/0512021v2, 8 avril 2006.\\ | |
362 | ||
363 | %\bibitem[8]{K} \bsc{Kant}, Critique de la raison pure, Traduction, présentation, notes par Alain Renaut, GF-Flammarion, 2006.\\ | |
364 | ||
365 | %\bibitem[9]{K2} \bsc{Kant}, Prolégomènes à toute métaphysique future, Traduction de Louis Guilermit, Vrin, 1986.\\ | |
366 | ||
367 | %\bibitem[10]{KU} Thomas \bsc{Kuhn}, La structure des révolutions scientifiques, Flammarion Champs Sciences, 2008. | |
368 | ||
369 | %\bibitem[11]{L} Marc \bsc{Lachièze-Rey}, Initiation à la cosmologie, 3ème édition, Dunod, 2000.\\ | |
e37aec65 | 370 | |
b0927d0a | 371 | %\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 | 372 | |
b0927d0a | 373 | %\bibitem[13]{Poi} Henri \bsc{Poincaré}, La Science et L'Hypothèse, Flammarion, Paris, 1968.\\ |
e37aec65 | 374 | |
b0927d0a JB |
375 | %\bibitem[14]{Mav} Stamatia \bsc{Mavridès}, La Relativité, Que sais-je, 4ème édition, PUF, 2000.\\ |
376 | ||
377 | %\bibitem[15]{R} Robert \bsc{Rynasiewicz}, The Lessons of the Hole Argument, The British Journal of the Philosophy of Science, | |
378 | %vol; 45 (2), 407-436, Oxford University Press, Oxford Journals, 1994. \\ | |
379 | ||
380 | %\bibitem[16]{S} Standford Encyclopedia of Philosophy.\\ | |
381 | ||
382 | %\bibitem[17]{W} Wikipedia.\\ | |
383 | ||
384 | %\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 | 385 | |
b0927d0a | 386 | %\bibitem[2]{Aspect} {\bf Alain Aspect}, Présentation naïve des inégalités de Bell, 2004.\\ |
b0927d0a | 387 | |
1ac77878 | 388 | \bibitem[3]{Basda} {\bf Jean-Louis Basdevant et Manuel Joffre}, Mécanique Quantique, Les éditions de l'Ecole Polytechnique, 2006.\\ |
b0927d0a | 389 | |
1ac77878 | 390 | %\bibitem[4]{Diu} {\bf Bernard Diu}, Le congrès de Solvay de 1927: petite chronique d'un grand évènement, Bibnum.\\ |
b0927d0a JB |
391 | |
392 | %\bibitem[1]{B} \bsc{Aristote}, Métaphysique, traduction J.Tricot, Vrin, 1974.\\ | |
393 | ||
b0927d0a | 394 | \end{thebibliography} |