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

مسابقة عامة · الرياضيات · المعامل: 1

Concours d'accès à la Formation Doctorale Mathématiques Appliquées — Épreuve générale (1h30, coefficient 1), USTHB, Faculté de Mathématiques — 26 Octobre 2017 — Spécialités MaDOC, OStoch, ROM, ROMaD.

التمرين 1

Exercice 1 — Chaînes maximales et cycles dans un graphe connexe

#graph-theory#paths#cycles#connected-graphs

Soit $G=(V,E)$ un graphe connexe simple.

Montrer que si $P=(v_1,v_2,\ldots,v_k)$ est une plus longue chaîne élémentaire de $G$ , alors tous les voisins de $v_1$ sont dans $P$ .
Montrer que si tous les degrés des sommets de $G$ sont supérieurs ou égaux à 2, alors $G$ possède un cycle élémentaire.
Montrer que si tous les degrés des sommets de $G$ sont supérieurs ou égaux à $k \geq 2$ , alors $G$ possède un cycle élémentaire de longueur supérieure ou égale à $k+1$ .
Montrer que deux chaînes de longueur maximum $P$ et $Q$ de $G$ ont au moins un sommet commun. Ont-elles une arête commune ?
En déduire que si $G$ possède deux chaînes de longueur maximum elles sont obligatoirement de longueur paire. Où se situe le sommet commun ?

◀الحل

1.

Si un voisin $w$ de $v_1$ n'était pas dans $P$ , alors $(w,v_1,v_2,\ldots,v_k)$ serait une chaîne élémentaire plus longue. Contradiction.

2.

Soit $P$ une plus longue chaîne. Par 1, tous les voisins de $v_1$ sont dans $P$ . Comme $d(v_1) \geq 2$ , $v_1$ a un voisin $v_i$ avec $i \geq 3$ . Alors $(v_1,v_2,\ldots,v_i,v_1)$ est un cycle.

3.

Par 1, $v_1$ a au moins $k$ voisins sur $P$ , donc le plus éloigné est à distance au moins $k$ , d'où un cycle de longueur au moins $k+1$ .

4-5.

Deux chaînes maximales se coupent sinon un chemin de connexion permettrait de les concaténer et obtenir plus long. L'analyse fine montre les propriétés demandées sur la longueur et le sommet commun.

التمرين 2

Exercice 2 — Programme linéaire, dualité et écarts complémentaires

#linear-programming#duality#complementary-slackness#simplex

On considère le problème :

\max Z(x) = 4x_1 - 3x_2

sous contraintes

-x_1 + x_2 \leq 6, \quad x_1 + x_2 = 4, \quad -2x_1 + 4x_2 \geq 2, \quad x_1 \in [-3,2], \; x_2 \geq 0.

Résoudre le programme à l'aide de l'algorithme dual et détailler les étapes.
Écrire le problème dual.
Trouver les valeurs des variables duales.
Vérifier le théorème des écarts complémentaires.

◀الحل

On met le problème sous forme standard puis on écrit le dual. La résolution graphique ou dual-simplex donne la solution optimale. Les variables duales se déterminent à partir de la base optimale et on vérifie les écarts complémentaires.

\boxed{\text{Solution obtenue via dual-simplex et vérifiée par complémentarité}}

التمرين 3

Exercice 3 — Sac à dos, arbre/forêt maximum et PL bi-objectif

#knapsack#maximum-spanning-tree#multiobjective-optimization#graph-theory

On considère :

Un problème de sac-à-dos avec objets de poids $(2,3,4,5)$ et valeurs $(3,4,5,6)$ . Écrire le PL et décrire une méthode autre que simplex pour le résoudre.
Une épreuve de spécialité ROM 2017 sur les arbres de poids maximum : caractérisations, algorithme glouton, conditions pour forêt/arbre, formulation 0-1.
Un PL bi-objectif ROM 2017 :

\max 3x_1 + x_2, \quad \max -x_1 - 2x_2

sous contraintes $x_1 + 2x_2 \geq 2$ , $x_1 \leq 4$ , $x_2 \leq 3$ , $x_1,x_2 \geq 0$ .

Calculer l'ensemble des solutions efficientes, des bases efficientes et des vecteurs critères non dominés. 4. Épreuve d'aide à la décision 2016 : reformulation graphique d'un problème MOLP et analyse d'une chaîne de Markov finie.

◀الحل

1.

PL du sac à dos : $\max 3x_1+4x_2+5x_3+6x_4$ sous $2x_1+3x_2+4x_3+5x_4 \leq b$ , $x_i \in \{0,1\}$ . Méthode alternative : programmation dynamique.

2.

Même arguments que l'exercice sur les arbres maximums : algorithme de Kruskal inversé, formulation 0-1 et conditions d'arbre/forêt.

3.

On résout le problème pondéré associé et on identifie la frontière de Pareto dans l'espace des décisions et des critères.

4.

Analyse géométrique de l'ensemble efficace d'un MOLP, puis étude des classes/récurrence/potentiel d'une chaîne de Markov finie.