مسابقة دكتوراه 2018 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — الموضوع 02

مسابقة تخصص · Recherche Opérationnelle · المعامل: 3

Concours d'accès à la Formation Doctorale Mathématiques Appliquées — Spécialité ROM — Épreuve de spécialité (2h00, coefficient 3), USTHB, Faculté de Mathématiques — 30 Octobre 2018.

التمرين 1

Exercice 1 — Sac à dos 0-1, ensembles bloquants et formulations

#combinatorial-optimization#knapsack#integer-programming

On considère le problème classique du sac à dos : objets $1,2,\ldots,n$ , poids $p_j$ , utilités $a_j$ , capacité $b$ .

Écrire le problème de remplissage du sac sous forme d'un programme linéaire à variables booléennes.
Montrer qu'on peut supposer $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 est supérieure à $b$ et chacun de ses sous-ensembles propres ne l'est pas. a. Associer à chaque ensemble caractéristique une contrainte 0-1. b. Montrer que l'ajout de ces contraintes permet de supprimer la contrainte obtenue en 1. c. Appliquer à l'exemple précédent.

◀الحل

Le sac à dos 0-1 s'écrit $\max \sum a_jx_j$ sous $\sum p_jx_j \le b$ , $x_j\in\{0,1\}$ . Les poids/utilités négatifs se traitent trivialement. Le glouton marche ici par ordre décroissant des rapports ou données spécifiques. Les ensembles bloquants fournissent des inégalités de couverture $\sum_{j\in B}x_j \le |B|-1$ .

التمرين 1

Exercice 1 — Stabilité d'un semi-groupe renormalisé et inégalité différentielle

#semigroups#differential-inequalities#banach-space

Supposons que $f$ et $g$ sont deux fonctions réelles continues sur $[a,b]$ et que $f'(t) \le g(t)f(t)$ . Posons $q(t)=\exp(-\int_a^t g(s)ds)$ .

Calculer $q'(t)$ .
Montrer que $F(t)=f(t)q(t)$ est non-croissante.
En déduire que $f(t) \le f(a)\exp(\int_a^t g(s)ds)$ .

Soit aussi un $C_0$ -semi-groupe $(T(t))$ tel que $\|T(t)\| \le Me^{\omega t}$ , montrer que $S(t)=e^{-\omega t}T(t)$ est un semi-groupe uniformément borné et que son générateur est $A-\omega I$ .

◀الحل

$q'(t)=-g(t)q(t)$ . Donc $(fq)' = f'q + fq' \le gfq-gfq=0$ , d'où $fq$ décroissante et l'inégalité de Gronwall. Pour le semi-groupe, $S(t+s)=S(t)S(s)$ , $\|S(t)\|\le M$ , et le générateur est $A-\omega I$ par dérivation en 0.

التمرين 2

Exercice 2 — Optimisation multiobjectifs binaire et solutions efficaces

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

Considérer le problème à variables binaires :

\max z_1 = 6x_1 + 3x_2 + x_3, \quad \max z_2 = x_1 + 3x_2 + 6x_3

s.c. $x_1+x_2+x_3 \le 1$ , $x_i \in \{0,1\}$ .

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 d'intégrité et représenter les solutions efficaces dans l'espace de décision et les solutions non dominées dans l'espace des critères.
La caractérisation de Geoffrion est-elle valable ? Justifier.

◀الحل

Les solutions admissibles sont $0, e_1, e_2, e_3$ avec images $(0,0),(6,1),(3,3),(1,6)$ . Les points non dominés sont $(6,1),(3,3),(1,6)$ . Les solutions efficaces sont donc $e_1,e_2,e_3$ . La caractérisation de Geoffrion s'applique ici dans le cas discret avec nuance : toutes les solutions non dominées sont proprement efficaces.

التمرين 2

Exercice 2 — Pseudo-différentiels, distributions homogènes et vp(1/x)

#distributions#pseudo-differential-operators#homogeneous-distributions

Montrer que si $p(x,\xi)=\sum a_\alpha(x)\xi^\alpha$ avec $a_\alpha \in C_b^\infty$ , alors $p \in S^m$ et $p(x,D)$ envoie $\mathcal S$ dans $\mathcal S$ .
Étudier les distributions homogènes $|x|$ , $\mathrm{sgn}(x)$ , $vp(1/x)$ et $pf(1/x^2)$ : degrés et équations.
Résoudre dans $\mathcal D'(\mathbb R)$ les équations $xT=0$ puis $xT=1$ .

◀الحل

Les estimations de symbole viennent du caractère polynomial en $\xi$ . Les distributions citées sont homogènes de degrés 1, 0, -1, -2 respectivement. $xT=0$ admet pour solutions les multiples de $\delta_0$ . Une solution particulière de $xT=1$ est $vp(1/x)$ , donc l'ensemble des solutions est $vp(1/x)+c\delta_0$ .

التمرين 3

Exercice 3 — Navier-Stokes variationnel, schémas de chaleur et polynômes de Legendre

#pde#navier-stokes#finite-differences#legendre-polynomials#functional-analysis

Écrire la formulation variationnelle de Navier-Stokes incompressible, montrer que la forme bilinéaire visqueuse est continue et coercive, et établir la décroissance de l'énergie si $f=0$ .
Étudier le schéma de Richardson puis celui de DuFort-Frankel pour l'équation de la chaleur en dimension 1 : ordre, stabilité, consistance.
Montrer l'orthogonalité des polynômes de Legendre, calculer leur norme, et établir l'équation différentielle de Legendre.
Étudier un opérateur intégral sur $C([0,1])$ , une forme linéaire continue et la complétude d'un espace préhilbertien.

◀الحل

La formulation variationnelle de Navier-Stokes fait intervenir l'espace divergence nulle $V$ et la forme $a(u,v)=\nu\int \nabla u:\nabla v$ . L'énergie vérifie $\frac d{dt}E(t)+D(t)=0$ si $f=0$ . Richardson est d'ordre 2 mais inconditionnellement instable; DuFort-Frankel est explicite et stable mais peu consistant si $\Delta t/h$ ne tend pas vers 0. Les polynômes de Legendre se traitent par Rodrigues et intégrations par parties.