مسابقة دكتوراه 2015 — Université Badji Mokhtar - Annaba — الموضوع 02

مسابقة تخصص · EDP · المدة: 2سا

Concours d'accès en doctorat 3ème cycle (2014/2015), Formation doctorale Équations Différentielles et Applications, Option EDP — Épreuve : EDP et Distributions, Université Badji Mokhtar - Annaba, Département de Mathématiques — 18 octobre 2014, durée 02h.

التمرين 1

Exercice 1 — Problème de Neumann et condition de compatibilité

#pde#neumann-problem#lax-milgram#weak-solution#compatibility-condition

Soient $\Omega \subset \mathbb{R}^n$ un ouvert borné avec une frontière $\partial\Omega$ assez régulière et $f \in L^2(\Omega)$ . On dit que $u \in H^1(\Omega)$ est solution faible du problème de Neumann

\begin{cases} -\Delta u = f, & \text{sur } \Omega \\\\ \frac{\partial u}{\partial \nu} = 0, & \text{sur } \partial\Omega \end{cases}

\int_\Omega \nabla u(x) \cdot \nabla v(x)dx = \int_\Omega f(x)v(x)dx, \quad \forall v \in H^1(\Omega).

Montrer que si $u \in H^2(\Omega)$ est solution de (1), alors l'équation variationnelle est vérifiée.
Si $u$ est solution de l'équation variationnelle et $u \in H^2(\Omega)$ , montrer que a) $-\Delta u = f$ dans $L^2(\Omega)$ . b) $\frac{\partial u}{\partial \nu}=0$ dans $L^2(\partial\Omega)$ au sens des traces.
Montrer que la condition $\int_\Omega f(x)dx = 0$ est nécessaire pour l'existence d'une solution.
Soit $H = \{v \in H^1(\Omega), \; \int_\Omega v(x)dx = 0\}$ . En supposant la condition (3) satisfaite, montrer que si $u \in H$ vérifie l'équation variationnelle pour tout $v \in H$ , alors elle est aussi vérifiée pour tout $v \in H^1(\Omega)$ .
Utiliser le théorème de Lax-Milgram dans l'espace de Hilbert $H$ , et déduire que la condition (3) est suffisante pour l'existence d'une solution.

◀الحل

L'intégration par parties montre l'équivalence entre la formulation forte et la formulation faible sous l'hypothèse $u \in H^2(\Omega)$ .

La condition de compatibilité se voit en testant avec $v \equiv 1$ :

0 = \int_\Omega \nabla u \cdot \nabla 1 = \int_\Omega f.

Sur $H = \{v \in H^1(\Omega): \int_\Omega v = 0\}$ , la forme $a(u,v)=\int_\Omega \nabla u \cdot \nabla v$ est coercive par l'inégalité de Poincaré-Wirtinger. La forme linéaire $L(v)=\int_\Omega fv$ est continue. Lax-Milgram donne donc existence et unicité dans $H$ , donc existence d'une solution faible modulo les constantes.

\boxed{\int_\Omega f = 0 \text{ est nécessaire et suffisante}}

التمرين 1

Exercice 1 — Appariement pondéré en binômes compatibles

#graph-theory#matching#optimization#assignment

On considère un ensemble de personnes $P=\{1,2,\ldots,n\}$ (avec $n$ pair), qui doivent travailler en binômes sur des projets. Chaque personne $i$ possède une capacité $c_i$ connue. Si on constitue un binôme entre deux personnes $i$ et $j$ , alors le temps que mettra le binôme pour terminer son projet est $c_i+c_j$ . On dispose de plus d'un graphe d'incompatibilité $G=(P,A)$ dont les sommets sont les personnes. L'existence d'une arête $\{i,j\}$ signifie que les personnes $i$ et $j$ ne peuvent pas être binôme. Le but est de répartir les personnes en binômes compatibles de sorte que tous les projets soient exécutés en un minimum de temps.

Donner une formulation mathématique de ce problème.
Donner une autre formulation.
Comparer les deux formulations.

◀الحل

On cherche un couplage parfait dans le graphe de compatibilité (complémentaire du graphe d'incompatibilité) minimisant la somme des temps.

Formulation 1 : variables binaires $x_{ij}$ valant 1 si $(i,j)$ est choisi.

\min \sum_{i<j} (c_i+c_j)x_{ij}

s.c. chaque sommet est incident à exactement une arête choisie, $x_{ij}=0$ si $\{i,j\}$ est une arête d'incompatibilité.

Formulation 2 : comme problème de matching pondéré sur graphe, résoluble par algorithmes spécialisés.

La deuxième formulation est plus compacte conceptuellement et permet d'utiliser la théorie des couplages.

التمرين 1

Exercice 1 — Sac à dos, ensembles bloquants et formulation linéaire

#combinatorial-optimization#knapsack#integer-programming#blocking-sets#greedy-algorithm

On considère le problème classique du sac à dos : les objets à emporter sont $1,2,\ldots,n$ , ont pour poids $p_1,p_2,\ldots,p_n$ et pour coefficients d'utilité $a_1,a_2,\ldots,a_n$ . La capacité du sac est $b$ .

Écrire le problème d'optimisation du remplissage du sac sous forme d'un programme linéaire à variables booléennes.
Montrer que nous pouvons supposer que $p_j \ge 0$ et $a_j \ge 0$ .
Montrer que l'algorithme glouton donne une solution optimale pour le cas $a^t=(7,5,4,3,2)$ , $p^t=(8,6,6,4,3)$ et $b=18$ .
Un ensemble d'objets est dit bloquant si la somme des poids des objets qui le composent est supérieure à $b$ . a) Montrer que l'on peut associer à chaque ensemble caractéristique une contrainte où les coefficients des variables sont 0 ou 1. b) Montrer que l'ajout de ces contraintes permet de supprimer la contrainte obtenue en 1, qui contenait des coefficients supérieurs à 1, et que les deux formulations sont équivalentes. c) Peut-on être assuré que l'optimum trouvé a toutes ses coordonnées égales à 0 ou 1 ? Appliquer à l'exemple précédent.

◀الحل

Le sac à dos 0-1 s'écrit :

\max \sum a_j x_j, \quad \sum p_j x_j \le b, \; x_j \in \{0,1\}.

On peut supposer $p_j,a_j \ge 0$ car un poids négatif ou une utilité négative se traite trivialement ou se supprime.

L'algorithme glouton par ratio $a_j/p_j$ peut être optimal dans certains cas numériques, comme l'exemple proposé, qu'on vérifie en comparant les combinaisons admissibles.

Les ensembles bloquants fournissent des inégalités de couverture de la forme $\sum_{j \in B} x_j \le |B|-1$ . Leur ajout renforce la relaxation et donne une formulation équivalente sur les solutions entières.

التمرين 2

Exercice 2 — EDP hyperbolique du second ordre et problème de Cauchy

#pde#classification#characteristics#cauchy-problem

Étant donnée l'équation aux dérivées partielles du second ordre

u_{xx} + 2u_{xy} - 3u_{yy} = 2.

De quel type est-elle ?
Déterminer les lignes caractéristiques de $(E)$ .
Transformer l'équation $(E)$ à l'aide du changement de variables suivant :

\begin{cases} \theta = x + y \\\\ \xi = -3x + y. \end{cases}

En déduire la solution générale de $(E)$ en termes des variables $x$ et $y$ . 4. Résoudre le problème de Cauchy

\begin{cases} u_{xx} + 2u_{xy} - 3u_{yy} = 2, & (x,y) \in \mathbb{R}^2 \\\\ u(x,0)=0, \\\\ u_y(x,0)=x+\cos x. \end{cases}

◀الحل

Les coefficients donnent $A=1$ , $B=1$ , $C=-3$ . Le discriminant $B^2-AC = 1 - (1)(-3) = 4 \gt 0$ , donc l'équation est hyperbolique.

Les caractéristiques vérifient $A(dy)^2 - 2Bdxdy + C(dx)^2 = 0$ , soit $dy^2 - 2dxdy - 3dx^2=0$ , donc $(dy-3dx)(dy+dx)=0$ , d'où $y=3x+c_1$ et $y=-x+c_2$ .

Avec $\theta=x+y$ , $\xi=-3x+y$ , l'équation se réduit à une forme canonique $u_{\theta\xi}= ext{constante}$ . On intègre deux fois pour obtenir la solution générale, puis on utilise les données de Cauchy pour déterminer les fonctions arbitraires.

التمرين 2

Exercice 2 — Sac à dos à regret minimal

#combinatorial-optimization#knapsack#dynamic-programming#regret

On considère $n$ objets, de poids respectifs $p_i$ et de regret $r_i$ , avec $P$ un entier. Le regret d'un sac est la somme des regrets des objets qui ne sont pas dans le sac. On cherche à construire un sac de poids inférieur ou égal à $P$ qui soit de regret minimal.

Modéliser ce problème à l'aide d'un programme mathématique.
Définir un schéma de programmation dynamique.
Notons $F_k(E)$ le regret minimum d'un sac de poids inférieur ou égal à $P-E$ parmi les objets $\{k,\ldots,n\}$ . Comment se définit la solution du problème initial ?
Que vaut $F_{n+1}(E)$ ?
Établir l'équation de récurrence satisfaite par les $F_k$ .
En déduire un algorithme pour résoudre le problème et donner sa complexité.

◀الحل

Le modèle 0-1 est :

\min \sum_i r_i(1-x_i), \quad \sum_i p_i x_i \le P, \; x_i \in \{0,1\}.

En programmation dynamique, à l'étape $k$ on décide de prendre ou non l'objet $k$ selon la capacité restante $E$ .

Base : $F_{n+1}(E)=0$ .

Récurrence :

si $p_k \le E$ : $F_k(E)=\min(F_{k+1}(E-p_k), r_k+F_{k+1}(E))$ ,
sinon $F_k(E)=r_k+F_{k+1}(E)$ .

La solution initiale est $F_1(P)$ . La complexité est pseudo-polynomiale en $O(nP)$ .

التمرين 2

Exercice 2 — Optimisation multiobjectifs à variables binaires

#multiobjective-optimization#binary-optimization#efficient-solutions#geoffrion-proper-efficiency

Considérons le problème d'optimisation multi-objectifs à variables binaires :

\max z_1 = 6x_1 + 3x_2 + x_3

\max z_2 = x_1 + 3x_2 + 6x_3

s.c.

x_1 + x_2 + x_3 \le 1, \quad x_1,x_2,x_3 \in \mathbb{R}_+.

Représenter l'ensemble des solutions admissibles dans l'espace des critères.
Trouver géométriquement l'ensemble des solutions efficaces et l'ensemble des solutions non-dominées.
Ajouter les contraintes $x_1,x_2,x_3 \in \mathbb{Z}$ et représenter les solutions efficaces dans l'espace de décision et l'ensemble des solutions non-dominées dans l'espace des critères.
La caractérisation de Geoffrion est-elle valable ? Justifier.

◀الحل

L'ensemble admissible sans intégralité est le triangle $x_1+x_2+x_3 \le 1$ , $x_i \ge 0$ . Son image dans l'espace des critères est l'enveloppe convexe des points $(0,0)$ , $(6,1)$ , $(3,3)$ , $(1,6)$ .

L'ensemble efficace correspond à l'enveloppe supérieure non dominée. Avec intégralité, les seules solutions sont $(0,0,0)$ , $(1,0,0)$ , $(0,1,0)$ , $(0,0,1)$ , donnant les points critères correspondants. On compare alors la dominance.

La propre efficacité au sens de Geoffrion dépend de la bornitude des rapports d'échange entre objectifs. Sur un ensemble fini, elle est généralement satisfaite pour les solutions efficaces non dominées.

التمرين 3

Exercice 3 — Système de Lorenz et hélice circulaire droite

#dynamical-systems#lorenz-system#stability#space-curves#frenet-frame

Exercice 1 : Considérons le système différentiel réel suivant

\begin{cases} x' = -ax + ay \\\\ y' = bx - y - xz \\\\ z' = -cz + xy \end{cases}

où $c \gt 0$ , $a \gt c+1$ et $b \gt 0$ , appelé système différentiel de Lorenz.

Vérifier que dans le cas $b \lt 1$ le seul point d'équilibre est la solution nulle.
Déterminer les points d'équilibre de ce système différentiel dans le cas $b \gt 1$ .
Étudier la stabilité de la solution nulle.

Exercice 2 : Soit dans $\mathbb{R}^3$ la courbe d'équations $x=\cos t$ , $y=\sin t$ , $z=bt$ où $b$ est une constante.

Faire un dessin.
Déterminer le trièdre de Frenet-Serret $(T,N,B)$ .
Démontrer que la courbure et la torsion sont constantes en tout point.

◀الحل

Pour Lorenz : les points d'équilibre satisfont $x=y$ et $bx-y-xz=0$ , $-cz+x^2=0$ .

Si $b \lt 1$ , seul $(0,0,0)$ convient.
Si $b \gt 1$ , on obtient $(0,0,0)$ et les deux points $\left(\pm\sqrt{c(b-1)}, \pm\sqrt{c(b-1)}, b-1\right)$ .

La stabilité de la solution nulle se lit sur la matrice jacobienne en 0.

Pour la courbe $\gamma(t)=(\cos t, \sin t, bt)$ , c'est une hélice circulaire droite.

$\gamma'(t)=(-\sin t, \cos t, b)$ , de norme $\sqrt{1+b^2}$ . Donc

T(t)=\frac{1}{\sqrt{1+b^2}}(-\sin t,\cos t,b).

On calcule ensuite $N$ à partir de $T'/\|T'\|$ puis $B=T\wedge N$ .

La courbure et la torsion valent

\boxed{\kappa = \frac{1}{1+b^2}, \quad \tau = \frac{b}{1+b^2}}

et sont constantes.

→←

→السابقConcours Doctorat 2015 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — Épreuve N°02 التاليConcours Doctorat 2015 — Source inconnue — Épreuve N°02←