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

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

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

التمرين 1

Exercice 1 — Programme linéaire, dualité et optimalité

#linear-programming#duality#feasibility#optimality

On considère le programme linéaire suivant :

(P_1) \begin{cases} \min Z = 5x_1 + 6x_2 + 3x_3 + 3x_4 + 5x_5 + 4x_6 \\ x_1 + x_2 + x_3 \leq 550 \\ x_4 + x_5 + x_6 \leq 350 \\ x_1 + x_4 \geq 400 \\ x_2 + x_5 \geq 300 \\ x_3 + x_6 \geq 200 \\ x_1, x_2, x_3, x_4, x_5, x_6 \geq 0 \end{cases}

Soit $(P)$ le programme $(P_1)$ , où toutes les inégalités sont remplacées par des égalités.

Montrer que les deux programmes linéaires $(P_1)$ et $(P)$ ont le même ensemble de solutions réalisables.
a) Écrire le dual $(D)$ de $(P)$ . b) Montrer que si $y^* = (y_1, y_2, y_3, y_4, y_5)^t$ est une solution réalisable optimale de $(D)$ , alors $y^* + \alpha$ est aussi une solution réalisable optimale de $(D)$ , avec $\alpha = (a, a, -a, -a, -a)^t$ .
Soit le vecteur $x = (x_1, \ldots, x_6)^t$ tel que $x_1 = 50, x_2 = 300, x_3 = 200, x_4 = 350$ et $x_5 = x_6 = 0$ . Chercher une solution réalisable de $(D)$ vérifiant la condition : $\forall i \in \{1, \ldots, 6\} : x_i \gt 0 \Rightarrow$ la $i$ -ème contrainte de $(D)$ est une égalité. En déduire que $x$ est une solution optimale de $(P)$ .

◀الحل

1.

Toute solution réalisable de $(P_1)$ satisfait les inégalités. Si une contrainte $\leq$ est stricte, les variables d'écart sont positives mais n'affectent pas la faisabilité de $(P)$ car les contraintes $\geq$ sont aussi satisfaites. Par complémentarité, à l'optimum les inégalités deviennent des égalités.

2.a.

Le dual de $(P)$ (avec égalités, variables $y_i$ non restreintes) est : $\max 550y_1 + 350y_2 + 400y_3 + 300y_4 + 200y_5$ sous les contraintes $y_1 + y_3 \leq 5$ , $y_1 + y_4 \leq 6$ , $y_1 + y_5 \leq 3$ , $y_2 + y_3 \leq 3$ , $y_2 + y_4 \leq 5$ , $y_2 + y_5 \leq 4$ .

2.b.

En substituant $y^* + \alpha$ , les contraintes duales sont préservées car $a$ s'annule dans chaque paire ( $y_1+a + y_3-a = y_1+y_3$ ). La valeur objectif reste inchangée car $550a + 350a - 400a - 300a - 200a = 0$ .

3.

Par les écarts complémentaires : $x_1 \gt 0 \Rightarrow y_1+y_3 = 5$ , $x_2 \gt 0 \Rightarrow y_1+y_4 = 6$ , $x_3 \gt 0 \Rightarrow y_1+y_5 = 3$ , $x_4 \gt 0 \Rightarrow y_2+y_3 = 3$ . Résoudre ce système donne une solution duale. La valeur primale égale la valeur duale, confirmant l'optimalité.

\boxed{x \text{ est solution optimale de } (P)}

التمرين 2

Exercice 2 — Graphe biparti : bornes et degré

#bipartite-graphs#edges-bounds#regular-graphs

Soit $G = (X \cup Y, E)$ un graphe biparti simple et connexe ayant $n$ sommets et $m$ arêtes.

Donner les bornes supérieure et inférieure du nombre d'arêtes.
Montrer qu'il existe un sommet dans $G$ de degré au plus $\frac{n}{2}$ .
Montrer que si $G$ est régulier de degré $r$ , alors $|X| = |Y|$ .

◀الحل

1.

Borne inférieure : $m \geq n - 1$ (connexe). Borne supérieure : si $|X| = p, |Y| = q$ avec $p+q = n$ , alors $m \leq pq \leq \lfloor n^2/4 \rfloor$ .

\boxed{n-1 \leq m \leq \lfloor n^2/4 \rfloor}

2.

La somme des degrés = $2m$ . Si tous les degrés $\gt n/2$ , alors $2m \gt n \cdot n/2 = n^2/2$ . Mais $m \leq n^2/4$ , contradiction.

\boxed{\exists v : \deg(v) \leq n/2}

3.

Si $G$ est $r$ -régulier : $\sum_{x \in X} \deg(x) = r|X| = m = r|Y| = \sum_{y \in Y} \deg(y)$ . Donc $|X| = |Y|$ .

\boxed{|X| = |Y|}

التمرين 3

Exercice 3 — Graphe planaire, maille et formule d'Euler

#planar-graphs#euler-formula#girth#non-planarity

La maille d'un graphe $G$ est la longueur du plus petit cycle de $G$ . Soit $G$ un graphe planaire simple et connexe ayant $n$ sommets, $m$ arêtes et $f$ faces. La formule d'Euler pour un tel graphe est $n - m + f = 2$ . On suppose que la maille de $G$ est $k$ ( $k \geq 3$ ).

Montrer que $kf \leq 2m$ .
En déduire que $m \leq \frac{k(n-2)}{k-2}$ .
En appliquant la formule (1), vérifier que : a. Pour $k = 3$ , $K_5$ n'est pas planaire. b. Pour $k = 4$ , $K_{3,3}$ n'est pas planaire. c. Pour $k = 5$ , le graphe de Petersen n'est pas planaire.

◀الحل

1.

Chaque face est bordée par au moins $k$ arêtes (maille = $k$ ). Chaque arête borde au plus 2 faces. Donc $kf \leq 2m$ .

\boxed{kf \leq 2m}

2.

De $kf \leq 2m$ et $f = 2 - n + m$ (Euler) : $k(2 - n + m) \leq 2m$ , soit $m(k-2) \leq k(n-2)$ , d'où $m \leq \frac{k(n-2)}{k-2}$ .

\boxed{m \leq \frac{k(n-2)}{k-2}}

3.a.

$K_5$ : $n = 5, m = 10, k \geq 3$ . Borne : $m \leq 3(5-2)/1 = 9 \lt 10$ . Contradiction.

3.b.

$K_{3,3}$ : $n = 6, m = 9, k \geq 4$ (biparti, pas de triangle). Borne : $m \leq 4(6-2)/2 = 8 \lt 9$ . Contradiction.

3.c.

Petersen : $n = 10, m = 15, k = 5$ (maille 5). Borne : $m \leq 5(10-2)/3 = 40/3 \approx 13.3 \lt 15$ . Contradiction.

\boxed{K_5, K_{3,3} \text{ et Petersen ne sont pas planaires}}