[Projet_Recherche_Operationnelle.git] / rapport / ProjetOptimRO.tex

\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}

Définissons le problème central $ \mathcal{P} $ que ce propose de résoudre la recherche opérationnelle.
\begin{Def}
 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}$.
 \newline
 La problèmatique $ \mathcal{P} $ se définit par :
 $$
  \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{Def}
\begin{Def}
 On définit $ \mathcal{C} $ l'ensemble des contraintes par :
 $$ \mathcal{C} = \left \{ x \in \mathbb{R}^n \ | \ g(x) \leq 0 \land h(x) = 0 \right \} $$
\end{Def}
Elle doit résoudre les problèmes d'existence d'une solution ($ \mathcal{C} \neq \emptyset $) ainsi que de construction d'une solution.

\section{Qu'est-ce que l'optimisation?}

\begin{Def}
 Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable.
 \newline
 Le gradient de $ f $, noté $\nabla f$, en $ x^\ast \in \mathbb{R}^n$ se définit par :
 \[
     \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
 \]
\end{Def}

La recherche d'un optimum au problème $ \mathcal{P} $ est l'activité principale de l'optimisation.
\newline
Dans le cas où $ J $ est continûment différentiable et ses dérivées sont continues,
une condition suffisante pour que $ x^\ast \in \mathbb{R}^n $ soit un de ses extremums
est que $ \nabla f(x^\ast) = 0 $

% 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}