rapport/ProjetOptimRO.tex

   1 \documentclass[12pt,oneside,a4paper]{book}
   2
   3
   4 %%%%%Packages
   5
   6
   7 \usepackage{latexsym}
   8 \usepackage{amsmath}
   9 \usepackage{mathtools}
  10 \usepackage{amssymb}
  11 \usepackage[utf8]{inputenc}
  12 \usepackage[francais]{babel}
  13 \usepackage{color}
  14 \usepackage{geometry}
  15 \usepackage{graphicx}
  16 \usepackage{amsfonts}
  17 \usepackage[T1]{fontenc}
  18 \usepackage{multirow}
  19 \usepackage{fancyhdr}
  20 \usepackage{tocbibind}
  21 \usepackage{lmodern}
  22
  23
  24 %%%%%Marges & en-t\^etes
  25
  26 \geometry{hmargin=2.3cm, vmargin=3cm}
  27 \fancyhf{} % supprime les en-t\^etes et pieds pr\'ed\'efinis
  28 \fancyhead[FC]{\bfseries\thepage} % N∞page centre bas
  29 \fancyhead[HC]{\footnotesize\leftmark} % chapitre centre haut
  30 \renewcommand{\headrulewidth}{0.2pt} % filet en haut
  31 \addtolength{\headheight}{0.5pt} % espace pour le filet
  32 \renewcommand{\footrulewidth}{0.2pt} % filet en bas
  33
  34
  35 %%%%%Th\'eor\`eme et d\'efinitions
  36
  37 \newtheorem{Def}{D\'efinition}
  38 \newtheorem{Not}[Def]{Notation}
  39 \newtheorem{Th}{Th\'eor\`eme}
  40 \newtheorem{Prop}[Th]{Proposition}
  41 \newtheorem{Cor}[Th]{Corollaire}
  42 \newtheorem{Rmq}{Remarque}
  43
  44 \newcommand{\norme}[1]{\left\Vert #1\right\Vert}
  45
  46 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  47 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  48
  49 \begin{document}
  50
  51 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  52 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  53
  54 %%%%%Page de garde
  55
  56 \begin{center}
  57
  58  %\includegraphics[scale=0.5]{logo_sciences_rvb.png}\\
  59  \includegraphics[scale=0.5]{polytech.png}\\
  60
  61  \vspace*{0.5cm}
  62
  63  \footnotesize{
  64   \large \bf D\'epartement d'Informatique, Réseaux et Multimédia\\
  65   \large \bf  5ème année\\
  66  }
  67
  68  \vspace*{0.5cm}
  69
  70  %\large{Master 2 Professionnel\\
  71  %Math\'ematiques et Informatique des Nouvelles Technologies\\}
  72
  73  \large{Projet \\ en \\ Optimisation et Recherche Opérationnelle \\}
  74
  75  \vspace*{0.7cm}
  76
  77  \begin{tabular}{c}
  78   \hline
  79   ~                                                           \\
  80   \LARGE\textbf {Programmation Séquentielle Quadratique}      \\
  81   \LARGE\textbf {en}                                          \\
  82   \LARGE\textbf {Optimisation non linéraire sous contraintes} \\
  83   ~                                                           \\
  84   \hline
  85  \end{tabular}
  86
  87  \vspace*{0.7cm}
  88
  89  \includegraphics[scale=0.4]{CE.PNG}\\
  90
  91  \vspace*{0.5cm}
  92
  93  \large par\\
  94
  95  %\large  \bsc{}\\
  96  %\normalsize{M\'emoire encadr\'e par :} \large St\'ephane \bsc{Ballet}\\
  97
  98  \vspace*{0.2cm}
  99  \large  {\bf Jérôme \bsc{Benoit} et Sylvain \bsc{Papa}}\\
 100
 101  %\vspace*{0.1cm}
 102
 103  % \large sous la direction de \\
 104
 105  %\vspace*{0.1cm}
 106
 107  %Eric Audureau et Thierry Masson
 108
 109  %\vspace*{1cm}
 110
 111  \vspace*{1cm}
 112
 113  %\normalsize{Licence de Mathématiques 3ème année}
 114  \normalsize{Année 2018-2019}
 115
 116 \end{center}
 117
 118 \thispagestyle{empty}
 119
 120 \newpage
 121
 122
 123 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 124 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 125
 126
 127 \pagestyle{plain}
 128 \frontmatter
 129
 130
 131 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 133
 134
 135 %%%%%Table des mati\`eres
 136
 137 \tableofcontents
 138
 139 \begin{figure}[!b]
 140  \begin{center}
 141   %\includegraphics{logo_fac2}
 142   \includegraphics[scale=0.04]{amu}
 143  \end{center}
 144 \end{figure}
 145
 146 \newpage
 147
 148
 149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 151
 152
 153 \mainmatter
 154 \pagestyle{fancy}
 155
 156
 157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 158 \chapter{Introduction générale}
 159
 160 \vspace{.5em}
 161
 162 \section{Qu'est-ce que la recherche opérationnelle?}
 163
 164 \subsection{Présentation rapide}
 165
 166 La recherche opérationnelle est une discipline dite "hybride" au confluent de plusieurs disciplines dont principalement les mathématiques (l'analyse numérique, les probabilités, la statistique) et l'informatique (l'algorithmie).
 167 \newline
 168 On la considère usuellement comme une sous discipline des mathématiques de la décision. Elle a de nombreuses applications, particulièrement en intelligence artificielle.
 169
 170 \subsection{Définition de la problèmatique}
 171
 172 Définissons le problème central $ \mathcal{P} $ que se propose de résoudre la recherche opérationnelle :
 173 \begin{Def}
 174  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}$.
 175  \newline
 176  La problèmatique $ \mathcal{P} $ se définit par :
 177  $$
 178   \mathcal{P} \left \{
 179   \begin{array}{r c l}
 180    \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
 181    g(x) \leq 0                                 \\
 182    h(x) = 0
 183   \end{array}
 184   \right .
 185  $$
 186 \end{Def}
 187 \begin{Def}
 188  On définit $ \mathcal{C} $ l'ensemble des contraintes par :
 189  $$ \mathcal{C} = \left \{ x \in \mathbb{R}^n \ | \ g(x) \leq 0 \land h(x) = 0 \right \} $$
 190 \end{Def}
 191 Elle se doit de résoudre les problèmes d'existence d'une solution ($ \mathcal{C} \neq \emptyset $ et $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $ défini dans $ \mathcal{C} $) ainsi que de construction de la solution dans $ \mathcal{C} $.
 192
 193 \section{Qu'est-ce que l'optimisation?}
 194
 195 \subsection{Définition}
 196
 197 La recherche d'une méthode permettant de trouver la solution au problème $ \mathcal{P} $ dans $ \mathcal{C} $ est l'activité principale de l'optimisation.
 198 \newline
 199 Si la modélisation de la problèmatique $ \mathcal{P} $ est considérée comme un art, la recherche d'une solution au problème $ \mathcal{P} $ dans $ \mathcal{C} $ est une science.
 200
 201 \subsection{Quelques définitions annexes}
 202
 203 Définissons quelques notions supplémentaires de base nécessaires à la suite :
 204 \begin{Def}
 205 Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
 206 \newline
 207 On dit que $ x^\ast $ est \textbf{intérieur} à $ A $ si $ A $ est un voisinage de $ x^\ast $. On appelle intérieur de $ A $ l'ensemble des points intérieurs à $ A $ et on le note $ \mathring{A} $.
 208 \end{Def}
 209 \begin{Def}
 210 Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
 211 \newline
 212 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} $.
 213 \end{Def}
 214
 215 \begin{Def}
 216 Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $.
 217 \newline
 218 On dit que $ f $ est continue en $ x^\ast $ si
 219 $$ \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 $$
 220 \end{Def}
 221 \begin{Def}
 222  Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $.
 223  \newline
 224  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
 225  $$ t \longmapsto f(x^\ast_1,\ldots,x^\ast_{k-1},x^\ast_k + t,x^\ast_{k+1},\ldots,x^\ast_n) $$
 226  définie sur un voisinage de $ 0 $ dans $ \mathbb{R} $ et à valeurs dans $ \mathbb{R} $ est dérivable en $ 0 $.
 227  \newline
 228  Dans ce cas on note
 229  $$ \frac{\partial f}{\partial x_k}(x^\ast) $$ ou $$ \partial_k f(x^\ast) $$
 230  cette dérivée.
 231 \end{Def}
 232 \begin{Def}
 233  Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $
 234  et $ x^\ast, h \in \mathbb{R}^n $.
 235  \newline
 236  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
 237  \[
 238   f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \underset{h \rightarrow 0}{\mathrm{o}}(\norme{h})
 239  \]
 240  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} $
 241  telle que $ \lim\limits_{h \rightarrow 0} \varepsilon_{x^\ast}(h) = 0 $ et
 242  \[
 243   f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \norme{h}\varepsilon_{x^\ast}(h)
 244  \]
 245  On appelle $ d_{x^\ast}f $ la différentielle de $ f $ en $ x^\ast $.
 246 \end{Def}
 247 \begin{Rmq}
 248  On peut démontrer que : $$ d_{x^\ast}f = \sum_{i=1}^n\frac{\partial f}{\partial x_i}(x^\ast) $$.
 249 \end{Rmq}
 250 \begin{Def}
 251  Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable.
 252  \newline
 253  Le gradient de $ f $, noté $\nabla f$, en $ x^\ast \in \mathbb{R}^n$ se définit par :
 254  \[
 255   \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
 256  \]
 257 \end{Def}
 258 \begin{Rmq}
 259  $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle $
 260 \end{Rmq}
 261
 262 \subsection{Conditions d'existence d'un extremum}
 263
 264 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 $.
 265 \newline
 266 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 ou globaux 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.
 267
 268 \subsubsection{Conditions de Kuhn-Tucker et Lagrange}
 269
 270 \begin{Th}
 271 Soient $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $.
 272 \newline
 273 Une condition nécessaire pour que $ x^\ast \in \mathcal{C}$ soit un minimum local est :
 274 $$ \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 $$
 275 et $ \{ \nabla g_1(x^\ast),\ldots,\nabla g_p(x^\ast),\nabla h_1(x^\ast),\ldots,\nabla h_q(x^\ast) \} $ sont linéairement indépendants.
 276 \newline
 277 \newline
 278 On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange.
 279 \end{Th}
 280 Il est à noter que une condition d'égalité peut se répresenter par deux conditions d'inégalité : $ \forall i \in \{ 1,\ldots,q \} \ h_i = 0 \Longleftrightarrow \exists g_i \ g_i \leq 0 \land g_i \geq 0 $.
 281 \newline
 282 \newline
 283 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.
 284
 285 % 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.}.
 286 % 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}.
 287
 288 %{\it La relativité}, Que sais-je?, 4ème  édition, puf, 2000, \cite{Mavr};
 289 %ainsi que Jean Hladik, {\it La relativité selon Einstein}, L'esprit des sciences, Ellipses, 2000, \cite{Hlad}.
 290
 291
 292 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 293
 294 \chapter{Méthodes de programmation quadratique séquentielle}
 295
 296 % \section{Cahier des charges}
 297 %
 298 % 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
 299 % à 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).
 300 %
 301 % \vspace{.5em}
 302 %
 303 % Sur la fond, toutes les sources de connaissance utilisées devront être citées. En particulier, la méthodologie universitaire sera privilégiée
 304 % (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...).
 305 % 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).
 306 % L'accent sera essentiellement mis sur la démarche scientifique utilisée à égal niveau avec le contenu acquis des connaissances.
 307 %
 308 % \vspace{.5em}
 309 %
 310 % Plusieurs sources devront être croisées afin de prétendre au maximum de vraisemblance
 311 % et d'objectivité scientifique. Le document  ne devra pas excéder 10 pages.
 312 % On privilégiera les qualités de synthèse, d'organisation ainsi que du contenu du document.
 313 %
 314 % \section{Proposition de sujets}
 315 %
 316 % \subsection{Analyse numérique}
 317 %
 318 % \vspace{.5em}
 319 %
 320 % 1) Méthode des moindres Carrés (cas général, cas pondéré, cas des équations non linéaires).
 321 %
 322 % \vspace{.5em}
 323 %
 324 % 2) Méthode de Newton-Raphson (cas d'une variable, cas de deux variables) - Application: extrema d'une fonction à deux variables.
 325 %
 326 % \vspace{.5em}
 327 %
 328 % 3) Autres méthodes: méthode de Jacobi, de Gauss-Seidel, etc....
 329 %
 330 % \vspace{.5em}
 331
 332 \section{Optimisation}
 333
 334 % \vspace{.5em}
 335
 336 % \subsubsection{Optimisation sans contrainte}
 337 %
 338 % {\bf A- Algorithmes déterministes}
 339 %
 340 % \vspace{.5em}
 341 %
 342 % 1) Régression linéaire sans contrainte (pré-requis: Méthode des moindres carrés).
 343 %
 344 % \vspace{.5em}
 345 %
 346 % 2) Méthodes de descente: la méthode du gradient (à pas constant ou à pas variable ou à pas optimal).
 347 %
 348 % \vspace{.5em}
 349 %
 350 % 3) Méthode de Newton (ou méthode dite de la tangente) et application à la recherche d'extrema.
 351 %
 352 % \vspace{.5em}
 353 %
 354 % 4) Méthodes de descente: méthode du gradient conjugué (cas linéaire et cas général)
 355 %
 356 % \vspace{.5em}
 357 %
 358 % 5) Méthode de relaxation
 359 %
 360 % \vspace{.5em}
 361 %
 362 % {\bf B- Algorithmes probabilistes ou dit stochastiques}
 363 %
 364 % \vspace{.5em}
 365 %
 366 % 1) Dynamique de métropolis (prérequis: chaines de Markov)
 367 %
 368 % \vspace{.5em}
 369 %
 370 % 2) Recuit simulé sur un ensemble fini et application au problème du voyageur de commerce (prérequis: dynamique de métropolis)
 371 %
 372 % \vspace{.5em}
 373
 374 \subsubsection{Optimisation ou minimisation avec contraintes}
 375
 376 % \vspace{.5em}
 377 %
 378 % 1) Régression linéaire avec contraintes (prérequis: méthode des moindres carrés, conditions ou équations dites de Karush-kuhn-Tucker (KKT)) .
 379 %
 380 % \vspace{.5em}
 381 %
 382 % 2) Cas de la programmation linéaire (prérequis: Lagrangien et multiplicateurs de Lagrange, conditions de KKT).
 383 %
 384 % \vspace{.5em}
 385 %
 386 % 3) Algorithmes: méthode du gradient projeté, méthode de Lagrange-Newton pour des contraintes en égalité,
 387 % méthode de Newton projetée pour des contraintes de bornes, méthodes de pénalisation,
 388 % méthodes de programmation quadratique successive (SQP Sequential Quadratic Programming),
 389 % méthode de dualité (méthode d'Uzawa, prérequis: théorie de la dualité convexe) etc...
 390 %
 391 % \vspace{.5em}
 392 %
 393 % \subsection{Recherche opérationnelle}
 394 %
 395 % \vspace{.5em}
 396 %
 397 % \subsubsection{La programmation linéaire (cas particulier de l'optimisation avec contraintes)}
 398 %
 399 % 1) Méthode d'énumération.
 400 %
 401 % \vspace{.5em}
 402 %
 403 % 2) Méthode du simplexe.
 404 %
 405 % \vspace{.5em}
 406 %
 407 % 3) Application à des problèmes de R.O:
 408 %
 409 % \vspace{.5em}
 410 %
 411 % \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}.
 412 %
 413 % \vspace{.5em}
 414 %
 415 % \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire.
 416 %
 417 % \vspace{.5em}
 418 %
 419 % \hspace{.6em} b) Combien d'oeufs extra et sublime doit-il fabriquer pour faire le plus grand bénéfice?
 420 %
 421 % \vspace{.5em}
 422 %
 423 % \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 :
 424 %
 425 % \vspace{.5em}
 426 %
 427 % \begin{center}
 428 %  $
 429 %   \begin{array}{|c|c|c|c|}
 430 %    \hline
 431 %    Atelier & A   & B   & C   \\
 432 %    \hline
 433 %    Pièce 1 & 3 h & 5 h & 2 h \\
 434 %    \hline
 435 %    Pièce 2 & 1 h & 3 h & 3 h \\
 436 %    \hline
 437 %   \end{array}
 438 %  $
 439 % \end{center}
 440 %
 441 % \vspace{.5em}
 442 %
 443 % 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.
 444 %
 445 % \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire.
 446 %
 447 % \vspace{.5em}
 448 %
 449 % \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?
 450 %
 451 % \vspace{.5em}
 452
 453 \bibliographystyle{plain}
 454 \bibliography{stdlib_sbphilo}
 455
 456 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 457
 458 \end{document}
 459
 460
 461 \begin{thebibliography}{6}\input{MemoireM2Ballet6.synctex.gz(busy)}
 462
 463  %\bibitem[1]{BL} Jean-Pierre \bsc{Bourguignon} et David \bsc{Langlois}, Cours de M1, Module Relativité Générale,
 464  %Ecole Polytechnique, ParisTech,   2011.\\
 465
 466  %\bibitem[2]{G} Gilles \bsc{Cohen-Tannoudji}, Einstein et la refondation relativiste de la physique, 2005.\\
 467
 468  %\bibitem[3]{D} Pierre \bsc{Duhem}, La théorie physique, son objet, sa structure, Vrin, 2007.\\
 469
 470  %\bibitem[4]{E1}  Albert \bsc{Einstein}, Die formale grundlage der allgemeinen Relativittstheorie. Kniglich Preussische
 471  %Akademie der Wissenschaften (Berlin),Sitzungsberichte: pp 1030-1085. \\
 472
 473  %\bibitem[5]{G} Christian \bsc{Godin}, Dictionnaire de philosophie, Fayard Edition du temps, 2004.\\
 474
 475  %\bibitem[6]{H} Jean \bsc{Hladik}, La Relativité selon Einstein, L'Esprit des Sciences, Ellipses.\\
 476
 477  %\bibitem[7]{IS}  \bsc{Iftime} and \bsc{Stachel}, The hole argument for covariant theories, arKiv:gr-qc/0512021v2, 8 avril 2006.\\
 478
 479  %\bibitem[8]{K} \bsc{Kant}, Critique de la raison pure, Traduction, présentation, notes par Alain Renaut, GF-Flammarion, 2006.\\
 480
 481  %\bibitem[9]{K2} \bsc{Kant}, Prolégomènes à toute métaphysique future, Traduction de Louis Guilermit, Vrin, 1986.\\
 482
 483  %\bibitem[10]{KU} Thomas \bsc{Kuhn}, La structure des révolutions scientifiques, Flammarion Champs Sciences, 2008.
 484
 485  %\bibitem[11]{L} Marc \bsc{Lachièze-Rey}, Initiation à la cosmologie, 3ème édition, Dunod, 2000.\\
 486
 487  %\bibitem[12]{Mas} Thierry \bsc{Masson}, Cours de géométrie différentielle, groupe et algèbre de Lie, fibrés et connexions, 2010.\\
 488
 489  %\bibitem[13]{Poi} Henri \bsc{Poincaré}, La Science et L'Hypothèse, Flammarion, Paris, 1968.\\
 490
 491  %\bibitem[14]{Mav} Stamatia \bsc{Mavridès}, La Relativité, Que sais-je, 4ème édition, PUF, 2000.\\
 492
 493  %\bibitem[15]{R} Robert \bsc{Rynasiewicz}, The Lessons of the Hole Argument, The British Journal of the Philosophy of Science,
 494  %vol; 45 (2), 407-436, Oxford University Press, Oxford Journals, 1994. \\
 495
 496  %\bibitem[16]{S} Standford Encyclopedia of Philosophy.\\
 497
 498  %\bibitem[17]{W} Wikipedia.\\
 499
 500  %\bibitem[1]{Bachtold}  {\bf Manuel Bächtold}, L'interprétation de la mécanique quantique, une approche pragmatique, Collection vision des sciences, Hermann, 2008 .\\
 501
 502  %\bibitem[2]{Aspect}  {\bf Alain Aspect}, Présentation naïve des inégalités de Bell, 2004.\\
 503
 504  % \bibitem[3]{Basda}  {\bf Jean-Louis Basdevant et Manuel Joffre}, Mécanique Quantique, Les éditions de l'Ecole Polytechnique, 2006.\\
 505
 506  %\bibitem[4]{Diu} {\bf Bernard Diu}, Le congrès de Solvay de 1927: petite chronique d'un grand évènement, Bibnum.\\
 507
 508  %\bibitem[1]{B}  \bsc{Aristote}, Métaphysique, traduction J.Tricot, Vrin, 1974.\\
 509
 510 \end{thebibliography}