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

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

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

التمرين 1

Exercice 1 — Programme linéaire, dualité et solution optimale

#linear-programming#duality#optimization

On considère un programme linéaire $(P)$ avec objectif $\min Z = 5x_1 + 6x_2 + 3x_3 + 3x_4 + 5x_5 + 4x_6$ et contraintes linéaires visibles sur l'énoncé.

Montrer que $(P_1)$ et $(P)$ ont le même ensemble de solutions réalisables.
Écrire le dual $(D)$ de $(P_1)$ .
Montrer que si $y^*=(y_1,\ldots,y_6)$ est solution réalisable optimale de $(D)$ , alors pour tout $a\in\mathbb{R}_+$ , $y^* + a\alpha$ est aussi optimale, avec $\alpha=(0,a,-a,-a,-a)^t$ .
Soit $x=(x_1,\ldots,x_6)$ tel que $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é de contrainte et en déduire que $x$ est optimale pour $(P_1)$ .

◀الحل

On reformule les contraintes en égalités avec variables d'écart. Le dual s'écrit classiquement. L'optimalité de $x$ se montre en construisant un dual réalisable satisfaisant les conditions de complémentarité.

التمرين 2

Exercice 2 — Graphes bipartis et planarité

#graph-theory#bipartite-graphs#planar-graphs#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 de $m$ .
Montrer qu'il existe un sommet de degré au plus $m/n$ .
Montrer que si $G$ est régulier de degré $r$ , alors $|X|=|Y|$ .
La maille d'un graphe $G$ est la longueur d'un plus petit cycle. Si $G$ est planaire, montrer que pour maille $k\ge3$ : $kf \le 2m$ puis en déduire $m \le \frac{k}{k-2}(n-2)$ .
Vérifier que $K_5$ , $K_{3,3}$ et le graphe de Petersen ne sont pas planaires.

◀الحل

On utilise les propriétés classiques : pour un graphe simple connexe, $n-1 \le m \le |X||Y|$ . Le degré moyen donne l'existence d'un sommet de petit degré. La régularité d'un biparti impose $r|X|=r|Y|$ . La formule d'Euler $n-m+f=2$ et la maille donnent $kf \le 2m$ , d'où la borne. On applique aux graphes donnés.

التمرين 3

Exercice 3 — PL paramétrique et planarité/coloration

#linear-programming#planar-graphs#graph-coloring

On considère un problème paramétrique $(P(t))$ puis des questions de planarité et de coloration : forme d'Euler, borne $m\le3n-6$ , cas sans triangle $m\le2n-4$ , borne sur la maille, non-planarité de $K_{3,3}$ et Petersen, et résultat de coloration planaire.

Résoudre $Q(t)$ , écrire le dual, résoudre graphiquement, puis démontrer les résultats de graphes demandés.

◀الحل

La partie LP se résout en mettant en forme standard puis en étudiant la dépendance au paramètre $t$ . La partie graphes utilise Euler, bornes d'arêtes, majoration de $\Delta(G)$ et arguments de coloration des graphes planaires.