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

التمرين 2

Exercice 2 — Solution efficace et scalarisation multiobjectif

#multiobjective-optimization#efficiency#scalarization#pareto-optimality

Soit $x^0$ une solution réalisable de $X = \{x \in \mathbb{R}^n : Ax=b, x \geq 0\}$ et $(P)$ le problème multi-objectif $\min\{Cx : x \in X\}$ où $C \in \mathbb{R}^{r \times n}$ . Montrer que $x^0$ est une solution efficiente si et seulement si il existe un vecteur $\lambda \in \mathbb{R}_+^r \setminus \{0\}$ tel que $\lambda^T Cx^0 \leq \lambda^T Cx$ pour tout $x \in X$ .

◀الحل

C'est la caractérisation classique par scalarisation pondérée.

$\Rightarrow$ : si $x^0$ est efficiente, le cône des directions d'amélioration strictes n'intersecte pas le cône négatif des critères. Par séparation convexe, il existe $\lambda \geq 0$ , $\lambda \neq 0$ tel que $\lambda^TCx^0 \leq \lambda^TCx$ pour tout $x$ .

$\Leftarrow$ : si un tel $\lambda$ existe et s'il existait $x$ dominant strictement $x^0$ , alors $Cx \leq Cx^0$ composante par composante avec au moins une stricte, d'où $\lambda^TCx \lt \lambda^TCx^0$ , contradiction.

\boxed{x^0 \text{ efficiente } \iff \exists \lambda \in \mathbb{R}_+^r \setminus \{0\} : \lambda^TCx^0 \leq \lambda^TCx, \forall x \in X}

التمرين 3

Exercice 3 — Ordonnancement par binômes, coloration et chaînes de Markov

#graph-theory#scheduling#graph-coloring#markov-chains#dynamic-programming

Partie B.

Dans une entreprise, les ouvriers $O$ doivent exécuter des tâches du projet. Chaque ouvrier ne peut être affecté qu'à une tâche par semaine. Modéliser le nombre minimum de semaines nécessaires pour terminer toutes les tâches avec un outil de théorie des graphes.
Soit $G=(V,E)$ simple, connexe, non orienté. Notons $\chi(G)$ le nombre chromatique, $\omega(G)$ la taille d'une clique maximum, $\alpha(G)$ la taille d'un plus grand stable et $\theta(G)$ la cardinalité d'une partition minimum en cliques. a. Montrer que $\omega(G) \leq \chi(G)$ et en déduire $\alpha(G) \leq \theta(G)$ . b. Montrer que $\chi(G)\alpha(G) \geq |V(G)|$ . c. Montrer que $\chi(G) \leq \Delta(G)+1$ . d. Montrer qu'un graphe planaire est 5-colorable et que $K_5$ n'est pas planaire.
Chaîne de Markov sur $E=\{1,\ldots,7\}$ de matrice donnée. Dessiner le graphe, donner les classes fermées, dire si la chaîne est irréductible, calculer certaines probabilités de non-retour/premier passage, classer les états, calculer la matrice potentielle et de premier passage, puis $P^\infty$ .

◀الحل

1.

Le problème se modélise par une coloration de graphe d'incompatibilité des tâches, ou un ordonnancement en couches : chaque semaine correspond à une couleur/partie stable. Le nombre minimal de semaines est le nombre chromatique du graphe d'incompatibilité.

2.

(a) Toute clique impose des couleurs distinctes, donc $\omega(G) \leq \chi(G)$ . En passant au complémentaire : $\alpha(G) = \omega(\bar{G}) \leq \chi(\bar{G}) = \theta(G)$ .

(b) Une coloration à $\chi(G)$ couleurs partitionne $V$ en $\chi(G)$ stables, chacun de taille au plus $\alpha(G)$ , donc $|V| \leq \chi(G)\alpha(G)$ .

(d) Pour les planaires, résultat des 5 couleurs. $K_5$ n'est pas planaire par Euler.

3.

Analyse standard de chaîne de Markov finie : graphe des transitions, classes de communication, états transitoires/récurrents, probabilités de premier passage via systèmes linéaires, matrice potentielle $N=(I-Q)^{-1}$ pour les transitoires, puis $P^\infty$ à partir des classes fermées.