X-Git-Url: https://git.piment-noir.org/?p=Projet_Recherche_Operationnelle.git;a=blobdiff_plain;f=rapport%2FProjetOptimRO.tex;h=8bbbec296a5528fd104d4176aef97c0ac1d9466d;hp=00d65623b8e1a0e7e0cebf76989512b56ec35239;hb=d17ef079f644ba2ff3a64abaa6dc37fe4b634320;hpb=6ec0df371d96fde117e6e47c3075bd58eda21684 diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index 00d6562..8bbbec2 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -3,7 +3,10 @@ %%%%%Packages + \usepackage{latexsym} +\usepackage{amsmath} +\usepackage{mathtools} \usepackage{amssymb} \usepackage[utf8]{inputenc} \usepackage[francais]{babel} @@ -26,7 +29,7 @@ \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 +\renewcommand{\footrulewidth}{0.2pt} % filet en bas %%%%%Th\'eor\`eme et d\'efinitions @@ -38,6 +41,7 @@ \newtheorem{Cor}[Th]{Corollaire} \newtheorem{Rmq}{Remarque} +\newcommand{\norme}[1]{\left\Vert #1\right\Vert} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -72,11 +76,11 @@ \begin{tabular}{c} \hline - ~ \\ - \LARGE\textbf {Programmation Séquentielle Quadratique} \\ - \LARGE\textbf {en} \\ + ~ \\ + \LARGE\textbf {Programmation Séquentielle Quadratique} \\ + \LARGE\textbf {en} \\ \LARGE\textbf {Optimisation non linéraire sous contraintes} \\ - ~ \\ + ~ \\ \hline \end{tabular} @@ -128,7 +132,6 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%Table des mati\`eres \tableofcontents @@ -166,202 +169,241 @@ On la considère usuellement comme une sous discipline des mathématiques de la \subsection{Définition de la problèmatique} -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 {\it objectif} $J: \mathbb{R}^n \longrightarrow \mathbb{R}$. -\newline -Définissons le problème central $ \mathcal{P} $ que ce propose de résoudre la recherche opérationnelle : +Définissons le problème central $ \mathcal{P} $ que ce propose de résoudre la recherche opérationnelle. \begin{Def} -$ - \mathcal{P} \left \{ - \begin{array}{r c l} - \displaystyle\min_{x \in \mathcal{C}} J(x) \\ - g(x) \leq 0 \\ - h(x) = 0 - \end{array} - \right . -$ + 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} -où $ \mathcal{C} $ est l'ensemble des contraintes défini par : \begin{Def} - $ \mathcal{C} = \left \{ x \in \mathbb{R}^n | g(x) \leq 0, h(x) = 0 \right \} $ + 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 ou des solution(s). +Elle se doit de 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?} -La recherche d'une solution optimale au problème $ \mathcal{P} $ est l'activité principale de l'optimisation. +La recherche d'une valeur optimum au problème $ \mathcal{P} $ est l'activité principale de l'optimisation. +\begin{Def} + Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $. + \newline + On dit que la $ k^{ième} $ dérivée partielle de $ f $ existe au point $ x^\ast \in \mathbb{R}^n $ si l’application + $$ t \longmapsto f(x^\ast_1,\ldots,x^\ast_{k-1},x^\ast_k + t,x^\ast_{k+1},\ldots,x^\ast_n) $$ + définie sur un voisinage de $ 0 $ dans $ \mathbb{R} $ et à valeurs dans $ \mathbb{R} $ est dérivable en $ 0 $. + \newline + Dans ce cas on note + $$ \frac{\partial f}{\partial x_k}(x^\ast) $$ ou $$ \partial_k f(x^\ast) $$ + cette dérivée. +\end{Def} +\begin{Def} + Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ + et $ x^\ast, h \in \mathbb{R}^n $. + \newline + On dit que $ f $ est différentiable en $ x^\ast $ si il existe une application linéraire $ d_{x^\ast}f $ de $ \mathbb{R}^n $ dans $ \mathbb{R} $ telle que + \[ + f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \underset{h \rightarrow 0}{\mathrm{o}}(\norme{h}) + \] + Autrement dit il existe une application $ \varepsilon_{x^\ast} $ définie sur le voisinage de $ 0 $ dans $ \mathbb{R}^n $ et à valeurs dans $ \mathbb{R} $ + telle que $ \lim\limits_{h \rightarrow 0} \varepsilon_{x^\ast}(h) = 0 $ et + \[ + f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \norme{h}\varepsilon_{x^\ast}(h) + \] + On appelle $ d_{x^\ast}f $ la différentielle de $ f $ en $ x^\ast $. +\end{Def} +\begin{Rmq} + On peut démontrer que : $$ d_{x^\ast}f = \sum_{i=1}^n\frac{\partial f}{\partial x_i}(x^\ast) $$. +\end{Rmq} +\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} +\begin{Rmq} + $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle $ +\end{Rmq} +Dans le cas où $ J $ est continûment différentiable et ses dérivées sont continues (c'est à dire de classe $ \mathcal{C}^1 $), une condition suffisante et nécessaire pour que $ x^\ast \in \mathbb{R}^n $ soit un de ses extremums local ou global est que $ \nabla f(x^\ast) = 0 $. \newline -Elle +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{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} +\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} +% \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} @@ -414,7 +456,7 @@ Pour éviter le chômage technique, l'atelier A doit obligatoirement fournir 120 %\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[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.\\