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

مسابقة عامة · الرياضيات · المعامل: 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 — Dualité linéaire et condition d'optimalité

#linear-programming#duality#optimality#standard-form

On considère le programme linéaire

\min Z = 5x_1 + 6x_2 + 3x_3 + 3x_4 + 5x_5 + 4x_6

sous contraintes de ressources et $x_i \geq 0$ .

Montrer que les programmes $(R_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,\dots,y_6)$ est une solution réalisable optimale de $(D)$ , alors $y^* + \alpha\omega$ est aussi solution réalisable optimale de $(D)$ , avec $\omega=(a,b,-a,-a,-a)^t$ .
Soit le vecteur $x = (x_1,\dots,x_6)$ avec $x_1=50, x_2=300, x_3=200, x_4=350, x_5=x_6=0$ . Chercher une solution réalisable de $(D)$ vérifiant une condition d'égalité sur les contraintes et en déduire que $x$ est une solution optimale de $(P)$ .

◀الحل

On met $(P)$ en forme standard et on écrit le dual. Les deux programmes ont le même ensemble réalisable car $(R_1)$ n'est qu'une réécriture avec variables d'écart.

Le point 2.b est une propriété d'invariance du dual sous ajout d'un vecteur du noyau des contraintes duales.

Pour 3, on utilise les conditions de complémentarité : choisir $y$ réalisable dual tel que pour chaque $i$ avec $x_i \gt 0$ , la contrainte duale correspondante soit saturée. On vérifie ensuite l'égalité des valeurs primale et duale pour conclure à l'optimalité de $x$ .

\boxed{x \text{ est optimal par dualité forte et complémentarité}}

التمرين 2

Exercice 2 — Graphes bipartis, maille et planarité

#graph-theory#bipartite-graphs#planar-graphs#girth#euler-formula

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 de $G$ de degré au plus $\frac{m}{n}$ .
Montrer que si $G$ est régulier de degré $r$ , alors $|X|=|Y|$ .

Exercice 3. La maille d'un graphe $G$ est la longueur d'un plus petit cycle. Soit $G$ un graphe planaire simple et connexe ayant $n$ sommets, $m$ arêtes et $f$ faces. 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}{k-2}(n-2)$ .
En appliquant la formule, 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.

◀الحل

2.1.

Dans un graphe biparti simple : $m \leq |X||Y| \leq n^2/4$ et $m \geq n-1$ si connexe.

2.2.

Le degré moyen vaut $2m/n$ . Il existe donc un sommet de degré au plus cette moyenne.

2.3.

Dans un graphe biparti $r$ -régulier : $r|X| = m = r|Y|$ , donc $|X|=|Y|$ .

3.

Chaque face a longueur au moins $k$ , et chaque arête borde au plus deux faces : $kf \leq 2m$ .

Avec Euler $n-m+f=2$ , on obtient $m \leq \frac{k}{k-2}(n-2)$ .

En remplaçant les valeurs de $k$ , on retrouve les non-planarités de $K_5$ , $K_{3,3}$ et du graphe de Petersen.