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

التمرين 1

Exercice 1 — Forêts et arbres de poids maximum

#graph-theory#maximum-spanning-tree#forest#greedy-algorithm#integer-programming

Rappeler les propriétés équivalentes caractérisant un graphe $T$ qui est un arbre. Soit $G=(V,E)$ un graphe connexe auquel on associe à chaque arête $\{i,j\}$ de $G$ un poids $p(i,j) \in \mathbb{R}$ .

Montrer qu'un arbre $T=(V,F)$ de $G$ est de poids maximum si et seulement si pour chaque arête $\{i,j\} \in E \setminus F$ et pour toute arête $\{k,l\}$ de la chaîne $C_{i,j}^T$ , on a $p(i,j) \leq p(k,l)$ .
Décrire et justifier un algorithme glouton pour trouver une forêt de poids maximum de $G$ .
Donner une condition nécessaire et suffisante pour qu'une forêt de poids maximum soit un arbre.
Quelle modification doit-on apporter à l'algorithme pour qu'il donne un arbre de poids maximum ?
On considère le programme linéaire en 0-1 $(F)$ du sujet. Montrer qu'il formule le problème de la forêt de poids maximum, ajouter la contrainte pour obtenir une formulation $(T)$ de l'arbre de poids maximum, et montrer l'équivalence avec la formulation par coupes.

◀الحل

1.

Critère d'optimalité par échange : si une arête hors arbre a un poids strictement supérieur à une arête du cycle qu'elle crée, on peut améliorer le poids total. Donc dans un arbre maximal, chaque arête hors arbre est au plus égale au minimum des arêtes du chemin unique entre ses extrémités.

2.

Algorithme glouton : trier les arêtes par poids décroissant et ajouter successivement toute arête qui ne crée pas de cycle. Cela construit une forêt de poids maximum (Kruskal maximal).

3.

Une forêt de poids maximum est un arbre ssi elle est connexe, i.e. elle possède exactement $n-1$ arêtes et relie tous les sommets.

4.

Pour obtenir un arbre de poids maximum, on poursuit l'algorithme jusqu'à obtenir $n-1$ arêtes en imposant la connexité finale.

5.

La formulation 0-1 standard avec contraintes de sous-graphes acycliques décrit une forêt. Ajouter $\sum x_{ij}=n-1$ donne l'arbre. Les contraintes de coupes $\sum_{E(S,V\setminus S)}x_{ij} \ge 1$ sont équivalentes à la connexité.

التمرين 2

Exercice 2 — Programme bi-objectif et ensemble efficace

#multiobjective-optimization#linear-programming#pareto-optimality#weighted-sum

On considère le programme linéaire bi-objectif suivant :

(P) \begin{cases} \max 3x_1 + x_2 \\\\ \max -x_1 - 2x_2 \\\\ x_1 + 2x_2 \ge 2, \; x_1 \le 4, \; x_2 \le 3, \; x_1,x_2 \ge 0. \end{cases}

Écrire le programme linéaire de la somme pondérée associé à $P$ , noté $LP(\lambda)$ .
Calculer l'ensemble des bases efficientes, l'ensemble des points extrêmes efficients, l'ensemble de toutes les solutions efficientes $X_{eff}$ et l'ensemble de tous les vecteurs critères non dominés $Y_N$ .
Donner les équations des courbes relatives aux valeurs critiques de $\lambda$ et retrouver graphiquement les résultats.
Retrouver graphiquement les ensembles $X_{eff}$ et $Y_N$ à l'aide du cône polaire semi-positif.

◀الحل

Le traitement est analogue à l'exercice bi-objectif précédent :

on forme $LP(\lambda)=\max \lambda(3x_1+x_2)+(1-\lambda)(-x_1-2x_2)$ ,
on liste les sommets admissibles,
on calcule leurs images dans l'espace des critères,
on élimine les points dominés,
on identifie les segments de Pareto.

\boxed{\text{L'ensemble efficace se lit sur le bord admissible non dominé du polyèdre}}