X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=rapport%2FProjetOptimRO.tex;h=7a583392366da994ecffccc23f01a7060463553f;hb=3b344e8c7829eb5db41c21b3a26eb1f90d4bffcd;hp=7370bba682f867a1e46db31c3f23345f94054e01;hpb=f899c72b16952ac4f1d71594788d03f62a596b3a;p=Projet_Recherche_Operationnelle.git diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index 7370bba..7a58339 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -188,7 +188,7 @@ Définissons le problème central $ \mathcal{P} $ que se propose de résoudre la 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 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} $. +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 d'une solution dans $ \mathcal{C} $. \section{Qu'est-ce que l'optimisation?} @@ -196,7 +196,7 @@ Elle se doit de résoudre les problèmes d'existence d'une solution ($ \mathcal{ 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. \newline -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. +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, elle, une science. \subsection{Quelques définitions annexes} @@ -261,9 +261,22 @@ $$ \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \exists \alpha \in \mathbb{R}_{+ \subsection{Conditions d'existence d'un extremum} +On peut démontrer que $ \mathcal{C }$ est un ensemble fermé de $ \mathbb{R}^n $ si $ g $ et $ h $ sont continues. +On peut en déduire que si $ J $ est continue, $ \mathcal{C }$ est un ensemble fermé et borné de $ \mathbb{R}^n $. +\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) $$ +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} $. +\end{Th} +On en déduit que $ \mathcal{P} $ admet au moins une solution dans le cas où $ J, g ,h $ sont continues. +\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 $. \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 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. +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. \subsubsection{Conditions de Kuhn-Tucker et Lagrange} @@ -271,13 +284,16 @@ On peut en déduire que une condition nécessaire et suffisante pour que $ x^\as Soient $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $. \newline Une condition nécessaire pour que $ x^\ast \in \mathcal{C}$ soit un minimum local est : -$$ \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 $$ -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. \newline \newline +\centerline{$ \{ \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.} +\newline +\newline +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 i \in \{ 1,\ldots,q \} \ h_i = 0 \Longleftrightarrow \exists g_i \ g_i \leq 0 \land g_i \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 \Longleftrightarrow 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.