From: Jérôme Benoit Date: Sat, 3 Nov 2018 14:57:04 +0000 (+0100) Subject: Add a some bibtex references. X-Git-Url: https://git.piment-noir.org/?p=Projet_Recherche_Operationnelle.git;a=commitdiff_plain;h=b6cd66324e449037753ac9fac47fea53c31d617b Add a some bibtex references. Signed-off-by: Jérôme Benoit --- diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index 7a58339..a0867ac 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -211,12 +211,11 @@ Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x \newline 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} $. \end{Def} - \begin{Def} Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $. \newline On dit que $ f $ est continue en $ x^\ast $ si -$$ \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 $$ +$$ \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \exists \alpha \in \mathbb{R}_{+}^{*} \ \forall x \in \mathbb{R}^n \ \norme{x - x^\ast} \leq \alpha \implies |f(x) - f(x^\ast)| \leq \varepsilon $$ \end{Def} \begin{Def} Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $. @@ -266,17 +265,18 @@ On peut en déduire que si $ J $ est continue, $ \mathcal{C }$ est un ensemble f \begin{Th}[Théorème de Weierstrass] Soient $ \mathcal{C} \neq \emptyset \subset \mathbb{R}^n $ un fermé borné et $ f : \mathcal{C} \longrightarrow \mathbb{R} $ une fonction continue. \newline -Alors $$ \exists x^\ast \in \mathcal{C} \ \forall x \in \mathcal{C} \ f(x) \geq f(x^\ast) $$ +Alors : $$ \exists x^\ast \in \mathcal{C} \ \forall x \in \mathcal{C} \ f(x) \geq f(x^\ast) $$ Autrement dit $ x^\ast $ est un minimum global de $ J $ sur $ \mathcal{C} $. \newline -De la même façon, il existe maximum global de $ J $ sur $ \mathcal{C} $. +De la même façon, il existe un maximum global de $ J $ sur $ \mathcal{C} $. \end{Th} -On en déduit que $ \mathcal{P} $ admet au moins une solution dans le cas où $ J, g ,h $ sont continues. +On en déduit que $ \mathcal{P} $ admet au moins une solution dans le cas où $ J, g ,h $ sont continues. L'étude de la convexité de $ J $ permet d'explorer l'unicité de la solution \cite{LJK}. + \subsection{Conditions de caractérisation d'un extremum} -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 $. +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 : $ x_i = \displaystyle\min_{x \in \mathcal{C}} J(x) \iff \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \norme{\nabla J(x_i)} < \varepsilon $, $ i \in \mathbb{N} $ \cite{FEA}. \newline -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. +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 \cite{FEA,WAL}. \subsubsection{Conditions de Kuhn-Tucker et Lagrange} @@ -293,234 +293,23 @@ et $$ \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 $$ On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange. \end{Th} -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 $. +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 \iff h_i(x) \leq 0 \land h_i(x) \geq 0 $. \newline \newline 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. -% 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.}. -% 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}. - -%{\it La relativité}, Que sais-je?, 4ème édition, puf, 2000, \cite{Mavr}; -%ainsi que Jean Hladik, {\it La relativité selon Einstein}, L'esprit des sciences, Ellipses, 2000, \cite{Hlad}. - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \chapter{Méthodes de programmation quadratique séquentielle} -% \section{Cahier des charges} -% -% 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 -% à 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). -% -% \vspace{.5em} -% -% Sur la fond, toutes les sources de connaissance utilisées devront être citées. En particulier, la méthodologie universitaire sera privilégiée -% (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...). -% 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). -% L'accent sera essentiellement mis sur la démarche scientifique utilisée à égal niveau avec le contenu acquis des connaissances. -% -% \vspace{.5em} -% -% Plusieurs sources devront être croisées afin de prétendre au maximum de vraisemblance -% et d'objectivité scientifique. Le document ne devra pas excéder 10 pages. -% On privilégiera les qualités de synthèse, d'organisation ainsi que du contenu du document. -% -% \section{Proposition de sujets} -% -% \subsection{Analyse numérique} -% -% \vspace{.5em} -% -% 1) Méthode des moindres Carrés (cas général, cas pondéré, cas des équations non linéaires). -% -% \vspace{.5em} -% -% 2) Méthode de Newton-Raphson (cas d'une variable, cas de deux variables) - Application: extrema d'une fonction à deux variables. -% -% \vspace{.5em} -% -% 3) Autres méthodes: méthode de Jacobi, de Gauss-Seidel, etc.... -% -% \vspace{.5em} - \section{Optimisation} -% \vspace{.5em} - -% \subsubsection{Optimisation sans contrainte} -% -% {\bf A- Algorithmes déterministes} -% -% \vspace{.5em} -% -% 1) Régression linéaire sans contrainte (pré-requis: Méthode des moindres carrés). -% -% \vspace{.5em} -% -% 2) Méthodes de descente: la méthode du gradient (à pas constant ou à pas variable ou à pas optimal). -% -% \vspace{.5em} -% -% 3) Méthode de Newton (ou méthode dite de la tangente) et application à la recherche d'extrema. -% -% \vspace{.5em} -% -% 4) Méthodes de descente: méthode du gradient conjugué (cas linéaire et cas général) -% -% \vspace{.5em} -% -% 5) Méthode de relaxation -% -% \vspace{.5em} -% -% {\bf B- Algorithmes probabilistes ou dit stochastiques} -% -% \vspace{.5em} -% -% 1) Dynamique de métropolis (prérequis: chaines de Markov) -% -% \vspace{.5em} -% -% 2) Recuit simulé sur un ensemble fini et application au problème du voyageur de commerce (prérequis: dynamique de métropolis) -% -% \vspace{.5em} - \subsubsection{Optimisation ou minimisation avec contraintes} -% \vspace{.5em} -% -% 1) Régression linéaire avec contraintes (prérequis: méthode des moindres carrés, conditions ou équations dites de Karush-kuhn-Tucker (KKT)) . -% -% \vspace{.5em} -% -% 2) Cas de la programmation linéaire (prérequis: Lagrangien et multiplicateurs de Lagrange, conditions de KKT). -% -% \vspace{.5em} -% -% 3) Algorithmes: méthode du gradient projeté, méthode de Lagrange-Newton pour des contraintes en égalité, -% méthode de Newton projetée pour des contraintes de bornes, méthodes de pénalisation, -% méthodes de programmation quadratique successive (SQP Sequential Quadratic Programming), -% méthode de dualité (méthode d'Uzawa, prérequis: théorie de la dualité convexe) etc... -% -% \vspace{.5em} -% -% \subsection{Recherche opérationnelle} -% -% \vspace{.5em} -% -% \subsubsection{La programmation linéaire (cas particulier de l'optimisation avec contraintes)} -% -% 1) Méthode d'énumération. -% -% \vspace{.5em} -% -% 2) Méthode du simplexe. -% -% \vspace{.5em} -% -% 3) Application à des problèmes de R.O: -% -% \vspace{.5em} -% -% \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}. -% -% \vspace{.5em} -% -% \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire. -% -% \vspace{.5em} -% -% \hspace{.6em} b) Combien d'oeufs extra et sublime doit-il fabriquer pour faire le plus grand bénéfice? -% -% \vspace{.5em} -% -% \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 : -% -% \vspace{.5em} -% -% \begin{center} -% $ -% \begin{array}{|c|c|c|c|} -% \hline -% Atelier & A & B & C \\ -% \hline -% Pièce 1 & 3 h & 5 h & 2 h \\ -% \hline -% Pièce 2 & 1 h & 3 h & 3 h \\ -% \hline -% \end{array} -% $ -% \end{center} -% -% \vspace{.5em} -% -% 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. -% -% \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire. -% -% \vspace{.5em} -% -% \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? -% -% \vspace{.5em} - \bibliographystyle{plain} \bibliography{stdlib_sbphilo} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document} - - -\begin{thebibliography}{6}\input{MemoireM2Ballet6.synctex.gz(busy)} - - %\bibitem[1]{BL} Jean-Pierre \bsc{Bourguignon} et David \bsc{Langlois}, Cours de M1, Module Relativité Générale, - %Ecole Polytechnique, ParisTech, 2011.\\ - - %\bibitem[2]{G} Gilles \bsc{Cohen-Tannoudji}, Einstein et la refondation relativiste de la physique, 2005.\\ - - %\bibitem[3]{D} Pierre \bsc{Duhem}, La théorie physique, son objet, sa structure, Vrin, 2007.\\ - - %\bibitem[4]{E1} Albert \bsc{Einstein}, Die formale grundlage der allgemeinen Relativittstheorie. Kniglich Preussische - %Akademie der Wissenschaften (Berlin),Sitzungsberichte: pp 1030-1085. \\ - - %\bibitem[5]{G} Christian \bsc{Godin}, Dictionnaire de philosophie, Fayard Edition du temps, 2004.\\ - - %\bibitem[6]{H} Jean \bsc{Hladik}, La Relativité selon Einstein, L'Esprit des Sciences, Ellipses.\\ - - %\bibitem[7]{IS} \bsc{Iftime} and \bsc{Stachel}, The hole argument for covariant theories, arKiv:gr-qc/0512021v2, 8 avril 2006.\\ - - %\bibitem[8]{K} \bsc{Kant}, Critique de la raison pure, Traduction, présentation, notes par Alain Renaut, GF-Flammarion, 2006.\\ - - %\bibitem[9]{K2} \bsc{Kant}, Prolégomènes à toute métaphysique future, Traduction de Louis Guilermit, Vrin, 1986.\\ - - %\bibitem[10]{KU} Thomas \bsc{Kuhn}, La structure des révolutions scientifiques, Flammarion Champs Sciences, 2008. - - %\bibitem[11]{L} Marc \bsc{Lachièze-Rey}, Initiation à la cosmologie, 3ème édition, Dunod, 2000.\\ - - %\bibitem[12]{Mas} Thierry \bsc{Masson}, Cours de géométrie différentielle, groupe et algèbre de Lie, fibrés et connexions, 2010.\\ - - %\bibitem[13]{Poi} Henri \bsc{Poincaré}, La Science et L'Hypothèse, Flammarion, Paris, 1968.\\ - - %\bibitem[14]{Mav} Stamatia \bsc{Mavridès}, La Relativité, Que sais-je, 4ème édition, PUF, 2000.\\ - - %\bibitem[15]{R} Robert \bsc{Rynasiewicz}, The Lessons of the Hole Argument, The British Journal of the Philosophy of Science, - %vol; 45 (2), 407-436, Oxford University Press, Oxford Journals, 1994. \\ - - %\bibitem[16]{S} Standford Encyclopedia of Philosophy.\\ - - %\bibitem[17]{W} Wikipedia.\\ - - %\bibitem[1]{Bachtold} {\bf Manuel Bächtold}, L'interprétation de la mécanique quantique, une approche pragmatique, Collection vision des sciences, Hermann, 2008 .\\ - - %\bibitem[2]{Aspect} {\bf Alain Aspect}, Présentation naïve des inégalités de Bell, 2004.\\ - - % \bibitem[3]{Basda} {\bf Jean-Louis Basdevant et Manuel Joffre}, Mécanique Quantique, Les éditions de l'Ecole Polytechnique, 2006.\\ - - %\bibitem[4]{Diu} {\bf Bernard Diu}, Le congrès de Solvay de 1927: petite chronique d'un grand évènement, Bibnum.\\ - - %\bibitem[1]{B} \bsc{Aristote}, Métaphysique, traduction J.Tricot, Vrin, 1974.\\ - -\end{thebibliography} diff --git a/rapport/stdlib_sbphilo.bib b/rapport/stdlib_sbphilo.bib index facedae..549b8b4 100644 --- a/rapport/stdlib_sbphilo.bib +++ b/rapport/stdlib_sbphilo.bib @@ -9,11 +9,41 @@ title="Présentation naïve des inégalités de Bell", journal="", volume=" ", number="", -pages="", +pages="", publisher="", year="2004", } +@BOOK{LJK, +author="Anatoli Iouditski", +title="Introduction à la Recherche Opérationnelle", +journal="", +volume=" ", +number="", +pages="", +publisher="Université de Grenoble", +year="2017" +} + +@BOOK{FEA, +author="Paul Feautrier", +title="Recherche Opérationnelle", +journal="", +volume=" ", +number="", +pages="", +publisher="Ecole Normale Supérieure de Lyon", +year="2005", +} + +@PHDTHESIS{WAL, +author="Eric Walter", +title="Méthodes numériques et optimisation, un guide du consommateur", +school="Université Paris-Sud", +year="2015", +key="" +} + @BOOK{Bach, author="Manuel Bächtold", title="L'interprétation de la mécanique quantique, une approche pragmatique", @@ -38,7 +68,7 @@ title="Le principe de complémentarité", journal="Nature", volume=" ", number="121", -pages="580-591", +pages="580-591", publisher="", year="1928", } @@ -50,7 +80,7 @@ title="Le congrès de Solvay de 1927: petite chronique d'un grand évènement", journal="Bibnum", volume=" ", number="", -pages="", +pages="", publisher="", year="", } @@ -63,8 +93,6 @@ publisher="Vrin", year="2007", } - - @BOOK{Eins1, author="Albert Einstein", title="Sur l’\'electrodynamique des corps en mouvement", @@ -121,9 +149,6 @@ publisher="Dunod", year="2009", } - - - @BOOK{Godi, author="Christian Godin", title="Dictionnaire de philosophie", @@ -147,7 +172,7 @@ title="The hole argument for covariant theories", journal="General Relativity and Gravitation", volume=" ", number="38", -pages="1241-1252", +pages="1241-1252", publisher="", year="2006", } @@ -193,7 +218,6 @@ publisher="PUF", year="2ème édition, 2000", } - @BOOK{Mass, author=" Thierry Masson", title="Cours de géométrie différentielle, groupe et algèbre de Lie, fibrés et connexions", @@ -202,7 +226,6 @@ publisher="", year="2010", } - @BOOK{Mavr, author="Stamatia Mavridès", title="La Relativit\'e ", @@ -244,8 +267,6 @@ publisher="GF-Flammarion", year="1985", } - - @BOOK{Poin, author="Henri Poincaré", title="La science et l'hypothèse", @@ -261,7 +282,7 @@ title="The Lessons of the Hole Argument", journal="The British Journal of the Philosophy of Science ", volume="vol; 45 ", number="2", -pages="407--436", +pages="407-436", publisher="Oxford University Press, Oxford Journals", year="Oxford University Press, Oxford Journals, 1994", } @@ -273,9 +294,3 @@ volume="", publisher="GF-Flammarion", year="1964", } - - - - - -