X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=ProjetOptimRO.tex;fp=ProjetOptimRO.tex;h=0000000000000000000000000000000000000000;hb=3d5196fd7a4c2a11701fe170155004a86259c505;hp=31657f5b30916c7b6c129d57843bfe1a8aae25fa;hpb=64f7c0648bba3e99a39f15896ce425cdfb06281e;p=Projet_Recherche_Operationnelle.git diff --git a/ProjetOptimRO.tex b/ProjetOptimRO.tex deleted file mode 100644 index 31657f5..0000000 --- a/ProjetOptimRO.tex +++ /dev/null @@ -1,416 +0,0 @@ -\documentclass[12pt,oneside,a4paper]{book} - - -%%%%%Packages - -\usepackage{latexsym} -\usepackage{amssymb} -\usepackage[utf8]{inputenc} -\usepackage[francais]{babel} -\usepackage{color} -\usepackage{geometry} -\usepackage{graphicx} -\usepackage{amsfonts} -\usepackage[T1]{fontenc} -\usepackage{multirow} -\usepackage{fancyhdr} -\usepackage{tocbibind} -\usepackage{lmodern} - - -%%%%%Marges & en-t\^etes - -\geometry{hmargin=2.3cm, vmargin=3cm} -\fancyhf{} % supprime les en-t\^etes et pieds pr\'ed\'efinis -\fancyhead[FC]{\bfseries\thepage} % N∞page centre bas -\fancyhead[HC]{\footnotesize\leftmark} % chapitre centre haut -\renewcommand{\headrulewidth}{0.2pt} % filet en haut -\addtolength{\headheight}{0.5pt} % espace pour le filet -\renewcommand{\footrulewidth}{0.2pt} %filet en bas - - -%%%%%Th\'eor\`eme et d\'efinitions - -\newtheorem{Def}{D\'efinition} -\newtheorem{Not}[Def]{Notation} -\newtheorem{Th}{Th\'eor\`eme} -\newtheorem{Prop}[Th]{Proposition} -\newtheorem{Cor}[Th]{Corollaire} -\newtheorem{Rmq}{Remarque} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\begin{document} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%Page de garde - -\begin{center} - - %\includegraphics[scale=0.5]{logo_sciences_rvb.png}\\ - \includegraphics[scale=0.5]{polytech.png}\\ - - \vspace*{0.5cm} - - \footnotesize{ - \large \bf D\'epartement d'Informatique, Réseaux et Multimédia\\ - \large \bf 5ème année\\ - } - - \vspace*{0.5cm} - - %\large{Master 2 Professionnel\\ - %Math\'ematiques et Informatique des Nouvelles Technologies\\} - - \large{Projet \\ en \\ Optimisation et Recherche Opérationnelle \\} - - \vspace*{0.7cm} - - \begin{tabular}{c} - \hline - ~ \\ - \LARGE\textbf {Programmation Séquentielle Quadratique} \\ - \LARGE\textbf {en} \\ - \LARGE\textbf {Optimisation non linéraire sous contraintes} \\ - ~ \\ - \hline - \end{tabular} - - \vspace*{0.7cm} - - \includegraphics[scale=0.4]{CE.PNG}\\ - - \vspace*{0.5cm} - - \large par\\ - - %\large \bsc{}\\ - %\normalsize{M\'emoire encadr\'e par :} \large St\'ephane \bsc{Ballet}\\ - - \vspace*{0.2cm} - \large {\bf Jérôme \bsc{Benoit} et Sylvain \bsc{Papa}}\\ - - %\vspace*{0.1cm} - - % \large sous la direction de \\ - - %\vspace*{0.1cm} - - %Eric Audureau et Thierry Masson - - %\vspace*{1cm} - - \vspace*{1cm} - - %\normalsize{Licence de Mathématiques 3ème année} - \normalsize{Année 2018-2019} - -\end{center} - -\thispagestyle{empty} - -\newpage - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -\pagestyle{plain} -\frontmatter - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%Table des mati\`eres - -\tableofcontents - -\begin{figure}[!b] - \begin{center} - %\includegraphics{logo_fac2} - \includegraphics[scale=0.04]{amu} - \end{center} -\end{figure} - -\newpage - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -\mainmatter -\pagestyle{fancy} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\chapter{Introduction générale} - -\vspace{.5em} - -\section{Qu'est-ce que la recherche opérationnelle?} - -\subsection{Présentation rapide} - -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. -\newline -On la considère usuellement comme une sous discipline des mathématiques de la décision. - -\subsection{Définition de la problèmatique} - -Soient $(n, p, q) \in \mathbb{N}^3$, $x \in \mathbb{R}^n$, deux fonctions $g: \mathbb{R}^n \longrightarrow \mathbb{R}^p$ et $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$, une fonction $J: \mathbb{R}^n \longrightarrow \mathbb{R}$; -\newline -On définit le problème central $ \mathcal{P} $ que ce propose de résoudre la recherche opérationnelle : -\newline -\begin{center} -$ - \mathcal{P} \left \{ - \begin{array}{r c l} - \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\ - g(x) \leq 0 \\ - h(x) = 0 - \end{array} - \right . -$ -\end{center} - - -\section{Qu'est-ce que l'optimisation?} - -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{Sujets d'étude en travaux dirigés} - -\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} - -\subsection{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}