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

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

Formation doctorale Mathématiques Appliquées, Spécialités : MaDOC, OStoch, ROM, ROMaD, Épreuve « générale » (1h30, coefficient 1), USTHB, Faculté de Mathématiques — 26 Octobre 2017.

التمرين 1

Exercice (Partie A) — Chaînes, cycles et propriétés des graphes connexes

#graph-theory#longest-path#elementary-cycles#connected-graphs

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

(2 pts) Montrer que si $P = (v_1, v_2, \ldots, v_k)$ est une plus longue chaîne élémentaire dans $G$ , alors tous les voisins de $v_1$ sont dans $P$ .
(2 pts) Montrer que si tous les degrés des sommets de $G$ sont supérieurs ou égaux à deux, alors $G$ possède un cycle élémentaire.
(2 pts) 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 dont la longueur est supérieure ou égale à $k + 1$ .
(2 pts) Dé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 ?
(2 pts) 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'est pas dans $P$ , alors $(w, v_1, v_2, \ldots, v_k)$ est une chaîne plus longue, contradiction.

\boxed{\text{Tous les voisins de } v_1 \text{ sont dans } P}

2.

Soit $P = (v_1, \ldots, v_k)$ un plus long chemin. Par Q1, tous les voisins de $v_1$ sont dans $P$ . Comme $\deg(v_1) \geq 2$ , $v_1$ a un voisin $v_j$ avec $j \geq 3$ , formant le cycle $(v_1, v_2, \ldots, v_j, v_1)$ .

\boxed{G \text{ possède un cycle élémentaire}}

3.

$v_1$ a au moins $k$ voisins dans $P$ . Le plus lointain $v_j$ vérifie $j \geq k+1$ , donnant un cycle de longueur $\geq k+1$ .

\boxed{\text{Cycle de longueur } \geq k+1}

4.

Si $P$ et $Q$ n'ont pas de sommet commun, comme $G$ est connexe, il existe un chemin reliant un sommet de $P$ à un sommet de $Q$ , permettant de construire un chemin plus long. Contradiction. Elles n'ont pas nécessairement une arête commune.

5.

Si les deux chaînes maximales ont longueur impaire, elles partagent un sommet central. Par symétrie de longueur, le sommet commun est au milieu.

\boxed{\text{Longueur paire, sommet commun au milieu}}

التمرين 2

Exercice (Partie B.A) — Programmation linéaire et algorithme dual

#linear-programming#dual-simplex#complementary-slackness#dual-variables

On considère le problème d'optimisation linéaire suivant :

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

\text{s.c.} \begin{cases} -x_1 + x_2 \leq 6 \\ x_1 + x_2 = 4 \\ -2x_1 + 4x_2 \geq 2 \\ x_1 \in [-3, 2], \quad x_2 \geq 0 \end{cases} \qquad (1)

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

◀الحل

1.

On met le problème sous forme standard et on applique l'algorithme du simplexe dual. On commence avec une base duale réalisable et on itère jusqu'à la réalisabilité primale.

2.

Le dual s'obtient en associant des multiplicateurs aux contraintes primales. $\min 6y_1 + 4y_2 + 2y_3 + \ldots$ sous les contraintes duales correspondantes.

3.

Les variables duales sont obtenues à la dernière itération du tableau du simplexe.

4.

À l'optimum : si $x_i \gt 0$ alors la contrainte duale $i$ est serrée, et si la contrainte primale $j$ est lâche alors $y_j = 0$ .

\boxed{\text{Écarts complémentaires vérifiés}}

التمرين 3

Exercice (Partie B.B) — Problème de sac-à-dos

#knapsack-problem#linear-programming#integer-programming

On considère le problème de sac-à-dos suivant :

Objet	1	2	3	4
Poids	2	3	4	5
Valeur	3	4	5	6

Écrire le programme linéaire correspondant.
Décrire une méthode autre que simplex pour résoudre ce problème.

◀الحل

1.

\max 3x_1 + 4x_2 + 5x_3 + 6x_4

\text{s.c. } 2x_1 + 3x_2 + 4x_3 + 5x_4 \leq P, \quad x_i \in \{0, 1\}

(où $P$ est la capacité du sac).

\boxed{\text{PLNE binaire}}

2.

La programmation dynamique : on construit un tableau $V[i][w]$ = valeur maximale avec les $i$ premiers objets et capacité $w$ . Complexité $O(nP)$ .

\boxed{\text{Programmation dynamique}}

→←

→السابقConcours Doctorat 2017 — Université Mohamed Khider - Biskra — Épreuve N°03 التاليConcours Doctorat 2017 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — Épreuve N°03←